首页 > 代码库 > [HDOJ3911]Black And White（线段树，区间合并）
[HDOJ3911]Black And White（线段树，区间合并）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3911
题意：一个01串，两种操作：
0 a b：查询[a,b]内连续1的最长长度。
1 a b：翻转[a,b]内的所有数字（0变1，1变0）。
更新操作落实到具体数字，这时候不能莽直接更新数字对吧，我们要考虑翻转这个操作如何跟懒惰标记对上。让我们可以通过懒惰标记间接更新而不是直接每次更新到叶子。
我们知道一个性质：翻转偶数次相当于没有翻转，那么懒惰标记就来标记翻转次数的奇偶吧，假如是偶数次，那么不需要往下更新了。但是这样的话偶数次解决了，奇数次岂不是还要更新。我们要求连续的1的长度，需要维护一组1的长度（从左起最长、从右起最长、区间内最长），那么再对应地维护一组0的长度，反转的时候相当于这两组数字的交换，每次更新再pushup就没有问题了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define lrt rt << 1 5 #define rrt rt << 1 | 1 6 typedef struct Node { 7 int l, r, v; 8 int lone, sone, rone; 9 int lzero, szero, rzero;10 }Node;11 const int maxn = 100100;12 int cmd;13 int n, q;14 int x[maxn];15 Node seg[maxn<<4];16 17 void pushUP(int rt, int len) {18 seg[rt].lone = seg[lrt].lone; seg[rt].rone = seg[rrt].rone;19 seg[rt].lzero = seg[lrt].lzero; seg[rt].rzero = seg[rrt].rzero;20 if(seg[rt].lone == len-len/2) seg[rt].lone += seg[rrt].lone;21 if(seg[rt].rone == len/2) seg[rt].rone += seg[lrt].rone;22 if(seg[rt].lzero == len-len/2) seg[rt].lzero += seg[rrt].lzero;23 if(seg[rt].rzero == len/2) seg[rt].rzero += seg[lrt].rzero;24 seg[rt].sone = max(seg[lrt].sone, seg[rrt].sone);25 seg[rt].sone = max(seg[rt].sone, seg[lrt].rone+seg[rrt].lone);26 seg[rt].szero = max(seg[lrt].szero, seg[rrt].szero);27 seg[rt].szero = max(seg[rt].szero, seg[lrt].rzero+seg[rrt].lzero);28 }29 30 void pushDOWN(int rt) {31 if(seg[rt].v) {32 seg[rt].v = 0;33 seg[lrt].v = !seg[lrt].v;34 seg[rrt].v = !seg[rrt].v;35 swap(seg[lrt].lone, seg[lrt].lzero);36 swap(seg[lrt].rone, seg[lrt].rzero);37 swap(seg[lrt].sone, seg[lrt].szero);38 swap(seg[rrt].lone, seg[rrt].lzero);39 swap(seg[rrt].rone, seg[rrt].rzero);40 swap(seg[rrt].sone, seg[rrt].szero);41 }42 }43 44 void build(int l, int r, int rt) {45 seg[rt].l = l; seg[rt].r = r; seg[rt].v = 0;46 if(l == r) {47 seg[rt].lone = seg[rt].rone = seg[rt].sone = (x[l] == 0) ? 0 : 1;48 seg[rt].lzero = seg[rt].rzero = seg[rt].szero = (x[l] == 1) ? 0 : 1;49 return;50 }51 int mid = (l + r) >> 1;52 build(l, mid, lrt);53 build(mid+1, r, rrt);54 pushUP(rt, r-l+1);55 }56 57 void update(int L, int R, int rt) {58 if(L <= seg[rt].l && seg[rt].r <= R) {59 swap(seg[rt].lone, seg[rt].lzero);60 swap(seg[rt].rone, seg[rt].rzero);61 swap(seg[rt].sone, seg[rt].szero);62 seg[rt].v = !seg[rt].v;63 return;64 }65 pushDOWN(rt);66 int mid = (seg[rt].l + seg[rt].r) >> 1;67 if(L <= mid) update(L, R, lrt);68 if(mid < R) update(L, R, rrt);69 pushUP(rt, seg[rt].r-seg[rt].l+1);70 }71 72 int query(int L, int R, int rt) {73 if(L == seg[rt].l && R == seg[rt].r) return seg[rt].sone;74 pushDOWN(rt);75 int mid = (seg[rt].l + seg[rt].r) >> 1;76 if(mid >= R) return query(L, R, lrt);77 else if(mid + 1 <= L) return query(L, R, rrt);78 else {79 int tmp = max(query(L, mid, lrt), query(mid+1, R, rrt));80 tmp = max(tmp, min(seg[lrt].rone,mid-L+1)+min(seg[rrt].lone,R-mid));81 return tmp;82 }83 }84 85 int main() {86 //freopen("in", "r", stdin);87 int a, b;88 while(~scanf("%d", &n)) {89 for(int i = 1; i <= n; i++) scanf("%d", &x[i]);90 build(1, n, 1);91 scanf("%d", &q);92 while(q--) {93 scanf("%d %d %d", &cmd, &a, &b);94 if(cmd == 0) printf("%d\n", query(a, b, 1));95 else update(a, b, 1);96 }97 }98 return 0;99 }
[HDOJ3911]Black And White（线段树，区间合并）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。