線段樹 區間更新 HDU 3911

Black And White

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3811 Accepted Submission(s): 1129


Problem Description There are a bunch of stones on the beach; Stone color is white or black. Little Sheep has a magic brush, she can change the color of a continuous stone, black to white, white to black. Little Sheep like black very much, so she want to know the longest period of consecutive black stones in a range [i, j].
Input There are multiple cases, the first line of each case is an integer n(1<= n <= 10^5), followed by n integer 1 or 0(1 indicates black stone and 0 indicates white stone), then is an integer M(1<=M<=10^5) followed by M operations formatted as x i j(x = 0 or 1) , x=1 means change the color of stones in range[i,j], and x=0 means ask the longest period of consecutive black stones in range[i,j]
Output When x=0 output a number means the longest length of black stones in range [i,j].
Sample Input

4
1 0 1 0
5
0 1 4
1 2 3
0 1 4
1 3 3
0 4 4

Sample Output

1
2
0

Source 2011 Multi-University Training Contest 8 - Host by HUST 裸裸的區間更新，注意點已在代碼中寫出

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define MAXN 100000 + 1000

struct node{
    int lsum0,rsum0,msum0,lsum1,rsum1,msum1;
    int ck;
    int l,r;
    int mid(){
        return (l+r)>>1;
    }
}tree[MAXN<<2];

int a[MAXN];

void PushUp(int rt){
    int ll = tree[rt<<1].r-tree[rt<<1].l+1;//左子樹區間的長度
    int rr = tree[rt<<1|1].r-tree[rt<<1|1].l+1;//右子樹區間的長度
    tree[rt].lsum1 = tree[rt<<1].lsum1;
    if(tree[rt<<1].lsum1 == ll){
        tree[rt].lsum1 = tree[rt].lsum1+tree[rt<<1|1].lsum1;
    }
    tree[rt].rsum1 = tree[rt<<1|1].rsum1;
    if(tree[rt<<1|1].rsum1 == rr){
        tree[rt].rsum1 = tree[rt].rsum1+tree[rt<<1].rsum1;
    }
    tree[rt].lsum0 = tree[rt<<1].lsum0;
    if(tree[rt<<1].lsum0 == ll){
        tree[rt].lsum0+=tree[rt<<1|1].lsum0;
    }
    tree[rt].rsum0 = tree[rt<<1|1].rsum0;
    if(tree[rt<<1|1].rsum0 == rr){
        tree[rt].rsum0+=tree[rt<<1].rsum0;
    }
    tree[rt].msum0=max(max(tree[rt<<1].msum0,tree[rt<<1|1].msum0),tree[rt<<1].rsum0+tree[rt<<1|1].lsum0);
    tree[rt].msum1 = max(max(tree[rt<<1].msum1,tree[rt<<1|1].msum1),tree[rt<<1].rsum1+tree[rt<<1|1].lsum1);
}

void PushDown(int rt){
    if(tree[rt].ck == 1){
        tree[rt<<1].ck ^= 1;//現在左子樹父親節點的所有01都需要交換，所以左子樹也是需要交換，那麼左子樹的左右子樹也是需要交換，如果原來左子樹就要交換
        tree[rt<<1|1].ck ^= 1;//，那麼交換了兩次就相當於不需要交換，這樣異或之後就可以不需要交換
        tree[rt].ck = 0;
        swap(tree[rt<<1].lsum0,tree[rt<<1].lsum1);
        swap(tree[rt<<1].rsum0,tree[rt<<1].rsum1);
        swap(tree[rt<<1].msum0,tree[rt<<1].msum1);

        swap(tree[rt<<1|1].lsum0,tree[rt<<1|1].lsum1);
        swap(tree[rt<<1|1].rsum0,tree[rt<<1|1].rsum1);
        swap(tree[rt<<1|1].msum0,tree[rt<<1|1].msum1);
    }
}

void build(int l,int r,int rt){
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].ck = 0;//開始的時候都不轉換
    if(l == r){
        if(a[l] == 0){
            tree[rt].lsum0=tree[rt].rsum0=tree[rt].msum0=1;
            tree[rt].lsum1=tree[rt].rsum1=tree[rt].msum1=0;
        }
        else{
            tree[rt].lsum1=tree[rt].rsum1=tree[rt].msum1=1;
            tree[rt].lsum0=tree[rt].rsum0=tree[rt].msum0=0;
        }
        return ;
    }
    //int m = (l+r)>>1;
    int m = tree[rt].mid();
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    PushUp(rt);
}

void update(int l,int r,int rt){
    if(l<=tree[rt].l && tree[rt].r<=r){
        tree[rt].ck ^= 1;
        swap(tree[rt].lsum0,tree[rt].lsum1);
        swap(tree[rt].rsum0,tree[rt].rsum1);
        swap(tree[rt].msum0,tree[rt].msum1);
        return ;
    }
    PushDown(rt);
    int m = tree[rt].mid();
    if(r <= m){
        update(l,r,rt<<1);
    }
    else if(l > m){
        update(l,r,rt<<1|1);
    }
    else{
        update(l,m,rt<<1);
        update(m+1,r,rt<<1|1);
    }
    PushUp(rt);
}

int query(int l,int r,int rt){
    if(l<=tree[rt].l && tree[rt].r<=r){
        return tree[rt].msum1;
    }
    PushDown(rt);
    int m = tree[rt].mid();
    if(r <= m){
        return query(l,r,rt<<1);
    }
    else if(l > m){
        return query(l,r,rt<<1|1);
    }
    else{
        int lr = query(l,m,rt<<1);
        int rr = query(m+1,r,rt<<1|1);
        int a = tree[rt<<1].rsum1;//左子樹最長的連續的1
        if(a > tree[rt<<1].r-l+1){//後面的那個是最大范圍
            a = tree[rt<<1].r-l+1;
        }
        int b = tree[rt<<1|1].lsum1;
        if(b > r-tree[rt<<1|1].l+1){
            b = r-tree[rt<<1|1].l+1;
        }
        return max(max(lr,rr),a+b);
    }
}

int main(){
    int i;
    int n,m,op,aa,b;

    while(~scanf("%d",&n)){
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        build(1,n,1);
        scanf("%d",&m);
        while(m--){
            scanf("%d%d%d",&op,&aa,&b);
            if(op == 0){
                int ans = query(aa,b,1);
                printf("%d\n",ans);
            }
            else{
                update(aa,b,1);
            }
        }
    }

    return 0;
}