又是一个LCT

写完了以后1A

具体做法有点意思,再写几题把LCT写成模版题即可..

LCT真是麻烦

这一题大概就是在LCT的基础上维护好一个size即可

询问:evert(n) access(x) 求x左子树(不计通过非prefer_edge连上的)

修改:cut了再link即可

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
    int size;
    bool rev;
    node * ch[2];
    node * father;
};
node * a[200005];
node * null;
node * new_node()
{
    static node a[200005];
    static int top=0;
    node * t=&a[top++];
    t->ch[0]=null;
    t->ch[1]=null;
    t->father=null;
    t->size=1;
    t->rev=false;
    return t;
}
int get_up(node * x)
{
    if (x->father->ch[0]==x) return 0;
    if (x->father->ch[1]==x) return 1;
    return -1;
}
void rotate(node * &x,int c)
{
    node * y=x->ch[c];
    x->ch[c]=y->ch[!c];
    y->ch[!c]->father=x;
    y->ch[!c]=x;
    y->father=x->father;
    x->father=y;
    y->size=x->size;
    x->size=x->ch[0]->size+x->ch[1]->size+1;
    x=y;
}
void update(node * &x)
{
    if (x->rev)
    {
        x->ch[0]->rev^=1;
        x->ch[1]->rev^=1;
        swap(x->ch[0],x->ch[1]);
        x->rev=false;
    }
}
void splay(node * &x)
{
    for (;;)
    {
        update(x->father->father);
        update(x->father);
        update(x);
        int t1=get_up(x);
        if (t1==-1) return;
        int t2=get_up(x->father);
        if (t2==-1)
        {
            x=x->father;
            rotate(x,t1);
            return;
        }
        int t3=get_up(x->father->father);
        if (t3==-1)
        {
            if (t1==t2)
            {
                x=x->father;
                x=x->father;
                rotate(x,t2);
                rotate(x,t1);
            }
            else
            {
                x=x->father;
                x=x->father;
                rotate(x->ch[t2],t1);
                rotate(x,t2);
            }
        }
        else
        {
            if (t1==t2)
            {
                x=x->father;
                x=x->father;
                x=x->father;
                rotate(x->ch[t3],t2);
                rotate(x->ch[t3],t1);
            }
            else
            {
                x=x->father;
                x=x->father;
                rotate(x->ch[t2],t1);
                x=x->father;
                rotate(x->ch[t3],t2);
            }
            x=x->ch[t3];
        }
    }
}
void access(node * x)
{
    for (;;)
    {
        splay(x);
        if (x->father==null)
        {
            x->size-=x->ch[1]->size;
            x->ch[1]=null;
            return;
        }
        splay(x->father);
        x->father->size-=x->father->ch[1]->size;
        x->father->ch[1]=x;
        x->father->size+=x->size;
    }
}
void evert(node * x)
{
    access(x);
    x->rev=true;
}
void cut(node * x,node * y)
{
    evert(x);
    access(y);
    y->size-=y->ch[0]->size;
    y->ch[0]->father=null;
    y->ch[0]=null;
}
void link(node * x,node * y)
{
    evert(x);
    x->father=y;
}
int b[200005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d",&n);
    null=new_node();
    null->size=0;
    null->ch[0]=null;
    null->ch[1]=null;
    null->father=null;
    int i;
    for (i=0;i<n;i++)
    {
        a[i]=new_node();
    }
    a[n]=new_node();
    for (i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
        b[i]+=i;
        if (b[i]>=n) b[i]=n;
        link(a[i],a[b[i]]);
    }
    scanf("%d",&m);
    for (i=0;i<m;i++)
    {
        int oper;
        scanf("%d",&oper);
        if (oper==1)
        {
            int x;
            scanf("%d",&x);
            evert(a[n]);
            access(a[x]);
            printf("%d\n",a[x]->ch[0]->size);
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);
            cut(a[x],a[b[x]]);
            b[x]=x+y;
            if (b[x]>=n) b[x]=n;
            link(a[x],a[b[x]]);
        }
    }
    return 0;
}