题：点击打开链接

分析：线段树区间更新。只不过掺杂了区间和、最大连续区间区间和。对于延迟标记在上一篇博客已经出现过：pojHelp with Intervals线段树解法

代码：

#include
  
   
#include
   
     #define lc (rt<<1) #define rc (rt<<1|1) #define lson l, m, lc #define rson m + 1, r, rc using namespace std; const int maxn = 100000 + 10; int unsum[maxn<<2], sum[maxn<<2], lsum[maxn<<2], rsum[maxn<<2], zsum[maxn<<2], lzsum[maxn<<2], rzsum[maxn<<2], col[maxn<<2]; void SWAP(int rt, int m){ col[rt] = 1 - col[rt]; unsum[rt] = m - unsum[rt]; swap(sum[rt], zsum[rt]); swap(lsum[rt], lzsum[rt]); swap(rsum[rt], rzsum[rt]); } void PushUp(int rt, int m){ unsum[rt] = unsum[lc] + unsum[rc]; lsum[rt] = lsum[lc]; rsum[rt] = rsum[rc]; if(lsum[rt] == m - (m>>1)) lsum[rt] += lsum[rc]; if(rsum[rt] == m>>1) rsum[rt] += rsum[lc]; sum[rt] = max(rsum[lc] + lsum[rc], max(sum[lc], sum[rc])); lzsum[rt] = lzsum[lc]; rzsum[rt] = rzsum[rc]; if(lzsum[rt] == m - (m>>1)) lzsum[rt] += lzsum[rc]; if(rzsum[rt] == m>>1) rzsum[rt] += rzsum[lc]; zsum[rt] = max(rzsum[lc] + lzsum[rc], max(zsum[lc], zsum[rc])); } void PushDown(int rt, int m){ if(col[rt] == 2){ col[rt] = 1 - col[rt]; SWAP(lc, m - (m>>1)); SWAP(rc, m>>1); } if(~col[rt]){ col[lc] = col[rc] = col[rt]; unsum[lc] = sum[lc] = lsum[lc] = rsum[lc] = col[rt] ? m - (m>>1) : 0; unsum[rc] = sum[lc | 1] = lsum[rc] = rsum[rc] = col[rt] ? m>>1 : 0; zsum[lc] = lzsum[lc] = rzsum[lc] = col[rt] ? 0 : m - (m>>1); zsum[rc] = lzsum[rc] = rzsum[rc] = col[rt] ? 0 : m>>1; col[rt] = -1; } } void build(int l, int r, int rt){ col[rt] = -1; if(l == r){ scanf("%d", &sum[rt]); unsum[rt] = lsum[rt] = rsum[rt] = sum[rt]; zsum[rt] = lzsum[rt] = rzsum[rt] = sum[rt]^1; return; } int m = r + l >> 1; build(lson); build(rson); PushUp(rt, r - l + 1); } void update(int L, int R, int add, int l, int r, int rt){ if (L <= l&&r <= R){ if(add == 2) SWAP(rt, r - l + 1); else{ col[rt] = add; unsum[rt] = sum[rt] = lsum[rt] = rsum[rt] = add ? r - l + 1 : 0; zsum[rt] = lzsum[rt] = rzsum[rt] = add ? 0 : r - l + 1; } return; } int m = l + r >> 1; PushDown(rt, r - l + 1); if (L <= m) update(L, R, add, lson); if (R > m) update(L, R, add, rson); PushUp(rt, r - l + 1); } int query(int L, int R, int op, int l, int r, int rt){ int m = l + r >> 1, ans = 0; if(op&1){ if(L <= l && r <= R) return unsum[rt]; PushDown(rt, r - l + 1); if(L <= m) ans += query(L, R, op, lson); if(m < R) ans += query(L, R, op, rson); return ans; } if(L <= l && r <= R) return sum[rt]; PushDown(rt, r - l + 1); ans = min(rsum[lc], m - L + 1) + min(lsum[rc], R - m); if(L <= m) ans = max(ans, query(L, R, op, lson)); if(m < R) ans = max(ans, query(L, R, op, rson)); return ans; } int main(){ int n, m, T, op, a, b; scanf("%d", &T); while(T--){ scanf("%d%d", &n, &m); build(1, n, 1); while(m--){ scanf("%d%d%d", &op, &a, &b); if(op < 3) update(a + 1, b + 1, op, 1, n, 1); else printf("%d\n", query(a + 1, b + 1, op, 1, n, 1)); } } return 0; }