题意：
给定一个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