1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 11047 Solved: 3460
[Submit][Status][Discuss]
Description
Input
输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。
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
Solution
splay模板题，exciting
插入和删除一个序列，有种方便快捷的方法
进行两次伸展，一次伸展到根，一次伸展到右子树上，这样会可以使得左子树空缺或需要删除是左子树
那么直接插入一整棵树到左子树，或者删除整个左子树即可
那么给定的序列，可以利用 线段树类似的build技巧，将其建成一个完美的二叉树，然后直接加入
BZOJ卡内存，所以删除的时候需要垃圾回收
具体的方法就是 使用一个队列，记录扔掉的点的编号，加入新东西时，先从队列中取编号，再建新编号即可
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
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;
}
#define maxn 1000100
queue<int>trashpool;
int n,m,cnt;
int fa[maxn],son[maxn][],key[maxn],size[maxn],sum[maxn],val[maxn],maxz[maxn],ll[maxn],rr[maxn],id[maxn];
bool rev[maxn],tag[maxn];
int sz,root;
void update(int now)
{
//if (!now) return;
size[now]=size[son[now][]]+size[son[now][]]+;
sum[now]=val[now]+sum[son[now][]]+sum[son[now][]];
maxz[now]=max(maxz[son[now][]],maxz[son[now][]]);
maxz[now]=max(maxz[now],rr[son[now][]]+val[now]+ll[son[now][]]);
ll[now]=max(ll[son[now][]],sum[son[now][]]+val[now]+ll[son[now][]]);
rr[now]=max(rr[son[now][]],sum[son[now][]]+val[now]+rr[son[now][]]);
}
void pushdown(int now)
{
int tg=tag[now],rv=rev[now];
if (tag[now])
{
tag[now]=; rev[now]=;
if (son[now][])
tag[son[now][]]=,val[son[now][]]=val[now],sum[son[now][]]=size[son[now][]]*val[now];
if (son[now][])
tag[son[now][]]=,val[son[now][]]=val[now],sum[son[now][]]=size[son[now][]]*val[now];
if(val[now]>=)
{
if(son[now][]) ll[son[now][]]=rr[son[now][]]=maxz[son[now][]]=sum[son[now][]];
if(son[now][]) ll[son[now][]]=rr[son[now][]]=maxz[son[now][]]=sum[son[now][]];
}
else
{
if(son[now][]) ll[son[now][]]=rr[son[now][]]=,maxz[son[now][]]=val[now];
if(son[now][]) ll[son[now][]]=rr[son[now][]]=,maxz[son[now][]]=val[now];
}
return;//
}
if (rev[now])
{
rev[now]^=; rev[son[now][]]^=; rev[son[now][]]^=;
swap(ll[son[now][]],rr[son[now][]]); swap(ll[son[now][]],rr[son[now][]]);
swap(son[son[now][]][],son[son[now][]][]); swap(son[son[now][]][],son[son[now][]][]);
}
}
void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l,r;
l=(son[y][]==x); r=l^;
if(y==k) k=x;
else son[z][son[z][]==y]=x;
fa[son[x][r]]=y; fa[y]=x;fa[x]=z;
son[y][l]=son[x][r]; son[x][r]=y;
update(y); update(x);
}
void splay(int x,int &k)
{
while(x!=k)
{
//printf("%d %d\n",x,k);
int y=fa[x],z=fa[y];
if(y!=k)
{
if(son[y][]==x^son[z][]==y)rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int findkth(int x,int rk)
{
pushdown(x);
int l=son[x][],r=son[x][];
if(size[l]+==rk) return x;
if(size[l]>=rk) return findkth(l,rk);
return findkth(r,rk-size[l]-);
}
void trash(int now)
{
if (!now) return;
trash(son[now][]),trash(son[now][]); trashpool.push(now);
fa[now]=son[now][]=son[now][]=tag[now]=rev[now]=;
}
int split(int pos,int tot)
{
int x=findkth(root,pos),y=findkth(root,pos+tot+);
splay(x,root);splay(y,son[x][]);
return son[y][];
}
void asksum(int pos,int tot)
{printf("%d\n",sum[split(pos,tot)]);}
void change(int pos,int tot,int va)
{
int x=split(pos,tot),y=fa[x];
val[x]=va; tag[x]=; sum[x]=size[x]*va;
if(va>=) ll[x]=rr[x]=maxz[x]=sum[x];
else ll[x]=rr[x]=,maxz[x]=va;
update(y); update(fa[y]);
}
void cover(int pos,int tot)
{
int x=split(pos,tot),y=fa[x];
if(!tag[x])
{
rev[x]^=;
swap(son[x][],son[x][]);swap(ll[x],rr[x]);
update(y); update(fa[y]);
}
}
void remove(int pos,int tot)
{
int x=split(pos,tot),y=fa[x];
trash(x); son[y][]=;
update(y); update(fa[y]);
}
void build(int l,int r,int father)
{
if(l>r) return;
int mid=(l+r)>>,now=id[mid],last=id[father];
if(l==r)
{
sum[now]=key[l]; size[now]=;
tag[now]=rev[now]=;
if(key[l]>=) ll[now]=rr[now]=maxz[now]=key[l];
else ll[now]=rr[now]=,maxz[now]=key[l];
// return;
}
else build(l,mid-,mid),build(mid+,r,mid);
val[now]=key[mid]; fa[now]=last; update(now);
son[last][mid>=father]=now;
}
void insert(int pos,int tot)
{
for (int i=; i<=tot; i++) key[i]=read();
for (int i=; i<=tot; i++)
if (!trashpool.empty()) id[i]=trashpool.front(),trashpool.pop(); else id[i]=++cnt;
build(,tot,); int mid=(+tot)>>;
int x=findkth(root,pos+),y=findkth(root,pos+),z=id[mid];
splay(x,root);splay(y,son[x][]);
fa[z]=y; son[y][]=z;
update(y); update(x);
} #define sb -100000000
int main()
{
n=read();m=read();
maxz[]=key[]=key[n+]=sb;
for (int i=; i<=n; i++) key[i+]=read();
for (int i=; i<=n+; i++) id[i]=i;
root=(n+)>>; cnt=n+;
build(,n+,);
char opt[];
while (m--)
{
scanf("%s",opt);int pos,tot,va;
switch (opt[])
{
case 'S': pos=read(),tot=read();insert(pos,tot); break;
case 'L': pos=read(),tot=read();remove(pos,tot); break;
case 'K': pos=read(),tot=read(),va=read(); change(pos,tot,va); break;
case 'V': pos=read(),tot=read();cover(pos,tot); break;
case 'T': pos=read(),tot=read();asksum(pos,tot); break;
case 'X': printf("%d\n",maxz[root]); break;
}
//for (int i=1; i<=n+1; i++) printf("%d ",val[i]);puts("");
//puts("---------------------------------------------------------------------");
}
return ;
}
真的是模板题，传说中NOI最难数据结构题？？逗我？也就写了好几个小时罢了QAQ
一开始电脑爆炸，每次处理标记，n都会变化..自己瞎搞1h30min后，问char哥，char哥说，你的xx数组爆了，因为内存空间是连续的，所以波及了n...
然后30min后，电脑爆炸，于是强行考程序换YveH自带的笔记本，于是发现2h处理了电脑的智障问题....
然后发现很多问题...
such as：Splay死循啊，pushdown蛋疼啊，垃圾回收废物利用编号出毛病啊.....
以后有学弟找我要Splay模板题，不说啥了，就这道！！！