最近在学高级数据结构，AVL、BST、SPLAY、Treap、红黑树等，能够快速实现AVL、BST、SPLAY、Treap，以及会利用简单变形解决某些问题就达到要求了。

大学计算机专业的学生，数据结构书上的所有数据结构能够快速实现，对计算机理论不至于精通，但要熟悉，随便提出一个基础理论至少不陌生。高数、现代、概率论都要达到熟悉的地步。

Treap,顾名思义，Tree+Heap的简称，与BST不同，节点还附加了一个随机优先级来平衡树，所以又带有堆的性质，可以证明最坏的查找、删除效率为O(logn)，它可以做到set做不到的事，如快速求第K大值，以及求值x的名次，也被称作名次树。如果附加的优先级是固定的话，那么就成了笛卡尔树。

                                              Treap

练习题:

问题：玩星际争霸时，我们常常会不顾一切地大肆建造军队以扩充自己的战斗力。当我们快速建造军队时，我们总想知道这支部队的战斗力，以便设计好战略。你的任务是设计出一个能够快速回答一支部队的战斗力强弱的程序，部队的战斗力就是部队的人数。

1. C num，往编号为num的部队里加一个兵，如果当前还没有编号为num的部队，则建立这支部队并添加一个兵；
2. D num，代表编号为num的部队里一个兵牺牲了，如果此时部队里没有兵了，则删掉此部队，如果没有编号为num的部队，忽略此操作。
3. M x<y，表示将y里面的兵合并到x中，然后y消失，如果x或者y中任意一个数不存在，则忽略此次操作。
4. 其中0<x,y,num<10^12

问：有n(<=15000)条命令，m<=5000组询问，每次询问请输出第k大值。

其实可以用map来解决的，但也可以用Treap来解决，可以粗略的判断时间复杂度大约为O(nlogn)。

首先Treap以num为主键，维护一个部队人数，然后按照题目给出的要求来进行模拟即可，最终求结果时，由于不是求键值第K大，所以需要遍历一次树，然后求出的结果进行排序，合法就输出，若k>size，则输出NO。

/*
Sample intput:

5
C 4
C 8
M 8<4
D 4
C 5
3
1 2 3

Sample output:
	2
	1
	NO
*/

#include <iostream>
#include <set>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
using namespace std;

typedef long long LL;

struct Node
{
	Node *ch[2];
	LL r, s, v;
	LL num;
	Node(LL v=0):v(v) { ch[0] = ch[1] = NULL; s = 1; r = rand() ; num = 1; }
	
	LL cmp(LL x) const
	{
		if(x == v) return -1;
		return x < v? 0:1;
	}
	void pushup()
	{
		s = 1;
		if(ch[0] != NULL) s += ch[0]->s;
		if(ch[1] != NULL) s += ch[1]->s;
	}
};

void rotate(Node *&o, LL d)
{
	Node *k = o->ch[d^1];
	o->ch[d^1] = k->ch[d], k->ch[d] = o;
	o->pushup(), k->pushup();
	o = k;
}

void insert(Node *&o, LL x)
{
	if(o == NULL) o = new Node(x);
	else
	{
		LL d = x < o->v? 0:1;
		insert(o->ch[d], x);
		if(o->ch[d]->r > o->r) rotate(o, d^1);
	}
	o->pushup();
};

void remove(Node *&o, LL x)
{
	LL d = o->cmp(x);
	if(d == -1)
	{
		Node *u = o;
		if(o->ch[0] != NULL && o->ch[1] != NULL)
		{
			LL d2 = (o->ch[0]->v > o->ch[1]->v)? 1:0;
			rotate(o, d2); remove(o->ch[d2], x);
		}
		else
		{
			if(o->ch[0] == NULL) o = o->ch[1]; else o = o->ch[0];
			delete u;
		}
	}
	else remove(o->ch[d], x);
	
	if(o != NULL) o->pushup();
}

Node* find(Node *o, LL x)
{
	if(o == NULL) return NULL;
	LL d = o->cmp(x);
	if(d == -1) return o;
	return find(o->ch[d], x);
}

void Travel(Node *o, vector<LL> &a)
{
	if(o == NULL) return ;
	if(o->num > 0) a.push_back(o->num);
	Travel(o->ch[0], a);
	Travel(o->ch[1], a);
}

/////////////////////////////////////////////
const LL maxn = 15000 + 100;
LL b[maxn];

LL cmp(LL a, LL b)
{
	return a > b;
}

int main()
{
	LL n, m;
	while(~scanf("%I64d", &n))
	{
		Node *root = NULL;
		for(LL i = 1; i <= n; i++)
		{
			char cmd[10];
			scanf("%s", &cmd);
			if(cmd[0] == 'C')
			{
				LL v; scanf("%I64d", &v);
				Node *o = find(root, v);
				if(o != NULL)
				{
					o->num++;
				}
				else insert(root, v);
			}
			else if(cmd[0] == 'D')
			{
				LL v; scanf("%I64d", &v);
				Node *o = find(root, v);
				if(o == NULL) continue ;
				else if(o->num <= 1) remove(root, o->v);
			}
			else if(cmd[0] == 'M')
			{
				char s[100];
				scanf("%s", s);
				LL x, y;
				sscanf(s, "%I64d%*c%I64d", &x, &y);
				Node *o1 = find(root, x), *o2 = find(root, y);
				if(o1 == NULL || o2 == NULL) continue ;
				o1->num += o2->num;
				remove(root, o2->v);
			}
		}
		
		scanf("%I64d", &m);
		
		vector<LL> a;
		Travel(root, a);
		
		LL size = 0;
		for(LL i = 0; i < a.size(); i++)
		{
			if(a[i] > 0) b[++size] = a[i];
		}
		sort(b+1, b+size+1, cmp);
		
		while(m--)
		{
			LL k; scanf("%I64d", &k);
			if(k > size) printf("NO\n");
			else printf("%I64d\n", b[k]);
		}
	}
	return 0;
}