自己造了许多数与第一个题解对比没啥问题, 讨论区说的问题我也解决了但就是全wa求大佬看看。
代码
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<string>
#include<cstring>
#define maxn 1000019
#define INF 2147483647
using namespace std;
int n; //操作的个数;
int ch[maxn][2]; //树堆
int val[maxn]; //值
int more[maxn]; // 多余的
int prio[maxn]; // 关键值
int child[maxn];
int tot;
int root; //树根
int input1(){ //输入
int sign = 1 ,out = 0;
char s;
s = getchar();
while(s >'9' || s < '0'){
sign = -1;
s = getchar();
}
while(s <= '9' && s >='0'){
out = out * 10 + s - '0';
s = getchar();
}
return out * sign;
}
int new1(int v){ //新建节点
val[++tot] = v;
prio[tot] = rand();
child[tot] = 1;
more[tot] = 1;
return tot;
}
void update(int id){ //更新节点的孩子数量便于之后按排名查找
child[id] = child[ch[id][0]] + child[ch[id][1]] + more[id];
}
void build(){ // 建树
root = new1(-INF);
ch[root][1] = new1(INF);
update(root);
}
void Rotate(int &id, int d){ //d = 0 左旋 1右旋
int temp = ch[id][1^d];
ch[id][1^d] = ch[temp][d];
ch[temp][d] = id;
id = temp;
update(ch[id][d]);
update(id);
}
void insert(int &id , int v){ //插入节点
if(!id){
id = new1(v);
return;
}
if(val[id] == v){
more[id]++;
}
else{
int d = v > val[id]? 1:0;
insert(ch[id][d],v);
if(prio[ch[id][d]] > prio[id]){
Rotate(id,1^d);
}
}
update(id);
}
void remove(int &id , int v){ // 删除节点
if(!id) return;
if(val[id] == v){
if(more[id] > 1){
more[id]--;
update(id);
return;
}
if(ch[id][0] || ch[id][1]){
if(!ch[id][1] || prio[ch[id][0]] > prio[ch[id][1]]){
Rotate(id,1);
remove(ch[id][1],v);
}
else{
Rotate(id,0);
remove(ch[id][0],v);
}
update(id);
}
else{
id = 0;
}
return;
}
v< val[id] ? remove(ch[id][0],v):remove(ch[id][1],v);
update(id);
}
int get_rank(int id,int v){
if(!id) return 0;
if(val[id] == v){
return child[ch[id][0]]+1;
}
else if(val[id] >v){
return get_rank(ch[id][0],v);
}
else{
return child[ch[id][0]] + more[id] + get_rank(ch[id][1], v);
}
}
int get_val(int id,int x){
if(!id) return INF;
if(x <= child[ch[id][0]]){
return get_val(ch[id][0],x);
}
else if(x <= child[ch[id][0]] + more[id]){
return val[id];
}
else{
return get_val(ch[id][1],x - child[ch[id][0]] - more[id]);
}
}
int get_next(int v){
int id = root,next = 0;
while(id){
if(val[id] > v){
next= val[id];
id = ch[id][0];
}
else{
id = ch[id][1];
}
}
return next;
}
int get_pre(int v){
int id = root ,pre = 0;
while(id){
if(val[id] < v){
pre = val[id];
id = ch[id][1];
}
else{
id = ch[id][0];
}
}
return pre;
}
int main(){
build();
int n = input1();
for(int i = 1 ; i<= n ; i++){
int order = input1();
int num = input1();
if(order == 1){
insert(root, num); //如果不存在该数则先插入(存在也先插入 对排名查找不影响)
cout << get_rank(root,num) -1 << endl; //查找
remove(root,num); // 删除
}
if(order == 2){
if(num <=0){
cout << INF << endl;
continue;
}
cout << get_val(root,num+1) << endl;
}
if(order == 3){
insert(root, num);
cout << get_pre(num) << endl;
remove(root,num);
}
if(order == 4){
insert(root, num);
cout << get_next(num) << endl;
remove(root,num);
}
if(order == 5){
insert(root, num);
}
}
return 0;
}