bzoj1858 序列操作

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
using namespace std;
const int maxn=100000+5;
#define lson (o<<1)
#define rson (o<<1|1)
int a[maxn],n,m;
namespace segment_tree{
    int sumv[maxn*6],setv[maxn*6],lefc[2][maxn*6],rghc[2][maxn*6],cot[2][maxn*6];
    bool rev[maxn*6];
    void ()
    {
        memset(setv,-1,sizeof(setv));
    }
    void maintain(int o, int l,int r)
    {
        sumv[o]=sumv[lson]+sumv[rson];
        int mid=(l+r)>>1;
        cot[0][o]=max(max(cot[0][lson],cot[0][rson]),rghc[0][lson]+lefc[0][rson]);
        cot[1][o]=max(max(cot[1][lson],cot[1][rson]),rghc[1][lson]+lefc[1][rson]);
        lefc[0][o]=lefc[0][lson];
        if(sumv[lson]==0) lefc[0][o]=mid-l+1+lefc[0][rson];
        lefc[1][o]=lefc[1][lson];
        if(sumv[lson]==(mid-l+1)) lefc[1][o]=mid-l+1+lefc[1][rson];
        rghc[0][o]=rghc[0][rson];
        if(sumv[rson]==0) rghc[0][o]=r-mid+rghc[0][lson];
        rghc[1][o]=rghc[1][rson];
        if(sumv[rson]==(r-mid)) rghc[1][o]=r-mid+rghc[1][lson];
        if(setv[o]!=-1){
            sumv[o]=setv[o]*(r-l+1);
            cot[0][o]=lefc[0][o]=rghc[0][o]=(setv[o]==0)*(r-l+1);
            cot[1][o]=lefc[1][o]=rghc[1][o]=(setv[o]==1)*(r-l+1);
        }
        if(rev[o]){
            sumv[o]=(r-l+1)-sumv[o];
            swap(cot[0][o],cot[1][o]),swap(lefc[0][o],lefc[1][o]),swap(rghc[0][o],rghc[1][o]);
        }
    }
    void getrev(int o,int l,int r)
    {
        rev[o]^=1;
        maintain(o,l,r);
    }
    void getset(int o,int l,int r,int val)
    {
        rev[o]=0;
        setv[o]=val;
        maintain(o,l,r);
    }
    void pushdown(int o,int l,int r)
    {
        int mid=(l+r)>>1;
        if(setv[o]!=-1){
            getset(lson,l,mid,setv[o]);
            getset(rson,mid+1,r,setv[o]);
            setv[o]=-1;
            maintain(o,l,r);
        }
        if(rev[o]){
            getrev(lson,l,mid);getrev(rson,mid+1,r);
            rev[o]=0;
            maintain(o,l,r);
        }
    }
    void Set(int o,int l,int r,int ql,int qr,int val)
    {
        if(ql>r || qr<l) return;
        if(ql<=l && r<=qr) {getset(o,l,r,val);return;}
        else{
            int mid=(l+r)>>1;
            pushdown(o,l,r);
            if(ql<=mid) Set(lson,l,mid,ql,qr,val);
            if(qr>mid) Set(rson,mid+1,r,ql,qr,val);
            maintain(o,l,r);
        }
    }
    void Rev(int o,int l,int r,int ql,int qr)
    {
        if(ql>r || qr<l) return;
        if(ql<=l && r<=qr) {getrev(o,l,r);return;}
        else{
            int mid=(l+r)>>1;
            pushdown(o,l,r);
            if(ql<=mid) Rev(lson,l,mid,ql,qr);
            if(qr>mid) Rev(rson,mid+1,r,ql,qr);
            maintain(o,l,r);
        }
    }
    int Qsum(int o,int l,int r,int ql,int qr)
    {
        if(ql>r || qr<l) return 0;
        if(ql<=l && r<=qr) return sumv[o];
        else{
            int mid=(l+r)>>1;
            pushdown(o,l,r);
            int ret=0;
            if(ql<=mid) ret+=Qsum(lson,l,mid,ql,qr);
            if(qr>mid) ret+=Qsum(rson,mid+1,r,ql,qr);
            return ret;
        }
    }
    int Qcon(int o,int l,int r,int ql,int qr,int dir)
    {
        if(ql>r || qr<l) return 0;
        if(ql<=l && r<=qr){
            if(dir==0) return cot[1][o];
            if(dir==1) return lefc[1][o];
            if(dir==2) return rghc[1][o];
        }else{
            int mid=(l+r)>>1;
            pushdown(o,l,r);
            if(qr<=mid) return Qcon(lson,l,mid,ql,qr,dir);
            else if(ql>mid) return Qcon(rson,mid+1,r,ql,qr,dir);
            else{
                int mid=(l+r)>>1;
                if(dir==0){
                    int ret=0;
                    ret=max(ret,Qcon(lson,l,mid,ql,qr,2)+Qcon(rson,mid+1,r,ql,qr,1));
                    ret=max(ret,Qcon(lson,l,mid,ql,qr,0));
                    ret=max(ret,Qcon(rson,mid+1,r,ql,qr,0));
                    return ret;
                }else if(dir==1){
                    int sm=Qsum(lson,l,mid,ql,qr);
                    if(sm==mid-max(l,ql)+1){
                        return sm+Qcon(rson,mid+1,r,ql,qr,1);
                    }else return Qcon(lson,l,mid,ql,qr,1);
                }else{
                    int sm=Qsum(rson,mid+1,r,ql,qr);
                    if(sm==min(r,qr)-mid){
                        return sm+Qcon(lson,l,mid,ql,qr,2);
                    }else return Qcon(rson,mid+1,r,ql,qr,2);
                }
                assert(0);
            }
            assert(0);
        }
    }
};    
using namespace segment_tree;
int main()
{
    ini();
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        Set(1,1,n,i,i,a[i]);
    }
    int op,l,r;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&op,&l,&r);
        l++,r++;
        if(op==0) Set(1,1,n,l,r,0);
        else if(op==1) Set(1,1,n,l,r,1);
        else if(op==2) Rev(1,1,n,l,r);
        else if(op==3) printf("%dn",Qsum(1,1,n,l,r));
        else printf("%dn",Qcon(1,1,n,l,r,0));
    }
    return 0;
}