【LCT维护基环内向树森林】BZOJ4764 弹飞大爷

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

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 ;
}
上一篇:BZOJ4764弹飞大爷——LCT


下一篇:java实现同步的两种方式