可能有重复数字的，这个比较复杂，你这样不一定，要加一个函数统计重复个数
我把我的代码给你看下
by cmll02 @ 2020-01-16 22:33:12
```cpp
#include <stdio.h>
#include <string.h>
inline long long read()
{
long long num = 0; int f = 1; char c = getchar();
while (c < 48 || c > 57)
{ if (c == '-')f = -1; c = getchar(); }
while (c >= 48 && c <= 57)
num = (num << 3) + (num << 1) + (c ^ 48), c = getchar();
return num*f;
}
#include <time.h>
#include <stdlib.h>
int rrnk, lrnk;
template<typename T = int>
class Treap
{
public:
struct Node{
Node *ch[2]; //左右子树
int r; //优先级。数值越大，优先级越高
T v;
int s;
int cmp(T x)const
{
if (x == v) return -1;
return x < v ? 0 : 1;
}
int Cmp(T z)
{
if (z == s)return -1;
return z < s ? 0 : 1;
}
void maintain()
{
s = 1;
if (ch[0])s += ch[0]->s;
if (ch[1])s += ch[1]->s;
}
};
protected:
int samenumber(Node *o, T x)
{
if (!o)return 0;
if (o->v != x)
{
if (o->v>x)
{
return samenumber(o->ch[0], x);
}
else
{
return samenumber(o->ch[1], x);
}
}
return 1 + samenumber(o->ch[0], x) + samenumber(o->ch[1], x);
}
int find(Node *o, T x){
int p = 0;
while (o != NULL){
int d = o->cmp(x);
if (d == -1)
return p + (o->ch[1] ? o->ch[1]->s + 1 : 1) + 0 * ((rrnk = samenumber(o->ch[1], x)) + (lrnk = samenumber(o->ch[0], x))); //存在
else p += (d ? 0 : (o->ch[1] ? o->ch[1]->s + 1 : 1)), o = o->ch[d];
}
return 0; //不存在
}
//d=0代表左旋,d=1代表右旋
void rotate(Node* &o, int d){
Node *k = o->ch[d ^ 1]; o->ch[d ^ 1] = k->ch[d]; k->ch[d] = o; o->maintain(); k->maintain(); o = k;
}
//在以o为根的子树中插入键值x，修改o
void Insert(Node* &o, T x){
if (o == NULL)
{
o = new Node(); o->ch[0] = o->ch[1] = NULL; o->v = x; o->r = rand();
}
else
{
//int d = (x<o->v ? 0 : 1);
int d = (x<o->v ? 0 : 1);
Insert(o->ch[d], x);
if (o->ch[d]->r > o->r)
rotate(o, d ^ 1);
}
if (o)
o->maintain();
};
void Remove(Node* &o, T x){
int d = o->cmp(x);
if (d == -1){
Node *u = o;
if (o->ch[0] == NULL) { o = o->ch[1]; delete u; }
else if (o->ch[1] == NULL) { o = o->ch[0]; delete u; }
else{
int d2 = (o->ch[0]->r>o->ch[1]->r ? 1 : 0);
rotate(o, d2);
Remove(o->ch[d2], x);
}
}
else
Remove(o->ch[d], x);
if (o)
o->maintain();
}
public:
static const T _TREAP_ERROR_404_NOT_FOUND = ((T)(0x1f2e3d4c));
protected:
T FindKth(Node *&o, int k)
{
if (k<1 || k>o->s)return _TREAP_ERROR_404_NOT_FOUND;
int s = o->ch[1] ? o->ch[1]->s : 0;
if (k <= s)return FindKth(o->ch[1], k);
if (k == s + 1)return o->v;
return FindKth(o->ch[0], k - s - 1);
}
/*int GetRank(Node *&o, T p, int r)
{
int s=
if (o->s)
}*/
void removetree(Node *&x)
{
if (!x)return;
if (x->ch[0] != NULL) removetree(x->ch[0]);
if (x->ch[1] != NULL) removetree(x->ch[1]);
delete x;
x = NULL;
}
Node *root = NULL;
public:
int size = 0;
int insert(T q){ Insert(root, q); return ++size; }
int remove(T q){ if (!find(root, q))return 0; Remove(root, q); return --size; }
int Find(T q){ return find(root, q); }
int findkth(int k){ return FindKth(root, k); }
/*int getrank(T q){ if (!find(root, q))return 0; return GetRank(root, q, 1); }*/
int getrank(T q){ return find(root, q); }
~Treap(){ if (root)removetree(root); }
private:
void fdebug(Node *a)
{
if (!a)return;
fdebug(a->ch[0]);
printf("%d ", a->v);
fdebug(a->ch[1]);
}
public:
void debug(){ fdebug(root); }
};
int main()
{
srand(time(0));
Treap<int> t;
int n;
n = read();
while (n--)
{
int k, q;
k = read(), q = read();
switch (k)
{
case 1:
t.insert(q);
break;
case 2:
t.remove(q);
break;
case 3:
if (t.Find(q))
printf("%d\n", t.size + 1 - t.getrank(q) - lrnk);
else
{
t.insert(q);
printf("%d\n", t.size + 1 - t.getrank(q) - lrnk);
t.remove(q);
}
break;
case 4:
printf("%d\n", t.findkth(t.size + 1 - q));
break;
case 5:
if (t.Find(q))
printf("%d\n", t.findkth(t.getrank(q) + lrnk + 1));
else
{
t.insert(q);
printf("%d\n", t.findkth(t.getrank(q) + lrnk + 1));
t.remove(q);
}
break;
default:
if (t.Find(q))
printf("%d\n", t.findkth(t.getrank(q) - rrnk - 1));
else
{
t.insert(q);
printf("%d\n", t.findkth(t.getrank(q) - rrnk - 1));
t.remove(q);
}
}
// t.debug(); puts("");
}getchar();
return 0;
}
```
by cmll02 @ 2020-01-16 22:35:01