Treap #1,2 WA
查看原帖
Treap #1,2 WA
1296826
lcfollower楼主2024/5/5 13:08

rt,大佬帮忙改一下,谢谢。

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rrep(i,x,y) for(int i=x;i>=y;i--)
#define sc scanf
#define pr printf
#define inf 0x3f3f3f3f
inline int read(){int s=0,w=1;char c=getchar();while(!isdigit(c)){if(c=='-') w=-1;c=getchar();}while(isdigit(c)){s=(s<<1)+(s<<3)+(c^48);c=getchar();}return s*w;}

const int N = 1e5 + 10;
int root,idx;

struct node{
  int l,r;
  int key;
  int val;
  int size;
  int cnt;
}tr[N];

inline int get(int key){
  return tr[++idx].key = key , tr[idx].val = rand() ,tr[idx].size = tr[idx].cnt = 1 , idx;
}

inline void pushup(int u){
  tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

inline void rturn(int &rt){
  int q = tr[rt].l;
  tr[rt].l = tr[q].r;
  tr[q].r = rt;
  rt = q;
  pushup(tr[rt].r);
  pushup(rt);
}

inline void lturn(int &rt){
  int q = tr[rt].r;
  tr[rt].r = tr[q].l;
  tr[q].l = rt;
  rt = q;
  pushup(tr[rt].l);
  pushup(rt);
}

inline void build(){
  get(-inf);
  get(inf);
  root = 1;
  tr[root].r = 2;
  pushup(root);
  if(tr[1].val < tr[2].val) lturn(root);
}

inline void insert(int &rt,int key){
  if(!rt){
    rt = get(key);
    return;
  }
  if(tr[rt].key == key) tr[rt].cnt++;
  if(tr[rt].key > key) {insert(tr[rt].l , key) ; if(tr[tr[rt].l].val > tr[rt].val) rturn(rt);}
  if(tr[rt].key < key) {insert(tr[rt].r , key) ; if(tr[tr[rt].r].val > tr[rt].val) lturn(rt);}
  pushup(rt);
}

inline void del(int &rt,int key){
  if(!rt) return;
  if(tr[rt].key == key){
    if(tr[rt].cnt > 1) tr[rt].cnt --;
    else {
      if(tr[rt].l || tr[rt].r){
        if(!tr[rt].r || tr[tr[rt].l].val > tr[tr[rt].r].val) rturn(rt) ,del(tr[rt].r , key);
        else lturn(rt) , del(tr[rt].l , key);
      }
      else rt = 0;
    }
  }
  else if(tr[rt].key > key) del(tr[rt].l , key);
  else del(tr[rt].r , key);
  pushup(rt);
}

inline int get_rank_by_key(int rt,int key){
  if(!rt) return 0;
  if(tr[rt].key == key) return tr[tr[rt].l].size + 1;
  else if(tr[rt].key > key) get_rank_by_key(tr[rt].l,key);
  else return tr[tr[rt].l].size + tr[rt].cnt + get_rank_by_key(tr[rt].r,key);
}

inline int get_key_by_rank(int rt,int rank){
  if(!rt) return 0;
  if(tr[tr[rt].l].size >= rank) return get_key_by_rank(tr[rt].l,rank);
  else if(tr[tr[rt].l].size + tr[rt].cnt >= rank) return tr[rt].key;
  else return get_key_by_rank(tr[rt].r,rank-tr[tr[rt].l].size-tr[rt].cnt);
}

inline int get_pre(int rt,int key){
  if(!rt) return -inf;
  if(tr[rt].key >= key) return get_pre(tr[rt].l,key);
  else return max(tr[rt].key , get_pre(tr[rt].r , key));
}

inline int get_next(int rt,int key){
  if(!rt) return inf;
  if(tr[rt].key <= key) return get_next(tr[rt].r,key);
  else return min(tr[rt].key , get_next(tr[rt].l , key));
}

signed main(){
  srand(time(0));
  build();
  int Q = read();
  while(Q--){
    int op = read() ,  x = read();
    if(op == 1) insert(root, x);
    if(op == 2) del(root , x);
    if(op == 3) pr("%lld\n",get_rank_by_key(root ,x) - 1);
    if(op == 4) pr("%lld\n",get_key_by_rank(root ,x + 1));
    if(op == 5) pr("%lld\n",get_pre(root , x));
    if(op == 6) pr("%lld\n",get_next(root , x));
  }
  return 0;
}
2024/5/5 13:08
加载中...