弹飞绵羊 正常维护 size。

gistfile1.cpp

#include <iostream>
#include <cstdio>
using namespace std;
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)
#define DO(N) while (N--)
#define DO_C(n) int n____ = n; while(n____--)
template<class T> inline void RD(T &x){char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';}
inline int RD(){ int x; RD(x); return x;}
template<class T> inline T& _RD(T &x){ RD(x); return x;}
template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}
template<class T> inline void OT(const T &x){printf("%d\n", x);}
 
/* .................................................................................................................................. */
 
const int N = 200001;
 
int l[N], r[N], p[N], sz[N]; bool rt[N];
int n, ans;
 
#define lx l[x]
#define rx r[x]
 
inline void Update(int x){
    sz[x] = sz[lx] + sz[rx] + 1;
}
 
inline void Set(int l[], int y, int x){
    l[y] = x, p[x] = y;
}
 
inline void Rotate(int x){
    int y = p[x], z = p[y];
 
    if (!rt[y]) Set(y == l[z] ? l : r, z, x);
    else p[x] = z;
 
    if (x == l[y]){
        Set(l, y, rx), Set(r, x, y);
    }
    else {
        Set(r, y, lx), Set(l, x, y);
    }
 
    if (rt[y]) rt[y] = false, rt[x] = true;
 
    Update(y);
}
 
inline void Splay(int x){
    while (!rt[x]) Rotate(x);
}
 
int Access(int x){
    int y = 0; do{
        Splay(x);
        rt[rx] = true, rt[rx = y] = false; Update(x);
        x = p[y = x];
    } while (x);
    return y;
}
 
int Root(int x){
    for (x = Access(x); lx ; x = lx);
    return x;
}
 
void Link(int x, int y){
    Access(x), Splay(x), rt[lx] = true;
    lx = p[lx] = 0, p[x] = y; //Update(x);
    Access(x);
}
 
int main(){
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
 
    REP_1_C(i, _RD(n)) sz[i] = 1, rt[i] = true;
 
    int k; REP_1(i, n){
        RD(k); if (i + k <= n) p[i] = i + k;
    }
 
    int cmd, x; DO_C(RD()){
        RD(cmd, x), ++x;
        if (cmd == 1){
            OT(sz[Access(x)]);
            //Access(x), Splay(x), OT(sz[lx] + 1);
            //int t = Root(x); Splay(t); OT(sz[r[t]] + 1);
        }
 
        else {
            RD(k); if (x + k <= n) Link(x, x+k);
            else Link(x, 0);
        }
    }
}