3678: wangxz与OJ
Time Limit: 10 Sec Memory Limit: 128 MB
http://www.lydsy.com/JudgeOnline/problem.php?id=3678
Description
某天，wangxz神犇来到了一个信息学在线评测系统(Online Judge)。由于他是一位哲♂学的神犇，所以他不打算做题。他发现这些题
目呈线性排列，被标记为1~n号，每道题都有一个难度值(可以<=0)。他决定与这些题目玩♂耍。
1、他可以在某个位置插♂入一些难度值特定的题目。
2、他可以吃♂掉(删除)一段题目。
3、他可以查询某个位置的题目的难度值。
维护一个初始有n个元素的序列(标记为1~n号元素)，支持以下操作：
0 p a b (0<=p<=当前序列元素个数) (a<=b) 在p位置和p+1位置之间插入整数:a,a+1,a+2,...,b-1,b。若p为0，插在序列最前面;
1 a b (1<=a<=b<=当前序列元素个数) 删除a,a+1,a+2,...,b-1,b位置的元素;
2 p (1<=p<=当前序列元素个数) 查询p位置的元素。
Input
输入第一行包括两个正整数n(1<=n<=20000),m(1<=m<=20000),代表初始序列元素个数和操作个数。
接下来n个整数,为初始序列元素。
接下来m行,每行第一个为整数sym,
若sym=0,接下来有一个非负整数p,两个整数a,b;
若sym=1,接下来有两个正整数a,b;
若sym=2,接下来有一个正整数p;
p、x、y的含义及范围见题目描述。
在任何情况下，保证序列中的元素总数不超过100000。
保证题目涉及的所有数在int内。
Output
对每个sym=2，输出一行，包括一个整数，代表询问位置的元素。
Sample Input
5 3
1 2 3 4 5
0 2 1 4
1 3 8
2 2
1 2 3 4 5
0 2 1 4
1 3 8
2 2
Sample Output
2
插入时插一个大节点，使用到他时分裂节点
大节点发现是公差为1的等差数列，所以记录首项、末项即可
#include<cstdio>
#define N 20001
using namespace std;
int n,m,tot,t1,t2,root;
int key[N*][],siz[N*],ch[N*][],fa[N*];
int read()
{
int x=,f=; char c=getchar();
while(c<''||c>'') { if(c=='-') f=-; c=getchar(); }
while(c>=''&&c<='') { x=x*+c-''; c=getchar(); }
return x*f;
}
struct SPLAY_TREE
{
void update(int k)
{
siz[k]=key[k][]-key[k][]+;
if(ch[k][]) siz[k]+=siz[ch[k][]];
if(ch[k][]) siz[k]+=siz[ch[k][]];
}
void build(int l,int r,int f)
{
if(l>r) return;
int mid=l+r>>;
siz[mid]=; fa[mid]=f; ch[f][mid>f]=mid;
build(l,mid-,mid);
build(mid+,r,mid);
update(mid);
}
void rotate(int x,int & goal)
{
int y=fa[x],z=fa[y],k=ch[y][]==x;
if(y==goal) goal=x;
else ch[z][ch[z][]==y]=x;
ch[y][k]=ch[x][k^]; ch[x][k^]=y;
fa[y]=x; fa[ch[y][k]]=y; fa[x]=z;
update(y);
}
bool getson(int x)
{
return ch[fa[x]][]==x;
}
void splay(int x,int & goal)
{
while(x!=goal)
{
int y=fa[x];
if(y!=goal)
{
if(getson(x)==getson(y)) rotate(y,goal);
else rotate(x,goal);
}
rotate(x,goal);
update(x);
}
}
int find(int now,int k)
{
if(k<=siz[ch[now][]]) return find(ch[now][],k);
else if(siz[now]-siz[ch[now][]]<k) return find(ch[now][],k-siz[now]+siz[ch[now][]]);
else
{
k-=siz[ch[now][]];
if(k!=)
{
fa[ch[++tot][]=ch[now][]]=tot; fa[ch[now][]=tot]=now;
key[tot][]=key[now][]; key[tot][]=key[tot][]+k-; key[now][]=key[tot][]+;
update(tot);
k=;
}
if(k!=key[now][]-key[now][]+)
{
fa[ch[++tot][]=ch[now][]]=tot; fa[ch[now][]=tot]=now;
key[tot][]=key[now][]; key[tot][]=key[now][]+k; key[now][]=key[tot][]-;
update(tot);
}
return now;
}
}
void spilt(int l,int r)
{
t1=find(root,l);
t2=find(root,r);
splay(t1,root);
splay(t2,ch[root][]);
}
}Splay;
int main()
{
/*freopen("data.txt","r",stdin);
freopen("my2.txt","w",stdout);*/
n=read(); m=read();
for(int i=;i<=n;i++) key[i+][]=key[i+][]=read();
Splay.build(,n+,);
tot=n+; root=n+>>;
int op,p,a,b;
while(m--)
{
scanf("%d",&op);
if(!op)
{
p=read(); a=read(); b=read();
Splay.spilt(p+,p+);
fa[ch[t2][]=++tot]=t2; key[tot][]=a; key[tot][]=b; siz[tot]=b-a+;
Splay.update(t2); Splay.update(t1);
}
else if(op==)
{
a=read(); b=read();
Splay.spilt(a,b+);
ch[t2][]=;
Splay.update(t2); Splay.update(t1);
}
else
{
p=read();
p=Splay.find(root,p+);
printf("%d\n",key[p][]);
}
}
}
狂WA代码：
#include<cstdio>
#define N 20005
using namespace std;
int n,m,now,tmp,root;
int a[N];
int siz[N*],fa[N*],key[N*],ch[N*][],cnt[N*];
int tot;
struct SPLAY_TREE
{
void update(int k)
{
siz[k]=cnt[k];
if(ch[k][]) siz[k]+=siz[ch[k][]];
if(ch[k][]) siz[k]+=siz[ch[k][]];
}
void build(int l,int r,int f)
{
if(l>r) return;
int mid=l+r>>;
if(mid<f) ch[f][]=mid;
else ch[f][]=mid;
siz[mid]=; cnt[mid]=; fa[mid]=f; key[mid]=a[mid];
build(l,mid-,mid);
build(mid+,r,mid);
update(mid);
}
int find_id(int x)
{
now=root;
while()
{
if(ch[now][]&&siz[ch[now][]]>=x) now=ch[now][];
else
{
tmp=(ch[now][] ? siz[ch[now][]] : )+cnt[now];
if(x<=tmp) return now;
x-=tmp;
now=ch[now][];
}
}
}
int getson(int x)
{
return ch[fa[x]][]==x;
}
void rotate(int x,int & goal)
{
int y=fa[x],z=fa[y],k=ch[y][]==x;
if(y==goal) goal=x;
else ch[z][ch[z][]==y]=x;
ch[y][k]=ch[x][k^]; ch[x][k^]=y;
fa[y]=x; fa[ch[y][k]]=y; fa[x]=z;
update(y);
}
void splay(int x,int & goal)
{
int y;
while(x!=goal)
{
y=fa[x];
if(y!=goal)
{
if(getson(x)==getson(y)) rotate(y,goal);
else rotate(x,goal);
}
rotate(x,goal);
update(x);
}
}
void insert_suf(int s,int t)
{
if(!ch[root][]) now=root;
else
{
now=ch[root][];
while(ch[now][]) now=ch[now][];
}
siz[++tot]=cnt[tot]=t-s+;
key[tot]=(s+t)*(t-s+)/;
fa[tot]=now;
ch[now][]=tot;
splay(tot,root);
}
void insert_pre(int s,int t)
{
if(!ch[root][]) now=root;
else
{
now=ch[root][];
while(ch[now][]) now=ch[now][];
}
siz[++tot]=cnt[tot]=t-s+;
key[tot]=(s+t)*(t-s+)/;
fa[tot]=now;
ch[now][]=tot;
splay(tot,root);
}
int find_pre()
{
now=ch[root][];
while(ch[now][]) now=ch[now][];
return now;
}
int find_suf()
{
now=ch[now][];
while(ch[now][]) now=ch[now][];
return now;
}
void del()
{
if(!ch[root][]&&!ch[root][]) root=;
else if(!ch[root][])
{
tmp=root;
root=ch[root][];
fa[root]=;
ch[tmp][]=;
}
else if(!ch[root][])
{
tmp=root;
root=ch[root][];
fa[root]=;
ch[tmp][]=;
}
else
{
int pre=find_pre();
tmp=root;
splay(pre,root);
ch[root][]=ch[tmp][];
if(ch[root][]) fa[ch[root][]]=root;
update(root);
}
}
}Splay;
int main()
{
/*freopen("data.txt","r",stdin);
freopen("my.txt","w",stdout);*/
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i+]);
Splay.build(,n+,);
root=n+>>;
int op,p,aa,bb,q;
int cutl,cutr;
int shouxiang1,shouxiang2,moxiang1,moxiang2,rest_in_aa,rest_in_bb;
tot=n+;
while(m--)
{
scanf("%d",&op);
if(op==)
{
scanf("%d%d%d",&p,&aa,&bb);
p++;q=p;
p=Splay.find_id(p);
Splay.splay(p,root);
if(cnt[p]==) Splay.insert_suf(aa,bb);
else
{
cutl=q-siz[ch[root][]]-;
cutr=siz[root]-siz[ch[root][]]-q;
shouxiang1=(*key[root]/cnt[root]-cnt[root]+)/;
moxiang1=shouxiang1+cutl-;
shouxiang2=moxiang1+;
moxiang2=shouxiang2+cutr-;
siz[root]=siz[root]-cnt[root]+;
cnt[root]=;
key[root]=moxiang1+;
Splay.insert_pre(shouxiang1,moxiang1);
Splay.splay(p,root);
Splay.insert_suf(shouxiang2,moxiang2);
Splay.splay(p,root);
Splay.insert_suf(aa,bb);
}
}
else if(op==)
{
scanf("%d%d",&aa,&bb);
aa++; bb++;
p=aa; q=bb;
aa=Splay.find_id(aa);
bb=Splay.find_id(bb);
if(aa==bb)
{
Splay.splay(aa,root);
cutl=p-siz[ch[root][]]-;
//cutr=siz[root]-siz[ch[root][1]]-q;
cutr=cnt[root]-cutl-(q-p+);
shouxiang1=(*key[root]/cnt[root]-cnt[root]+)/;
moxiang1=shouxiang1+cutl-;
shouxiang2=moxiang1+q-p+;//+1
moxiang2=shouxiang2+cutr-;
if(shouxiang1<=moxiang1)
{
Splay.insert_pre(shouxiang1,moxiang1);//++
Splay.splay(aa,root);
siz[root]=siz[root]-(moxiang1-shouxiang1+);
cnt[root]=cnt[root]-(moxiang1-shouxiang1+);
key[root]=key[root]-(shouxiang1+moxiang1)*(moxiang1-shouxiang1+)/;
}
siz[root]=siz[root]-(q-p+);
cnt[root]=cnt[root]-(q-p+);
key[root]=key[root]-(shouxiang2-+shouxiang2--(q-p+)+)*(q-p+)/;
if(!cnt[root]) Splay.del();
continue;
}
Splay.splay(aa,root);
rest_in_aa=p-siz[ch[root][]]-;
Splay.splay(bb,ch[root][]);
rest_in_bb=cnt[bb]-(q-p+-(cnt[aa]-rest_in_aa+siz[ch[bb][]]));//+1
siz[aa]-=siz[ch[bb][]];
siz[bb]-=siz[ch[bb][]];
ch[bb][]=;
shouxiang1=(*key[bb]/cnt[bb]-cnt[bb]+)/;
key[bb]-=(shouxiang1+shouxiang1+cnt[bb]-rest_in_bb-)*(cnt[bb]-rest_in_bb)/;
cnt[bb]=rest_in_bb;
Splay.update(bb);
shouxiang1=(*key[aa]/cnt[aa]-cnt[aa]+)/;
key[aa]=(shouxiang1+shouxiang1+rest_in_aa-)*rest_in_aa/;
cnt[aa]=rest_in_aa;
Splay.update(aa);
}
else
{
scanf("%d",&p);
p++;
q=Splay.find_id(p);
if(cnt[q]==) printf("%d\n",key[q]);
else
{
Splay.splay(q,root);
p=p-siz[ch[root][]];
shouxiang1=(*key[root]/cnt[root]-cnt[root]+)/;
printf("%d\n",shouxiang1+p-);
}
}
}
}