链接 思路:并查集+treap维护第k大 TLE

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<time.h>
#include<cstdlib>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
#define ll long long 
#define ull unsigned long long
#define lid (id << 1)
#define rid (id << 1 | 1)
const int N = 2e5+5;
const double alpha = 0.75;
struct treap_node{
	int ls, rs;
	int key, pri, size;
};
struct Treap{
	treap_node t[N];
	int cnt, root;
	void newnode(int x){
		++cnt;
		t[cnt].size = 1;
		t[cnt].ls = t[cnt].rs = 0;
		t[cnt].key = x;
		t[cnt].pri = rand();
	}
	void update(int u){
		t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;
	}
	void rotate(int &o, int d){ //d=0 right d=1 left
		int k;
		if (d == 1){
			k = t[o].rs;
			t[o].rs = t[k].ls;
			t[k].ls = o;
		}
		else{
			k = t[o].ls;
			t[o].ls = t[k].rs;
			t[k].rs = o;
		}
		t[k].size = t[o].size;
		update(o);
		o = k;
	}
	void insert1(int &u, int x){
		if (u == 0){
			newnode(x);
			u = cnt;
			return;
		}
		++t[u].size;
		if (x >= t[u].key) insert1(t[u].rs, x);
		else insert1(t[u].ls, x);
		if (t[u].ls != 0 && t[u].pri > t[t[u].ls].pri) rotate(u, 0);
		if (t[u].rs != 0 && t[u].pri >t[t[u].rs].pri) rotate(u, 1);
		update(u);
	}
	void del1(int &u, int x){
		--t[u].size;
		if (t[u].key == x){
			if(t[u].ls==0 && t[u].rs == 0){
				u = 0;
				return;
			}
			if(t[u].ls == 0 || t[u].rs == 0){
				u = t[u].ls + t[u].rs;
				return;
			}
			if (t[t[u].ls].pri < t[t[u].rs].pri){
				rotate(u, 0);
				del1(t[u].rs, x);
				return;
			}
			else{
				rotate(u, 1);
				del1(t[u].ls, x);
				return;
			}
		}
		if(t[u].key >= x) del1(t[u].ls, x);
		else del1(t[u].rs, x);
		update(u);
	}
	int rk1(int u, int x){
		if (u == 0) return 0;
		if (x > t[u].key) return t[t[u].ls].size + 1 + rk1(t[u].rs, x);
		return rk1(t[u].ls, x);
	}
	int kth1(int u, int k){
		if (k == t[t[u].ls].size + 1) return t[u].key;
		if (k > t[t[u].ls].size + 1) return kth1(t[u].rs, k - t[t[u].ls].size - 1);
		if (k <= t[t[u].ls].size) return kth1(t[u].ls, k);
	}
	int precursor(int u, int x){
		if (u == 0) return 0;
		if (t[u].key >= x) return precursor(t[u].ls, x);
		int tmp = precursor(t[u].rs, x);
		if (tmp == 0) return t[u].key;
		return tmp;
	}
	int successor(int u, int x){
		if (u == 0) return 0;
		if (t[u].key <= x) return successor(t[u].rs, x);
		int tmp = successor(t[u].ls, x);
		if (tmp == 0) return t[u].key;
		return tmp;
	}
	int rk(int x){
		return rk1(root, x) + 1;
	}
	int kth(int x){
		return kth1(root, x);
	}
	int pre(int x){
		return precursor(root, x);
	}
	int suc(int x){
		return successor(root, x);
	}
	void insert(int x){
		insert1(root, x);
	}
	void del(int x){
		del1(root, x);
	}
};
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;
}
Treap treap;
int n, q;
int s[N], siz[N], setnum, yuanshen;
int find(int x){
	if (s[x] == x) return x;
	return s[x] = find(s[x]);
}
void merge(int a, int b){
	int x = find(a), y = find(b);
	if (x != y){
		treap.del(siz[x]);
		treap.del(siz[y]);
		s[x] = y;
		--setnum;
		siz[y] += siz[x];
		treap.insert(siz[y]);
	}
}
int main() {
	//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	n = read();
	q = read();
	for (int i = 1;i <= n;++i){
		s[i] = i;
		siz[i] = 1;
		treap.insert(1);
	}
	setnum = n;
	while (q--){
		int op;
		cin >> op;
		if (op == 0){
			int a, b;
			a = read();
			b = read();
			merge(a, b);
		}
		else{
			int a;
			a = read();
			a = setnum - a + 1;
			printf("%d\n", treap.kth(a));
		}
	}
	return 0;
}