Treap求条 玄关
查看原帖
Treap求条 玄关
730195
Little_Cabbage楼主2024/2/28 17:00
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 10010;
int read() {
	char c = 0;
	int f = 1, x = 0;
	while (c < '0' || c > '9') {
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + (int)(c - '0');
		c = getchar();
	}
	return f * x;
}
void write(int x) {
	if (x == 0) {
		putchar(x + '0');
		return ;
	}
	if (x < 0) {
		putchar('-');
		x = abs(x);
	}
	stack<int> s;
	while (x) {
		s.push(x % 10);
		x /= 10;
	}
	while (s.size()) {
		putchar(s.top() + '0');
		s.pop();
	}
}
int n, k, tot, root;
map<int, int> ma;
#define ls(k) TreapTree[k].left_son
#define rs(k) TreapTree[k].right_son
#define fa(k) TreapTree[k].father
#define va(k) TreapTree[k].val
#define pri(k) TreapTree[k].priority
#define lss(k) TreapTree[k].left_son_sum
#define rss(k) TreapTree[k].right_son_sum
#define cn(k) TreapTree[k].cnt
struct Treap_Tree {
	int left_son, right_son;
	int father;
	int val;
	int priority;
	int left_son_sum, right_son_sum;
	int cnt;
} TreapTree[N];
void Zig(int x) {
	int y = fa(x);
	ls(y) = rs(x);
	if (rs(x)) fa(rs(x)) = y;
	fa(x) = fa(y);
	if (fa(y)) {
		if (ls(fa(y)) == y)
			ls(fa(y)) = x;
		else
			rs(fa(y)) = x;
	}
	rs(x) = y;
	fa(y) = x;
	lss(y) = rss(x);
	rss(x) = lss(y) + rss(y) + 1;
}
void Zag(int x) {
	int y = fa(x);
	rs(y) = ls(x);
	if (ls(x)) fa(ls(x)) = y;
	fa(x) = fa(y);
	if (fa(y)) {
		if (ls(fa(y)) == y)
			ls(fa(y)) = x;
		else
			rs(fa(y)) = x;
	}
	ls(x) = y;
	fa(y) = x;
	rss(y) = lss(x);
	lss(x) = lss(y) + rss(y) + 1;
}
void Insert(int &id, int x) {
	if (!id) {
		id = ++tot;
		TreapTree[id].val = x;
		TreapTree[id].left_son = TreapTree[id].right_son = 0;
		TreapTree[id].left_son_sum = TreapTree[id].right_son_sum = 0;
		TreapTree[id].priority = rand();
		return ;
	}
	if (x < va(id)) {
		Insert(ls(id), x);
		lss(id)++;
		if (pri(ls(id)) < pri(id)) 
			Zig(id);
	} else {
		Insert(rs(id), x);
		rss(id)++;
		if (pri(rs(id)) < pri(id))
			Zag(id);
	}
}
int Query() {
	int t = k;
	int y = 1;
	while(y) {
		if (lss(y) + 1 == t)
			return va(y);
		if (t < lss(y))
			y = ls(y);
		else {
			t = t - lss(y) - 1;
			y = rs(y);
		}
	}
}
signed main() {
	srand(time(NULL));
	n = read(), k = read();
	for (int i = 1; i <= n; i++) {
		int x;
		x = read();
		if (ma[x]) continue;
		int t = 1;
		Insert(t, x);
	}
	if (k > tot) {
		cout << "NO RESULT";
		return 0;
	}	
	cout << Query();
	return 0;
}
2024/2/28 17:00
加载中...