社区讨论
为什么MLE 在线等大佬 求助
学术版参与者 6已保存回复 20
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 20 条
- 当前快照
- 1 份
- 快照标识符
- @mi6yde2a
- 此快照首次捕获于
- 2025/11/20 12:50 4 个月前
- 此快照最后确认于
- 2025/11/20 15:30 4 个月前
C
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,opt,root,ans,xx,size;
struct treep{int lc,rc,key,pri,cnt,sze;}t[100005];
void update(int k){
t[k].sze=t[t[k].lc].sze+t[t[k].rc].sze+t[k].cnt;}
void yx(int &k){
int tt=t[k].lc;
t[k].lc=t[k].rc;t[tt].rc=k;t[tt].sze=t[k].sze;
update(k); k=tt;
}
void zx(int &k){
int tt=t[k].rc;
t[k].rc=t[k].lc;
t[tt].lc=k;
t[tt].sze=t[k].sze;
update(k); k=tt;
}
void cr(int &k,int x){
if(k==0){
size++; k=size;
t[k].sze=t[k].cnt=1;
t[k].key=x; t[k].pri=rand();
return;
}
t[k].sze++;
if(t[k].key==x) t[k].cnt++;
else if(x>t[k].key){
cr(t[k].rc,x);
if(t[t[k].rc].pri<t[k].pri) zx(k);
}else
{
cr(t[k].lc,x);
if(t[t[k].lc].pri<t[k].pri) yx(k);
}
}
void sc(int &k,int x){
if(k==0) return ;
if(t[k].key==x){
if(t[k].cnt>1){
t[k].cnt--;
t[k].sze--;
return;
}
if(t[k].rc*t[k].lc==0)
k=t[k].lc+t[k].rc;
else
if(t[t[k].lc].pri<t[t[k].rc].pri){
yx(k);sc(k,x);
}
else {zx(k);sc(k,x);}
}
else if(x>t[k].key)
{t[k].sze--;sc(t[k].rc,x);}
else {t[k].sze--;sc(t[k].lc,x);}
}
int pm(int k,int x ){
if(k==0) return 0;
if(t[k].key==x)
return t[t[k].lc].sze+1;
else
if(x>t[k].key)
return
t[t[k].lc].sze+t[k].cnt+pm(t[k].rc,x);
else return pm(t[k].lc,x);
}
int dj(int k,int x){
if(k==0) return 0;
if(x<=t[t[k].lc].sze)
return dj(t[k].lc,x);
else
if(x>t[t[k].lc].sze+t[k].cnt)
return
dj(t[k].rc,x-t[t[k].lc].sze-t[k].cnt);
else return t[k].key;
}
void qq(int k,int x){
if(k==0) return ;
if(t[k].key<x){ans=k;qq(t[k].rc,x);}
else qq(t[k].lc,x);
}
void hq(int k,int x){
if(k==0) return ;
if(t[k].key>x){ans=k;hq(t[k].lc,x);}
else hq(t[k].rc,x);
}
int main(){
freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&opt,&xx);
if(opt==1) cr(root,xx);
if(opt==2) sc(root,xx);
if(opt==3)
printf("%d\n",pm(root,xx));
if(opt==4)
printf("%d\n",dj(root,xx));
if(opt==5) {
ans=0;qq(root,xx);
printf("%d\n",t[ans].key);
}
if(opt==6) {
ans=0;hq(root,xx);
printf("%d\n",t[ans].key);
}
}
return 0;
}
回复
共 20 条回复,欢迎继续交流。
正在加载回复...