lct裸题
#include <iostream>
#include <cstdio>
using namespace std;
int n, ski[200005], m, uu, vv, opt, siz[200005], ch[200005][2], fa[200005];
int rev[200005];
bool isRoot(int x){
return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
}
bool getW(int x){
return ch[fa[x]][1]==x;
}
void pushDown(int x){
if(rev[x]){
swap(ch[x][0], ch[x][1]);
rev[ch[x][0]] ^= 1;
rev[ch[x][1]] ^= 1;
rev[x] = 0;
}
}
void upd(int x){
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
}
void xf(int x){
if(!isRoot(x)) xf(fa[x]);
pushDown(x);
}
void rotate(int x){
int old=fa[x], oldf=fa[old], w=getW(x);
if(!isRoot(old)) ch[oldf][ch[oldf][1]==old] = x;
ch[old][w] = ch[x][w^1]; ch[x][w^1] = old;
fa[ch[old][w]] = old; fa[ch[x][w^1]] = x; fa[x] = oldf;
upd(old); upd(x);
}
void splay(int x){
xf(x);
while(!isRoot(x)){
int f=fa[x];
if(!isRoot(f)) rotate(getW(f)==getW(x)?f:x);
rotate(x);
}
}
void access(int x){
int y=0;
while(x){
splay(x);
ch[x][1] = y;
upd(x);
y = x;
x = fa[x];
}
}
void makeRoot(int x){
access(x);
splay(x);
rev[x] ^= 1;
}
void link(int u, int v){
makeRoot(u);
fa[u] = v;
}
void cut(int u, int v){
makeRoot(u);
access(v);
splay(v);
ch[v][0] = fa[u] = 0;
}
int main(){
cin>>n;
for(int i=1; i<=n; i++){
scanf("%d", &ski[i]);
if(i+ski[i]>n) link(i, n+1);
else link(i, i+ski[i]);
}
cin>>m;
while(m--){
scanf("%d", &opt);
if(opt==1){
scanf("%d", &uu);
uu++;
makeRoot(uu);
access(n+1);
splay(n+1);
printf("%d
", siz[n+1]-1);
}
else{
scanf("%d %d", &uu, &vv);
uu++;
if(uu+ski[uu]>n) cut(uu, n+1);
else cut(uu, uu+ski[uu]);
ski[uu] = vv;
if(uu+ski[uu]>n) link(uu, n+1);
else link(uu, uu+ski[uu]);
}
}
return 0;
}