首页 > 代码库 > [HDOJ3308]LCIS（线段树，区间合并）
[HDOJ3308]LCIS（线段树，区间合并）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3308
题意：给定n个数，两个操作：
U A B：将位置A的数值改成B
Q A B：查询[A,B]内最长连续上升子序列的长度。
注意到‘连续’一词，可以用线段树维护[L,R]区间内的LICS。
定义结构Node，内部ls，rs为左右儿子的下标。l，r记录当前区间分别从左起和右起的LICS长度，s记录整个区间内的LICS长度。
pushup：和一般的区间合并操作一样，但是要注意假如合并的左右子树中间有可能成为LICS的时候，要判断是否符合条件，即左起右边界和右起左边界是否满足严格的关系。
update：更新节点的时候直接赋值，再更新到线段树上的操作也是很常规的。
query：比较奇特，因为有左起右边界和右起左边界连接起来的情况，所以查询的时候不是缩小线段树规模，而是缩小查询规模来获得解。而且要注意[L,R]的边界问题。子树的范围未必恰好满足，可能会更长。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <cassert> 8 #include <cstdio> 9 #include <bitset> 10 #include <vector> 11 #include <deque> 12 #include <queue> 13 #include <stack> 14 #include <ctime> 15 #include <set> 16 #include <map> 17 #include <cmath> 18 using namespace std; 19 20 #define lrt rt << 1 21 #define rrt rt << 1 | 1 22 const int maxn = 100050; 23 typedef struct Node { 24 int ls, rs; 25 int s, l, r; 26 }Node; 27 28 Node seg[maxn<<2]; 29 int n, q; 30 int seq[maxn]; 31 char cmd[3]; 32 33 34 void pushUP(int rt, int len) { 35 seg[rt].l = seg[lrt].l; 36 seg[rt].r = seg[rrt].r; 37 if(seg[rt].l == len-len/2) { 38 if(seq[seg[lrt].rs] < seq[seg[rrt].ls]) { 39 seg[rt].l += seg[rrt].l; 40 } 41 } 42 if(seg[rt].r == len/2) { 43 if(seq[seg[lrt].rs] < seq[seg[rrt].ls]) { 44 seg[rt].r += seg[lrt].r; 45 } 46 } 47 seg[rt].s = max(seg[lrt].s, seg[rrt].s); 48 if(seq[seg[lrt].rs] < seq[seg[rrt].ls]) { 49 seg[rt].s = max(seg[rt].s, seg[lrt].r+seg[rrt].l); 50 } 51 } 52 53 void build(int l, int r, int rt) { 54 seg[rt].ls = l; 55 seg[rt].rs = r; 56 if(l == r) { 57 seg[rt].l = seg[rt].r = seg[rt].s = 1; 58 return; 59 } 60 int mid = (l + r) >> 1; 61 build(l, mid, lrt); 62 build(mid+1, r, rrt); 63 pushUP(rt, seg[rt].rs-seg[rt].ls+1); 64 } 65 66 int query(int L, int R, int rt) { 67 if(L <= seg[rt].ls && seg[rt].rs <= R) return seg[rt].s; 68 int mid = (seg[rt].ls + seg[rt].rs) >> 1; 69 if(mid >= R) return query(L, R, lrt); 70 else if(mid + 1 <= L) return query(L, R, rrt); 71 else { 72 int tmp = max(query(L, mid, lrt), query(mid+1, R, rrt)); 73 if(seq[seg[lrt].rs] < seq[seg[rrt].ls]) { 74 tmp = max(tmp, min(seg[lrt].r,mid-L+1)+min(seg[rrt].l,R-mid)); 75 } 76 return tmp; 77 } 78 } 79 80 void update(int L, int R, int rt) { 81 if(L <= seg[rt].ls && seg[rt].rs <= R) { 82 seg[rt].l = seg[rt].r = seg[rt].s = 1; 83 return; 84 } 85 int mid = (seg[rt].ls + seg[rt].rs) >> 1; 86 if(mid >= L) update(L, R, lrt); 87 if(mid < R) update(L, R, rrt); 88 pushUP(rt, seg[rt].rs-seg[rt].ls+1); 89 } 90 91 int main() { 92 // freopen("in", "r", stdin); 93 int qaq, a, b; 94 scanf("%d", &qaq); 95 while(qaq--) { 96 scanf("%d %d", &n, &q); 97 for(int i = 1; i <= n; i++) { 98 scanf("%d", &seq[i]); 99 }100 build(1, n, 1);101 while(q--) {102 scanf("%s %d %d",cmd,&a,&b);103 a++;104 if(cmd[0] == ‘Q‘) {105 b++;106 printf("%d\n", query(a, b, 1));107 }108 else if(cmd[0] == ‘U‘) {109 seq[a] = b;110 update(a, a, 1);111 }112 }113 }114 return 0;115 }
[HDOJ3308]LCIS（线段树，区间合并）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。