题目链接
\(Solution\)
\(LCT\)裸题
我们首先先新建一个节\(n+1\)点，表示被弹飞
对于点\(i,link(i,min(n+1,i+k_i))\)
再看看修改:
现在要将点\(x\)修改为\(K,\)则\(:cut(x,min(n+1,x+k_x)),link(x,min(n+1,x+K)),k_x=K\)
最后对于询问，直接\(splix(x,n+1)\)就好了，不多说了.
\(Code\)
#include<bits/stdc++.h>
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return f*x;
}
struct node {
int fa,v,lazy,ch[2];
}a[1000010];
stack<int>s;
bool nroot(int x){
return a[a[x].fa].ch[0]==x||a[a[x].fa].ch[1]==x;
}
void pushup(int x){
a[x].v=a[a[x].ch[0]].v+a[a[x].ch[1]].v+1;
}
void work(int x){
swap(a[x].ch[0],a[x].ch[1]),a[x].lazy^=1;
}
void pushdown(int x){
if(a[x].lazy){
if(a[x].ch[0]) work(a[x].ch[0]);
if(a[x].ch[1]) work(a[x].ch[1]);
a[x].lazy=0;
}
}
void rotate(int x){
int y=a[x].fa,z=a[y].fa,k=(a[y].ch[1]==x);
if(nroot(y)) a[z].ch[a[z].ch[1]==y]=x;
a[x].fa=z,a[a[x].ch[k^1]].fa=y;
a[y].ch[k]=a[x].ch[k^1],a[y].fa=x;
a[x].ch[k^1]=y,pushup(x),pushup(y);
}
void splay(int x){
int u=x;
s.push(u);
while(nroot(u)) s.push(u=a[u].fa);
while(!s.empty()) pushdown(s.top()),s.pop();
while(nroot(x)){
int y=a[x].fa,z=a[y].fa;
if(nroot(y))
(a[y].ch[0]==x)^(a[z].ch[0]==y)?rotate(x):rotate(y);
rotate(x);
}
pushup(x);
}
void access(int x){
for(int y=0;x;y=x,x=a[x].fa)
splay(x),a[x].ch[1]=y,pushup(x);
}
void makeroot(int x){
access(x),splay(x),work(x);
}
int findroot(int x){
access(x),splay(x);
while(a[x].ch[0]) pushdown(x),x=a[x].ch[0];
splay(x);
return x;
}
void split(int x,int y){
makeroot(x),access(y),splay(y);
}
void link(int x,int y){
makeroot(x);
if(findroot(y)!=x)
a[x].fa=y;
}
void cut(int x,int y){
makeroot(x);
if(findroot(y)!=x||a[y].fa!=x||a[y].ch[0]) return ;
a[y].fa=a[x].ch[1]=0,pushup(x);
}
int k[1000001];
int main(){
int n=read();
for(int i=1;i<=n;i++)
k[i]=read(),link(i,min(n+1,i+k[i]));
int m=read(),K;
for(int i=1;i<=m;i++){
int opt=read(),x=read()+1;
if(opt==1)
split(x,n+1),printf("%d\n",a[n+1].v-1);
else K=read(),cut(x,min(n+1,x+k[x])),link(x,min(n+1,x+K)),k[x]=K;
}
return 0;
}