計蒜客 - 硬币翻轉

#include<bits/stdc++.h>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ls rt<<1
#define rs rt<<1|1
const int maxn=100000+100;
const int INF=0x3f3f3f3f;

struct Tree{
    
    int lm,mm,rm;
    int Lm,Mm,Rm;
    int s;
    int S;
    int l,r;
    int lv,rv;
    int add;
}tree[maxn<<2];
int ans[maxn];

inline Tree merge(Tree l,Tree r){
    
    Tree fa;
    fa.mm=max(l.mm,r.mm);
    fa.Mm=max(l.Mm,r.Mm);
    fa.lm=l.lm;fa.rm=r.rm;
    fa.Lm=l.Lm;fa.Rm=r.Rm;
    fa.l=l.l;fa.r=r.r;
    fa.lv=l.lv;fa.rv=r.rv;
    fa.s=fa.S=-INF;
    if(l.rv && r.lv){
        
        fa.mm=max(fa.mm,l.rm+r.lm);
        fa.lm=max(fa.lm,l.s+r.lm);
        fa.rm=max(fa.rm,l.rm+r.s);
        fa.s=max(fa.s,l.s+r.s);
    }
    if(!l.rv && !r.lv){
        
        fa.Mm=max(fa.Mm,l.Rm+r.Lm);
        fa.Lm=max(fa.Lm,l.S+r.Lm);
        fa.Rm=max(fa.Rm,l.Rm+r.S);
        fa.S=max(fa.S,l.S+r.S);
    }
    return fa;
}

void build(int rt,int l,int r){
    
    if(l==r){
        
        tree[rt].mm=tree[rt].lm=tree[rt].rm=tree[rt].s=ans[l];
        tree[rt].Mm=tree[rt].Lm=tree[rt].Rm=tree[rt].S=(!ans[l]);
        tree[rt].l=l;tree[rt].r=r;
        tree[rt].add=0;
        tree[rt].lv=ans[l];
        tree[rt].rv=ans[r];
        return ;
    }
    
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    tree[rt]=merge(tree[ls],tree[rs]);tree[rt].add=0;
}

inline void updateup(int rt){
    
    tree[ls].add++;tree[ls].add%=2;
    tree[rs].add++;tree[rs].add%=2;
    tree[ls].lv++;tree[ls].lv%=2;tree[ls].rv++;tree[ls].rv%=2;
    tree[rs].lv++;tree[rs].lv%=2;tree[rs].rv++;tree[rs].rv%=2;
    swap(tree[ls].lm,tree[ls].Lm);swap(tree[ls].rm,tree[ls].Rm);
    swap(tree[ls].mm,tree[ls].Mm);swap(tree[ls].s,tree[ls].S);
    swap(tree[rs].lm,tree[rs].Lm);swap(tree[rs].rm,tree[rs].Rm);
    swap(tree[rs].mm,tree[rs].Mm);swap(tree[rs].s,tree[rs].S);
    tree[rt].add=0;
}

inline void update(int rt,int l,int r,int L,int R){
    
    if(L>r || R<l) return ;
    if(L<=l && R>=r){
        
        tree[rt].add++;tree[rt].add%=2;
        tree[rt].lv++;tree[rt].lv%=2;
        tree[rt].rv++;tree[rt].rv%=2;
        swap(tree[rt].lm,tree[rt].Lm);
        swap(tree[rt].rm,tree[rt].Rm);
        swap(tree[rt].mm,tree[rt].Mm);
        swap(tree[rt].s,tree[rt].S);
        return ;
    }
    if(tree[rt].add) updateup(rt);
    int mid=(l+r)>>1;
    update(lson,L,R);
    update(rson,L,R);
    int tmp=tree[rt].add;
    tree[rt]=merge(tree[ls],tree[rs]);tree[rt].add=tmp;
}

inline Tree query(int rt,int l,int r,int L,int R){
    
    if(L<=l && R>=r) return tree[rt];
    if(tree[rt].add) updateup(rt);
    int mid=(l+r)>>1;
    if(R<=mid) return query(lson,L,R);
    else if(L>mid) return query(rson,L,R);
    else return merge(query(lson,L,R),query(rson,L,R));
}

int main(){
    
    int n;
    while(scanf("%d",&n)==1){
        
       for(int i=1;i<=n;i++) scanf("%d",&ans[i]);
       build(1,1,n);
       int m;
       scanf("%d",&m);
       while(m--){
        
           int type,l,r;
           scanf("%d%d%d",&type,&l,&r);
           if(type) update(1,1,n,l,r);
           else printf("%d\n",query(1,1,n,l,r).mm);
       }
    }
}