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
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
【数据规模和约定】
你可以认为在任何时刻，数列中至少有 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（好整齐的说。。。）
#include<cstdio>
#include<iostream>
#define N 1000005
#define inf 1000000000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,sz,rt;
int fa[N],c[N][],id[N];
int a[N],lmx[N],rmx[N],mx[N],size[N],rec[N],v[N],sum[N];
bool tag[N],rev[N];
void pushup(int k)
{
int l=c[k][],r=c[k][];
size[k]=size[l]+size[r]+;
sum[k]=sum[l]+sum[r]+v[k];
mx[k]=max(mx[l],mx[r]);
mx[k]=max(mx[k],rmx[l]+v[k]+lmx[r]);
lmx[k]=max(lmx[l],sum[l]+v[k]+lmx[r]);
rmx[k]=max(rmx[r],sum[r]+v[k]+rmx[l]);
}
void pushdown(int k)
{
int l=c[k][],r=c[k][];
if(tag[k])
{
tag[k]=rev[k]=;
if(l){tag[l]=;v[l]=v[k];sum[l]=v[k]*size[l];}
if(r){tag[r]=;v[r]=v[k];sum[r]=v[k]*size[r];}
if(v[k]>=)
{
if(l)lmx[l]=rmx[l]=mx[l]=sum[l];
if(r)lmx[r]=rmx[r]=mx[r]=sum[r];
}
else
{
if(l)lmx[l]=rmx[l]=,mx[l]=v[k];
if(r)lmx[r]=rmx[r]=,mx[r]=v[k];
}
}
if(rev[k])
{
rev[k]^=;rev[l]^=;rev[r]^=;
swap(lmx[l],rmx[l]);swap(lmx[r],rmx[r]);
swap(c[l][],c[l][]);swap(c[r][],c[r][]);
pushup(k);
}
}
void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l,r;
if(c[y][]==x)l=;else l=;r=l^;
if(y==k)k=x;
else {if(c[z][]==y)c[z][]=x;else c[z][]=x;}
fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
c[y][l]=c[x][r];c[x][r]=y;
pushup(y);pushup(x);
}
void splay(int x,int &k)
{
while(x!=k)
{
int y=fa[x],z=fa[y];
if(y!=k)
{
if(c[y][]==x^c[z][]==y)rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
void build(int l,int r,int f)
{
if(l>r)return;
int now=id[l],last=id[f];
if(l==r)
{
v[now]=mx[now]=sum[now]=a[l];
fa[now]=last;size[now]=;
if(a[l]>=)lmx[now]=rmx[now]=a[l];
else lmx[now]=rmx[now]=;
if(l<f)c[last][]=now;
else c[last][]=now;
return;
}
int mid=(l+r)>>;now=id[mid];
build(l,mid-,mid);build(mid+,r,mid);
v[now]=a[mid];fa[now]=last;pushup(now);
if(mid<f)c[last][]=now;
else c[last][]=now;
}
int find(int k,int rk)
{
if(tag[k]||rev[k])pushdown(k);
int l=c[k][],r=c[k][];
if(size[l]+==rk)return k;
else if(size[l]>=rk)return find(l,rk);
else return find(r,rk-size[l]-);
}
void reclaim(int k)
{
if(!k)return;
int l=c[k][],r=c[k][];
reclaim(l);reclaim(r);
fa[k]=c[k][]=c[k][]=;
tag[k]=rev[k]=;
rec[++rec[]]=k;
}
void ins(int k,int tot)
{
int x,y,z;
for(int i=;i<=tot;i++)
{
a[i]=read();
if(rec[])id[i]=rec[rec[]--];
else id[i]=++sz;
}
build(,tot,);
z=id[(tot+)>>];
x=find(rt,k+);y=find(rt,k+);
splay(x,rt);splay(y,c[x][]);
c[y][]=z;fa[z]=y;
pushup(y);pushup(x);
}
void dele(int k,int tot)
{
int x,y,z;
x=find(rt,k);y=find(rt,k+tot+);
splay(x,rt);splay(y,c[x][]);
z=c[y][];reclaim(z);c[y][]=;
pushup(y);pushup(x);
}
void solve_change(int k,int val)
{
v[k]=val;tag[k]=;
sum[k]=v[k]*size[k];
if(val>=)lmx[k]=rmx[k]=mx[k]=sum[k];
else lmx[k]=rmx[k]=,mx[k]=v[k];
}
void solve_rever(int k)
{
if(tag[k])return;
rev[k]^=;
swap(c[k][],c[k][]);
swap(lmx[k],rmx[k]);
}
void change(int k,int tot,int val)
{
int x,y,z;
x=find(rt,k);y=find(rt,k+tot+);
splay(x,rt);splay(y,c[x][]);
z=c[y][];
solve_change(z,val);
pushup(y);pushup(x);
}
void rever(int k,int tot)
{
int x,y,z;
x=find(rt,k);y=find(rt,k+tot+);
splay(x,rt);splay(y,c[x][]);
z=c[y][];
solve_rever(z);
pushup(y);pushup(x);
}
void query(int k,int tot)
{
int x,y,z;
x=find(rt,k);y=find(rt,k+tot+);
splay(x,rt);splay(y,c[x][]);
z=c[y][];
printf("%d\n",sum[z]);
}
int main()
{
n=read();m=read();
mx[]=-inf;
a[]=a[n+]=-inf;
for(int i=;i<=n;i++)
a[i+]=read();
for(int i=;i<=n+;i++)
id[i]=i;
build(,n+,);
rt=(n+)>>;sz=n+;
char s[];
int k,tot,val;
for(int i=;i<=m;i++)
{
scanf("%s",s);
switch(s[])
{
case 'I':k=read();tot=read();ins(k,tot);break;
case 'D':k=read();tot=read();dele(k,tot);break;
case 'M':
if(s[]=='K')
{k=read();tot=read();val=read();change(k,tot,val);}
else printf("%d\n",mx[rt]);
break;
case 'R':k=read();tot=read();rever(k,tot);break;
case 'G':k=read();tot=read();query(k,tot);break;
}
}
return ;
}
2.mine
{$inline on}
{$M 1000000000,0,maxlongint}
const maxn=+;
var s,sum,v,lm,rm,mx,fa,sta,id,a:array[..maxn] of longint;
rev,tag:array[..maxn] of boolean;
c:array[..maxn,..] of longint;
i,n,m,x,y,z,top,rt,now,num:longint;
ch:char;
procedure swap(var x,y:longint);inline;
var t:longint;
begin
t:=x;x:=y;y:=t;
end;
function max(x,y:longint):longint;inline;
begin
if x>y then exit(x) else exit(y);
end;
procedure pushup(x:longint);inline;
var l,r:longint;
begin
l:=c[x,];r:=c[x,];
s[x]:=s[l]+s[r]+;
sum[x]:=sum[l]+sum[r]+v[x];
lm[x]:=max(lm[l],sum[l]+v[x]+lm[r]);
rm[x]:=max(rm[r],sum[r]+v[x]+rm[l]);
mx[x]:=max(rm[l]+lm[r]+v[x],max(mx[l],mx[r]));
end;
procedure change(x,y:longint);inline;
begin
if x= then exit;
tag[x]:=true;
v[x]:=y;sum[x]:=s[x]*y;
if v[x]>= then
begin
lm[x]:=sum[x];rm[x]:=sum[x];mx[x]:=sum[x];
end
else
begin
lm[x]:=;rm[x]:=;mx[x]:=v[x];
end;
end;
procedure rever(x:longint);inline;
begin
if (tag[x]) or (x=) then exit;
rev[x]:=not(rev[x]);
swap(c[x,],c[x,]);
swap(lm[x],rm[x]);
end;
procedure pushdown(x:longint);inline;
var l,r:longint;
begin
l:=c[x,];r:=c[x,];
if tag[x] then
begin
tag[x]:=false;rev[x]:=false;
change(l,v[x]);change(r,v[x]);
end;
if rev[x] then
begin
rev[x]:=false;
rever(l);rever(r);
pushup(x);
end;
end;
procedure rotate(x:longint;var k:longint);inline;
var y,z,l,r:longint;
begin
y:=fa[x];z:=fa[y];
l:=ord(c[y,]=x);r:=l xor ;
if y=k then k:=x else c[z,ord(c[z,]=y)]:=x;
fa[x]:=z;fa[y]:=x;fa[c[x,r]]:=y;
c[y,l]:=c[x,r];c[x,r]:=y;
pushup(y);pushup(x);
end;
procedure splay(x:longint;var k:longint);inline;
var y,z:longint;
begin
while x<>k do
begin
y:=fa[x];z:=fa[y];
if y<>k then
if (c[z,]=y) xor (c[y,]=x) then rotate(x,k)
else rotate(y,k);
rotate(x,k);
end;
end;
function find(x,rank:longint):longint;inline;
var l,r:longint;
begin
if (tag[x]) or (rev[x]) then pushdown(x);
l:=c[x,];r:=c[x,];
if s[l]+=rank then exit(x)
else if s[l]>=rank then exit(find(l,rank))
else exit(find(r,rank-s[l]-));
end;
procedure build(l,r,f:longint);inline;
var x,y,z,mid:longint;
begin
if l>r then exit;
mid:=(l+r)>>;
x:=id[mid];y:=id[f];
v[x]:=a[mid];
c[y,ord(mid>f)]:=x;fa[x]:=y;
if l=r then
begin
s[x]:=;sum[x]:=v[x];mx[x]:=v[x];
if v[x]>= then z:=v[x] else z:=;
lm[x]:=z;rm[x]:=z;
exit;
end;
build(l,mid-,mid);build(mid+,r,mid);
pushup(x);
end;
procedure split(l,r:longint;var x,y:longint);inline;
begin
x:=find(rt,l);y:=find(rt,r);
splay(x,rt);splay(y,c[x,]);
end;
procedure insert;inline;
var i,x,y:longint;
begin
for i:= to n do
begin
read(a[i]);
id[i]:=sta[top];dec(top);
end;
readln;
build(,n,);
split(now+,now+,x,y);
z:=id[(n+)>>];
c[y,]:=z;fa[z]:=y;
pushup(y);pushup(x);
end;
procedure delete(x:longint);inline;
begin
if x= then exit;
delete(c[x,]);
delete(c[x,]);
inc(top);
sta[top]:=x;c[x,]:=;c[x,]:=;fa[x]:=;
rev[x]:=false;tag[x]:=false;
end;
procedure main;
begin
readln(n,m);
a[]:=-;a[n+]:=-;mx[]:=-;
for i:= to n+ do read(a[i]);readln;
for i:= to n+ do id[i]:=i;
build(,n+,);rt:=(n+)>>;
for i:=maxn downto n+ do sta[maxn+-i]:=i;
top:=maxn-n-;
fillchar(tag,sizeof(tag),false);
fillchar(rev,sizeof(rev),false);
for i:= to m do
begin
read(ch);
case ch of
'I':begin
while ch<>' ' do read(ch);
read(now,n);
insert;
end;
'D':begin
while ch<>' ' do read(ch);
readln(now,n);
split(now,now+n+,x,y);
delete(c[y,]);c[y,]:=;
pushup(y);pushup(x);
end;
'R':begin
while ch<>' ' do read(ch);
readln(now,n);
split(now,now+n+,x,y);
rever(c[y,]);
pushup(y);pushup(x);
end;
'M':begin
read(ch);read(ch);
if ch='K' then
begin
while ch<>' ' do read(ch);
readln(now,n,num);
split(now,now+n+,x,y);
change(c[y,],num);
pushup(y);pushup(x);
end
else
begin
readln;
writeln(mx[rt]);
end;
end;
'G':begin
while ch<>' ' do read(ch);
readln(now,n);
split(now,now+n+,x,y);
writeln(sum[c[y,]]);
end;
end;
end;
end;
begin
assign(input,'input.txt');assign(output,'output.txt');
reset(input);rewrite(output);
main;
close(input);close(output);
end.
吐槽一下：wikioi网又慢，机子又慢，时限还短
vijos网快，机子快，时限长
bzoj网快，机子时快时慢，时限短