HDU3397Sequence operation線段樹解法

HDU3397Sequence operation線段樹解法

題：點擊打開鏈接

分析：線段樹區間更新。只不過摻雜了區間和、最大連續區間區間和。對於延遲標記在上一篇博客已經出現過：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;
}