传送门 第一次写fhq平衡树，写个博客纪念一下，附全部模板
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cstdlib> using namespace std; typedef long long ll; const int N=500010; int n,m,cnt,root,a[N],b[N]; struct node { int l,r,val,key,sz;//左右儿子，值，权值，大小 }tr[N]; inline int newnode(int val)//新建节点 { tr[++cnt].val=val; tr[cnt].sz=1; tr[cnt].key=rand();//随机化权值，相当于随机化排序了 return cnt; } void update(int rt) { tr[rt].sz=tr[tr[rt].l].sz+tr[tr[rt].r].sz+1; } void split(int now,int val,int &x,int &y)//将树now分裂为两棵树x，y { if(!now) x=y=0; else { if(tr[now].val<=val) { x=now; split(tr[now].r,val,tr[x].r,y); } else { y=now; split(tr[now].l,val,x,tr[y].l); } update(now); } } int merge(int x,int y)//合并两棵树，返回合并后的节点 { if(!x||!y) return x+y; if(tr[x].key>tr[y].key)//> >= < <= 都可以 { tr[x].r=merge(tr[x].r,y); update(x); return x; } tr[y].l=merge(x,tr[y].l); update(y); return y; } int x,y,z; void insert(int val)//插入一个值为val的节点 { int now=newnode(val); split(root,val,x,y); root=merge(merge(x,now),y); } void del(int val)//删除 { split(root,val,x,z); split(x,val-1,x,y); y=merge(tr[y].l,tr[y].r); root=merge(merge(x,y),z); } inline int get_pre(int val)//求小于等于val的最大值 { split(root,val,x,y); int now=x; while(tr[now].r) now=tr[now].r; root=merge(x,y);//拆开后别忘了合并 return tr[now].val; } inline int get_next(int val)//求大于等于val的最小值 { split(root,val-1,x,y); int now=y; while(tr[now].l) now=tr[now].l; root=merge(x,y); return tr[now].val?tr[now].val:n+1; } inline int get_num(int k)//第k大的值 { int now=root; while(now) { if(tr[tr[now].l].sz+1==k) break; else if(tr[tr[now].l].sz>=k) now=tr[now].l; else { k-=tr[tr[now].l].sz+1; now=tr[now].r; } } return tr[now].val; } inline int get_rank(int val)//求排名 { split(root,val-1,x,y); int num=tr[x].sz+1; root=merge(x,y); return num; } int q[N],l,r,pos; char op[5]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) scanf("%d",a+i); for(int i=1;i<=n;i++) scanf("%d",b+i); for(int i=1,j=1;i<=n;i++) { while(j<=m&&j<=b[i]) insert(a[j++]); printf("%d\n",get_num(i)); } return 0; } /* * ┌───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐ * │Esc│ │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│ ┌┐ ┌┐ ┌┐ * └───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘ └┘ └┘ └┘ * ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐ * │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │ * ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤ * │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │ │ * ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │ * │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter │ │ 4 │ 5 │ 6 │ │ * ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤ ┌───┐ ├───┼───┼───┼───┤ * │ Shift │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│ Shift │ │ ↑ │ │ 1 │ 2 │ 3 │ │ * ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││ * │ Ctrl│ Win│ Alt│ Space │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │ 0 │ . │←─┘│ * └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘ */