9.CF490F Treeland Tour 线段树合并

9.CF490F Treeland Tour 线段树合并

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给出一棵带点权树，求树上最长上升子序列的长度

对每个点开两棵线段树，记录叶节点到当前节点的LIS和LDS，然后合并时取最大值即可

洛谷传送门：CF490F Treeland Tour - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：F. Treeland Tour (codeforces.com)

题目分析

给出一棵带点权树，求树上最长上升子序列的长度

对每个点开两棵线段树，记录叶节点到当前节点的LIS和LDS，然后合并时取最大值即可

可以假定 $w_u$ 就为一段路径的中间必经点，现在就只需要在子树里找到一截尾部小于 $w_u$ 的 $LIS$，和一截尾部大于 $w_u$ 的 $LDS$，加起来再加一就行了。

设我们正在合并的两个线段树结点$x_1,x_2$，我们只考虑统计跨 $mid=\frac{l_x+r_x}{2}$的答案，那么显然只需在 $[l,mid]$ 中找出一条最长的 最长上升/下降子序列 与 $[mid+1,r]$中找出的一条最长的 最长上升/下降子序列 拼在一起。这样找出的两条拼在一起一定是合法的，因为线段树的下标即为结尾元素的值。

代码实现细节比较多，容易写挂。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
// #define int long long
#define endl '\n'
using namespace std;

const int N = 6005, MOD = 1e9 + 7;
int w[N], b[N], n1, ans;

vector<int> g[N];

void diz(int n){
    sort(b + 1, b + 1 + n);
    n1 = unique(b + 1, b + 1 + n) - (b + 1);
    for(int i = 1; i <= n; i++) w[i] = std::lower_bound(b + 1, b + 1 + n1, w[i]) - b;
}

int get_rank(int x){ return lower_bound(b + 1, b + 1 + n1, x) - b; }

#define pii pair<int, int>
#define fir first
#define sec second

namespace SegTree{
    #define ls lc[rt]
    #define rs rc[rt]
    #define lson ls, l, mid
    #define rson rs, mid + 1, r

    int root[N], lis[N * 50], lds[N * 50], lc[N * 50], rc[N * 50], tot = 0;
    
    inline void clear(){ tot = 0; }
    
    inline void push_up(int rt){
        lis[rt] = std::max(lis[ls], lis[rs]);
        lds[rt] = std::max(lds[ls], lds[rs]);
    }

    inline pii change(pii a, pii b){ return make_pair(std::max(a.fir, b.fir), std::max(a.sec, b.sec)); }

    void update(int &rt, int l, int r, int pos, int val1, int val2){
        if(!rt) rt = ++tot;
        if(l == r){
            lis[rt] = max(lis[rt], val1);
            lds[rt] = max(lds[rt], val2);
            return;
        }
        int mid = l + r >> 1;
        if(mid >= pos) update(lson, pos, val1, val2);
        else update(rson, pos, val1, val2);
        push_up(rt);
    }

    void query(int rt, int l, int r, int L, int R, int &nlis, int &nlds){
        if(!rt) return;
        if(l >= L && r <= R){
            nlis = max(nlis, lis[rt]);
            nlds = max(nlds, lds[rt]);
            return;
        }
        int mid = l + r >> 1;
        if(mid >= L) query(lson, L, R, nlis, nlds);
        if(mid < R) query(rson, L, R, nlis, nlds); 
    }

    int merge(int u, int v, int l, int r){
        if(!u) return v;
        if(!v) return u;
        int mid = l + r >> 1;
        lis[u] = std::max(lis[u], lis[v]);
        lds[u] = std::max(lds[u], lds[v]);
        ans = std::max({ans, lis[lc[u]] + lds[rc[v]], lds[rc[u]] + lis[lc[v]]});
        lc[u] = merge(lc[u], lc[v], l, mid);
        rc[u] = merge(rc[u], rc[v], mid + 1, r);
        // push_up(u);
        return u;
    }
}

#define root SegTree::root
#define SEGRG root[i], 1, n1

void dfs(int u, int fa){
    int mlis = 0, mlds = 0;
    for(auto &v : g[u]){
        if(v == fa) continue;
        dfs(v, u);
        int vlis = 0, vlds = 0, tmp = 0;
        SegTree::query(root[v], 1, n1, 1, w[u] - 1, vlis, tmp);
        SegTree::query(root[v], 1, n1, w[u] + 1, n1, tmp, vlds);
        ans = max(ans, mlis + vlds + 1);
        ans = max(ans, mlds + vlis + 1);
        mlis = max(mlis, vlis), mlds = max(mlds, vlds);
        root[u] = SegTree::merge(root[u], root[v], 1, n1);
    }
    SegTree::update(root[u], 1, n1, w[u], mlis + 1, mlds + 1);
}

inline void solve(){
    int n = 0; cin >> n; ans = -1, SegTree::clear();
    for(int i = 1; i <= n; i++) cin >> w[i], b[i] = w[i];
    for(int i = 1; i <= n - 1; i++){
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    diz(n);
    for(int i = 1; i <= n; i++) SegTree::update(SEGRG, w[i], 1, 1);
    dfs(1, 0);
    cout << ans << endl;
}

signed main(){
    #ifdef ONLNE_JUDGE
    ios_base::sync_with_stdio(false), cin.tie(0);
    #endif
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122