@ysner
2018-09-17T22:04:07.000000Z
字数 2344
阅读 2010
LCT
图论
学校中有个地点,用到的整数表示,每个地点设有若干个刷卡机。
有以下三类事件:
直接看到这道题可能会想到什么奇奇怪怪的东西。。。
动态维护还是大概率。
但是需要动点脑子。
单向边?对不起,不支持维护单向边,所以需要单独开个并查集维护。
成了环怎么办?可以把整个环缩成一个点,用另一个并查集维护。
因为缩了点,记得每次跳父亲都要找其在并查集里的根,即改为。
听说经常会?反正我一次也没用。
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define ls t[0][x]
#define rs t[1][x]
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=6e5+100;
int n,m,f[N],t[2][N],sta[N],top,tag[N],scc[N],con[N],s[N],w[N],val[N];
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il int find(re int x){return x==scc[x]?x:scc[x]=find(scc[x]);}
il int Find(re int x){return x==con[x]?x:con[x]=Find(con[x]);}
il void dfs(re int x,re int rt){if(!x) return;scc[find(x)]=rt;dfs(ls,rt);dfs(rs,rt);}
il void upd(re int x){s[x]=s[ls]+s[rs]+val[x];}
il void rev(re int x){if(!x) return;swap(ls,rs);tag[x]^=1;}
il void pushdown(re int x){if(tag[x]) rev(ls),rev(rs),tag[x]=0;}
il int son(re int x){return x==t[1][find(f[x])];}
il int isrt(re int x){return x!=t[0][find(f[x])]&&x!=t[1][find(f[x])];}
il void rotate(re int x)
{
re int y=find(f[x]),z=find(f[y]),c=son(x);
t[c][y]=t[c^1][x];if(t[c][y]) f[t[c][y]]=y;
f[x]=z;if(!isrt(y)) t[son(y)][z]=x;
t[c^1][x]=y;f[y]=x;upd(y);
}
il void splay(re int x)
{
sta[top=1]=x;
for(re int i=x;!isrt(i);i=find(f[i])) sta[++top]=find(f[i]);
while(top) pushdown(sta[top--]);
for(re int y=find(f[x]);!isrt(x);rotate(x),y=find(f[x]))
if(!isrt(y)) son(x)^son(y)?rotate(x):rotate(y);
upd(x);
}
il void access(re int x){for(re int y=0;x;y=x,x=find(f[x])) splay(x),rs=y,upd(x);}
il void makert(re int x){access(x);splay(x);rev(x);}
il void split(re int x,re int y){makert(x);access(y);splay(y);}
il void link(re int x,re int y){makert(x);f[x]=y;}
int main()
{
n=gi();m=gi();
fp(i,1,n) con[i]=scc[i]=i,val[i]=w[i]=gi();
fp(i,1,m)
{
re int op=gi(),u=gi(),v=gi();
if(op==1)
{
u=find(u);v=find(v);
if(Find(u)^Find(v)) link(u,v),con[Find(u)]=Find(v);
else
{
split(u,v);val[v]=s[v];
dfs(v,v);t[0][v]=t[1][v]=0;
}
}
if(op==2)
{
re int fu=find(u);val[fu]+=v-w[u];w[u]=v;splay(fu);
}
if(op==3)
{
u=find(u),v=find(v);
if(Find(u)^Find(v)) {puts("-1");continue;}
split(u,v);
printf("%d\n",s[v]);
}
}
return 0;
}