bzoj 2959 长跑 题解

(Updated: )
oi
,

Description

　　某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”，同学们纷纷离开寝室，离开教室，离开实验室，到操场参加3000米长跑运动。一时间操场上熙熙攘攘，摩肩接踵，盛况空前。
　　为了让同学们更好地监督自己，学校推行了刷卡机制。
　　学校中有n个地点，用1到n的整数表示，每个地点设有若干个刷卡机。
　　有以下三类事件：
　　1、修建了一条连接A地点和B地点的跑道。
　　2、A点的刷卡机台数变为了B。
　　3、进行了一次长跑。问一个同学从A出发，最后到达B最多可以刷卡多少次。具体的要求如下：
　　当同学到达一个地点时，他可以在这里的每一台刷卡机上都刷卡。但每台刷卡机只能刷卡一次，即使多次到达同一地点也不能多次刷卡。
　　为了安全起见，每条跑道都需要设定一个方向，这条跑道只能按照这个方向单向通行。最多的刷卡次数即为在任意设定跑道方向，按照任意路径从A地点到B地点能刷卡的最多次数。

Solution

开2个并查集，一个保存的是原树之间的关系用来判断连通性，一个保存的是强联通分量的代表节点。

每连一条边u-v，就用第一个并查集判断一下u,v是否连通。如果没有，就直接连接，否则意味着图中出现了一个环。我们把这个环上的所有节点（也就是原来u-v的路径上的所有点）的点权移到一个代表节点上，然后丢掉其他所有点，还要把所有点的第二个并查集的父亲赋值为代表节点，因为它们属于的强联同分量改变了。

对于舍弃掉的点，只要保证不会在各种操作的时候跳到即可。具体实现时，只要把所有的fa改为getfa(fa)即可，就会跳到代表节点上。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
int n,m,op,x,y,a[150010];
namespace IO{
inline int read(){int res=0,f=1;char ch=getchar();while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch&15),ch=getchar();return res*f;}
inline void write(int x){if(x<0) putchar('-'),x=-x;if(x<10) putchar(x+'0');else write(x/10),putchar(x%10+'0');}
}
namespace UFS{
int fa[150010][2];
inline int getfa(int x,int y){return fa[x][y]==x?x:fa[x][y]=getfa(fa[x][y],y);}
inline void merge(int x,int y,int z){if(x=getfa(x,z),y=getfa(y,z),x!=y) fa[x][z]=y;}
}
namespace LCT{
struct node{int s,v,ch[2],fa,tag;}tr[150010];
int stk[150010],top;
inline bool isroot(int x){return tr[UFS::getfa(tr[x].fa,1)].ch[0]!=x&&tr[UFS::getfa(tr[x].fa,1)].ch[1]!=x;}
inline void pushup(int x){tr[x].s=tr[x].v+tr[tr[x].ch[0]].s+tr[tr[x].ch[1]].s;}
inline void flip(int x){swap(tr[x].ch[0],tr[x].ch[1]);tr[x].tag^=1;}
inline void pushdown(int x){
if(!tr[x].tag) return ;
if(tr[x].ch[0]) flip(tr[x].ch[0]);
if(tr[x].ch[1]) flip(tr[x].ch[1]);
tr[x].tag=0;
}
inline void rotate(int x){
int y=UFS::getfa(tr[x].fa,1),z=UFS::getfa(tr[y].fa,1),k=tr[y].ch[1]==x,v=tr[x].ch[!k];
if(!isroot(y)) tr[z].ch[tr[z].ch[1]==y]=x;
tr[x].ch[!k]=y,tr[y].ch[k]=v;
if(v) tr[v].fa=y;
tr[y].fa=x,tr[x].fa=z;
pushup(y),pushup(x);
}
inline void splay(int x){
int y=x,z;top=0;stk[++top]=y;
while(!isroot(y)) stk[++top]=y=tr[y].fa;
while(top) pushdown(stk[top--]);
while(!isroot(x)){
y=UFS::getfa(tr[x].fa,1),z=UFS::getfa(tr[y].fa,1);
if(!isroot(y)) rotate((tr[y].ch[0]==x)^(tr[z].ch[0]==y)?x:y);
rotate(x);
}
pushup(x);
}
inline void access(int x){for(int y=0;x;x=UFS::getfa(tr[y=x].fa,1)) splay(x),tr[x].ch[1]=y,pushup(x);}
inline void makeroot(int x){access(x),splay(x),flip(x);}
inline int findroot(int x){access(x),splay(x);while(tr[x].ch[0]) pushdown(x),x=tr[x].ch[0];return x;}
inline void split(int x,int y){makeroot(x),access(y),splay(y);}
inline void link(int x,int y){makeroot(x);tr[x].fa=y;}
inline void cut(int x,int y){split(x,y);if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ch[1]) tr[x].fa=tr[y].ch[0]=0,pushup(y);}
inline void reset(int x){tr[x].fa=tr[x].ch[0]=tr[x].ch[1]=0,pushup(x);}
inline void change(int x,int y){int t=UFS::getfa(x,1);splay(t),tr[t].v-=a[x],a[x]=y,tr[t].v+=a[x],pushup(x);}
}
inline int dfs(int f,int x){
if(!x) return 0;
UFS::fa[x][1]=f;
return dfs(f,LCT::tr[x].ch[0])+dfs(f,LCT::tr[x].ch[1])+LCT::tr[x].v;
}
int main(){
n=IO::read(),m=IO::read();
for(int i=1;i<=n;i++) UFS::fa[i][0]=UFS::fa[i][1]=i,LCT::tr[i].s=LCT::tr[i].v=a[i]=IO::read();
for(int i=1;i<=m;i++){
op=IO::read(),x=IO::read(),y=IO::read();
if(op==1){
if(x=UFS::getfa(x,1),y=UFS::getfa(y,1),x==y) continue ;
if(UFS::getfa(x,0)!=UFS::getfa(y,0)) LCT::link(x,y),UFS::merge(x,y,0);
else LCT::split(x,y),LCT::tr[x].v=dfs(x,y),LCT::reset(x);
}else if(op==2) LCT::change(x,y);
else if(op==3){
if(UFS::getfa(x,0)!=UFS::getfa(y,0)){puts("-1");continue ;}
x=UFS::getfa(x,1),y=UFS::getfa(y,1),LCT::split(x,y),IO::write(LCT::tr[y].s),putchar('\n');
}
}
}