[关闭]
@ysner 2018-09-17T22:04:07.000000Z 字数 2344 阅读 2010

[bzoj2959]长跑

LCT 图论


题面

学校中有个地点,用的整数表示,每个地点设有若干个刷卡机。
有以下三类事件:

解析

直接看到这道题可能会想到什么奇奇怪怪的东西。。。

动态维护还是大概率
但是需要动点脑子。
单向边?对不起,不支持维护单向边,所以需要单独开个并查集维护。
成了环怎么办?可以把整个环缩成一个点,用另一个并查集维护。
因为缩了点,记得每次跳父亲都要找其在并查集里的根,即改为

听说经常?反正我一次也没用。

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cmath>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define ls t[0][x]
  11. #define rs t[1][x]
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=6e5+100;
  16. int n,m,f[N],t[2][N],sta[N],top,tag[N],scc[N],con[N],s[N],w[N],val[N];
  17. il ll gi()
  18. {
  19. re ll x=0,t=1;
  20. re char ch=getchar();
  21. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  22. if(ch=='-') t=-1,ch=getchar();
  23. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  24. return x*t;
  25. }
  26. il int find(re int x){return x==scc[x]?x:scc[x]=find(scc[x]);}
  27. il int Find(re int x){return x==con[x]?x:con[x]=Find(con[x]);}
  28. il void dfs(re int x,re int rt){if(!x) return;scc[find(x)]=rt;dfs(ls,rt);dfs(rs,rt);}
  29. il void upd(re int x){s[x]=s[ls]+s[rs]+val[x];}
  30. il void rev(re int x){if(!x) return;swap(ls,rs);tag[x]^=1;}
  31. il void pushdown(re int x){if(tag[x]) rev(ls),rev(rs),tag[x]=0;}
  32. il int son(re int x){return x==t[1][find(f[x])];}
  33. il int isrt(re int x){return x!=t[0][find(f[x])]&&x!=t[1][find(f[x])];}
  34. il void rotate(re int x)
  35. {
  36. re int y=find(f[x]),z=find(f[y]),c=son(x);
  37. t[c][y]=t[c^1][x];if(t[c][y]) f[t[c][y]]=y;
  38. f[x]=z;if(!isrt(y)) t[son(y)][z]=x;
  39. t[c^1][x]=y;f[y]=x;upd(y);
  40. }
  41. il void splay(re int x)
  42. {
  43. sta[top=1]=x;
  44. for(re int i=x;!isrt(i);i=find(f[i])) sta[++top]=find(f[i]);
  45. while(top) pushdown(sta[top--]);
  46. for(re int y=find(f[x]);!isrt(x);rotate(x),y=find(f[x]))
  47. if(!isrt(y)) son(x)^son(y)?rotate(x):rotate(y);
  48. upd(x);
  49. }
  50. il void access(re int x){for(re int y=0;x;y=x,x=find(f[x])) splay(x),rs=y,upd(x);}
  51. il void makert(re int x){access(x);splay(x);rev(x);}
  52. il void split(re int x,re int y){makert(x);access(y);splay(y);}
  53. il void link(re int x,re int y){makert(x);f[x]=y;}
  54. int main()
  55. {
  56. n=gi();m=gi();
  57. fp(i,1,n) con[i]=scc[i]=i,val[i]=w[i]=gi();
  58. fp(i,1,m)
  59. {
  60. re int op=gi(),u=gi(),v=gi();
  61. if(op==1)
  62. {
  63. u=find(u);v=find(v);
  64. if(Find(u)^Find(v)) link(u,v),con[Find(u)]=Find(v);
  65. else
  66. {
  67. split(u,v);val[v]=s[v];
  68. dfs(v,v);t[0][v]=t[1][v]=0;
  69. }
  70. }
  71. if(op==2)
  72. {
  73. re int fu=find(u);val[fu]+=v-w[u];w[u]=v;splay(fu);
  74. }
  75. if(op==3)
  76. {
  77. u=find(u),v=find(v);
  78. if(Find(u)^Find(v)) {puts("-1");continue;}
  79. split(u,v);
  80. printf("%d\n",s[v]);
  81. }
  82. }
  83. return 0;
  84. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注