題意：
給定一個N<=100000個數(shù)的01序列，要你支持共Q<=100000個五種操作
0 a b 把[a, b]區(qū)間內(nèi)的所有數(shù)全變成0
1 a b 把[a, b]區(qū)間內(nèi)的所有數(shù)全變成1
2 a b 把[a,b]區(qū)間內(nèi)的所有數(shù)全部取反，也就是說把所有的0變成1，把所有的1變成0
3 a b 詢問[a, b]區(qū)間內(nèi)總共有多少個1
4 a b 詢問[a, b]區(qū)間內(nèi)最多有多少個連續(xù)的1
做法：
我只會用很傻逼的方法（雖然在八中oj上跑的最快）
線段樹里保存很多很多值：
左邊開始最多有多少個0 多少個1
右邊開始最多有多少個0 多少個1
區(qū)間內(nèi)最大連續(xù)有多少個0 多少個1
區(qū)間總共有多少個0 多少個1
區(qū)間是否被0或者1 覆蓋
區(qū)間是否被取反
如果沒有取反的操作 那么就很簡單
有了取反的操作：
假設(shè)取反前已經(jīng)被0或者1覆蓋 那么把這個值取反
如果沒有被0或者1覆蓋 那么將 區(qū)間取反標(biāo)記 取反
如果該區(qū)間被覆蓋了 無論之前有沒有被取反 取反標(biāo)記都是無用的
這樣就可以解決這個問題了。。
ps：這個題調(diào)了我2個小時。。結(jié)果是因為懶得寫Rch 直接復(fù)制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