@[Akrain](/space/show?uid=137066) 头像让我想起了一些东西
by Ynoi @ 2019-09-06 20:05:54
发下你的getchar?
by 分块 @ 2019-09-06 20:08:31
@[Ynoi](/space/show?uid=124721) 树剖姐姐？
by __OccDreamer__ @ 2019-09-06 20:08:37
@[Akrain](/space/show?uid=137066) 怎么getchar的，麻烦发一下
by 冥诺在线发呆 @ 2019-09-06 20:09:37
我想要你的头像
by 暮光闪闪 @ 2019-09-06 20:12:35
头像警告
by Uichiha_Itachi @ 2019-09-06 20:17:43
```c++
#include<algorithm>
#include<iostream>
#include<cstdio>
#define MAX 100005
using namespace std;
int bel[MAX];
struct BST{
int root[MAX],tot;
struct Tree{
int ch[2];
int val,size,fa,pos;
}tree[MAX];
void pushup(int x){
tree[x].size=tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+1;
return;
}
void rotate(int x){
int fa=tree[x].fa;int fra=tree[fa].fa;
bool son=(tree[fa].ch[1]==x);
tree[x].fa=fra;tree[fa].fa=x;
tree[fra].ch[tree[fra].ch[1]==fa]=x;
tree[fa].ch[son]=tree[x].ch[son^1];
tree[tree[x].ch[son^1]].fa=fa;
tree[x].ch[son^1]=fa;
pushup(fa);pushup(x);
return;
}
void splay(int x,int tar,int to){
int u=root[to];
while(u&&tar!=tree[x].fa){
int fa=tree[x].fa;int fra=tree[fa].fa;
if(tar!=fra)
(tree[fra].ch[1]==fa)^(tree[fa].ch[1]==x)?rotate(x):rotate(fa);
rotate(x);
}
if(!tar)
root[to]=x;
return;
}
void insert(int x,int to,int pos,int use,bool opt){
int u=root[to],fa=0;
while(u&&tree[u].val!=x){
fa=u;
u=tree[u].ch[tree[u].val<x];
}
if(!opt)
u=++tot;
else
u=use;
tree[u].val=x;
tree[u].fa=fa;
tree[u].size=1;
tree[u].pos=pos;
tree[fa].ch[x>tree[fa].val]=u;
splay(u,0,to);
return;
}
int kth(int x,int to){
int u=root[to];
if(tree[u].size<x)
return -1;
while(19260817){
int l=tree[u].ch[0];
if(tree[l].size+1==x)
return tree[u].pos;
else if(tree[l].size<x){
x-=tree[l].size+1;
u=tree[u].ch[1];
}
else
u=l;
}
return 19260817;
}
void delate(int x,int to){
if(tree[x].ch[0])
delate(tree[x].ch[0],to);
if(tree[x].ch[1])
delate(tree[x].ch[1],to);
bel[tree[x].pos]=to;
insert(tree[x].val,to,tree[x].pos,x,1);
return;
}
void union_splay(int x,int y){
int rx=root[x],ry=root[y];
if(tree[rx].size<tree[ry].size)
swap(rx,ry);
delate(ry,bel[tree[rx].pos]);
return;
}
}slay;
struct DSU{
int fa[MAX];
void init(int n){
for(int i=1;i<=n;i++)
fa[i]=i;
return;
}
void father(int x,int y){
int fx=find(x),fy=find(y);
fa[fx]=fy;
return;
}
int find(int x){
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
}dsu;
int read(){
char c=getchar();
int rt=0,f=1;
while(c<'0'||c>'9'){
if(f=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rt=rt*10+c-'0';
c=getchar();
}
return rt*f;
}
int rkk[MAX],rtot;
int main(){
int n=read(),m=read();
dsu.init(n);
for(int i=1;i<=n;i++)
rkk[i]=read();
for(int i=1;i<=m;i++){
int a=read(),b=read();
dsu.father(b,a);
}
for(int i=1;i<=n;i++){
if(dsu.find(i)==i){
bel[i]=++rtot;
slay.insert(rkk[i],bel[i],i,0,0);
}
}
for(int i=1;i<=n;i++){
int fa=dsu.find(i);
if(fa!=i){
bel[i]=bel[fa];
slay.insert(rkk[i],bel[i],i,0,0);
}
}
int t=read();
while(t--){
char c=getchar();
int a=read(),b=read();
if(c=='Q')
printf("%d\n",slay.kth(b,bel[a]));
else{
slay.union_splay(bel[a],bel[b]);
}
}
return 0;
}
```
by Akrain @ 2019-09-06 20:18:10
头像，好,,,好暴力啊QAQ
by Boeing737_MAX_8 @ 2019-09-06 20:18:16
我想要你的头像..
by WhalFaling @ 2019-09-06 20:18:34
19260817警告
by shixuanyu @ 2019-09-06 20:19:04