【线段树】序列操作

线段树

传送阵：BZOJ1858

思路：利用线段树

操作0：区间覆盖标记

操作1：区间覆盖标记

操作2：区间反转标记，交换0/1信息

操作3：询问区间和

操作4：从区间最大、左区间右最大+右区间左最大中选较大值

注意：

操作0、1、2间可能相互覆盖：

操作0、1后要去掉标记2，0、1标记；

标记下传时先传覆盖再传反转

区间覆盖标记下传后要记得覆盖掉已有的区间反转标记（奇坑无比）

详见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,op,x,y,a[400000],cov[400000],rev[400000],sum[400000][2],ll[400000][2],rr[400000][2],Max[400000][2];
inline void pushdown(int cur,int l,int r,int mid){
    if (cov[cur]!=-1){
        cov[cur<<1]=cov[cur<<1|1]=cov[cur]; 
        sum[cur<<1][cov[cur]]=mid-l+1; sum[cur<<1][cov[cur]^1]=0;
        sum[cur<<1|1][cov[cur]]=r-mid; sum[cur<<1|1][cov[cur]^1]=0;
        ll[cur<<1][cov[cur]]=rr[cur<<1][cov[cur]]=mid-l+1;
        ll[cur<<1][cov[cur]^1]=rr[cur<<1][cov[cur]^1]=0;
        ll[cur<<1|1][cov[cur]]=rr[cur<<1|1][cov[cur]]=r-mid;
        ll[cur<<1|1][cov[cur]^1]=rr[cur<<1|1][cov[cur]^1]=0;
        Max[cur<<1][cov[cur]]=mid-l+1; Max[cur<<1|1][cov[cur]]=r-mid;
        Max[cur<<1][cov[cur]^1]=Max[cur<<1|1][cov[cur]^1]=0;
        rev[cur<<1]=rev[cur<<1|1]=0;//---------------------------REALLY IMPORTANT!!!!!!
    }
    if (rev[cur]==1){
        swap(sum[cur<<1][0],sum[cur<<1][1]); swap(sum[cur<<1|1][0],sum[cur<<1|1][1]);
        swap(ll[cur<<1][0],ll[cur<<1][1]); swap(rr[cur<<1][0],rr[cur<<1][1]);
        swap(ll[cur<<1|1][0],ll[cur<<1|1][1]); swap(rr[cur<<1|1][0],rr[cur<<1|1][1]);
        swap(Max[cur<<1][0],Max[cur<<1][1]); swap(Max[cur<<1|1][0],Max[cur<<1|1][1]);
    }
    rev[cur<<1]^=rev[cur]; rev[cur<<1|1]^=rev[cur];
    cov[cur]=-1; rev[cur]=0;
}
inline void update(int cur,int l,int r,int mid){
    Max[cur][0]=max(Max[cur<<1][0],Max[cur<<1|1][0]); Max[cur][0]=max(Max[cur][0],rr[cur<<1][0]+ll[cur<<1|1][0]);
    Max[cur][1]=max(Max[cur<<1][1],Max[cur<<1|1][1]); Max[cur][1]=max(Max[cur][1],rr[cur<<1][1]+ll[cur<<1|1][1]);
    if (ll[cur<<1][0]==mid-l+1) ll[cur][0]=ll[cur<<1][0]+ll[cur<<1|1][0]; else ll[cur][0]=ll[cur<<1][0];
    if (ll[cur<<1][1]==mid-l+1) ll[cur][1]=ll[cur<<1][1]+ll[cur<<1|1][1]; else ll[cur][1]=ll[cur<<1][1];
    if (rr[cur<<1|1][0]==r-mid) rr[cur][0]=rr[cur<<1|1][0]+rr[cur<<1][0]; else rr[cur][0]=rr[cur<<1|1][0];
    if (rr[cur<<1|1][1]==r-mid) rr[cur][1]=rr[cur<<1|1][1]+rr[cur<<1][1]; else rr[cur][1]=rr[cur<<1|1][1];
    sum[cur][0]=sum[cur<<1][0]+sum[cur<<1|1][0]; sum[cur][1]=sum[cur<<1][1]+sum[cur<<1|1][1];
}
        
void add(int cur,int l,int r,int L,int R,int x){
    if (L<=l && R>=r){
        rev[cur]=0; cov[cur]=x; sum[cur][x]=r-l+1; sum[cur][x^1]=0;
        Max[cur][x]=ll[cur][x]=rr[cur][x]=r-l+1; Max[cur][x^1]=ll[cur][x^1]=rr[cur][x^1]=0;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(cur,l,r,mid);
    if (L<=mid) add(cur<<1,l,mid,L,R,x);
    if (R>mid) add(cur<<1|1,mid+1,r,L,R,x);
    update(cur,l,r,mid);
}
void reverse(int cur,int l,int r,int L,int R){
    if (L<=l && R>=r){
        rev[cur]^=1;
        swap(sum[cur][0],sum[cur][1]); swap(ll[cur][0],ll[cur][1]); swap(rr[cur][0],rr[cur][1]); swap(Max[cur][0],Max[cur][1]);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(cur,l,r,mid);
    if (L<=mid) reverse(cur<<1,l,mid,L,R);
    if (R>mid) reverse(cur<<1|1,mid+1,r,L,R);
    update(cur,l,r,mid);
}
int query1(int cur,int l,int r,int L,int R){
    if (L<=l && R>=r) return sum[cur][1];
    int mid=(l+r)>>1,tmp=0;
    pushdown(cur,l,r,mid);
    if (L<=mid) tmp+=query1(cur<<1,l,mid,L,R);
    if (R>mid) tmp+=query1(cur<<1|1,mid+1,r,L,R);
    return tmp;
}
int query2(int cur,int l,int r,int L,int R){
    if (L<=l && R>=r){return Max[cur][1];}
    int mid=(l+r)>>1,tmp=0;
    pushdown(cur,l,r,mid);
    if (L<=mid) tmp=max(tmp,query2(cur<<1,l,mid,L,R));
    if (R>mid) tmp=max(tmp,query2(cur<<1|1,mid+1,r,L,R));
    if (L<=mid && R>mid) tmp=max(tmp,min(rr[cur<<1][1],mid-L+1)+min(ll[cur<<1|1][1],R-mid));
    return tmp;
}
int main(){
    memset(cov,-1,sizeof cov);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){scanf("%d",&a[i]); add(1,1,n,i,i,a[i]);}
    
    for (int i=1;i<=m;i++){
        scanf("%d%d%d",&op,&x,&y); x++; y++;
        if (op==0) add(1,1,n,x,y,0);
        if (op==1) add(1,1,n,x,y,1);
        if (op==2) reverse(1,1,n,x,y);
        if (op==3) printf("%d\n",query1(1,1,n,x,y));
        if (op==4) printf("%d\n",query2(1,1,n,x,y)); 
    }
    return 0;
}