bzoj2002(lct模板)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=;
struct node{
int ls,rs,fa,is_root;
}tr[maxn];
int n,m,siz[maxn],k[maxn];
void update(int x){
siz[x]=;
if(tr[x].ls)siz[x]+=siz[tr[x].ls];
if(tr[x].rs)siz[x]+=siz[tr[x].rs];
}
void rx(int x){
int y=tr[x].fa,z=tr[y].fa;
tr[y].ls=tr[x].rs;
if(tr[x].rs)tr[tr[x].rs].fa=y;
tr[x].rs=y;tr[y].fa=x;
tr[x].fa=z;
if(z&&!tr[y].is_root){//注意这句判断,辅助树之间的边是单向的;
if(tr[z].ls==y)tr[z].ls=x;else tr[z].rs=x;
}
if(tr[y].is_root)tr[x].is_root=,tr[y].is_root=;
update(y);update(x);
}
void lx(int x){
int y=tr[x].fa,z=tr[y].fa;
tr[y].rs=tr[x].ls;
if(tr[x].ls)tr[tr[x].ls].fa=y;
tr[x].ls=y;tr[y].fa=x;
tr[x].fa=z;
if(z&&!tr[y].is_root){
if(tr[z].ls==y)tr[z].ls=x;else tr[z].rs=x;
}
if(tr[y].is_root)tr[x].is_root=,tr[y].is_root=;
update(y);update(x);
}
void splay(int x){
while(!tr[x].is_root){
int y=tr[x].fa,z=tr[y].fa;
if(tr[y].is_root){if(tr[y].ls==x)rx(x);else lx(x);}
else{
if(tr[z].ls==y&&tr[y].ls==x){rx(y);rx(x);}
else if(tr[z].ls==y&&tr[y].rs==x){lx(x);rx(x);}
else if(tr[z].rs==y&&tr[y].ls==x){rx(x);lx(x);}
else{lx(y);lx(x);}
}
}
}
void ace(int x){
int y=;
do{
splay(x);
tr[tr[x].rs].is_root=;
tr[tr[x].rs=y].is_root=;
update(x);
x=tr[y=x].fa;
}while(x);
}
void link(int u,int v){//虽然说是link,但也包含和原来的断开然后和新的连上的两个过程
if(v>n)v=;
ace(u);splay(u);
tr[tr[u].ls].is_root=;
tr[tr[u].ls].fa=;tr[u].ls=;
tr[u].fa=v;update(u);
}
int query(int x){
ace(x);splay(x);
return siz[tr[x].ls]+;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i){
tr[i].is_root=siz[i]=;
tr[i].fa=tr[i].ls=tr[i].rs=;
}
for(int i=;i<=n;++i){
scanf("%d",&k[i]);
link(i,i+k[i]);
}
scanf("%d",&m);
int op,pos,cha;
for(int i=;i<=m;++i){
scanf("%d%d",&op,&pos);
if(op==)printf("%d\n",query(pos+));
else{
scanf("%d",&cha);
link(pos+,pos+cha+);
}
}
//system("pause");
return ;
}
上一篇:LCT模板


下一篇:SPSS Clementine 数据挖掘入门1