【LCT缩环+并查集】BZOJ2959 长跑

题面在这里

显然一个边双联通分量里的值可以同时取到

那么把边双缩成点,就可以用LCT维护了

并查集用于维护每个点被缩到哪个点上

注意LCT维护连通性,getrt后一定要splay(x)!!不然复杂度是错的,T了一发查好久

示例程序:

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
74
75
76
77
#include<cstdio>
#include<algorithm>
using namespace std;
inline char nc(){
static char buf[100000],*l=buf,*r=buf;
return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int red(){
int res=0,f=1;char ch=nc();
while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
return res*f;
}

const int maxn=150005;
int n,q,f[maxn];//ff[maxn];
inline int getf(int x) {return f[x]==x?x:f[x]=getf(f[x]);}
//inline int getff(int x) {return ff[x]==x?x:ff[x]=getff(ff[x]);}
int fa[maxn],s[maxn][2],sum[maxn],w[maxn],val[maxn];
bool flp[maxn];
#define fa(x) (getf(fa[x]))
#define isroot(x) (s[fa(x)][0]!=x&&s[fa(x)][1]!=x)
inline void pushup(int x) {sum[x]=sum[s[x][0]]+sum[s[x][1]]+val[x];}
inline void addflip(int x) {swap(s[x][0],s[x][1]),flp[x]^=1;}
inline void pushdown(int x) {if (flp[x]) addflip(s[x][0]),addflip(s[x][1]),flp[x]^=1;}
inline void rotate(int x){
int f=fa(x),g=fa(f),d= s[f][0]==x;
if (!isroot(f)) s[g][s[g][1]==f]=x; fa[x]=g;
s[f][d^1]=s[x][d]; fa[s[x][d]]=f;
s[x][d]=f; fa[f]=x; pushup(f); pushup(x);
}
int stk[maxn],top;
inline void splay(int x){
stk[top=1]=x;
for (int i=x;!isroot(i);i=fa(i)) stk[++top]=fa(i);
while (top) pushdown(stk[top--]);
while (!isroot(x)){
int f=fa(x),g=fa(f),d= s[f][0]==x,dd= s[g][0]==f;
if (!isroot(f))
if (d==dd) rotate(f),rotate(x);
else rotate(x),rotate(x);
else rotate(x);
}
}
inline void access(int x) {for (int t=0;x;t=x,x=fa(x)) splay(x),s[x][1]=t,pushup(x);}
inline void mr(int x) {access(x);splay(x);addflip(x);}
inline void link(int x,int y) {mr(x);fa[x]=y;}
inline int getrt(int x) {access(x);splay(x);while (s[x][0]) pushdown(x),x=s[x][0];splay(x);return x;}
void dfs(int x,int rt){
if (s[x][0]) val[rt]+=val[s[x][0]],dfs(s[x][0],rt);
if (s[x][1]) val[rt]+=val[s[x][1]],dfs(s[x][1],rt);
f[x]=rt;s[x][0]=s[x][1]=0;
}
int main(){
n=red(),q=red();
for (int i=1;i<=n;i++) val[i]=w[i]=red(),f[i]=i;
while (q--){
int c=red(),x=red(),y=red();
if (c==1){
x=getf(x);y=getf(y);
if (getrt(x)!=getrt(y)) link(x,y);else
if (x!=y){
mr(x);access(y);splay(x);
dfs(x,x);pushup(x);
}
}else
if (c==2){
int fx=getf(x);
mr(fx);access(fx);val[fx]+=y-w[x];w[x]=y;pushup(fx);
}else{
x=getf(x);y=getf(y);
if (getrt(x)!=getrt(y)) puts("-1");
else mr(x),access(y),splay(y),printf("%d\n",sum[y]);
}
}
return 0;
}