http://acm.hdu.edu.cn/showproblem.php?pid=3397
空间要开大点不然就RE。更新比较复杂，在取反时要注意先向下更新。
如这样的数据：
1
10 10
0 0 0 1 1 0 1 0 1 1
2 0 9
2 0 9
4 0 2
1 0 9
2 0 8
4 0 2
1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#define
lson l,mid,i<<1
5
#define
rson mid+1,r,i<<1|1
6
using
namespace
std;
7
const
int
Ni =
100100
;
8
int
n;
9
struct
node {
10
int
sum1,sum0;
11
int
mx1,lm1,rm1;
12
int
mx0,lm0,rm0;
13
int
lnum,rnum;
14
}tree[Ni<<
3
];
15
int
color[Ni<<
3
];
16
inline
void
changes(
int
i)
17
{
18
swap(tree[i].mx1,tree[i].mx0);
19
swap(tree[i].sum1,tree[i].sum0);
20
swap(tree[i].lm1,tree[i].lm0);
21
swap(tree[i].rm1,tree[i].rm0);
22
tree[i].lnum=!
tree[i].lnum;
23
tree[i].rnum=!
tree[i].rnum;
24
}
25
inline
void
pushup(
int
l,
int
r,
int
i)
26
{
27
tree[i].mx1=max(tree[i<<
1
].mx1,tree[i<<
1
|
1
].mx1);
///
111111
28
if
(tree[i<<
1
].rnum==
1
&&tree[i<<
1
|
1
].lnum==
1
)
29
{
30
tree[i].mx1=max(tree[i].mx1,tree[i<<
1
].rm1+tree[i<<
1
|
1
].lm1);
31
}
32
int
mid=(l+r)>>
1
;
33
if
(tree[i<<
1
].mx1==mid-l+
1
&&tree[i<<
1
].rnum==
1
&&tree[i<<
1
|
1
].lnum==
1
)
34
tree[i].lm1=tree[i<<
1
].mx1+tree[i<<
1
|
1
].lm1;
35
else
36
tree[i].lm1=tree[i<<
1
].lm1;
37
38
if
(tree[i<<
1
|
1
].mx1==r-mid&&tree[i<<
1
].rnum==
1
&&tree[i<<
1
|
1
].lnum==
1
)
39
tree[i].rm1=tree[i<<
1
|
1
].mx1+tree[i<<
1
].rm1;
40
else
41
tree[i].rm1=tree[i<<
1
|
1
].rm1;
42
tree[i].lnum=tree[i<<
1
].lnum;
43
tree[i].rnum=tree[i<<
1
|
1
].rnum;
44
tree[i].sum1=tree[i<<
1
].sum1+tree[i<<
1
|
1
].sum1;
45
46
tree[i].mx0=max(tree[i<<
1
].mx0,tree[i<<
1
|
1
].mx0);
///
000000
47
if
(tree[i<<
1
].rnum==
0
&&tree[i<<
1
|
1
].lnum==
0
)
48
{
49
tree[i].mx0=max(tree[i].mx0,tree[i<<
1
].rm0+tree[i<<
1
|
1
].lm0);
50
}
51
mid=(l+r)>>
1
;
52
if
(tree[i<<
1
].mx0==mid-l+
1
&&tree[i<<
1
].rnum==
0
&&tree[i<<
1
|
1
].lnum==
0
)
53
tree[i].lm0=tree[i<<
1
].mx0+tree[i<<
1
|
1
].lm0;
54
else
55
tree[i].lm0=tree[i<<
1
].lm0;
56
57
if
(tree[i<<
1
|
1
].mx0==r-mid&&tree[i<<
1
].rnum==
0
&&tree[i<<
1
|
1
].lnum==
0
)
58
tree[i].rm0=tree[i<<
1
|
1
].mx0+tree[i<<
1
].rm0;
59
else
60
tree[i].rm0=tree[i<<
1
|
1
].rm0;
61
tree[i].lnum=tree[i<<
1
].lnum;
62
tree[i].rnum=tree[i<<
1
|
1
].rnum;
63
tree[i].sum0=tree[i<<
1
].sum0+tree[i<<
1
|
1
].sum0;
64
}
65
inline
void
pushdown(
int
l,
int
r,
int
i)
66
{
67
if
(color[i]==-
8
)
return
;
68
if
(color[i]==
1
)
69
{
70
color[i<<
1
]=color[i<<
1
|
1
]=
1
;
71
color[i]=-
8
;
72
int
mid=(l+r)>>
1
;
73
tree[i<<
1
].mx1=tree[i<<
1
].sum1=mid-l+
1
;
74
tree[i<<
1
].lm1=tree[i<<
1
].rm1=mid-l+
1
;
75
tree[i<<
1
].mx0=tree[i<<
1
].sum0=
0
;
76
tree[i<<
1
].lm0=tree[i<<
1
].rm0=
0
;
77
tree[i<<
1
].lnum=tree[i<<
1
].rnum=
1
;
78
79
tree[i<<
1
|
1
].mx1=tree[i<<
1
|
1
].sum1=r-
mid;
80
tree[i<<
1
|
1
].lm1=tree[i<<
1
|
1
].rm1=r-
mid;
81
tree[i<<
1
|
1
].mx0=tree[i<<
1
|
1
].sum0=
0
;
82
tree[i<<
1
|
1
].lm0=tree[i<<
1
|
1
].rm0=
0
;
83
tree[i<<
1
|
1
].lnum=tree[i<<
1
|
1
].rnum=
1
;
84
}
else
if
(color[i]==
0
)
85
{
86
color[i<<
1
]=color[i<<
1
|
1
]=
0
;
87
color[i]=-
8
;
88
int
mid=(l+r)>>
1
;
89
tree[i<<
1
].mx1=tree[i<<
1
].sum1=
0
;
90
tree[i<<
1
].lm1=tree[i<<
1
].rm1=
0
;
91
tree[i<<
1
].mx0=tree[i<<
1
].sum0=mid-l+
1
;
92
tree[i<<
1
].lm0=tree[i<<
1
].rm0=mid-l+
1
;
93
tree[i<<
1
].lnum=tree[i<<
1
].rnum=
0
;
94
95
tree[i<<
1
|
1
].mx1=tree[i<<
1
|
1
].sum1=
0
;
96
tree[i<<
1
|
1
].lm1=tree[i<<
1
|
1
].rm1=
0
;
97
tree[i<<
1
|
1
].mx0=tree[i<<
1
|
1
].sum0=r-
mid;
98
tree[i<<
1
|
1
].lm0=tree[i<<
1
|
1
].rm0=r-
mid;
99
tree[i<<
1
|
1
].lnum=tree[i<<
1
|
1
].rnum=
0
;
100
}
else
if
(color[i]==
2
)
101
{
102
if
(l<
r){
103
int
mid=(l+r)>>
1
;
104
pushdown(l,mid,i<<
1
);
105
pushdown(mid+
1
,r,i<<
1
|
1
);
106
}
107
color[i<<
1
]=color[i<<
1
|
1
]=
2
;
108
color[i]=-
8
;
109
changes(i<<
1
);
110
changes(i<<
1
|
1
);
111
}
112
}
113
void
build(
int
l=
1
,
int
r=n,
int
i=
1
)
114
{
115
color[i]=-
8
;
116
if
(l==
r)
117
{
118
int
num;
119
scanf(
"
%d
"
,&
num);
120
tree[i].lnum=tree[i].rnum=
num;
121
122
tree[i].sum1=tree[i].mx1=
num;
123
tree[i].lm1=tree[i].rm1=
num;
124
125
tree[i].sum0=tree[i].mx0=!
num;
126
tree[i].lm0=tree[i].rm0=!
num;
127
return
;
128
}
129
int
mid=(l+r)>>
1
;
130
build(lson);
131
build(rson);
132
pushup(l,r,i);
133
}
134
int
query(
int
ql,
int
qr,
int
flg,
int
l=
1
,
int
r=n,
int
i=
1
)
135
{
136
int
ans=
0
;
137
if
(flg==
4
)
138
{
139
int
lsum=
0
,rsum=
0
;
140
if
(ql<=l&&r<=qr)
return
tree[i].mx1;
141
int
mid=(l+r)>>
1
;
142
pushdown(l,r,i);
143
if
(tree[i<<
1
].rnum==
1
&&tree[i<<
1
|
1
].lnum==
1
)
144
{
145
int
lsum,rsum;
146
lsum=min(mid-ql+
1
,tree[i<<
1
].rm1);
147
rsum=min(qr-mid,tree[i<<
1
|
1
].lm1);
148
ans=lsum+
rsum;
149
}
150
if
(ql<=mid) lsum=
query(ql,qr,flg,lson);
151
if
(qr>mid) rsum=
query(ql,qr,flg,rson);
152
ans=
max(ans,lsum);
153
ans=
max(ans,rsum);
154
}
155
else
156
{
157
if
(ql<=l&&r<=qr)
return
tree[i].sum1;
158
int
mid=(l+r)>>
1
;
159
pushdown(l,r,i);
160
if
(ql<=mid) ans+=
query(ql,qr,flg,lson);
161
if
(qr>mid) ans+=
query(ql,qr,flg,rson);
162
}
163
return
ans;
164
}
165
void
update(
int
ql,
int
qr,
int
num,
int
l=
1
,
int
r=n,
int
i=
1
)
166
{
167
if
(ql<=l&&r<=
qr)
168
{
169
if
(num==
1
)
170
{
171
tree[i].mx1=tree[i].sum1=(r-l+
1
);
172
tree[i].lm1=tree[i].rm1=(r-l+
1
);
173
174
tree[i].mx0=tree[i].sum0=
0
;
175
tree[i].lm0=tree[i].rm0=
0
;
176
177
tree[i].lnum=tree[i].rnum=
num;
178
color[i]=
num;
179
}
180
else
if
(num==
0
)
181
{
182
tree[i].mx1=tree[i].sum1=
0
;
183
tree[i].lm1=tree[i].rm1=
0
;
184
185
tree[i].mx0=tree[i].sum0=(r-l+
1
);
186
tree[i].lm0=tree[i].rm0=(r-l+
1
);
187
188
tree[i].lnum=tree[i].rnum=
num;
189
color[i]=
num;
190
}
191
else
if
(num==
2
)
192
{
193
if
(color[i]==
2
)
194
{
195
color[i]=-
8
;
196
}
197
else
198
{
199
if
(l<
r)
200
pushdown(l,r,i);
201
color[i]=
2
;
202
}
203
changes(i);
204
}
205
return
;
206
}
207
pushdown(l,r,i);
208
int
mid=(l+r)>>
1
;
209
if
(ql<=
mid) update(ql,qr,num,lson);
210
if
(qr>
mid) update(ql,qr,num,rson);
211
pushup(l,r,i);
212
}
213
int
main()
214
{
215
int
m,i,t,l,r,f;
216
cin>>
t;
217
while
(t--
)
218
{
219
scanf(
"
%d%d
"
,&n,&
m);
220
build();
221
for
(i=
0
;i<m;i++
)
222
{
223
scanf(
"
%d%d%d
"
,&f,&l,&
r);
224
l++;r++
;
225
if
(f<
3
)
226
{
227
update(l,r,f);
228
}
229
else
230
{
231
int
ans=
query(l,r,f);
232
printf(
"
%d\n
"
,ans);
233
}
234
}
235
}
236
return
0
;
237
}
