Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
84185
492737
HINT
Source
Solution
哦，这道题几乎涵盖了treap所有操作。然后窝写挂了好~~~长时间
话说BZOJ1500窝是不是AC无望QAQ
#include <bits/stdc++.h>
using namespace std;
struct treap
{
int l, r, siz, key, val, pri;
}a[];
int root, ptot, ans; void push_up(int k)
{
a[k].siz = a[a[k].l].siz + a[a[k].r].siz + a[k].val;
} void lturn(int &k)
{
int tmp = a[k].r;
a[k].r = a[tmp].l, a[tmp].l = k;
a[tmp].siz = a[k].siz, push_up(k), k = tmp;
} void rturn(int &k)
{
int tmp = a[k].l;
a[k].l = a[tmp].r, a[tmp].r = k;
a[tmp].siz = a[k].siz, push_up(k), k = tmp;
} void insert(int &k, int x)
{
if(!k)
{
k = ++ptot, a[k].siz = a[k].val = ;
a[k].key = x, a[k].pri = rand();
return;
}
a[k].siz++;
if(x == a[k].key) a[k].val++;
else if(x < a[k].key)
{
insert(a[k].l, x);
if(a[k].pri < a[a[k].l].pri) rturn(k);
}
else
{
insert(a[k].r, x);
if(a[k].pri < a[a[k].r].pri) lturn(k);
}
} void del(int &k, int x)
{
if(!k) return;
if(x == a[k].key)
if(a[k].val > ) a[k].val--, a[k].siz--;
else if(!(a[k].l * a[k].r)) k = a[k].l + a[k].r;
else if(a[a[k].l].pri < a[a[k].r].pri)
lturn(k), del(k, x);
else rturn(k), del(k, x);
else if(x < a[k].key) a[k].siz--, del(a[k].l, x);
else a[k].siz--, del(a[k].r, x);
} int query_rank(int k, int x)
{
if(!k) return ;
if(x < a[k].key) return query_rank(a[k].l, x);
if(x == a[k].key) return a[a[k].l].siz + ;
return a[a[k].l].siz + a[k].val + query_rank(a[k].r, x);
} int query_num(int k, int x)
{
if(!k) return ;
if(x <= a[a[k].l].siz) return query_num(a[k].l, x);
if(x <= a[a[k].l].siz + a[k].val) return a[k].key;
return query_num(a[k].r, x - a[a[k].l].siz - a[k].val);
} void query_pro(int k, int x)
{
if(!k) return;
if(x <= a[k].key) query_pro(a[k].l, x);
else ans = a[k].key, query_pro(a[k].r, x);
} void query_sub(int k, int x)
{
if(!k) return;
if(x >= a[k].key) query_sub(a[k].r, x);
else ans = a[k].key, query_sub(a[k].l, x);
} int main()
{
int n, op, x;
scanf("%d", &n), srand(n);
while(n--)
{
scanf("%d%d", &op, &x);
if(op == ) insert(root, x);
if(op == ) del(root, x);
if(op == ) printf("%d\n", query_rank(root, x));
if(op == ) printf("%d\n", query_num(root, x));
if(op == ) ans = , query_pro(root, x), printf("%d\n", ans);
if(op == ) ans = , query_sub(root, x), printf("%d\n", ans);
}
return ;
}