16分,前两个点对了,其他的点 T 了
哼哼啊啊啊啊
#include <iostream>
#define ll long long
using namespace std;
const ll N=1e6+10;
inline ll read(){
ll x,y;
char c=getchar();
x=0,y=1;
while(c<'0'||c>'9') {if(c=='-') y=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
return x*y;
}
ll data[N];
ll ch[N][2];
ll fa[N];
ll root;
ll tot;
ll sum[N];
ll cnt[N];
void update(ll x){
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+cnt[x];
}
ll get_wh(ll x){
if(ch[fa[x]][0]==x) return 0;
return 1;
}
void rotate(ll x){
ll y=fa[x],z=fa[y],k=get_wh(x);
fa[x]=z;
ch[z][get_wh(y)]=x;
fa[ch[x][k^1]]=y;
ch[y][k]=ch[x][k^1];
fa[y]=x;
ch[x][k^1]=y;
update(y);update(x);
}
void splay(ll x,ll target){
while(fa[x]!=target){
ll y=fa[x],z=fa[y];
if(z!=target){
if(get_wh(x)==get_wh(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
if(!target) root=x;
}
void insert_(ll v){
ll x=root,y=0;
while(x&&data[x]!=v){
y=x;
x=ch[x][v>data[x]];
}
if(x) cnt[x]++;
else{
x=++tot;
if(y) ch[y][v>data[y]]=x;
ch[x][0]=ch[x][1]=0;
fa[x]=y;data[x]=v;cnt[x]=1;sum[x]=1;
}
splay(x,0);
}
void find_splay(ll v){
ll x=root;
if(!x) return;
while(ch[x][v>data[x]]&&v!=data[x]){
x=ch[x][v>data[x]];
}
splay(x,0);
}
ll pn_pos(ll v,ll f){//若 f=0 则为找前驱,否则为找后继
find_splay(v);
ll x=root;
if(data[x]>v&&f) return x;
if(data[x]<v&&!f) return x;
x=ch[x][f];
while(ch[x][f^1]) x=ch[x][f^1];
return x;
}
void del(ll v){
ll pre=pn_pos(v,0),nxt=pn_pos(v,1);
splay(pre,0);splay(nxt,pre);
ll x=ch[nxt][0];
if(cnt[x]>1) cnt[x]--,splay(x,0);
else{
ch[nxt][0]=0;
fa[x]=0;
splay(nxt,0);
}
}
ll kth(ll k){
ll x=root;
if(sum[x]<k) return 0;
while(1){
ll lc=ch[x][0];
if(k>sum[lc]+cnt[x]){
k-=(sum[lc]+cnt[x]);
x=ch[x][1];
}
else{
if(sum[lc]>=k) x=lc;
else return data[x];
}
}
}
ll getrank(ll v){
ll x=root,rank=0;
while(x){
if(data[x]<v){
rank+=sum[ch[x][0]]+cnt[x];
x=ch[x][1];
}
else x=ch[x][0];
}
return rank+1;
}
ll n;
int main(){
ll opt,x;
n=read();
while(n--){
opt=read();
x=read();
if(opt==1){
insert_(x);
}
if(opt==2){
del(x);
}
if(opt==3){
printf("%lld\n",getrank(x));
}
if(opt==4){
printf("%lld\n",kth(x));
}
if(opt==5){
printf("%lld\n",data[pn_pos(x,0)]);
}
if(opt==6){
printf("%lld\n",data[pn_pos(x,1)]);
}
}
return 0;
}
样例过了的
自己的测试数据也过了的
但为什么 T 了(悲悲悲悲悲悲悲
大佬如果发现有错的地方请指正
没有错的地方请帮忙卡常