首页 > > 程序设计 > C/C++ >

bzoj2002 [ HNOI2010 ] -- LCT

2018-06-17 23:11:42来源：未知阅读 ()

考虑建一棵树，对于一个点i，如果i+k_i<=n，将i+k_i作为它的父亲。那么答案就是这个点的深度。

由于有修改操作，用LCT维护这棵树，每个修改操作改变父节点就可以了。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define N 200010
 6 int i,j,k,n,m,T,f[N],ch[N][2],s[N],x,y;
 7 bool b[N];
 8 inline char nc(){
 9     static char buf[100000],*p1=buf,*p2=buf;
10     if(p1==p2){
11         p2=(p1=buf)+fread(buf,1,100000,stdin);
12         if(p1==p2)return EOF;
13     }
14     return *p1++;
15 }
16 inline void Read(int& x){
17     char c=nc();
18     for(;c<'0'||c>'9';c=nc());
19     for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
20 }
21 inline void Pushup(int x){s[x]=s[ch[x][0]]+s[ch[x][1]]+1;}
22 inline int Get(int x){return x==ch[f[x]][1];}
23 inline void Rotate(int x){
24     bool d=Get(x);int y=f[x];
25     if(b[y])b[y]=0,b[x]=1;else ch[f[y]][Get(y)]=x;
26     ch[y][d]=ch[x][d^1];f[ch[y][d]]=y;
27     ch[x][d^1]=y;f[x]=f[y];f[y]=x;
28     Pushup(y);
29 }
30 inline void Splay(int x){
31     for(;!b[x];Rotate(x))
32     if(!b[f[x]])Rotate(Get(x)==Get(f[x])?f[x]:x);
33     Pushup(x);
34 }
35 inline void Access(int x){
36     int y=0;
37     while(x){
38         Splay(x);
39         b[ch[x][1]]=1;b[y]=0;
40         ch[x][1]=y;Pushup(x);
41         y=x;x=f[x];
42     }
43 }
44 inline void Link(int x,int y){
45     Access(y);Splay(y);
46     f[ch[y][0]]=0;b[ch[y][0]]=1;
47     ch[y][0]=0;f[y]=x;
48     Pushup(y);
49 }
50 inline void Update(int x,int y){if(x+y>n)Link(0,x);else Link(x+y,x);}
51 inline int Query(int x){Access(x);Splay(x);return s[ch[x][0]]+1;}
52 char S[30];
53 int Len;
54 inline void Print(int x){
55     for(Len=0;x;x/=10)S[++Len]=x%10;
56     for(;Len;)putchar(S[Len--]+48);putchar('\n');
57 }
58 int main()
59 {
60     Read(n);
61     for(i=1;i<=n;i++)b[i]=s[i]=1;
62     for(i=1;i<=n;i++){
63         Read(x);
64         if(i+x<=n)Link(i+x,i);
65     }
66     Read(T);
67     while(T--){
68         Read(k);
69         if(k==1)Read(x),Print(Query(x+1));else Read(x),Read(y),Update(x+1,y);
70     }
71     return 0;
72 }