\u5e76\u67e5\u96c6\u7ef4\u62a4\u4e00\u4e0b\u8fde\u901a\u6027\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u8fde\u901a\u5757\u5efa\u4e00\u9897\u6743\u503c\u7ebf\u6bb5\u6811\uff0c\u7136\u540e\u641e\u7ebf\u6bb5\u6811\u5408\u5e76\u3002<\/strong><\/p>\n#include<cstdio>\r\n#include<iostream>\r\nusing namespace std;\r\n#define N 100010\r\n#define M 1800100\r\ninline int read()\r\n{\r\n int x=0,f=1;char ch=getchar();\r\n while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}\r\n while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}\r\n return x*f;\r\n}\r\nint fa[N];\r\nint findf(int x){return x==fa[x]?x:fa[x]=findf(fa[x]);}\r\nint rt[N],ls[M],rs[M],sum[M],cnt;\r\nvoid add(int l,int r,int &y,int v)\r\n{\r\n if(!y) y=++cnt;\r\n if(l==r){sum[y]=1;return;}\r\n int mid=(l+r)>>1;\r\n if(v>mid) add(mid+1,r,rs[y],v);\r\n else add(l,mid,ls[y],v);\r\n sum[y]=sum[ls[y]]+sum[rs[y]];\r\n}\r\nint que(int l,int r,int y,int k)\r\n{\r\n if(l==r) return l;\r\n int mid=(l+r)>>1;\r\n if(sum[ls[y]]>=k) return que(l,mid,ls[y],k);\r\n else return que(mid+1,r,rs[y],k-sum[ls[y]]);\r\n}\r\nint lj(int x,int y)\r\n{\r\n if(!x) return y;\r\n if(!y) return x;\r\n ls[x]=lj(ls[x],ls[y]);\r\n rs[x]=lj(rs[x],rs[y]);\r\n sum[x]=sum[ls[x]]+sum[rs[x]];\r\n return x;\r\n}\r\nint n,m,a,b,q,v[N],di[N],x,k,ans;\r\nchar cc;\r\nint main()\r\n{\r\n n=read();m=read();\r\n for(int i=1;i<=n;i++) v[i]=read();\r\n for(int i=0;i<=n;i++) fa[i]=i;\r\n for(int i=0;i<m;i++)\r\n {\r\n a=read();b=read();\r\n a=findf(a);b=findf(b);\r\n fa[a]=b;\r\n }\r\n for(int i=1;i<=n;i++)\r\n {\r\n add(1,n,rt[findf(i)],v[i]);\r\n di[v[i]]=i;\r\n }\r\n q=read();\r\n while(q--)\r\n {\r\n cc=getchar();\r\n while(cc<'A'||cc>'Z') cc=getchar();\r\n x=read();k=read();\r\n if(cc=='Q')\r\n {\r\n a=findf(x);\r\n if(sum[rt[a]]<k){puts(\"-1\");continue;}\r\n ans=que(1,n,rt[a],k);\r\n printf(\"%d\\n\",di[ans]);\r\n }\r\n else \r\n {\r\n a=findf(x);b=findf(k);\r\n if(a!=b)\r\n {\r\n fa[a]=b;\r\n rt[b]=lj(rt[a],rt[b]);\r\n }\r\n }\r\n }\r\n}<\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
2733: [HNOI2012]\u6c38\u65e0\u4e61 Time Limit:\u00a010 Sec\u00a0\u00a0Memory L […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[10],"class_list":["post-381","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-10"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/381","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=381"}],"version-history":[{"count":2,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/381\/revisions"}],"predecessor-version":[{"id":383,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/381\/revisions\/383"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=381"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=381"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=381"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}