这道题不能用cincout..会RE到你怀疑人生的...
#include<bits/stdc++.h>
using namespace std;
int a,f[1510010],n,m,l,r,tot=0,i,j;
struct one
{
int l,r,v,id,d,fa;
};
one tree[1510010];
bool pd()
{
char ch=getchar();
while(ch<'A'||ch>'Z')
{ch=getchar();}
if(ch=='M')return true;
else return false;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void newpoint(int v,int id)
{
tree[++tot].v=v;
tree[tot].id=id;
tree[tot].d=1;
}
int getfather(int p)
{
while(tree[p].fa)
p=tree[p].fa;
return p;
}
int merge(int k1,int k2,int fa)
{
if(k1==0||k2==0){tree[k1+k2].fa=fa;return k1+k2;}
if(tree[k1].v>tree[k2].v)swap(k1,k2);
tree[k1].r=merge(tree[k1].r,k2,k1);
if(tree[tree[k1].l].d>tree[tree[k1].r].d)swap(tree[k1].l,tree[k1].r);
tree[k1].d=tree[tree[k1].r].d+1;
tree[k1].fa=fa;
return k1;
}
int main()
{
//freopen("xf.in","r",stdin);
//freopen("xf.out","w",stdout);
n=read();
int tot2=0;
for(i=1;i<=n;i++)
a=read(),newpoint(a,i);
m=read();
for(i=1;i<=m;i++)
{
if(pd())
{
l=read();r=read();
if(f[l]||f[r])continue;
int f1=getfather(l);
int f2=getfather(r);
if(f1!=f2)
merge(f1,f2,0);
}
else
{
l=read();
int fa=getfather(l);
tot2++;
if(f[fa]){printf("%d\n",0);continue;}
f[fa]=1;
printf("%d\n",tree[fa].v);
merge(tree[fa].l,tree[fa].r,0);
}
}
return 0;
}
转播
