题解 P2713 【罗马游戏】

随机合并的随机堆了解一下。 合并的时候```rand()&1```一下，决定往左儿子还是右儿子合并。由于合并完全随机，不可能被卡掉，因而表现十分优异。 ``` #include<cstdio> #include<cctype> #include<cstdlib> #include<algorithm> int Read() { int x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+(c^48); c=getchar(); } return x; } //和普通的斜堆、左偏树相同 int ch[1000005][2],val[1000005],fa[1000005]; bool out[1000005]; int merge(int x,int y) { if (!x||!y) return x+y; if (val[x]>val[y]||(val[x]==val[y] && x>y)) std::swap(x,y); int opt=rand()&1; //合并的时候随机一下，决定往哪边走路 ch[x][opt]=merge(ch[x][opt],y); fa[ch[x][opt]]=x; return x; } int find(int x) { while(fa[x]) x=fa[x]; return x; } void pop(int x) { val[x]=-1; fa[ch[x][0]]=fa[ch[x][1]]=0; merge(ch[x][0],ch[x][1]); } int main() { srand(19260817); int n=Read(),x,y; for(int i=1; i<=n; i++) val[i]=Read(); int m=Read(); char opt[3]; while(m--) { scanf("%s",opt); if(opt[0]=='M') { x=Read(),y=Read(); if(val[x]==-1||val[y]==-1||(x=find(x))==(y=find(y))) continue; merge(x,y); } else { x=Read(); if(val[x]==-1) puts("0"); else { x=find(x); printf("%d\n",val[x]); pop(x); } } } return 0; } ```