带旋 Treap WA on #1#2 求条
查看原帖
带旋 Treap WA on #1#2 求条
1308728
xsmfollower楼主2024/5/2 14:41

rt。

似乎是查询一个不在集合里的数的排名时挂了?有没有大佬教教我咋改

#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;
const int N=1e5+10; int root,tot,ans,v[N],w[N],c[N],s[N],lc[N],rc[N];
int new_node(int _v) { return v[++tot]=_v,w[tot]=rand(),c[tot]=s[tot]=1,tot; }
void update(int k) { s[k]=s[lc[k]]+s[rc[k]]+c[k]; }
void lturn(int &k) {
  int t=rc[k];
  rc[k]=lc[t],lc[t]=k,s[t]=s[k];
  update(k),k=t;
}
void rturn(int &k) {
  int t=lc[k];
  lc[k]=rc[t],rc[t]=k,s[t]=s[k];
  update(k),k=t;
}
void insert(int &k,int x) {
  if(!k) return k=new_node(x),void();
  s[k]++;
  if(v[k]==x) c[k]++;
  else if(v[k]<x) {
    insert(rc[k],x);
    if(w[rc[k]]<w[k]) lturn(k);
  }
  else {
    insert(lc[k],x);
    if(w[lc[k]]<w[k]) rturn(k);
  }
}
bool del(int &k,int x) {
  if(!k) return false;
  if(v[k]==x) {
    if(c[k]>1) return c[k]--,s[k]--,true;
    else if(!lc[k]||!rc[k]) return k=lc[k]+rc[k],true;
    else {
      if(w[lc[k]]<w[rc[k]]) rturn(k);
      else lturn(k);
      return del(k,x);
    }
  }
  else {
    bool flag;
    if(v[k]<x) flag=del(rc[k],x);
    else flag=del(lc[k],x);
    if(flag) s[k]--;
    return flag;
  }
}
int query_rank(int k,int x) {
  if(!k) return 0;
  if(v[k]==x) return s[lc[k]]+1;
  if(x<v[k]) return query_rank(lc[k],x);
  return s[lc[k]]+c[k]+query_rank(rc[k],x);
}
int query_kth(int k,int x) {
  if(!k) return 0;
  if(x<=s[lc[k]]) return query_kth(lc[k],x);
  if(x>s[lc[k]]+c[k]) return query_kth(rc[k],x-s[lc[k]]-c[k]);
  return v[k];
}
void query_pre(int k,int x) {
  if(!k) return;
  if(v[k]<x) ans=k,query_pre(rc[k],x);
  else query_pre(lc[k],x);
}
void query_suc(int k,int x) {
  if(!k) return;
  if(v[k]>x) ans=k,query_suc(lc[k],x);
  else query_suc(rc[k],x);
}
int main() {
  srand(time(0));
  int n; scanf("%d",&n);
  while(n--) {
    int opt,x; scanf("%d %d",&opt,&x);
    if(opt==1) insert(root,x);
    if(opt==2) del(root,x);
    if(opt==3) printf("%d\n",query_rank(root,x));
    if(opt==4) printf("%d\n",query_kth(root,x));
    if(opt==5) query_pre(root,x),printf("%d\n",v[ans]);
    if(opt==6) query_suc(root,x),printf("%d\n",v[ans]);
  }
  return 0;
}
2024/5/2 14:41
加载中...