首页 > 代码库 > BZOJ1858: [Scoi2010]序列操作
BZOJ1858: [Scoi2010]序列操作
1858: [Scoi2010]序列操作
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1068 Solved: 545
[Submit][Status]
Description
lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 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 对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？
Input
输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目 第二行包括n个数，表示序列的初始状态 接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b<n）表示对于区间[a, b]执行标号为op的操作="" <="" div="">
View Code
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
Source
Day2
这题的区间合并实在太恶心了，写完我都快吐了。。。那天过来再调吧。。。
代码：
1 {$inline on} 2 {$M 1000000000,0,maxlongint} 3 const maxn=100000+1000; 4 var s,sum1,sum0,v,lx0,rx0,lx1,rx1,mx0,mx1,fa,id,a:array[0..maxn] of longint; 5 rev,tag:array[0..maxn] of boolean; 6 c:array[0..maxn,0..1] of longint; 7 i,n,m,x,y,z,rt,ch,ll,rr:longint; 8 procedure swap(var x,y:longint);inline; 9 var t:longint; 10 begin 11 t:=x;x:=y;y:=t; 12 end; 13 function max(x,y:longint):longint;inline; 14 begin 15 if x>y then exit(x) else exit(y); 16 end; 17 procedure pushup(x:longint); 18 var l,r:longint; 19 begin 20 l:=c[x,0];r:=c[x,1]; 21 s[x]:=s[l]+s[r]+1; 22 sum1[x]:=sum1[l]+sum1[r]+ord(v[x]=1); 23 sum0[x]:=sum0[l]+sum0[r]+ord(v[x]=0); 24 if lx0[l]=s[l] then 25 begin 26 if v[x]=0 then lx0[x]:=s[l]+1+lx0[r] 27 else lx0[x]:=s[l]; 28 end 29 else lx0[x]:=lx0[l]; 30 if rx0[r]=s[r] then 31 begin 32 if v[x]=0 then rx0[x]:=s[r]+1+rx0[l] 33 else rx0[x]:=s[r]; 34 end; 35 if lx1[l]=s[l] then 36 begin 37 if v[x]=1 then lx1[x]:=s[l]+1+lx1[r] 38 else lx1[x]:=s[l]; 39 end 40 else lx1[x]:=lx1[l]; 41 if rx1[r]=s[r] then 42 begin 43 if v[x]=1 then rx1[x]:=s[r]+1+rx1[l] 44 else rx1[x]:=s[r]; 45 end; 46 mx0[x]:=max(mx0[l],mx0[r]); 47 if v[x]=0 then mx0[x]:=max(mx0[x],rx0[l]+lx0[r]+1); 48 mx1[x]:=max(mx1[l],mx1[r]); 49 if v[x]=1 then mx1[x]:=max(mx1[x],rx1[l]+lx1[r]+1); 50 end; 51 procedure rotate(x:longint;var k:longint); 52 var y,z,l,r:longint; 53 begin 54 y:=fa[x];z:=fa[y]; 55 l:=ord(c[y,1]=x);r:=l xor 1; 56 if y=k then k:=x else c[z,ord(c[z,1]=y)]:=x; 57 fa[x]:=z;fa[y]:=x;fa[c[x,r]]:=y; 58 c[y,l]:=c[x,r];c[x,r]:=y; 59 pushup(y);pushup(x); 60 end; 61 procedure splay(x:longint;var k:longint); 62 var y,z:longint; 63 begin 64 while x<>k do 65 begin 66 y:=fa[x];z:=fa[y]; 67 if y<>k then 68 if (c[z,0]=y) xor (c[y,0]=x) then rotate(x,k) 69 else rotate(y,k); 70 rotate(x,k); 71 end; 72 end; 73 74 75 procedure build(l,r,f:longint); 76 var mid,x,y:longint; 77 begin 78 if l>r then exit; 79 mid:=(l+r)>>1; 80 x:=id[mid];y:=id[f]; 81 c[y,ord(mid>f)]:=x;fa[x]:=y; 82 v[x]:=a[mid]; 83 if l=r then 84 begin 85 s[x]:=1;sum0[x]:=ord(v[x]=0);sum1[x]:=ord(v[x]=1); 86 lx0:=sum0;rx0:=sum0;mx0:=sum0; 87 lx1:=sum1;rx1:=sum1;mx1:=sum1; 88 exit; 89 end; 90 build(l,mid-1,mid);build(mid+1,r,mid); 91 pushup(x); 92 end; 93 procedure init; 94 begin 95 readln(n,m); 96 a[1]:=-1;a[n+2]:=-1; 97 for i:=2 to n+1 do read(a[i]);readln; 98 for i:=1 to n+2 do id[i]:=i; 99 build(1,n+2,0);rt:=(n+3)>>1;100 end;101 procedure same0(x:longint);102 begin103 tag[x]:=true;v[x]:=0;104 sum0[x]:=s[x];lx0[x]:=s[x];rx0[x]:=s[x];mx0[x]:=s[x];105 sum1[x]:=0;lx1[x]:=0;rx1[x]:=0;mx1[x]:=0;106 end;107 procedure same1(x:longint);108 begin109 tag[x]:=true;v[x]:=1;110 sum1[x]:=s[x];lx1[x]:=s[x];rx1[x]:=s[x];mx1[x]:=s[x];111 sum0[x]:=0;lx0[x]:=0;rx0[x]:=0;mx0[x]:=0;112 end;113 procedure rever(x:longint);114 begin115 if (x=0) or (tag[x]) then exit;116 rev[x]:=not(rev[x]);v[x]:=v[x] xor 1;117 swap(lx0[x],lx1[x]);118 swap(rx0[x],rx1[x]);119 swap(sum0[x],sum1[x]);120 swap(mx0[x],mx1[x]);121 end;122 procedure pushdown(x:longint);123 var l,r:longint;124 begin125 l:=c[x,0];r:=c[x,1];126 if tag[x] then127 begin128 tag[x]:=false;rev[x]:=false;129 if v[x]=0 then begin same0(l);same0(r);end130 else begin same1(l);same1(r);end;131 end;132 if rev[x] then133 begin134 rev[x]:=false;135 rever(l);rever(r);136 pushup(x);137 end;138 end;139 140 function find(x,rk:longint):longint;141 var l,r:longint;142 begin143 pushdown(x);l:=c[x,0];r:=c[x,1];144 if s[l]+1=rk then exit(x)145 else if s[l]>=rk then exit(find(l,rk))146 else exit(find(r,rk-s[l]-1));147 end;148 149 procedure split(l,r:longint;var x,y:longint);150 begin151 x:=find(rt,l);y:=find(rt,r);152 splay(x,rt);splay(y,c[x,1]);153 end;154 procedure main;155 begin156 for i:=1 to m do157 begin158 readln(ch,ll,rr);inc(ch);inc(ll,1);inc(rr,3);159 split(ll,rr,x,y);160 case ch of161 1:same0(c[y,0]);162 2:same1(c[y,0]);163 3:rever(c[y,0]);164 4:writeln(sum1[c[y,0]]);165 5:writeln(mx1[c[y,0]]);166 end;167 end;168 end;169 begin170 assign(input,‘input.txt‘);assign(output,‘output.txt‘);171 reset(input);rewrite(output);172 init;173 main;174 close(input);close(output);175 end.176
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。