首页 > 代码库 > [HDOJ3308]LCIS（线段树，区间合并，新的代码）

[HDOJ3308]LCIS（线段树，区间合并，新的代码）

2024-09-19 16:18:46   220人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3308

题意：给定n个数，两个操作：

U A B：将位置A的数值改成B

Q A B：查询[A,B]内最长连续上升子序列的长度。

 

我认为当时的代码风格和现在的不一样（因为喜欢在Seg里存l和r的下标，然而根本不用），所以重写了一份，也算是复习了。

pushup操作里是不需要根据seg[rt].ls和seg[rt].rs更新seg[rt].ms的，而是从左右儿子的ms更新，以及lrt的最右元素与rrt的最左元素满足上升关系时，将这lrt的rs和rrt的ls连起来。

query的时候也会遇到合并的问题，所以要像pushup操作一样，把两部分加起来更新一下结果。

query里除了判断上升关系，L <= mid && mid < R这个我认为也是必要的，但是似乎不加也过了，可能是因为假如不满足这个条件，那么最优解肯定不在这里。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define lrt rt << 1
 5 #define rrt rt << 1 | 1
 6 typedef struct Seg {
 7     int ls, rs, ms;
 8 }Seg;
 9 const int maxn = 100100;
10 Seg seg[maxn<<2];
11 int val[maxn];
12 int n, q;
13 char op[3];
14 
15 void pushup(int l, int r, int rt) {
16     int mid = (l + r) >> 1;
17     seg[rt].ls = seg[lrt].ls; seg[rt].rs = seg[rrt].rs;
18     if(seg[rt].ls == mid - l + 1 && val[mid] < val[mid+1]) seg[rt].ls += seg[rrt].ls;
19     if(seg[rt].rs == r - mid && val[mid] < val[mid+1]) seg[rt].rs += seg[lrt].rs;
20     seg[rt].ms = max(seg[lrt].ms, seg[rrt].ms);
21     if(val[mid] < val[mid+1]) seg[rt].ms = max(seg[rt].ms, seg[lrt].rs+seg[rrt].ls);
22 }
23 
24 void build(int l, int r, int rt) {
25     if(l == r) {
26         seg[rt].ls = seg[rt].rs = seg[rt].ms = 1;
27         return;
28     }
29     int mid = (l + r) >> 1;
30     build(l, mid, lrt);
31     build(mid+1, r, rrt);
32     pushup(l, r, rt);
33 }
34 
35 void update(int pos, int val, int l, int r, int rt) {
36     if(l == r) {
37         seg[rt].ls = seg[rt].rs = seg[rt].ms = 1;
38         return;
39     }
40     int mid = (l + r) >> 1;
41     if(pos <= mid) update(pos, val, l, mid, lrt);
42     else update(pos, val, mid+1, r, rrt);
43     pushup(l, r, rt);
44 }
45 
46 int query(int L, int R, int l, int r, int rt) {
47     if(L <= l && r <= R) return seg[rt].ms;
48     int mid = (l + r) >> 1;
49     int ret = 0;
50     if(L <= mid) ret = max(ret, query(L, R, l, mid, lrt));
51     if(mid < R) ret = max(ret, query(L, R, mid+1, r, rrt));
52     if(L <= mid && mid < R && val[mid] < val[mid+1]) {
53         ret = max(ret, min(seg[lrt].rs, mid-L+1)+min(seg[rrt].ls,R-mid));
54     }
55     return ret;
56 }
57 int main() {
58     // freopen("in", "r", stdin);
59     int T, a, b;
60     scanf("%d", &T);
61     while(T--) {
62         scanf("%d%d",&n,&q);
63         for(int i = 1; i <= n; i++) {
64             scanf("%d", &val[i]);
65         }
66         build(1, n, 1);
67         while(q--) {
68             scanf("%s%d%d",op,&a,&b);
69             a++;
70             if(op[0] == ‘Q‘) {
71                 b++;
72                 printf("%d\n", query(a, b, 1, n, 1));
73             }
74             else {
75                 val[a] = b;
76                 update(a, b, 1, n, 1);
77             }
78         }
79     }
80     return 0;
81 }

 

[HDOJ3308]LCIS（线段树，区间合并，新的代码）


联系
我们