Link-Cut-Tree套路题
//BZOJ 2002
//by Cydiater
//2016.9.12
#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
;
const int oo=0x3f3f3f3f;
inline int read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
,q[MAXN],op,num,node;
struct SplayTree{
],fa,siz,tag;
}t[MAXN];
namespace solution{
inline ]!=node&&t[t[node].fa].son[]!=node;}
inline ]==node;}
inline void updata(int node){
if(node){
t[node].siz=;
t[node].siz+=t[t[node].son[]].siz;
t[node].siz+=t[t[node].son[]].siz;
}
}
inline void downit(int node){
if(t[node].tag){
t[t[node].son[]].tag^=;t[t[node].son[]].tag^=;
swap(t[node].son[],t[node].son[]);
t[node].tag=;
}
}
void rotate(int node){
int old=t[node].fa,oldf=t[old].fa,which=get(node);
]]=node;
t[old].son[which]=t[node].son[which^];t[t[old].son[which]].fa=old;
t[old].fa=node;t[node].son[which^]=old;t[node].fa=oldf;
updata(old);updata(node);
}
void splay(int node){
top=;q[++top]=node;
for(int i=node;!isroot(i);i=t[i].fa)q[++top]=t[i].fa;
down(i,top,)downit(q[i]);
while(!isroot(node)){
int old=t[node].fa,oldf=t[old].fa;
if(!isroot(old))rotate(get(node)==get(old)?old:node);
rotate(node);
}
}
;]=tmp;tmp=node;node=t[node].fa;}}
;}
void Link(int noda,int nodb){Reverse(noda);t[noda].fa=nodb;splay(noda);}
]=t[noda].fa=;}
);access(node);splay(node);]].siz;}
void init(){
N=read();up(i,,N)a[i]=read();
up(i,,N){t[i].fa=min(a[i]+i,N+);t[i].siz=;}
t[N+].siz=;
}
void slove(){
M=read();
while(M--){
op=read();
)printf());
){
node=read()+;num=read();
Cut(node,min(node+a[node],N+));
a[node]=num;
Link(node,min(node+a[node],N+));
}
}
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
;
}