4764: 弹飞大爷
Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 101 Solved: 52
[Submit][Status][Discuss]
Description
自从WC退役以来，大爷是越来越懒惰了。为了帮助他活动筋骨，也是受到了弹飞绵羊一题的启发，机房的小伙伴们
决定齐心合力构造一个下面这样的序列。这个序列共有N项，每项都代表了一个小伙伴的力量值，如果大爷落到了
第i个小伙伴的手里，那么第i个小伙伴会把大爷弹到第i+ai个小伙伴手里，其中ai就是第i个小伙伴的力量值，也
就是序列的第i项。然而，因为大爷太沉了，所以有些小伙伴不能撑到锻（you）炼（xi）结束，所以我们中途会替
换一些小伙伴，也就是改变序列的某些项。而且，因为大爷太沉了，所以有些小伙伴不能把大爷扔向前方，而是会
把大爷往反方向扔，也就是序列中的一些项会是负的（当然，也可能是零喽）。现在机智的大爷通过在空中的观察
，已经知道小伙伴们的所有活动——即初始序列、所有更改操作，他想请你算一算，如果他在某时刻落到了某个位
置，那么他会在几次弹起之后落到小伙伴序列之外（毕竟摔在地上还是蛮疼的）。
Input
第一行为两个整数N和M，代表序列长度和操作次数。
第二行为N个整数，代表初始的小伙伴序列。
接下来有M行，每行代表一个操作。
如果这一行的第一个数是1，代表该操作是一个询问操作，接下来一个数X，代表询问此时大爷从X处，经过几次弹
起会摔在地上。如果永远不会摔在地上，请输出-1。
如果这一行的第一个数是2，代表该操作是一个更改操作，接下来两个数X，Y，代表将序列的第X项改为Y。
N,M <= 200000 |Ai| < N
Output
对于每次询问操作，输出弹起次数或-1。
Sample Input
3 19
1 1 1
1 1
1 2
1 3
2 1 2
1 1
1 2
1 3
2 3 -1
1 1
1 2
1 3
2 2 233
1 1
1 2
1 3
2 2 -233
1 1
1 2
1 3
1 1 1
1 1
1 2
1 3
2 1 2
1 1
1 2
1 3
2 3 -1
1 1
1 2
1 3
2 2 233
1 1
1 2
1 3
2 2 -233
1 1
1 2
1 3
Sample Output
3
2
1
2
2
1
-1
-1
-1
3
1
2
3
1
2
题解
LCT维护基环内向树森林
具体来说，就是当我们原来维护的无向图变成了一个每个点出度为1的有向图
显然它是可能存在环的，并且更重要的是它不能换根（方向问题）
所以若它是一棵树的话，正常维护LCT
如果它形成了环，我们记一下这个联通块的根到达的点的位置pos[i]
对于Link操作，我们判断一下这条有向边x--->y的端点y在被连接之前的根节点是否已经可以是x
- 如果是，那么加上这条边之后形成环，我们显然不能把它加上，所以我们令pos[x]=y
- 如果不是，正常地把x连到y的下面
对于Cut操作，我们要判断一下这条有向边x--->y的端点x形成的环是否正好连到y，即判断pos[x]是否等于y
- 如果是，那么直接把环去掉，即令pos[x]=0
- 如果不是，我们先记一下x在联通块中的根节点rt，然后正常地去掉这条边
- 但是然后我们还要判断一下割断这条边后是否会保留原来的环，如果已经没环，就把记录的边加上，如果环还在，退出
具体看代码吧
代码
//by 减维
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<bitset>
#include<set>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<ctime>
#include<algorithm>
#define ll long long
#define il inline
#define rg register
#define db double
#define mpr make_pair
#define maxn 200005
#define inf (1<<30)
#define eps 1e-8
#define pi 3.1415926535897932384626L
using namespace std; inline int read()
{
int ret=;bool fla=;char ch=getchar();
while((ch<''||ch>'')&&ch!='-')ch=getchar();
if(ch=='-'){fla=;ch=getchar();}
while(ch>=''&&ch<=''){ret=ret*+ch-'';ch=getchar();}
return fla?-ret:ret;
} int n,m,fa[maxn],son[maxn][],siz[maxn],rev[maxn],pos[maxn];
int a[maxn]; il bool pdp(int x){return son[fa[x]][]==x;}
il bool isrt(int x){return son[fa[x]][]!=x&&son[fa[x]][]!=x;}
il void rever(int x){rev[x]^=;swap(son[x][],son[x][]);}
il void upda(int x){siz[x]=siz[son[x][]]+siz[son[x][]]+;} il void pdn(int x)
{
if(rev[x])
{
if(son[x][]) rever(son[x][]);
if(son[x][]) rever(son[x][]);
rev[x]=;
}
} void pd(int x){if(!isrt(x)) pd(fa[x]);pdn(x);} il void rot(int x)
{
int f=fa[x],g=fa[f],o=pdp(x);
if(!isrt(f)) son[g][pdp(f)]=x;fa[x]=g;
son[f][o]=son[x][!o];fa[son[f][o]]=f;
son[x][!o]=f;fa[f]=x;
upda(f),upda(x);
} il void splay(int x)
{
pd(x);
for(;!isrt(x);rot(x))
if(!isrt(fa[x])) rot(pdp(fa[x])==pdp(x)?fa[x]:x);
} il void acc(int x)
{
for(int y=;x;y=x,x=fa[x])
splay(x),son[x][]=y,upda(x);
} il int find(int x)
{
acc(x),splay(x);
while(son[x][]) pdn(x),x=son[x][];
return x;
} il void link(int x,int y)
{
if(find(y)==x) pos[x]=y;
else acc(x),splay(x),fa[x]=y;
} il void cut(int x,int y)
{
if(pos[x]==y) pos[x]=;
else{
int t=find(x);
acc(x),splay(x),fa[son[x][]]=,son[x][]=,upda(x);
if(pos[t]&&find(pos[t])!=t) link(t,pos[t]),pos[t]=;
}
} int main()
{
n=read(),m=read();
for(int i=;i<=n;++i) a[i]=read(),siz[i]=;
for(int i=;i<=n;++i)
if(i+a[i]>=&&i+a[i]<=n) link(i,a[i]+i);
for(int i=,op,x,y;i<=m;++i)
{
op=read(),x=read();
if(op==){
acc(x),y=find(x);
if(pos[y]) puts("-1");
else splay(x),printf("%d\n",siz[x]);
}else{
y=read();
if(x+a[x]>=&&a[x]+x<=n) cut(x,a[x]+x);
if(x+y>=&&x+y<=n) link(x,x+y);
a[x]=y;
}
}
return ;
}