【BZOJ2002】弹飞绵羊

    裸的lct。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=200010,maxm=100010;
  
struct LCT
{
    struct Node
    {
        Node *c[2],*p,*lcp;
        int size;
        bool w() {return p->c[1]==this;}
    }*Null,*ID[maxn];
  
    #define ls x->c[0]
    #define rs x->c[1]
  
    void Update(Node *x)
    {
        if (x==Null) return;
        x->size=ls->size+rs->size+1;
    }
  
    void Rotate(Node *x)
    {
        Node *p=x->p;
        bool w=x->w();
        x->lcp=p->lcp;
        p->lcp=Null;
        x->c[!w]->p=p;
        p->p->c[p->w()]=x;
        x->p=p->p;
        p->c[w]=x->c[!w];
        x->c[!w]=p;
        p->p=x;
        Update(p);
    }
  
    void Splay(Node *x)
    {
        if (x==Null) return;
        while (x->p!=Null)
        {
            if (x->p->p==Null) {Rotate(x);break;}
            if (x->p->w()==x->w()) Rotate(x->p),Rotate(x);
            else Rotate(x),Rotate(x);
        }
        Update(x);
    }
  
    void Access(Node *x)
    {
        Node *v=Null,*pre=x;
        while (x!=Null)
        {
            Splay(x);
            rs->p=Null;
            rs->lcp=x;
            rs=v;
            v->p=x;
            v->lcp=Null;
            Update(x);
            v=x;x=x->lcp;
        }
        Splay(pre);
    }
  
    Node* Find_Root(Node *x)
    {
        Access(x);
        Splay(x);
        while (ls!=Null) x=ls;
        Splay(x);
        return x;
    }
  
    void Cut(Node *x)
    {
        Access(x);
        ls->p=ls->lcp=Null;
        x->lcp=Null;
        ls=Null;
    }
  
    void Link(Node *x,Node *v)
    {
        Access(x);
        x->lcp=v;
        Access(x);
    }
  
    void Init(int n)
    {
        for (int i=0;i<=n;i++) ID[i]=new Node;
        Null=new Node;
        for (int i=0;i<=n;i++) ID[i]->size=1,ID[i]->c[0]=ID[i]->c[1]=ID[i]->p=ID[i]->lcp=Null;
        Null->size=0;Null->c[0]=Null->c[1]=Null->p=Null->lcp=Null;
    }
  
    int Node_Depth(int x)
    {
        Access(ID[x]);
        Splay(ID[x]);
        return ID[x]->c[0]->size;
    }
  
    void Change_Node(int x,int y)
    {
        Cut(ID[x]);
        Link(ID[x],ID[y]);
    }
}T;
  
void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}
  
int n,m;
  
int main()
{
    read(n);
    T.Init(n);
    for (int i=0,x;i<n;i++)
    {
        read(x);
        x+=i;
        if (x>=n) x=n;
        T.Change_Node(i,x);
    }
    read(m);
    while (m--)
    {
        int ctr,x,y;
        read(ctr);
        if (ctr==1) read(x),printf("%d\n",T.Node_Depth(x));
        if (ctr==2)
        {
            read(x),read(y);
            y+=x;
            if (y>=n) y=n;
            T.Change_Node(x,y);
        }
    }
    return 0;
}