求助……fhq treap求调
查看原帖
求助……fhq treap求调
316827
Temperature_automata楼主2021/2/4 11:18

求后继会WA,求调

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5+5;
struct node {
  int l , r ;
  int val , key ;
  int size ;
}fhq[N] ;
int cnt , root , n ;

#include <ctime>
#include <cstdlib>

inline int newnode (int val) {
  srand(time(0)) ;
  fhq[++cnt].val = val ;
  fhq[cnt].key = rand () ;
  fhq[cnt].size = 1 ;
  return cnt ;
}//建立新节点

inline void update (int now) {
  fhq[now].size = fhq[fhq[now].l].size
  +fhq[fhq[now].r].size+1 ;
}//更新大小

inline void split(int now,int val,int &x,int &y) {   //x,y返回两棵树的根
  if(!now) x = y = 0 ;
  else {
    if(val>=fhq[now].val) {
      x = now ;
      split(fhq[now].r,val,fhq[now].r,y) ;
    }
    else {
      y = now ;
      split(fhq[now].l,val,x,fhq[now].l) ;
    }
    update(now) ;
  }
}//分裂

inline int merge(int x,int y) { //严格保证x树所有值<y树所有值
  if(!x||!y) return x + y ;
  if(fhq[x].key>fhq[y].key) {   // > >= < <= 皆可
    fhq[x].r = merge(fhq[x].r,y) ;
    update(x) ;
    return x ;
  }
  else {
    fhq[y].l = merge(fhq[y].l,x) ;
    update(y) ;
    return y ;
  }
}

int x , y , z ;

inline void ins ( int val ) {
  split(root,val,x,y) ;
  root = merge(merge(x,newnode(val)),y) ;
}//新建

inline void del ( int val ) {
  split(root,val,x,z) ;
  split(x,val-1,x,y) ;
  y = merge(fhq[y].l,fhq[y].r) ;
  root = merge(merge(x,y),z) ;
}//删除

inline void getrank(int val) {
  split(root,val-1,x,y) ;
  cout << fhq[x].size + 1 << endl ;
  root = merge(x,y) ;
}

inline void getnum(int rank) {
  int now = root ;
  while(now) {
    if(fhq[fhq[now].l].size+1==rank) {
      break;
    }
    else if(fhq[fhq[now].l].size>=rank) {
      now = fhq[now].l ;
    }
    else  {
      rank-=fhq[fhq[now].l].size + 1 ;
      now = fhq[now].r ;
    }
  }
  cout << fhq[now].val << endl  ;
}

inline void pre(int val) {
  split(root,val-1,x,y) ;
  int now = x ;
  while(fhq[now].r)
    now = fhq[now].r;
  cout << fhq[now].val << endl ;
  root = merge(x,y) ;
}

inline void nxt(int val) {
  split(root,val,x,y) ;
  int now = y ;
  while(fhq[now].l)
    now = fhq[now].l;
  cout << fhq[now].val << endl ;
  root = merge(x,y) ;
}

int main ( ) {
  cin >> n ;
  while(n--) {
    int opt , x ;
    cin >> opt >> x ;
    switch(opt) {
      case 1 :
        ins(x) ;
        break ;
      case 2 :
        del(x) ;
        break ;
      case 3 :
        getrank(x) ;
        break ;
      case 4 :
        getnum(x) ;
        break ;
      case 5 :
        pre(x) ;
        break ;
      case 6 :
        nxt(x) ;
        break ;
    }
  }
  // system("pause") ;
  return 0 ;
}
2021/2/4 11:18
加载中...