bzoj 2002: [Hnoi2010]Bounce 弹飞绵羊

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

Sample Output

2
3

题解：

算是简单的吧，可以用把每个弹簧看作一个点，然后LCT维护连通性即可.

如果i+a[i]>n就将i连向n+1 反之连在i+a[i]上.

修改就是先cut再link

答案就是将n+1旋到根并且把询问点和n+1放到同一Splay中 , 深度比它小的点的个数为答案,然后显然为左子树大小

但是有个问题：gdb的时候并没有发现reserve的作用...于是发现确实没卵用..只不过修改操作要稍作变化

个人浅薄的理解为：mroot操作只是为了在cut得时候把不相关的连在一起，而这题只是cut与原父亲的连边所以不必mroot

1RE :rotate都打错好多遍，果然还是巨水

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 using namespace std;
  8 const int N=200005;
  9 int ch[N][2],size[N],fa[N];bool rev[N],rt[N];
 10 int gi(){
 11     int str=0;char ch=getchar();
 12     while(ch>'9' || ch<'0')ch=getchar();
 13     while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
 14     return str;
 15 }
 16 void updata(int r){
 17     if(!r)return ;
 18     swap(ch[r][0],ch[r][1]);
 19     rev[r]^=1;
 20 }
 21 void pushdown(int r){
 22     if(!rev[r])return ;
 23     updata(ch[r][0]);updata(ch[r][1]);
 24     rev[r]=0;
 25 }
 26 void upsize(int r){
 27     if(r)
 28     size[r]=size[ch[r][1]]+size[ch[r][0]]+1;
 29 }
 30 void rotate(int r){
 31     int y=fa[r];bool t=(ch[y][1]==r);
 32     ch[y][t]=ch[r][!t];
 33     ch[r][!t]=y;
 34     fa[ch[y][t]]=y;
 35     fa[r]=fa[y];
 36     if(rt[y])
 37         rt[y]=false,rt[r]=true;
 38     else
 39         ch[fa[y]][ch[fa[y]][1]==y]=r;
 40     fa[y]=r;
 41     upsize(y);upsize(r);
 42 }
 43 void Push(int r){
 44     if(!rt[r] && r)Push(fa[r]);
 45     pushdown(r);
 46 }
 47 void splay(int r){
 48     Push(r);
 49     while(!rt[r]){
 50         int y=fa[r],yy=fa[y];
 51         if(rt[y])
 52             rotate(r);
 53         if((ch[yy][1]==y)==(ch[y][1]==r))rotate(y),rotate(r);
 54         else rotate(r),rotate(r);
 55     }
 56     pushdown(r);upsize(r);
 57 }
 58 void access(int x){
 59     int y=0;
 60     do{
 61         splay(x);
 62         rt[ch[x][1]]=true;rt[ch[x][1]=y]=false;
 63         upsize(x);
 64         x=fa[y=x];
 65     }while(x);
 66 }
 67 void mroot(int x){
 68     access(x);
 69     splay(x);
 70     updata(x);
 71 }
 72 void link(int x,int y){
 73     mroot(x);fa[x]=y;upsize(y);
 74 }
 75 void cut(int x,int y){
 76     mroot(x);access(y);splay(y);
 77     pushdown(y);
 78     fa[x]=ch[y][0]=0;rt[x]=true;
 79     upsize(y);
 80 }
 81 int n,m,a[N];
 82 void query(int x){
 83     mroot(n+1);
 84     access(x);
 85     splay(x);
 86     printf("%d
",size[ch[x][0]]);
 87 }
 88 void change(int x,int to){
 89     if(x+a[x]<=n)cut(x,x+a[x]);
 90     else cut(x,n+1);
 91     a[x]=to;
 92     if(x+a[x]<=n)link(x,x+a[x]);
 93     else link(x,n+1);
 94 }
 95 int main()
 96 {
 97     freopen("bzoj_2002.in","r",stdin);
 98     freopen("bzoj_2002.out","w",stdout);
 99     int x,y,z;
100     n=gi();rt[0]=true;
101     for(int i=1;i<=n+1;i++)size[i]=1,rt[i]=true;
102     for(int i=1;i<=n;i++){
103         a[i]=gi();
104          if(i+a[i]<=n)link(i,i+a[i]);
105           else link(i,n+1);
106     }
107     m=gi();
108     while(m--){
109         x=gi();y=gi();y++;
110         if(x==1)query(y);
111         else z=gi(),change(y,z);
112     }
113     return 0;
114 }