1858: [Scoi2010]序列操作
Time Limit: 10 Sec Memory Limit:
64 MB
Submit: 444 Solved: 240
[Submit][Status][Discuss]
Description
lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：0 a b 把[a, b]区间内的所有数全变成01 a b 把[a, b]区间内的所有数全变成12 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成03 a b 询问[a, b]区间内总共有多少个14 a b 询问[a, b]区间内最多有多少个连续的1对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？
Input
输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目 第二行包括n个数，表示序列的初始状态 接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b
Output
对于每一个询问操作，输出一行，包括1个数，表示其对应的答案
Sample Input
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
Sample Output
5
2
6
5
2
6
5
HINT
对于30%的数据，1<=n, m<=1000
对于100%的数据，1<=n, m<=100000
线段树的应用
好久不写普通线段树了，写了竟然wa了……
program bzoj1858;
type
group=record
max,maxl,maxr:longint;
end;
var
a,b,o,tot,n,m,i,j,k:longint;
stop,sum,left,right,maxl1,maxr1,max1,maxl0,maxr0,max0:array [0..200001] of longint;
procedure swap (var a,b:longint);inline;
begin
if a=b then exit;
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;
function max (a,b:longint):longint;inline;
begin
if a>b then exit(a) else exit(b);
end;
procedure build (s,e,now:longint);
var
mid:longint;
begin
stop[now]:=-1;
maxl0[now]:=e-s+1;
maxr0[now]:=e-s+1;
max0[now]:=e-s+1;
if s=e then exit;
mid:=(s+e) div 2;
inc(tot);
left[now]:=tot;
build(s,mid,tot);
inc(tot);
right[now]:=tot;
build(mid+1,e,tot);
end;
procedure quick (o,l,r,now:longint);
begin
case o of
0:
begin
sum[now]:=0;
maxl0[now]:=r-l+1;
maxr0[now]:=r-l+1;
max0[now]:=r-l+1;
maxl1[now]:=0;
maxr1[now]:=0;
max1[now]:=0;
stop[now]:=0;
end;
1:
begin
sum[now]:=r-l+1;
maxl0[now]:=0;
maxr0[now]:=0;
max0[now]:=0;
maxl1[now]:=r-l+1;
maxr1[now]:=r-l+1;
max1[now]:=r-l+1;
stop[now]:=1;
end;
2:
begin
sum[now]:=r-l+1-sum[now];
swap(maxl0[now],maxl1[now]);
swap(maxr0[now],maxr1[now]);
swap(max0[now],max1[now]);
case stop[now] of
-1:stop[now]:=2;
0:stop[now]:=1;
1:stop[now]:=0;
2:stop[now]:=-1;
end;
end;
end;
end;
procedure update (l,r,now:longint);
var
mid:longint;
begin
if stop[now]=-1 then exit;
mid:=(l+r) div 2;
quick(stop[now],l,mid,left[now]);
quick(stop[now],mid+1,r,right[now]);
stop[now]:=-1;
end;
procedure fill (o,s,e,l,r,now:longint);
var
mid:longint;
begin
if (s=l)and(e=r) then
begin
quick(o,l,r,now);
exit;
end;
update(l,r,now);
mid:=(l+r) div 2;
if e<=mid then fill(o,s,e,l,mid,left[now])
else
if s>mid then fill(o,s,e,mid+1,r,right[now])
else
begin
fill(o,s,mid,l,mid,left[now]);
fill(o,mid+1,e,mid+1,r,right[now]);
end;
sum[now]:=sum[left[now]]+sum[right[now]];
if maxl0[left[now]]=mid-l+1 then maxl0[now]:=maxl0[left[now]]+maxl0[right[now]]
else maxl0[now]:=maxl0[left[now]];
if maxr0[right[now]]=r-mid then maxr0[now]:=maxr0[right[now]]+maxr0[left[now]]
else maxr0[now]:=maxr0[right[now]];
max0[now]:=max0[left[now]];
if max0[now]<max0[right[now]] then max0[now]:=max0[right[now]];
if max0[now]<maxr0[left[now]]+maxl0[right[now]] then max0[now]:=maxr0[left[now]]+maxl0[right[now]];
if maxl1[left[now]]=mid-l+1 then maxl1[now]:=maxl1[left[now]]+maxl1[right[now]]
else maxl1[now]:=maxl1[left[now]];
if maxr1[right[now]]=r-mid then maxr1[now]:=maxr1[right[now]]+maxr1[left[now]]
else maxr1[now]:=maxr1[right[now]];
max1[now]:=max1[left[now]];
if max1[now]<max1[right[now]] then max1[now]:=max1[right[now]];
if max1[now]<maxr1[left[now]]+maxl1[right[now]] then max1[now]:=maxr1[left[now]]+maxl1[right[now]];
end;
function qsum (s,e,l,r,now:longint):longint;
var
mid:longint;
begin
if (s=l)and(e=r) then exit(sum[now]);
update(l,r,now);
mid:=(l+r) div 2;
if e<=mid then exit(qsum(s,e,l,mid,left[now]))
else
if s>mid then exit(qsum(s,e,mid+1,r,right[now]))
else exit(qsum(s,mid,l,mid,left[now])+qsum(mid+1,e,mid+1,r,right[now]));
end;
function find (s,e,l,r,now:longint):group;
var
mid:longint;
ans,q,p:group;
begin
if (s=l)and(e=r) then
begin
ans.max:=max1[now];
ans.maxl:=maxl1[now];
ans.maxr:=maxr1[now];
exit(ans);
end;
update(l,r,now);
mid:=(l+r) div 2;
if e<=mid then exit(find(s,e,l,mid,left[now]))
else
if s>mid then exit(find(s,e,mid+1,r,right[now]))
else
begin
q:=find(s,mid,l,mid,left[now]);
p:=find(mid+1,e,mid+1,r,right[now]);
ans.max:=max(max(q.max,p.max),q.maxr+p.maxl);
if q.maxl=mid-s+1 then ans.maxl:=q.maxl+p.maxl
else ans.maxl:=q.maxl;
if p.maxr=e-mid then ans.maxr:=p.maxr+q.maxr
else ans.maxr:=p.maxr;
exit(ans);
end;
end;
begin
read(n,m);
build(1,n,0);
for i:=1 to n do
begin
read(k);
fill(k,i,i,1,n,0);
end;
for i:=1 to m do
begin
read(o,a,b);
inc(a);
inc(b);
case o of
0:fill(0,a,b,1,n,0);
1:fill(1,a,b,1,n,0);
2:fill(2,a,b,1,n,0);
3:writeln(qsum(a,b,1,n,0));
4:writeln(find(a,b,1,n,0).max);
end;
end;
end.