蓝桥杯算法提高VIP-幸运顾客 （C++代码）

        Splay 全局 Kth

参考代码:

#include <bits/stdc++.h>
constexpr auto Inf = 0x3F3F3F3F;
typedef long long LL;
using namespace std;

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) != 'Q' && o != 'D'); return o;
	}
}
using namespace IO;

const int SIZE = 1E5 + 7;

struct Node {
	int son[2], Fa, sze, w, c;
} Node[SIZE << 4]; int Ind, Root;

inline void pushup(int now) {
	Node[now].sze = Node[Node[now].son[1]].sze + Node[Node[now].son[0]].sze + Node[now].c;
}

inline int which(int now) {
	return now == Node[Node[now].Fa].son[1];
}

void Rot(int now) {
	int F = Node[now].Fa, FF = Node[F].Fa, w = which(now);
	Node[Node[now].son[!w]].Fa = F, Node[F].son[w] = Node[now].son[!w];
	Node[now].Fa = FF, Node[FF].son[which(F)] = now;
	Node[now].son[!w] = F, Node[F].Fa = now; pushup(F), pushup(now);
}

void Splay(int now, int pos) {
	for (int F = Node[now].Fa; F != pos; Rot(now), F = Node[now].Fa)
		if (Node[F].Fa != pos)
			which(now) ^ which(F) ? Rot(now) : Rot(F);
	if (!pos) Root = now;
}

int Ins(int& now, int F, int w) {
	if (!now) {
		now = ++Ind, Node[now].Fa = F, Node[now].sze = Node[now].c = 1, Node[now].w = w; return now;
	}
	if (Node[now].w == w) {
		Node[now].c++, pushup(now); return now;
	}
	int pos = Ins(Node[now].son[Node[now].w < w], now, w); pushup(now); return pos;
}

void Ins(int w) {
	int pos = Ins(Root, 0, w); Splay(pos, 0);
}

int Kth(int now, int K) {
	if (K >= Node[Node[now].son[0]].sze + 1 && K <= Node[Node[now].son[0]].sze + Node[now].c) return now;
	if (K <= Node[Node[now].son[0]].sze) return Kth(Node[now].son[0], K);
	return Kth(Node[now].son[1], K - Node[Node[now].son[0]].sze - Node[now].c);
}

int main() {
	int N = read(), Tmp, K = 1; Ins(Inf), Ins(-Inf);
	while (N--) {
		Tmp = read();
		if (~Tmp)
			Ins(Tmp);
		else
			printf("%d\n", Node[Kth(Root, K++ + 1)].w);
	}
}