提交了只有16分。
下载了第一组错误数据,程序输出的答案与正确答案一样,却 WA 了。
这里是数据。
求助大佬 QWQ。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1000010
#define INF 0x3f3f3f3f
using namespace std;
int sum[N],val[N],siz[N],dat[N];
int ch[N][2];
int tot,root;
int New(int v){
tot++;
val[tot]=v;
siz[tot]=1;
sum[tot]=1;
dat[tot]=rand();
return tot;
}
void pushup(int id){
siz[id]=siz[ch[id][0]]+siz[ch[id][0]]+sum[id];
}
void rotate(int &id,int d){
int temp=ch[id][d^1];
ch[id][d^1]=ch[temp][d];
ch[temp][d]=id;
id=temp;
pushup(ch[id][d]);
pushup(id);
}
void insert(int &id,int v){
if(!id){
id=New(v);
return;
}
if(v==val[id]){
sum[id]++;
siz[id]++;
}else{
int d;
if(v<=val[id]) d=0;
else d=1;
insert(ch[id][d],v);
if(dat[id]<dat[ch[id][d]])
rotate(id,d^1);
}
pushup(id);
}
void del(int &id,int v){
if(!id) return;
if(v==val[id]){
if(sum[id]>1){
sum[id]--;
pushup(id);
return;
}
else{
if(ch[id][0]||ch[id][1]){
if(!ch[id][1]||dat[ch[id][0]]>dat[ch[id][1]]){
rotate(id,1);
del(ch[id][1],v);
}else{
rotate(id,0);
del(ch[id][0],v);
}
pushup(id);
}else id=0;
}
}
if(v<val[id])
del(ch[id][0],v);
else del(ch[id][1],v);
pushup(id);
}
int get_rk(int id,int v){
if(!id) return 0;
if(v==val[id]) return siz[ch[id][0]]+1;
else if(v<val[id]) return get_rk(ch[id][0],v);
else return siz[ch[id][0]]+sum[id]+get_rk(ch[id][1],v);
}
int get_x(int id,int rk){
if(!id) return 0;
if(rk<=siz[ch[id][0]]) return get_x(ch[id][0],rk);
else if(rk>siz[ch[id][0]]+sum[id]) return get_x(ch[id][1],rk-siz[ch[id][0]]-sum[id]);
else return val[id];
}
int get_pre(int id,int v){
if(!id) return -INF;
if(v<=val[id]) return get_pre(ch[id][0],v);
else return max(val[id],get_pre(ch[id][1],v));
}
int get_lst(int id,int v){
if(!id) return INF;
if(v>=val[id]) return get_lst(ch[id][1],v);
else return min(val[id],get_lst(ch[id][0],v));
}
int main(){
// freopen("11.in","r",stdin);
// freopen("11.out","w",stdout);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int op,v;
scanf("%d%d",&op,&v);
if(op==1) insert(root,v);
if(op==2) del(root,v);
if(op==3) printf("%d\n",get_rk(root,v));
if(op==4) printf("%d\n",get_x(root,v));
if(op==5) printf("%d\n",get_pre(root,v));
if(op==6) printf("%d\n",get_lst(root,v));
}
return 0;
// fclose(stdin);
// fclose(stdout);
}