NOI2005维护数列

1500: [NOI2005]维修数列

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 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

Sample Output

-1
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
",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
",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 }

View Code

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 then
105     begin
106      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  begin
116   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  begin
122  for i:=1 to n do
123    begin
124     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  begin
136  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  begin
145   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 do
155    begin
156     read(ch);
157     case ch of
158     'I':begin
159         while ch<>' ' do read(ch);
160         read(now,n);
161         insert;
162         end;
163     'D':begin
164         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':begin
171         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':begin
178         read(ch);read(ch);
179         if ch='K' then
180          begin
181           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          end
187         else
188          begin
189           readln;
190           writeln(mx[rt]);
191          end;
192         end;
193     'G':begin
194         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 begin
203   assign(input,'input.txt');assign(output,'output.txt');
204   reset(input);rewrite(output);
205   main;
206   close(input);close(output);
207 end.

View Code

吐槽一下：wikioi网又慢，机子又慢，时限还短

vijos网快，机子快，时限长

bzoj网快，机子时快时慢，时限短