记录编号	383042	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	0.291 s
提交时间	2017-03-15 07:49:19	内存使用	2.20 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005, inf = ~0U>>1;
int w[maxn], rd[maxn], ch[maxn][2], sz[maxn], p_, s;
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
int randint() {
	static int seed = 233;
	return seed = int(seed*48271LL%inf);
}
int newnode(int v) {
	w[++p_] = v; rd[p_] = randint();
	sz[p_] = 1; ch[p_][0] = ch[p_][1] = 0;
	return p_;
}
void up(int x) { sz[x] = sz[lc(x)]+sz[rc(x)]+1; }
void rot(int &x, int c) {
	int y = ch[x][c^1];
	ch[x][c^1] = ch[y][c];
	ch[y][c] = x;
	up(x); up(y); x = y;
}
void ins(int v, int &x=s) {
	if(!x) { x = newnode(v); return; }
	int c = w[x]<v; 
	ins(v, ch[x][c]); ++sz[x];
	if(rd[ch[x][c]]>rd[x]) rot(x, c^1);
}
void del(int v, int &x=s) {
	if(w[x]==v) {
		if(!lc(x)) { x = rc(x); return; }
		if(!rc(x)) { x = lc(x); return; }
		int c = rd[lc(x)]<rd[rc(x)];
		rot(x, c^1); del(v, ch[x][c^1]);
	} else del(v, ch[x][w[x]<v]); up(x);
}
int kth(int k, int x=s) {
	int size = sz[lc(x)]+1;
	if(size==k) return x;
	if(size>k) return kth(k, lc(x));
	return kth(k-size, rc(x));
}
int rank(int v, int x=s) {
	int c = w[x]<v, ans = 0;
	if(c) ans += sz[lc(x)]+1;
	if(ch[x][c]) return ans+rank(v, ch[x][c]);
	return ans+1;
}
int pre(int v) { return kth(rank(v)-1); }
int nex(int v) { return kth(rank(v+1)); }
int main() {
	freopen("phs.in", "r", stdin);
	freopen("phs.out", "w", stdout);
	int Q, op, v; scanf("%d", &Q);
	while(Q--) {
		scanf("%d%d", &op, &v);
		if(op==1) ins(v);
		else if(op==2) del(v);
		else if(op==3) printf("%d\n", rank(v));
		else if(op==4) printf("%d\n", w[kth(v)]);
		else if(op==5) printf("%d\n", w[pre(v)]);
		else if(op==6) printf("%d\n", w[nex(v)]);
	}
	getchar(), getchar();
	return 0;
}