评测记录

treap,呜真的没有下载次数了

初学者，信心打击好大，昨天学splay和替罪羊都过了

求大佬帮调

恩情永世不忘

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<ctime>
#define INF 0x7fffffff
using namespace std;

template<class T>inline
void read(T &x)
{
		x = 0; int f = 1; char c = getchar();
		while (!isdigit(c)){if (c == '-') f = -1; c = getchar();}
		while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
		x *= f;
}

const int MAXN = 100005;
struct Treap{ 
		int l, r;//左、右儿子 
		int val, date;//数值，权值 
		int cnt, size;//节点副本数量，整棵树大小 
}tree[MAXN];
int n, idx, rt;

inline int New(int val)//新建 
{
		tree[++ idx].val = val;
		tree[idx].date = rand();
		tree[idx].cnt = tree[idx].size = 1;
		return idx;
}

inline void Update(int p)//更新tree[p].size 
{
		tree[p].size = tree[tree[p].l].size + tree[tree[p].r].size + tree[p].cnt;
}

inline void Build()//初始化init 
{
		New(~INF); New(INF);
		rt = 1; tree[1].r = 2;
		Update(rt);
}

inline int Getrank(int p, int val)//查询排名（操作三） 
{
		if (!p) return 0;
		if (val == tree[p].val) return tree[tree[p].l].size + 1;
		if (val < tree[p].val) return Getrank(tree[p].l, val);
		return Getrank(tree[p].r, val) + tree[tree[p].l].size + tree[p].cnt;
}

inline int Getval(int p, int rank)//查询值（操作四） 
{
		if (!p) return INF;
		if (tree[tree[p].l].size >= rank) return Getval(tree[p].l, rank);
		if (tree[tree[p].l].size + tree[p].cnt >= rank) return tree[p].val;
		return Getval(tree[p].r, rank - tree[tree[p].l].size - tree[p].cnt);
}

inline void zip(int &p)//左旋 
{
		int q = tree[p].l;
		tree[p].l = tree[q].r, tree[q].r = p, p = q;
		Update(tree[p].r), Update(p);
}

inline void zap(int &p)//右旋 
{
		int q = tree[p].r;
		tree[p].r = tree[q].l, tree[q].l = p, p = q;
		Update(tree[p].l), Update(p);
}

inline void Insert(int &p, int val)//操作一 
{
		if (!p) {
				p = New(val);
				return;
		}
		
		if (tree[p].val == val) {
				++ tree[p].cnt, Update(p);
				return;
		}
		
		if (tree[p].val > val) {
				Insert(tree[p].l, val);
				if (tree[p].date < tree[tree[p].l].date) zip(p);
		}
		else {
				Insert(tree[p].r, val);
				if (tree[p].date < tree[tree[p].r].date) zap(p);
		}
		
		Update(p);
}

inline int Getpre(int val)//操作五 
{
		int ans = 1, p = rt;
		
		while (p)
		{
				if (val == tree[p].val) {
						if (tree[p].l) {
								p = tree[p].l;
								while (tree[p].r) p = tree[p].r;
								ans = p;
						}
						break;
				}
				
				if (tree[p].val < val && tree[p].val > tree[ans].val) ans = p;
				p = (tree[p].val > val) ? tree[p].l : tree[p].r;
		}
		
		return tree[ans].val;
}

inline int Getnext(int val)//操作六 
{
		int ans = 2, p = rt;
		
		while (p)
		{
				if (val == tree[p].val) {
						if (tree[p].r > 0) {
								p = tree[p].r;
								while (tree[p].r) p = tree[p].r;
								ans = p;	
						}
						break;
				}
				
				if (tree[p].val > val && tree[p].val < tree[ans].val) ans = p;
				p = (tree[p].val > val) ? tree[p].l : tree[p].r;
		}
		
		return tree[ans].val;
}

inline void Remove(int &p, int val)//操作二 
{
		if (!p) return;
		
		if (val == tree[p].val) {
				if (tree[p].cnt > 1) {
						-- tree[p].cnt, Update(p);
						return;
				}
				
				if (tree[p].l || tree[p].r) {
						if (tree[p].r == 0 || tree[tree[p].l].date > tree[tree[p].r].date)
								zip(p), Remove(tree[p].r, val);
						else
								zap(p), Remove(tree[p].l, val);
						Update(p);
				}
				else p = 0;
				return;
		}
		
		val < tree[p].val ? Remove(tree[p].l, val) : Remove(tree[p].r, val);
		Update(p);
}

int main()
{
		Build(); srand(time(0));
		read(n);
		
		while (n --)
		{
				int opt, x;//如题 
				read(opt); read(x);
				switch (opt) {
					
				case 1:
						Insert(rt, x);
						break;
				case 2:
						Remove(rt, x);
						break;
				case 3:
						printf ("%d\n", Getrank(rt, x) - 1);
						break;
				case 4:
						printf ("%d\n", Getval(rt, x + 1));
						break;
				case 5:
						printf ("%d\n", Getpre(x));
						break;
				case 6:
						printf ("%d\n", Getnext(x));
						break;
				}
		}
		
		return 0;
}