题意略…（今天比较懒）
由于只有建造公路没有破环公路，所以可以用启发式合并保持操作数为log，暴力拆开小的联通块，用LCT插到大的联通块内，然后用LCT维护子树信息，具体看这里
#include <cstdio>#include <iostream>#include <algorithm>#define N 300010using namespace std;int n,m,rt[N],g[N],Ans,x,y,tp;char op;int fa[N],ch[N][2],sz[N],isz[N],rev[N],sta[N],tot[N],G[N],cnt;struct edge{ int t,nx;}E[N<<3];inline int isr(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}inline int isl(int x){return ch[fa[x]][1]==x;}int fifa(int x){return rt[x]==x?x:(rt[x]=fifa(rt[x]));}inline void upd(int x){ if(!x) return; sz[x]=1+isz[x]; if(ch[x][0]) sz[x]+=sz[ch[x][0]]; if(ch[x][1]) sz[x]+=sz[ch[x][1]];}inline void pushdown(int x){ if(!(x&&rev[x])) return; swap(ch[x][0],ch[x][1]); if(ch[x][0]) rev[ch[x][0]]^=1; if(ch[x][1]) rev[ch[x][1]]^=1; rev[x]=0;}inline void rot(int x){ int y=fa[x],z=fa[y],lor=isl(x); if(!isr(y)) ch[z][ch[z][1]==y]=x; fa[x]=z; if(ch[y][lor]=ch[x][lor^1]) fa[ch[y][lor]]=y; fa[ch[x][lor^1]=y]=x; upd(y); upd(x);}inline void splay(int x){ sta[tp=1]=x; for(int i=x;!isr(i);i=fa[i]) sta[++tp]=fa[i]; for(;tp;--tp) pushdown(sta[tp]); for(;!isr(x);rot(x)) if(!isr(fa[x])) rot(isl(x)^isl(fa[x])?x:fa[x]);}inline void access(int x){ int t=0; for(;x;x=fa[x]){ splay(x); isz[x]+=sz[ch[x][1]]-sz[t]; ch[x][1]=t; t=x; upd(x); }}inline void reverse(int x){access(x); splay(x); rev[x]^=1;}inline void link(int x,int y){ reverse(x); reverse(y); fa[x]=y; isz[y]+=sz[x]; upd(y); reverse(g[fifa(y)]); access(x); splay(g[fifa(y)]); int S=sz[g[fifa(y)]],t=ch[g[fifa(y)]][1];pushdown(t); while(ch[t][0]) pushdown(t=ch[t][0]); access(t); if((isz[t]+1)*2>S||((isz[t]+1)*2==S&&t<g[fifa(y)])){ Ans^=g[fifa(y)]^t; g[fifa(y)]=t; }}inline void reaD(int &x){ char Ch=getchar();x=0; for(;Ch>'9'||Ch<'0';Ch=getchar()); for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=getchar());}inline void InserT(int x,int y){ E[++cnt].t=y;E[cnt].nx=G[x];G[x]=cnt; E[++cnt].t=x;E[cnt].nx=G[y];G[y]=cnt;}void dfs(int x,int f){ ch[x][0]=ch[x][1]=fa[x]=isz[x]=rev[x]=0; sz[x]=1; link(x,f); for(int i=G[x];i;i=E[i].nx) if(E[i].t!=f) dfs(E[i].t,x);}inline void merge(int x,int y){ tot[fifa(y)]+=tot[fifa(x)]; Ans^=g[fifa(x)]; rt[fifa(x)]=fifa(y); dfs(x,y); InserT(x,y);}int main(){ reaD(n); reaD(m); for(int i=1;i<=n;i++) rt[i]=i,g[i]=i,Ans^=i,tot[i]=1; for(int i=1;i<=m;i++){ while((op=getchar())!='A'&&op!='Q'&&op!='X'); if(op=='X') PRintf("%d/n",Ans); else if(op=='Q') reaD(x),printf("%d/n",g[fifa(x)]); else{ reaD(x); reaD(y); if(tot[fifa(x)]>tot[fifa(y)]) swap(x,y); merge(x,y); } }}新闻热点
疑难解答
