树套树-白红宇

树套树

阅读量：6925 次

发布时间：2019-06-27

本文共 4234 字，大约阅读时间需要 14 分钟。

前言：

什么，你说线段树码量大？那来写平衡树吧~~~

什么，你又说平衡树码量大？那来写树套树吧~~~

如果你想，可以将以前学过的数据结构自由组合一下

不过经常会用到的只有两种——线段树套平衡树和树状数组套主席树

正文：

线段树套平衡树

假设你对平衡树的各种操作已经很熟练了（你为什么那么熟练~~~）

那么如果要你写一种数据结构支持查询区间排名，区间前驱，区间后继等

你会怎么办那

提到区间操作，很容易就会想到线段树

所以我们可以线段树套平衡树啊（当然也可以线段树套线段树）

没错，就是这么简单（真香~~~）

不过我写了好久，可能是因为它码量小吧

无奈被某谷数据卡常（题目来自）

只好吸口氧才过了~~~

这里我套的是 $fhq\ treap$ ，模板在

#include
     
      #include
      
       const int maxn=55555;#define inf (0x7fffffff)int get_rand(){    static int seed=19260817;    return seed=(((seed^142857)+200303)*2019)%0x3f3f3f3f;}struct node{    int son[2];    int w,key,size;    node(){}    node(int w):w(w)    {        size=1;        key=get_rand();        son[0]=0,son[1]=0;    }};int tree_cnt;node tree[maxn*4*18];class fhq_treap{    private:        int root;                int newnode(int w)        {            tree[++tree_cnt]=node(w);            return tree_cnt;        }                void update(int now)        {            tree[now].size=tree[tree[now].son[0]].size+tree[tree[now].son[1]].size+1;        }        void split(int now,int num,int &x,int &y)        {            if(!now)            {                x=0,y=0;                return;            }            if(tree[now].w<=num)            {                x=now;                split(tree[now].son[1],num,tree[now].son[1],y);            }            else            {                y=now;                split(tree[now].son[0],num,x,tree[now].son[0]);            }            update(now);        }        int merge(int x,int y)        {            if(!x||!y) return x+y;            if(tree[x].key
       
        left_size+1) k-=left_size+1,now=tree[now].son[1],flag=1;                else return tree[now].w;            }            return flag?inf:-inf;        }        int get_pre(int num)        {            int rank=get_rank(num);            return get_kth(rank-1);        }        int get_suf(int num)        {            int rank=get_rank(num+1);            return get_kth(rank);        }}treap[maxn<<2];int n,m;int data[maxn];#define left(x) (x<<1)#define right(x) (x<<1|1)void build(int k,int l,int r){    for(int i=l;i<=r;i++)        treap[k].insert(data[i]);    if(l==r) return;    int mid=(l+r)>>1;    build(left(k),l,mid);    build(right(k),mid+1,r);}void update(int k,int l,int r,int pos,int num){    treap[k].remove(data[pos]);    treap[k].insert(num);    if(l==r) return;    int mid=(l+r)>>1;    if(pos<=mid) update(left(k),l,mid,pos,num);    else update(right(k),mid+1,r,pos,num);}int get_rank(int k,int l,int r,int x,int y,int num){    if(l>y||r
        
         =x&&r<=y) return treap[k].get_rank(num)-1;    int mid=(l+r)>>1;    return get_rank(left(k),l,mid,x,y,num)+get_rank(right(k),mid+1,r,x,y,num);}int get_kth(int x,int y,int k){    int l=0,r=inf,ans=-1;    while(l<=r)    {        int mid=(l+r)>>1;        if(get_rank(1,1,n,x,y,mid)+1<=k) ans=mid,l=mid+1;        else r=mid-1;    }    return ans;}int get_pre(int k,int l,int r,int x,int y,int num){    if(l>y||r
         
          =x&&r<=y) return treap[k].get_pre(num);    int mid=(l+r)>>1;    return std::max(get_pre(left(k),l,mid,x,y,num),get_pre(right(k),mid+1,r,x,y,num));}int get_suf(int k,int l,int r,int x,int y,int num){    if(l>y||r
          
           =x&&r<=y) return treap[k].get_suf(num); int mid=(l+r)>>1; return std::min(get_suf(left(k),l,mid,x,y,num),get_suf(right(k),mid+1,r,x,y,num));}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&data[i]); build(1,1,n); for(int i=1,opt;i<=m;i++) { scanf("%d",&opt); if(opt==1) { int x,y,num; scanf("%d%d%d",&x,&y,&num); printf("%d\n",get_rank(1,1,n,x,y,num)+1); } if(opt==2) { int x,y,k; scanf("%d%d%d",&x,&y,&k); printf("%d\n",get_kth(x,y,k)); } if(opt==3) { int pos,num; scanf("%d%d",&pos,&num); update(1,1,n,pos,num); data[pos]=num; } if(opt==4) { int x,y,num; scanf("%d%d%d",&x,&y,&num); printf("%d\n",get_pre(1,1,n,x,y,num)); } if(opt==5) { int x,y,num; scanf("%d%d%d",&x,&y,&num); printf("%d\n",get_suf(1,1,n,x,y,num)); } } return 0;}