題意：
給定一個N<=100000個數的01序列，要你支持共Q<=100000個五種操作
0 a b 把[a, b]區間內的所有數全變成0
1 a b 把[a, b]區間內的所有數全變成1
2 a b 把[a,b]區間內的所有數全部取反，也就是說把所有的0變成1，把所有的1變成0
3 a b 詢問[a, b]區間內總共有多少個1
4 a b 詢問[a, b]區間內最多有多少個連續的1
做法：
我只會用很傻逼的方法（雖然在八中oj上跑的最快）
線段樹里保存很多很多值：
左邊開始最多有多少個0 多少個1
右邊開始最多有多少個0 多少個1
區間內最大連續有多少個0 多少個1
區間總共有多少個0 多少個1
區間是否被0或者1 覆蓋
區間是否被取反
如果沒有取反的操作 那么就很簡單
有了取反的操作：
假設取反前已經被0或者1覆蓋 那么把這個值取反
如果沒有被0或者1覆蓋 那么將 區間取反標記 取反
如果該區間被覆蓋了 無論之前有沒有被取反 取反標記都是無用的
這樣就可以解決這個問題了。。
ps：這個題調了我2個小時。。結果是因為懶得寫Rch 直接復制Lch 有幾個地方還是Lch 沒改成Rch....好2的錯誤
1
#include <cstdio>
2
3#define Lch(t) (t<<1)
4#define Rch(t) ((t<<1)+1)
5#define max(a,b) ((a)>(b)?(a):(b))
6struct Tnode
7
{
8
int lm[2],rm[2],d[2],s[2],m[2],last;
9 bool inv;
10
} T[400005];
11int A[100005],N,M;
12inline void swap(int &u,int &v)
13{
14 int t=u;u=v;v=t;
15}
16inline void Downdraw(int t,int L,int R,int c)
17{
18 T[Lch(t)].lm[c]=T[Lch(t)].rm[c]=T[Lch(t)].m[c]=T[Lch(t)].s[c]=L;
19 T[Lch(t)].lm[c^1]=T[Lch(t)].rm[c^1]=T[Lch(t)].m[c^1]=T[Lch(t)].m[c^1]=T[Lch(t)].s[c^1]=0;
20 T[Lch(t)].d[c]=1,T[Lch(t)].d[c^1]=0;
21 T[Rch(t)].lm[c]=T[Rch(t)].rm[c]=T[Rch(t)].m[c]=T[Rch(t)].s[c]=R;
22 T[Rch(t)].lm[c^1]=T[Rch(t)].rm[c^1]=T[Rch(t)].m[c^1]=T[Rch(t)].m[c^1]=T[Rch(t)].s[c^1]=0;
23 T[Rch(t)].d[c]=1,T[Rch(t)].d[c^1]=0;
24 T[Lch(t)].inv=T[Rch(t)].inv=0;
25 T[t].d[c]=0;
26}
27inline void Downinve(int t,int L,int R)
28{
29 swap(T[Lch(t)].lm[0],T[Lch(t)].lm[1]);
30 swap(T[Lch(t)].rm[0],T[Lch(t)].rm[1]);
31 swap(T[Lch(t)].m[0],T[Lch(t)].m[1]);
32 swap(T[Lch(t)].s[0],T[Lch(t)].s[1]);
33 swap(T[Lch(t)].d[0],T[Lch(t)].d[1]);
34 if (!T[Lch(t)].d[0]&&!T[Lch(t)].d[1]) T[Lch(t)].inv^=1;
35 swap(T[Rch(t)].lm[0],T[Rch(t)].lm[1]);
36 swap(T[Rch(t)].rm[0],T[Rch(t)].rm[1]);
37 swap(T[Rch(t)].m[0],T[Rch(t)].m[1]);
38 swap(T[Rch(t)].s[0],T[Rch(t)].s[1]);
39 swap(T[Rch(t)].d[0],T[Rch(t)].d[1]);
40 if (!T[Rch(t)].d[0]&&!T[Rch(t)].d[1]) T[Rch(t)].inv^=1;
41 T[t].inv=0;
42}
43inline void Down(int t,int L,int R)
44{
45 int c=-1;
46 if (T[t].d[0]>0) c=0;
47 if (T[t].d[1]>0) c=1;
48 if (c>=0) Downdraw(t,L,R,c);
49 else
50 if (T[t].inv) Downinve(t,L,R);
51}
52inline void Update(Tnode &t,Tnode &l,Tnode &r,int L,int R)
53{
54 for (int i=0;i<2;++i)
55
{
56 t.lm[i]=l.lm[i],t.rm[i]=r.rm[i];
57 if (l.lm[i]==L) t.lm[i]=L+r.lm[i];
58 if (r.rm[i]==R) t.rm[i]=l.rm[i]+R;
59 t.s[i]=l.s[i]+r.s[i];
60 t.m[i]=max(l.m[i],r.m[i]);
61 t.m[i]=max(t.m[i],l.rm[i]+r.lm[i]);
62
}
63}
64inline void Build(int t,int l,int r)
65{
66 if (l==r)
67 {
68 T[t].lm[A[l]]=T[t].rm[A[l]]=T[t].m[A[l]]=T[t].s[A[l]]=1;
69 return;
70 }
71 int mid=(l+r)>>1,L=mid-l+1,R=r-mid;
72 Down(t,L,R);
73 Build(Lch(t),l,mid);
74 Build(Rch(t),mid+1,r);
75 Update(T[t],T[Lch(t)],T[Rch(t)],L,R);
76}
77inline void Draw(int t,int l,int r,int ll,int rr,int c)
78{
79 if (ll==l&&rr==r)
80 {
81 T[t].lm[c]=T[t].rm[c]=T[t].m[c]=T[t].m[c]=T[t].s[c]=r-l+1;
82 T[t].lm[c^1]=T[t].rm[c^1]=T[t].m[c^1]=T[t].m[c^1]=T[t].s[c^1]=0;
83 T[t].d[c]=1,T[t].d[c^1]=0;
84 T[t].inv=0;
85 return;
86 }
87 int mid=(l+r)>>1,L=mid-l+1,R=r-mid;
88 Down(t,L,R);
89 if (rr<=mid) Draw(Lch(t),l,mid,ll,rr,c);
90 else
91 if (ll>mid) Draw(Rch(t),mid+1,r,ll,rr,c);
92 else
93 {
94 Draw(Lch(t),l,mid,ll,mid,c);
95 Draw(Rch(t),mid+1,r,mid+1,rr,c);
96 }
97 Update(T[t],T[Lch(t)],T[Rch(t)],L,R);
98}
99inline void Inverse(int t,int l,int r,int ll,int rr)
100{
101 if (ll==l&&rr==r)
102 {
103 swap(T[t].lm[0],T[t].lm[1]);
104 swap(T[t].rm[0],T[t].rm[1]);
105 swap(T[t].m[0],T[t].m[1]);
106 swap(T[t].s[0],T[t].s[1]);
107 swap(T[t].d[0],T[t].d[1]);
108 if (!T[t].d[0]&&!T[t].d[1]) T[t].inv^=1;
109 return;
110 }
111 int mid=(l+r)>>1,L=mid-l+1,R=r-mid;
112 Down(t,L,R);
113 if (rr<=mid) Inverse(Lch(t),l,mid,ll,rr);
114 else
115 if (ll>mid) Inverse(Rch(t),mid+1,r,ll,rr);
116 else
117 {
118 Inverse(Lch(t),l,mid,ll,mid);
119 Inverse(Rch(t),mid+1,r,mid+1,rr);
120 }
121 Update(T[t],T[Lch(t)],T[Rch(t)],L,R);
122}
123inline Tnode Query(int t,int l,int r,int ll,int rr)
124{
125 if (ll==l&&rr==r) return T[t];
126 int mid=(l+r)>>1,L=mid-l+1,R=r-mid;
127 Down(t,L,R);
128 if (rr<=mid) return Query(Lch(t),l,mid,ll,rr);
129 if (ll>mid) return Query(Rch(t),mid+1,r,ll,rr);
130 Tnode left=Query(Lch(t),l,mid,ll,mid);
131 Tnode right=Query(Rch(t),mid+1,r,mid+1,rr);
132 Tnode ret;Update(ret,left,right,L,R);
133 return ret;
134}
135int main()
136{
137 int a,b,c;
138 scanf("%d%d",&N,&M);
139 for (int i=1;i<=N;++i)
140 scanf("%d",&A[i]);
141 Build(1,1,N);
142 for (;M--;)
143 {
144 scanf("%d%d%d",&c,&a,&b),++a,++b;
145 if (c<2) Draw(1,1,N,a,b,c);
146 else
147 if (c==2) Inverse(1,1,N,a,b);
148 else
149 if (c==3) printf("%d\n",Query(1,1,N,a,b).s[1]);
150 else printf("%d\n",Query(1,1,N,a,b).m[1]);
151 }
152 return 0;
153}
154