RT,目测是操作三有问题,不过也不排除前两个操作的锅
#include <bits/stdc++.h>
#define int1 int
#define N 200000
#define INF 1145141919
using namespace std;
int1 n,opt,x,rt,tot;
struct treap{
int1 ls,rs,cnt,siz,pty,val;
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define cnt(x) tree[x].cnt
#define pty(x) tree[x].pty
#define siz(x) tree[x].siz
#define val(x) tree[x].val
} tree[N + 5];
int1 read(){
int1 x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)){
if (ch == '-'){
f = -1;
}
ch = getchar();
}
while (isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void uprint(int1 x){
if (x >= 10){
uprint(x / 10);
}
putchar(x % 10 ^ 48);
return ;
}
void print(int1 x){
if (x < 0){
putchar('-');
x = -x;
}
uprint(x);
return ;
}
void ps(int1 x){
print(x);
putchar(' ');
return ;
}
void pe(int1 x){
print(x);
putchar('\n');
return ;
}
int1 rd(){//随机优先级
return rand() * rand();
}
void upd(int1 &x){
siz(x) = siz(ls(x)) + siz(rs(x)) + cnt(x);
}
void zig(int1 &x){//右旋
int1 y = ls(x);
ls(x) = rs(y);
rs(y) = x;
siz(y) = siz(x);
x = y;
upd(rs(x));
upd(x);
return ;
}
void zag(int1 &x){//左旋
int1 y = rs(x);
rs(x) = ls(y);
ls(y) = x;
siz(y) = siz(x);
x = y;
upd(ls(x));
upd(x);
return ;
}
void insert(int1 x,int1 &now){//插入
if(!now){//新节点
val(now = ++tot) = x,pty(now) = rd();
ls(now) = rs(now) = 0;
cnt(now) = siz(now) = 1;
return ;
}
siz(now)++;
if(x == val(now)){//原有节点
cnt(now)++;
return ;
}
if(x < val(now)){
insert(x,ls(now));
}else{
insert(x,rs(now));
}
if(ls(now) && pty(ls(now)) < pty(now)){//调整树高
zig(now);
}
if(rs(now) && pty(rs(now)) < pty(now)){//同上
zag(now);
}
upd(now);
return ;
}
void del(int1 x,int1 &now){//删除(应该不会有**题目删除不存在的元素吧)
if(!now){//找不到就润了
return ;
}
siz(now)--;
if(x == val(now)){//找到了
cnt(now)--;
if(!cnt(now)){//多个只删除一个
if(!ls(now) || !rs(now)){//叶子或者链节点
now = ls(now) + rs(now);
}else if(pty(ls(now)) < pty(rs(now))){//左儿子优先
zig(now);
del(x,now);
}else{//右儿子优先
zag(now);
del(x,now);
}
}
return ;
}
if(x < val(now)){
del(x,ls(now));
}else{
del(x,rs(now));
}
upd(now);
return ;
}
int1 xrank(int1 x){//查询x的排名
int1 now = rt,s = 0;
while(now){
if(x == val(now)){
return siz(ls(now)) + s + 1;
}
if(x < val(now)){
now = ls(now);
}else{
s += siz(ls(now)) + cnt(now);
now = rs(now);
}
}
return s + 1;
}
int1 rankx(int1 x){//查询第x名的数
int1 now = rt;
while(now){
if(siz(ls(now)) < x && x <= siz(ls(now)) + cnt(now)){
return val(now);
}
if(x <= siz(ls(now))){
now = ls(now);
}else{
x -= siz(ls(now)) + cnt(now);
now = rs(now);
}
}
return INF;
}
int1 pre(int1 x){//查询前驱
int1 now = rt,s = -INF;
while(now){
if(val(now) < x){
s = val(now),now = rs(now);
}else{
now = ls(now);
}
}
return s;
}
int1 nex(int1 x){//查询后继
int1 now = rt,s = INF;
while(now){
if(val(now) > x){
s = val(now),now = ls(now);
}else{
now = rs(now);
}
}
return s;
}
int main(){
srand(time(0));
n = read();
while(n--){
opt = read(),x = read();
if(opt == 1){
insert(x,rt);
}else if(opt == 2){
del(x,rt);
}else if(opt == 3){
pe(xrank(x));
}else if(opt == 4){
pe(rankx(x));
}else if(opt == 5){
pe(pre(x));
}else{
pe(nex(x));
}
}
return 0;
}
有意思的是#5:
50
1 577793
1 408221
1 880861
2 408221
1 460353
1 223489
6 577713
4 2
5 889905
2 880861
1 100033
1 73956
1 22575
5 583761
6 571549
1 812645
4 3
1 643621
1 451623
6 14895
1 556691
4 1
1 225789
2 22575
1 632329
3 73956
1 316785
5 101413
4 11
5 639414
6 636353
1 272382
1 434049
2 643621
1 99617
2 577793
1 921581
1 894033
3 223489
1 767367
3 272382
1 642721
1 272033
3 632329
1 737721
1 864513
5 746457
1 877545
1 51097
1 484817
我本地输出(也就是正确输出):
577793
460353
880861
577793
577793
100033
22575
22575
1
100033
643621
632329
643621
4
6
13
737721
但注释掉 srand(time(0)); 并交上去后倒数第二行输出 12……