普通线段树

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
插入x数
删除x数(若有多个相同的数，因只删除一个)
查询x数的排名(若有多个相同的数，因输出最小的排名)
查询排名为x的数
求x的前驱(前驱定义为小于x，且最大的数)
求x的后继(后继定义为大于x，且最小的数)

输入描述

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号

输出描述

对于操作3,4,5,6每行输出一个数，表示对应答案

题解

平衡树的板子题，实际上感觉就是实现了下map功能，关于旋转，其实我认为初学者不必要理解太多原理，毕竟旋转只是为了保持一个较好的复杂度。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int>PII;
int max(int a,int b)
{if(a>=b) return a;else return b;
}
int min(int a,int b)
{if(a>=b) return b;else return a;
}
inline int read()
{int X=0; bool flag=1; char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}if(flag) return X;return ~(X-1);
}
int qmi(int a,int b,int c)    
{int res=1%c;while(b){if(b&1) res=res*a%c;a=a*a%c;b>>=1;}return res;
}
int gcd(int a,int b)   
{return b?gcd(b,a%b):a;
}
const int N=1e6+10;
struct node{int l;   //左儿子 int r;   //右儿子 int val; //权值 int size; //子树大小（包括自身） int rnd; //随机数 int ct; //当前节点的副本数 
}tr[N];
int sz; //用于创建节点 
void pushup(int u)
{tr[u].size=tr[tr[u].l].size+tr[tr[u].r].size+tr[u].ct;
}
void lturn(int &k)
{int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;tr[t].size=tr[k].size;pushup(k);k=t;
}
void rturn(int &k)
{int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;tr[t].size=tr[k].size;pushup(k);k=t;
}
void ins(int &u,int x)
{if(u==0){u=++sz;tr[u].size=tr[u].ct=1;tr[u].val=x;tr[u].rnd=rand();return ;}tr[u].size++;if(tr[u].val==x)  tr[u].ct++;else if(x>tr[u].val){ins(tr[u].r,x);if(tr[tr[u].r].rnd<tr[u].rnd) lturn(u);}else {ins(tr[u].l,x);if(tr[tr[u].l].rnd<tr[u].rnd) rturn(u);}
}
void del(int &u,int x)
{if(u==0) return;if(tr[u].val==x){if(tr[u].ct>1) tr[u].ct--,tr[u].size--;else{if(tr[u].l==0 || tr[u].r==0) u=tr[u].l+tr[u].r;else if(tr[tr[u].l].rnd<tr[tr[u].r].rnd) rturn(u),del(u,x);else lturn(u),del(u,x);}}else if(x>tr[u].val) tr[u].size--,del(tr[u].r,x);else tr[u].size--,del(tr[u].l,x);
}
int get_rank(int u,int x)
{if(u==0) return 0;if(tr[u].val==x) return tr[tr[u].l].size+1;if(x>tr[u].val) return tr[tr[u].l].size+tr[u].ct+get_rank(tr[u].r,x);else return get_rank(tr[u].l,x);
}
int get_val(int u,int x)
{if(u==0) return 0;if(x<=tr[tr[u].l].size) return get_val(tr[u].l,x);x-=tr[tr[u].l].size;if(x<=tr[u].ct) return tr[u].val;x-=tr[u].ct;return get_val(tr[u].r,x);
}
int get_pre(int u,int x)
{if(u==0) return -INF;if(tr[u].val<x) return max(tr[u].val,get_pre(tr[u].r,x));else return get_pre(tr[u].l,x); 
}
int get_next(int u,int x)
{if(u==0) return INF;if(tr[u].val>x) return min(tr[u].val,get_next(tr[u].l,x));else return get_next(tr[u].r,x);
}
int ss;
void solve()
{sz=0;int n;cin>>n;for(int i=1;i<=n;i++){int op,x;cin>>op>>x;if(op==1) ins(ss,x);if(op==2) del(ss,x);if(op==3) cout<<get_rank(ss,x)<<endl;if(op==4) cout<<get_val(ss,x)<<endl;if(op==5) cout<<get_pre(ss,x)<<endl;if(op==6) cout<<get_next(ss,x)<<endl;}
}
signed main()
{ios_base::sync_with_stdio(false);cin.tie(0);int t;t=1;while(t--) {solve();}return 0;}