题解 P2713 【罗马游戏】
SuperJvRuo
2018-10-20 17:59:38
随机合并的随机堆了解一下。
合并的时候```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;
}
```