LCT 维护子树大小.....
2002: [Hnoi2010]Bounce 弹飞绵羊
Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 4085 Solved: 2188
[Submit][Status]
Description
某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
Input
第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000
Output
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
Sample Input
4
1 2 1 1
3
1 1
2 1 1
1 1
1 2 1 1
3
1 1
2 1 1
1 1
Sample Output
2
3
3
HINT
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=220000;
int n,m;
int pre[maxn],ch[maxn][2],size[maxn];
bool rt[maxn];
void init()
{
for(int i=0;i<=n+10;i++)
rt[i]=1,pre[i]=0,ch[i][0]=ch[i][1]=0,size[i]=1;
size[0]=0;
}
void push_up(int r)
{
size[r]=size[ch[r][0]]+size[ch[r][1]]+1;
}
void Rotate(int x)
{
int y=pre[x],kind=ch[y][1]==x;
ch[y][kind]=ch[x][!kind];
pre[ch[y][kind]]=y;
pre[x]=pre[y];
pre[y]=x;
ch[x][!kind]=y;
if(rt[y]) rt[y]=false,rt[x]=true;
else ch[pre[x]][ch[pre[x]][1]==y]=x;
push_up(y);
}
void Splay(int r)
{
while(!rt[r])
{
int f=pre[r],ff=pre[f];
if(rt[f]) Rotate(r);
else if((ch[ff][1]==f)==(ch[f][1]==r)) Rotate(f),Rotate(r);
else Rotate(r),Rotate(r);
}
push_up(r);
}
int Access(int x)
{
int y=0;
for(;x;x=pre[y=x])
{
Splay(x);
rt[ch[x][1]]=true; rt[ch[x][1]=y]=false;
push_up(x);
}
return y;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
init();
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
pre[i]=(i+t>n+1)?n+1:i+t;
}
scanf("%d",&m);
while(m--)
{
int tk,u,v;
scanf("%d",&tk);
if(tk==1)
{
scanf("%d",&u);
u++;
Access(u);
Splay(u);
printf("%d\n",size[ch[u][0]]);
}
else
{
scanf("%d%d",&u,&v);
u++;
Access(u);
Splay(u);
pre[ch[u][0]]=pre[u];
pre[u]=0;
rt[ch[u][0]]=true;
ch[u][0]=0;
push_up(u);
pre[u]=(u+v)>n+1?n+1:u+v;
}
}
}
return 0;
}