【BZOJ-2002】[HNOI2010] Bounce 彈飛綿羊

題目連結

題目描述

某天，Lostmonkey發明了一種超級彈力裝置，為了在他的綿羊朋友面前顯擺，他邀請小綿羊一起玩個遊戲。遊戲一開始，Lostmonkey在地上沿着一條直線擺上n個裝置，每個裝置設定初始彈力系數ki，當綿羊達到第i個裝置時，它會往後彈ki步，達到第i+ki個裝置，若不存在第i+ki個裝置，則綿羊被彈飛。綿羊想知道當它從第i個裝置起步時，被彈幾次後會被彈飛。為了使得遊戲更有趣，Lostmonkey可以修改某個彈力裝置的彈力系數，任何時候彈力系數均為正整數。

題解

容易發現(顯然)從一個彈簧隻會被彈到一個确定的地方，但一個地方可能會從不同的彈簧彈過來。不覺得這是一棵樹麼，彈到哪個點上，哪個點就是它的父親節點。我們建立一個點表示彈出去了，那麼次數不就是出發點到這個點的樹上距離嗎？

再來看看更換彈力系數實際上幹了些啥，不就是給他換了個父親嗎。

于是成了 LCT 裸題，動态詢問樹上兩點間的距離。

/*
  LCT 求一個點到根的距離方法:
  先access(p),Splay(p) 這樣p的左子樹就是所有在p點上方的點,維護size即可;
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;
inline int read()
{
    int x=;char ch=getchar();int t=;
    for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=-;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<)+(x<<)+(ch-);
    return x*t;
}
#define __ NULL
#define ls son[0]
#define rs son[1]
#define get_son(a) (a->fa->rs==a)
#define get_size(a) (a==__? 0:a->size)
const int N=+;
struct node{
    node* fa;node* son[];int k;
    bool rev,is_root;int size;//要維護size 
    void clear(){fa=ls=rs=__;rev=;is_root=;size=;k=;}
}*tr[N];
node pool[N];int cnt;
node* st[N];int h;
inline void updata(node* p){p->size=+get_size(p->ls)+get_size(p->rs);}
inline void push_down(node* p)
{
    if(p==__||p->rev==) return;
    p->rev=;
    if(p->ls!=__)p->ls->rev^=;
    if(p->rs!=__)p->rs->rev^=;
    swap(p->ls,p->rs);
}
inline void rotate(node* p)
{
    if(p==__||p->is_root==) return;
    register int k=get_son(p);
    register node* q=p->fa;register node* gp=q->fa;
    q->son[k]=p->son[k^];
    if(p->son[k^]!=__) p->son[k^]->fa=q;p->fa=gp;
    if(q->is_root) q->is_root=,p->is_root=;
    else gp->son[get_son(q)]=p;
    q->fa=p;p->son[k^]=q;
    updata(p);updata(q);
}
inline void Splay(node* p)
{
    if(p==__)return;
    h=;
    st[h]=p;
    for(register node* i=p;!i->is_root;st[++h]=(i=i->fa));
    while(h) push_down(st[h--]);
    for(;!p->is_root;rotate(p)){
        if(p->fa->is_root) {rotate(p);break;}
        if(get_son(p->fa)==get_son(p)) rotate(p->fa);
        else rotate(p);
    }
    updata(p);
}
inline void access(node* p){
    for(register node* pre=__;p!=__;pre=p,p=p->fa){
        Splay(p);
        if(p->rs!=__) p->rs->is_root=;
        p->rs=pre;if(pre!=__) pre->is_root=;updata(p);
    }
}
inline void m_root(node* p){access(p);Splay(p);p->rev^=;}
inline void Link(node* p,node* q){m_root(p);p->fa=q;}
inline void split(node* p,node* q){m_root(p);access(q);Splay(q);}
inline void Cut(node* p,node* q) {
    split(p,q);
    if(q->ls==p) p->fa=q->ls=__,p->is_root=,updata(q);
}
int n;
inline void Query(node* p)
{
    split(tr[n+],p);
    printf("%d\n",get_size(p->ls));
}
int main()
{
    n=read();
    for(register int i=;i<=n;i++) tr[i]=&pool[cnt++],tr[i]->clear(),tr[i]->k=read();
    tr[n+]=&pool[cnt++];tr[n+]->clear();
    for(register int i=;i<=n;i++){
        register int nt=tr[i]->k+i;
        if(nt>n) nt=n+;Link(tr[i],tr[nt]);
    }
    int m=read();register int op;register int x,y;
    for(register int i=;i<=m;i++){
        op=read();
        if(op==) Query(tr[read()+]);
        else {
            x=read()+;y=read();
            register int nt1=tr[x]->k+x;
            if(nt1>n) nt1=n+;
            register int nt2=y+x;
            if(nt2>n) nt2=n+;
            if(nt1==nt2) continue;
            tr[x]->k=y;
            Cut(tr[x],tr[nt1]);
            Link(tr[x],tr[nt2]);
        }
    }
}