蒟蒻调了2天了QwQ,第6组数据其中一个求排名的数据有错(我是617,答案616
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <pthread.h>
#include <bits/stdc++.h>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
//#include "file2.h"
using namespace std;
const int maxn=1005;
struct Node{
Node *child[2];//子节点
int r,v; //r为优先级,v为键值
int s; //节点总数
Node (int v):v(v){child[0]=child[1]=NULL;r=rand();s=1;}
};
void maintain(Node* &o){//同线段树一样的整理函数
o->s=1; //用到更新子节点的地方便应该整理一次
if(o->child[0]!=NULL)o->s+=o->child[0]->s;
if(o->child[1]!=NULL)o->s+=o->child[1]->s;
}
//d=0代表左旋,d=1代表右旋
void Rotate(Node* &o,int d){//向那一边旋转,根节点便会被下放到那一边
Node* k=o->child[d^1];o->child[d^1]=k->child[d];k->child[d]=o;
maintain(o);maintain(k);o=k;//先整理o,后整理k
}
void Insert(Node* &o,int x){//插入节点函数
if(o==NULL)o=new Node(x); //没有便新建一个
else{
int d=(x<o->v?0:1); //选择方向
Insert(o->child[d], x);
if(o->r < o->child[d]->r)Rotate(o, d^1);
} //子节点优先级更高,根下放到低优先级一侧,让为给高优先级
maintain(o);
}
void Remove(Node* &o,int x){//删除节点函数
if(o->v==x){//找到啦!
if(o->child[0]==NULL)o=o->child[1];//如果只找到了一个节点,那么替换掉
else if(o->child[1]==NULL)o=o->child[0];
else{ //选择优先级低的那一边
int d=(o->child[0]->r < o->child[1]->r?0:1);
Rotate(o, d);//将根节点下放到底优先级那一边
Remove(o->child[d],x);//对底优先级一侧删除
//maintain(o);
}
} //没找到,去子节点找
else if(o->v<x)Remove(o->child[1], x);
else Remove(o->child[0], x);
if(o!=NULL)maintain(o);
}
bool Find(Node* o,int x){//寻找节点,注意根节点并未引用
while(o!=NULL){ //一直找到无法找到
if(o->v == x)return true;//找到啦!
int d=(o->v>x?0:1);
o=o->child[d]; //没找到,接着找
}
return false;//没找到。
}
int Value(Node* o,int k){//这里的k值表示在以当前节点为根的情况下的排名
if(o==NULL or k<=0 or k>o->s)return 0;//找不到
int now_rank=(o->child[0]==NULL?1:o->child[0]->s+1);//寻找当前节点排名
if(now_rank==k)return o->v;//找到啦!
else if(k<now_rank)return Value(o->child[0], k);
else return Value(o->child[1], k-now_rank);
}
int Rank(Node* o,int v){
if(o==NULL)return 0;
int now_rank=(o->child[0]==NULL?1:o->child[0]->s+1);//寻找当前节点排名
if(o->v==v)return now_rank;
else if(o->v<v)return now_rank+Rank(o->child[1], v);
else return Rank(o->child[0], v);
}
int Find_pre(Node* o,int v){
int pre_num;
while (o!=NULL) {
if(o->v<v)pre_num=o->v,o=o->child[1];
else o=o->child[0];
}
return pre_num;
}
int Find_next(Node* o,int v){
int next_num;
while (o!=NULL) {
if(o->v>v)next_num=o->v,o=o->child[0];
else o=o->child[1];
}
return next_num;
}
Node* root=new Node(0x7fffffff);
int main(){
freopen("output","w",stdout);
freopen("input","r",stdin);
int n;
int opt,val;
scanf("%d",&n);
while (n--) {
scanf("%d%d",&opt,&val);
if(opt==1)Insert(root, val);
else if(opt==2)Remove(root, val);
else if(opt==3)printf("获得排名%d :%d\n",Rank(root, val),val);
else if(opt==4)printf("获得值%d\n",Value(root, val));
else if(opt==5)printf("找前驱%d\n",Find_pre(root, val));
else printf("找后继%d\n",Find_next(root, val));
}
return 0;
}