大规模单步调试现场
这里只提供模板，详细解说请参见这位大佬的题解。
PS：这位大佬的rank操作跑的飞飞飞飞飞慢，利用Find操作优化之后可以极大优化时间
PPS:这位大佬的ins操作里判空也有点问题，修改后有两种写法：
1.直接在开始时ins一个\(INF\)和一个\(-INF\)、之后3号操作找到的\(rank\)+1后输出，4号操作找排名为x+1的数。
2.把判空改为本人的样式
#include<cstdio>
#include<iostream>
#include<cmath>
#include<fstream>
#include<time.h>
using namespace std;
char *p1,*p2,buf[1<<20];
#define GC (p1==p2&&(p1=buf,p2=buf+fread(buf,1,1<<20,stdin),p1==p2)?0:(*(p1++)))
//#define GC getchar()
inline int in()
{
int x=0,w=0;
char ch=0;
while(!isdigit(ch)){
w|=ch=='-';
ch=GC;
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=GC;
}
return w?-x:x;
}
struct node{
int id,f;
int son[2];
int size;
int cnt;
};
const int maxn=200010;
struct tree{
node t[maxn];
int n,points;
#define root t[0].son[1]
void updata(int p){
t[p].size=t[t[p].son[0]].size+t[t[p].son[1]].size+t[p].cnt;
}
int identify(int p)
{
return t[t[p].f].son[0]==p?0:1;
}
void connect(int p,int f,int son)
{
t[p].f=f;
t[f].son[son]=p;
return;
}
void rotate(int p)
{
int f=t[p].f;
int ff=t[f].f;
int fs=identify(f);
int s=identify(p);
int Os=t[p].son[s^1];
connect(Os,f,s);
connect(f,p,(s^1));
connect(p,ff,fs);
updata(f);
updata(p);
}
void splay(int now,int to)
{
to=t[to].f;
while(t[now].f!=to){
int up=t[now].f;
if(t[up].f==to)rotate(now);
else {
if(identify(up)==identify(now)){
rotate(up);
rotate(now);
}
else{
rotate(now);
rotate(now);
}
}
}
}
int add_point(int val,int f){
n+=1;
t[n].id=val;
t[n].f=f;
t[n].cnt=t[n].size=1;
return n;
}
void destroy(int p){
t[p].cnt=t[p].f=t[p].id=t[p].size=t[p].son[1]=t[p].son[0]=0;
if(p==n)n-=1;
}
int find(int val){
int now=root;
while(1){
if(t[now].id==val){
splay(now,root);
return now;
}
int nex=val<t[now].id?0:1;
if(!t[now].son[nex])return 0;
now=t[now].son[nex];
}
}
int ins(int val){
points+=1;
if(points==1){
root=n+1;
add_point(val,0);
return 0;
}
int now=root;
while(1){
t[now].size+=1;
if(val==t[now].id){
t[now].cnt+=1;
return now;
}
int nex=val<t[now].id?0:1;
if(!t[now].son[nex]){
add_point(val,now);
t[now].son[nex]=n;
return n;
}
now=t[now].son[nex];
}
splay(now,root);
return 0;
}
void push(int val){
int add=ins(val);
splay(add,root);
}
void del(int val){
int tar=find(val);
if(!tar)return;
points-=1;
if(t[tar].cnt>1){
t[tar].cnt-=1;
t[tar].size-=1;
return;
}
if(!t[tar].son[0]){
root=t[tar].son[1];
t[root].f=0;
}
else{
int ls=t[tar].son[0];
while(t[ls].son[1])ls=t[ls].son[1];
splay(ls,t[tar].son[0]);
int rs=t[tar].son[1];
connect(rs,ls,1);
connect(ls,0,1);
updata(ls);
}
destroy(tar);
}
int rank(int val){
// int res=0,now=root;
// while(1){
// if(t[now].id==val)return res+t[t[now].son[0]].size+1;
// if(!now)return 0;
// if(val<t[now].id)now=t[now].son[0];
// else{
// res+=t[t[now].son[0]].size+t[now].cnt;
// now=t[now].son[1];
// }
// }
// splay(now,root);
// return 0;
find(val);
return t[t[root].son[0]].size+1;
}
int get_k(int val){
if(val>points)return -23333333;
int now=root;
while(1){
int tmp=t[now].size-t[t[now].son[1]].size;
if(val>t[t[now].son[0]].size&&val<=tmp)break;
if(val<tmp)now=t[now].son[0];
else{
val-=tmp;
now=t[now].son[1];
}
}
splay(now,root);
return t[now].id;
}
int lower(int val)
{
int now=root;
int res=-23333333;
while(now){
if(t[now].id<val&&t[now].id>res)res=t[now].id;
if(val>t[now].id)now=t[now].son[1];
else now=t[now].son[0];
}
return res;
}
int upper(int val)
{
int now=root;
int res=23333333;
while(now){
if(t[now].id>val&&t[now].id<res)res=t[now].id;
if(val<t[now].id)now=t[now].son[0];
else now=t[now].son[1];
}
return res;
}
#undef root
}tr;
int n;
int main()
{
// freopen("splay.in","r",stdin);
// freopen("splay.out","w",stdout);
// clock_t st,fs;
// st=clock();
// ofstream fl("time.txt");
n=in();
int i;
// tr.push(23333333);
// tr.push(-23333333);
for(i=1;i!=n+1;++i){
int ch,x;
// fs=clock();
// fl<<fs-st<<endl;
ch=in();x=in();
switch(ch){
case 1:{
tr.push(x);
break;
}
case 2:{
tr.del(x);
break;
}
case 3:{
printf("%d\n",tr.rank(x));
break;
}
case 4:{
printf("%d\n",tr.get_k(x));
break;
}
case 5:{
printf("%d\n",tr.lower(x));
break;
}
case 6:{
printf("%d\n",tr.upper(x));
break;
}
}
}
}原文：https://www.cnblogs.com/cooper233/p/12000363.html