BZOJ 4668: 冷战 LCT November 9, 2016 ###Description 1946 年 3 月 5 日，英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁幕演说”，正式拉开了冷战序幕。 美国和苏联同为世界上的“超级大国”，为了争夺世界霸权，两国及其盟国展开了数十年的斗争。在这段时期，虽然分歧和冲突严重，但双方都尽力避免世界范围的大规模战争（第三次世界大战）爆发，其对抗通常通过局部代理战争、科技和军备竞赛、太空竞争、外交竞争等“冷”方式进行，即“相互遏制，不动武力”，因此称之为“冷战”。 Reddington 是美国的海军上将。由于战争局势十分紧张，因此他需要时刻关注着苏联的各个活动，避免使自己的国家陷入困境。苏联在全球拥有 N 个军工厂，但由于规划不当，一开始这些军工厂之间是不存在铁路的，为了使武器制造更快，苏联决定修建若干条道路使得某些军工厂联通。 Reddington 得到了苏联的修建日程表，并且他需要时刻关注着某两个军工厂是否联通，以及最早在修建哪条道路时会联通。具体而言，现在总共有M 个操作，操作分为两类： • 0 u v，这次操作苏联会修建一条连接 u 号军工厂及 v 号军工厂的铁路，注意铁路都是双向的; • 1 u v， Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第几条条铁路后会联通，假如到这次操作都没有联通，则输出 0; 作为美国最强科学家， Reddington 需要你帮忙设计一个程序，能满足 他的要求。 ###Input 第一行两个整数 N, M。 接下来 M 行，每行为 0 u v 或 1 u v 的形式。 数据是经过加密的，对于每次加边或询问，真正的 u, v 都等于读入的 u, v 异或上上一次询问的答案。一开始这个值为 0。 1 ≤ N, M ≤ 500000，解密后的 u, v 满足1 ≤ u, v ≤ N, u不等于v ###Output 对于每次 1 操作，输出 u, v 最早在加入哪条边后会联通，若到这个操 作时还没联通，则输出 0。 ###Sample Input 5 9 0 1 4 1 2 5 0 2 4 0 3 4 1 3 1 0 7 0 0 6 1 0 1 6 1 2 6 ###Sample Output ``` 0 3 5 ``` ###Solution 直接用LCT维护动态最小生成树就行了，虽然很暴力，但能AC ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> inline T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d) const int N=1000001; struct node { node *c[2],*fa; int val,ma; bool rev; inline void rotate(bool f); inline void pushdown(); inline void pushup(); }s[N],_null,*null=&_null; inline void node::pushdown() { if(fa->c[0]==this||fa->c[1]==this) fa->pushdown(); if(rev) { rev=0; std::swap(c[0],c[1]); if(c[0]!=null)c[0]->rev=!c[0]->rev; if(c[1]!=null)c[1]->rev=!c[1]->rev; } } inline void node::rotate(bool f) { fa->c[f]=c[!f]; c[!f]=fa; fa=c[!f]->fa; if(c[!f]->fa->c[1]==c[!f]) c[!f]->fa->c[1]=this; else if(c[!f]->fa->c[0]==c[!f]) c[!f]->fa->c[0]=this; c[!f]->fa=this; c[!f]->c[f]->fa=c[!f]; c[!f]->pushup(); } inline void node::pushup() { ma=val; if(c[0]!=null)repr(ma,c[0]->ma); if(c[1]!=null)repr(ma,c[1]->ma); } inline void init(node *x,int v) { x->val=v,x->c[0]=null,x->c[1]=null,x->fa=null; } inline void splay(node *a) { a->pushdown(); while(a->fa->c[0]==a||a->fa->c[1]==a) a->rotate(a==a->fa->c[1]); a->pushup(); } inline void access(node *a) { node *x=null; while(a!=null) { splay(a); a->c[1]=x; a->pushup(); x=a,a=a->fa; } } inline void movetoroot(node *x) { access(x); splay(x); x->rev=!x->rev; } inline void link(node *x,node *y) { movetoroot(x); x->fa=y; } inline void cut(node *x,node *y) { movetoroot(x); access(y); splay(y); x->fa=null; y->c[0]=null; y->pushup(); } inline void split(node *x,node *y) { movetoroot(x),access(y),splay(y); } inline node* findroot(node *x) { while(x->fa!=null) x=x->fa; return x; } int main() { int n,m,lstans=0,opt,x,y; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) init(s+i,0); for(int i=1,ec=0;i<=m;i++) { scanf("%d%d%d",&opt,&x,&y); x^=lstans,y^=lstans; if(opt==0) { ec++; if(findroot(s+x)!=findroot(s+y)) { init(s+n+ec,ec); link(s+x,s+n+ec); link(s+y,s+n+ec); } } else { split(s+x,s+y); if(findroot(s+x)==s+y) lstans=s[y].ma; else lstans=0; printf("%d\n",lstans); } } } ```