首页 > 代码库 > NOI2005维护数列
NOI2005维护数列
1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 6263 Solved: 1879
[Submit][Status]
Description
Input
输入文件的第1行包含两个数N和M，N表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。以下M行，每行一条命令，格式参见问题描述中的表格。
Output
对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。
Sample Input
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
Sample Output
-1
10
1
10
10
1
10
HINT
Source
Splay
【数据规模和约定】
你可以认为在任何时刻，数列中至少有 1 个数。
输入数据一定是正确的，即指定位置的数在数列中一定存在。
50%的数据中，任何时刻数列中最多含有 30 000 个数；
100%的数据中，任何时刻数列中最多含有 500 000 个数。
100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。
100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 个，输入文件
大小不超过 20MBytes。
题解：
原来看起来望而生畏啊，现在看着也不觉得什么。。。
这里面难度最大的操作是：区间修改成某个定值。好像这块我原来在写线段树的时候就没学会。。。
貌似splay的自顶向下的东西全都加到pushdown里面就可以，自底向上的东西全部加到pushup里就可以？
ms是这样的。。。
代码的缩行技巧值得思考，我想了大半天。。。
（ps：其实我觉得这题 1000*500000=50亿是可以爆longint的，所以应该用int64，但既然longint可以过那我就懒得改了
不过考试的话为了保险我还是会用int64de。。。）
代码：
1.hzwer（好整齐的说。。。）
1 #include<cstdio> 2 #include<iostream> 3 #define N 1000005 4 #define inf 1000000000 5 using namespace std; 6 inline int read() 7 { 8 int x=0,f=1;char ch=getchar(); 9 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 10 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 11 return x*f; 12 } 13 int n,m,sz,rt; 14 int fa[N],c[N][2],id[N]; 15 int a[N],lmx[N],rmx[N],mx[N],size[N],rec[N],v[N],sum[N]; 16 bool tag[N],rev[N]; 17 void pushup(int k) 18 { 19 int l=c[k][0],r=c[k][1]; 20 size[k]=size[l]+size[r]+1; 21 sum[k]=sum[l]+sum[r]+v[k]; 22 mx[k]=max(mx[l],mx[r]); 23 mx[k]=max(mx[k],rmx[l]+v[k]+lmx[r]); 24 lmx[k]=max(lmx[l],sum[l]+v[k]+lmx[r]); 25 rmx[k]=max(rmx[r],sum[r]+v[k]+rmx[l]); 26 } 27 void pushdown(int k) 28 { 29 int l=c[k][0],r=c[k][1]; 30 if(tag[k]) 31 { 32 tag[k]=rev[k]=0; 33 if(l){tag[l]=1;v[l]=v[k];sum[l]=v[k]*size[l];} 34 if(r){tag[r]=1;v[r]=v[k];sum[r]=v[k]*size[r];} 35 if(v[k]>=0) 36 { 37 if(l)lmx[l]=rmx[l]=mx[l]=sum[l]; 38 if(r)lmx[r]=rmx[r]=mx[r]=sum[r]; 39 } 40 else 41 { 42 if(l)lmx[l]=rmx[l]=0,mx[l]=v[k]; 43 if(r)lmx[r]=rmx[r]=0,mx[r]=v[k]; 44 } 45 } 46 if(rev[k]) 47 { 48 rev[k]^=1;rev[l]^=1;rev[r]^=1; 49 swap(lmx[l],rmx[l]);swap(lmx[r],rmx[r]); 50 swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]); 51 pushup(k); 52 } 53 } 54 void rotate(int x,int &k) 55 { 56 int y=fa[x],z=fa[y],l,r; 57 if(c[y][0]==x)l=0;else l=1;r=l^1; 58 if(y==k)k=x; 59 else {if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;} 60 fa[c[x][r]]=y;fa[y]=x;fa[x]=z; 61 c[y][l]=c[x][r];c[x][r]=y; 62 pushup(y);pushup(x); 63 } 64 void splay(int x,int &k) 65 { 66 while(x!=k) 67 { 68 int y=fa[x],z=fa[y]; 69 if(y!=k) 70 { 71 if(c[y][0]==x^c[z][0]==y)rotate(x,k); 72 else rotate(y,k); 73 } 74 rotate(x,k); 75 } 76 } 77 void build(int l,int r,int f) 78 { 79 if(l>r)return; 80 int now=id[l],last=id[f]; 81 if(l==r) 82 { 83 v[now]=mx[now]=sum[now]=a[l]; 84 fa[now]=last;size[now]=1; 85 if(a[l]>=0)lmx[now]=rmx[now]=a[l]; 86 else lmx[now]=rmx[now]=0; 87 if(l<f)c[last][0]=now; 88 else c[last][1]=now; 89 return; 90 } 91 int mid=(l+r)>>1;now=id[mid]; 92 build(l,mid-1,mid);build(mid+1,r,mid); 93 v[now]=a[mid];fa[now]=last;pushup(now); 94 if(mid<f)c[last][0]=now; 95 else c[last][1]=now; 96 } 97 int find(int k,int rk) 98 { 99 if(tag[k]||rev[k])pushdown(k);100 int l=c[k][0],r=c[k][1];101 if(size[l]+1==rk)return k;102 else if(size[l]>=rk)return find(l,rk);103 else return find(r,rk-size[l]-1);104 }105 void reclaim(int k)106 {107 if(!k)return;108 int l=c[k][0],r=c[k][1];109 reclaim(l);reclaim(r);110 fa[k]=c[k][0]=c[k][1]=0;111 tag[k]=rev[k]=0;112 rec[++rec[0]]=k;113 }114 void ins(int k,int tot)115 {116 int x,y,z;117 for(int i=1;i<=tot;i++)118 {119 a[i]=read();120 if(rec[0])id[i]=rec[rec[0]--];121 else id[i]=++sz;122 }123 build(1,tot,0);124 z=id[(tot+1)>>1];125 x=find(rt,k+1);y=find(rt,k+2);126 splay(x,rt);splay(y,c[x][1]);127 c[y][0]=z;fa[z]=y;128 pushup(y);pushup(x);129 }130 void dele(int k,int tot)131 {132 int x,y,z;133 x=find(rt,k);y=find(rt,k+tot+1);134 splay(x,rt);splay(y,c[x][1]);135 z=c[y][0];reclaim(z);c[y][0]=0;136 pushup(y);pushup(x);137 }138 void solve_change(int k,int val)139 {140 v[k]=val;tag[k]=1;141 sum[k]=v[k]*size[k];142 if(val>=0)lmx[k]=rmx[k]=mx[k]=sum[k];143 else lmx[k]=rmx[k]=0,mx[k]=v[k];144 }145 void solve_rever(int k)146 {147 if(tag[k])return;148 rev[k]^=1;149 swap(c[k][0],c[k][1]);150 swap(lmx[k],rmx[k]);151 }152 void change(int k,int tot,int val)153 {154 int x,y,z;155 x=find(rt,k);y=find(rt,k+tot+1);156 splay(x,rt);splay(y,c[x][1]);157 z=c[y][0];158 solve_change(z,val);159 pushup(y);pushup(x);160 }161 void rever(int k,int tot)162 {163 int x,y,z;164 x=find(rt,k);y=find(rt,k+tot+1);165 splay(x,rt);splay(y,c[x][1]);166 z=c[y][0];167 solve_rever(z);168 pushup(y);pushup(x);169 }170 void query(int k,int tot)171 {172 int x,y,z;173 x=find(rt,k);y=find(rt,k+tot+1);174 splay(x,rt);splay(y,c[x][1]);175 z=c[y][0];176 printf("%d\n",sum[z]);177 }178 int main()179 {180 n=read();m=read();181 mx[0]=-inf;182 a[1]=a[n+2]=-inf;183 for(int i=1;i<=n;i++)184 a[i+1]=read();185 for(int i=1;i<=n+2;i++)186 id[i]=i;187 build(1,n+2,0);188 rt=(n+3)>>1;sz=n+2;189 char s[10];190 int k,tot,val;191 for(int i=1;i<=m;i++)192 {193 scanf("%s",s);194 switch(s[0])195 {196 case ‘I‘:k=read();tot=read();ins(k,tot);break;197 case ‘D‘:k=read();tot=read();dele(k,tot);break;198 case ‘M‘:199 if(s[2]==‘K‘)200 {k=read();tot=read();val=read();change(k,tot,val);}201 else printf("%d\n",mx[rt]);202 break;203 case ‘R‘:k=read();tot=read();rever(k,tot);break;204 case ‘G‘:k=read();tot=read();query(k,tot);break;205 }206 }207 return 0;208 }
2.mine
1 {$inline on} 2 {$M 1000000000,0,maxlongint} 3 const maxn=500000+1000; 4 var s,sum,v,lm,rm,mx,fa,sta,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,top,rt,now,num:longint; 8 ch:char; 9 procedure swap(var x,y:longint);inline; 10 var t:longint; 11 begin 12 t:=x;x:=y;y:=t; 13 end; 14 function max(x,y:longint):longint;inline; 15 begin 16 if x>y then exit(x) else exit(y); 17 end; 18 procedure pushup(x:longint);inline; 19 var l,r:longint; 20 begin 21 l:=c[x,0];r:=c[x,1]; 22 s[x]:=s[l]+s[r]+1; 23 sum[x]:=sum[l]+sum[r]+v[x]; 24 lm[x]:=max(lm[l],sum[l]+v[x]+lm[r]); 25 rm[x]:=max(rm[r],sum[r]+v[x]+rm[l]); 26 mx[x]:=max(rm[l]+lm[r]+v[x],max(mx[l],mx[r])); 27 end; 28 procedure change(x,y:longint);inline; 29 begin 30 if x=0 then exit; 31 tag[x]:=true; 32 v[x]:=y;sum[x]:=s[x]*y; 33 if v[x]>=0 then 34 begin 35 lm[x]:=sum[x];rm[x]:=sum[x];mx[x]:=sum[x]; 36 end 37 else 38 begin 39 lm[x]:=0;rm[x]:=0;mx[x]:=v[x]; 40 end; 41 end; 42 procedure rever(x:longint);inline; 43 begin 44 if (tag[x]) or (x=0) then exit; 45 rev[x]:=not(rev[x]); 46 swap(c[x,0],c[x,1]); 47 swap(lm[x],rm[x]); 48 end; 49 procedure pushdown(x:longint);inline; 50 var l,r:longint; 51 begin 52 l:=c[x,0];r:=c[x,1]; 53 if tag[x] then 54 begin 55 tag[x]:=false;rev[x]:=false; 56 change(l,v[x]);change(r,v[x]); 57 end; 58 if rev[x] then 59 begin 60 rev[x]:=false; 61 rever(l);rever(r); 62 pushup(x); 63 end; 64 end; 65 procedure rotate(x:longint;var k:longint);inline; 66 var y,z,l,r:longint; 67 begin 68 y:=fa[x];z:=fa[y]; 69 l:=ord(c[y,1]=x);r:=l xor 1; 70 if y=k then k:=x else c[z,ord(c[z,1]=y)]:=x; 71 fa[x]:=z;fa[y]:=x;fa[c[x,r]]:=y; 72 c[y,l]:=c[x,r];c[x,r]:=y; 73 pushup(y);pushup(x); 74 end; 75 procedure splay(x:longint;var k:longint);inline; 76 var y,z:longint; 77 begin 78 while x<>k do 79 begin 80 y:=fa[x];z:=fa[y]; 81 if y<>k then 82 if (c[z,0]=y) xor (c[y,0]=x) then rotate(x,k) 83 else rotate(y,k); 84 rotate(x,k); 85 end; 86 end; 87 function find(x,rank:longint):longint;inline; 88 var l,r:longint; 89 begin 90 if (tag[x]) or (rev[x]) then pushdown(x); 91 l:=c[x,0];r:=c[x,1]; 92 if s[l]+1=rank then exit(x) 93 else if s[l]>=rank then exit(find(l,rank)) 94 else exit(find(r,rank-s[l]-1)); 95 end; 96 procedure build(l,r,f:longint);inline; 97 var x,y,z,mid:longint; 98 begin 99 if l>r then exit;100 mid:=(l+r)>>1;101 x:=id[mid];y:=id[f];102 v[x]:=a[mid];103 c[y,ord(mid>f)]:=x;fa[x]:=y;104 if l=r then105 begin106 s[x]:=1;sum[x]:=v[x];mx[x]:=v[x];107 if v[x]>=0 then z:=v[x] else z:=0;108 lm[x]:=z;rm[x]:=z;109 exit;110 end;111 build(l,mid-1,mid);build(mid+1,r,mid);112 pushup(x);113 end;114 procedure split(l,r:longint;var x,y:longint);inline;115 begin116 x:=find(rt,l);y:=find(rt,r);117 splay(x,rt);splay(y,c[x,1]);118 end;119 procedure insert;inline;120 var i,x,y:longint;121 begin122 for i:=1 to n do123 begin124 read(a[i]);125 id[i]:=sta[top];dec(top);126 end;127 readln;128 build(1,n,0);129 split(now+1,now+2,x,y);130 z:=id[(n+1)>>1];131 c[y,0]:=z;fa[z]:=y;132 pushup(y);pushup(x);133 end;134 procedure delete(x:longint);inline;135 begin136 if x=0 then exit;137 delete(c[x,0]);138 delete(c[x,1]);139 inc(top);140 sta[top]:=x;c[x,0]:=0;c[x,1]:=0;fa[x]:=0;141 rev[x]:=false;tag[x]:=false;142 end;143 procedure main;144 begin145 readln(n,m);146 a[1]:=-10000;a[n+2]:=-10000;mx[0]:=-10000;147 for i:=2 to n+1 do read(a[i]);readln;148 for i:=1 to n+2 do id[i]:=i;149 build(1,n+2,0);rt:=(n+3)>>1;150 for i:=maxn downto n+3 do sta[maxn+1-i]:=i;151 top:=maxn-n-2;152 fillchar(tag,sizeof(tag),false);153 fillchar(rev,sizeof(rev),false);154 for i:=1 to m do155 begin156 read(ch);157 case ch of158 ‘I‘:begin159 while ch<>‘ ‘ do read(ch);160 read(now,n);161 insert;162 end;163 ‘D‘:begin164 while ch<>‘ ‘ do read(ch);165 readln(now,n);166 split(now,now+n+1,x,y);167 delete(c[y,0]);c[y,0]:=0;168 pushup(y);pushup(x);169 end;170 ‘R‘:begin171 while ch<>‘ ‘ do read(ch);172 readln(now,n);173 split(now,now+n+1,x,y);174 rever(c[y,0]);175 pushup(y);pushup(x);176 end;177 ‘M‘:begin178 read(ch);read(ch);179 if ch=‘K‘ then180 begin181 while ch<>‘ ‘ do read(ch);182 readln(now,n,num);183 split(now,now+n+1,x,y);184 change(c[y,0],num);185 pushup(y);pushup(x);186 end187 else188 begin189 readln;190 writeln(mx[rt]);191 end;192 end;193 ‘G‘:begin194 while ch<>‘ ‘ do read(ch);195 readln(now,n);196 split(now,now+n+1,x,y);197 writeln(sum[c[y,0]]);198 end;199 end;200 end;201 end;202 begin203 assign(input,‘input.txt‘);assign(output,‘output.txt‘);204 reset(input);rewrite(output);205 main;206 close(input);close(output);207 end.
吐槽一下：wikioi网又慢，机子又慢，时限还短
vijos网快，机子快，时限长
bzoj网快，机子时快时慢，时限短
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。