题解:
这个应该还是比较简单的
首先比较容易想到用lct来维护
我们可以建立一个特殊点
然后我们要处理环
其实只要判断它和不和这个特殊点联通就行了
那么当它不是环了我们怎么还原呢
只要对每个在根节点记录一下lazy标记 然后处理一下就好了
代码:
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define ll long long
#define IL inline
#define rint register int
#define me(x) memset(x,0,sizeof(x))
#define fi first
#define se second
#define mid ((h+t)>>1)
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
#define setit set<int>::iterator
const int INF=1e9;
char ss[<<],*A=ss,*B=ss;
IL char gc()
{
return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
}
template<class T> read(T &x)
{
rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=c^;
while (c=gc(),<c&&c<) x=(x<<)+(x<<)+(c^);
x*=f;
}
const int N=6e5;
int fa[N],ls[N],rs[N],count2[N],p[N];
bool rev[N];
struct re{
int a,b;
}lazy[N];
IL void updata(int x)
{
count2[x]=count2[ls[x]]+count2[rs[x]]+;
}
IL bool pd(int x)
{
int fa1=fa[x];
if (ls[fa1]!=x&&rs[fa1]!=x) return();
else return();
}
IL void down(int x)
{
if (!rev[x]) return;
swap(ls[x],rs[x]);
rev[ls[x]]^=; rev[rs[x]]^=;
rev[x]=;
}
void rotate(int x,int y)
{
int fa1=fa[x];
if (y==)
{
rs[fa1]=ls[x];
if (ls[x]) fa[ls[x]]=fa1;
} else
{
ls[fa1]=rs[x];
if (rs[x]) fa[rs[x]]=fa1;
}
fa[x]=fa[fa1];
if (pd(fa1))
{
if (ls[fa[fa1]]==fa1) ls[fa[fa1]]=x; else rs[fa[fa1]]=x;
}
fa[fa1]=x;
if (y==) ls[x]=fa1; else rs[x]=fa1;
updata(fa1); updata(x);
}
void dfs(int x)
{
if (pd(x)) dfs(fa[x]);
down(x);
}
void splay(int x)
{
dfs(x);
int fa1=fa[x];
while (pd(x))
{
if (!pd(fa1))
{
if (x==ls[fa1]) rotate(x,); else rotate(x,);
} else
if (ls[fa[fa1]]==fa1)
if (ls[fa1]==x)
rotate(fa1,),rotate(x,);
else
rotate(x,),rotate(x,);
else
if (rs[fa1]==x)
rotate(fa1,),rotate(x,);
else
rotate(x,),rotate(x,);
fa1=fa[x];
}
}
void access(int x)
{
for (int y=;x;y=x,x=fa[x])
{
splay(x);
rs[x]=y,updata(x);
}
}
void mkr(int x)
{
access(x);
splay(x);
rev[x]^=;
}
int fdr(int x)
{
access(x);
splay(x);
while(ls[x]) x=ls[x];
return(x);
}
void split(int x,int y)
{
mkr(x);
access(y);
splay(y);
}
void link(int x,int y)
{
mkr(x);
if (fdr(y)!=x) fa[x]=y;
else
{
int x1=fdr(y);
lazy[x1].a=x,lazy[x1].b=y;
}
}
void cut(int x,int y)
{
int x1=fdr(x);
if ((lazy[x1].a==x&&lazy[x1].b==y)||(lazy[x1].a==y&&lazy[x1].b==x))
{
lazy[x1].a=lazy[x1].b=;
} else
{
int tmp1=lazy[x1].a,tmp2=lazy[x1].b;
lazy[x1].a=lazy[x1].b=;
mkr(x);
access(y);
splay(y);
fa[x]=ls[y]=;
updata(y);
if (tmp1!=)
{
link(tmp1,tmp2);
}
}
}
int n,m;
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
read(n); read(m);
int k;
rep(i,,n) count2[i]=;
rep(i,,n)
{
read(k);
p[i]=k;
if (i+k<=n&&i+k>=)
{
link(i,i+k);
} else link(i,n+);
}
rep(i,,m)
{
int x,y,z;
read(x); read(y);
if (x==)
{
access(y);
int x1=fdr(y);
if (lazy[x1].a) printf("%d\n",-);
else
{
split(n+,y);
printf("%d\n",count2[y]-);
}
} else
{
read(z);
if (y+p[y]<=n&&y+p[y]>=) cut(y,y+p[y]);
else cut(y,n+);
if (y+z<=n&&y+z>=) link(y,y+z);
else link(y,n+);
p[y]=z;
}
}
return ;
}