社区讨论

为什么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 条回复,欢迎继续交流。

正在加载回复...