【bzoj3196】二逼平衡树

2015.02.06 16:53 Fri | 4次阅读 | 旧日oi | 固定链接 | 源码

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数,表示有序序列
下面有m行,opt表示操作标号
若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行,表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围:n,m<=50000
2.序列中每个数的数据范围:[0,1e8]
3.虽然原题没有,但事实上5操作的k可能为负数

题解

学了treap之后写了道树套树,线段树套treap。感觉并不是很难,但是代码很长……也不怎么好调试,但是写多了也就熟了,上代码吧,bzoj6000ms+蒟蒻代码留念……

我的程序

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 50005
#define maxm 3000001
#define inf 100000000
using namespace std;
int n,m,opt,x,ans,y,z;
struct Treap{
    int l[maxm],r[maxm];
    int v[maxm],w[maxm],rnd[maxm],size[maxm];
    int tot,root;
    inline void update(int k)
    {
        size[k]=size[l[k]]+size[r[k]]+w[k];
    }
    inline void lturn(int &k)
    {
        int t=r[k];r[k]=l[t];l[t]=k;
        size[t]=size[k];update(k);k=t;
    }
    void rturn(int &k)
    {
        int t=l[k];l[k]=r[t];r[t]=k;
        size[t]=size[k];update(k);k=t;
    }
    void insert(int &k,int num)
    {
        if(k==0)
        {
            k=++tot;
            v[k]=num;
            size[k]=w[k]=1;
            rnd[k]=rand();
            return;
        }
        size[k]++;
        if(v[k]==num) w[k]++;
        else if(v[k]<num) 
        {
            insert(r[k],num);
            if(rnd[r[k]]<rnd[k]) lturn(k);
        }
        else 
        {
            insert(l[k],num);
            if(rnd[l[k]]<rnd[k]) rturn(k);
        }
    }
    void del(int &k,int num)
    {
        if(k==0) return;
        if(v[k]==num)
        {
            if(w[k]>1)
            {
                w[k]--;size[k]--;return;
            } 
            if(l[k]*r[k]==0) k=l[k]+r[k];
            else if(rnd[l[k]]<rnd[r[k]]) rturn(k),del(k,num);
            else lturn(k),del(k,num);
        }
        else if(v[k]<num) size[k]--,del(r[k],num);
        else size[k]--,del(l[k],num);
    }
    inline void get_rank(int k,int num)
    {
        if(!k) return;
        int tmp=k;
        while(k)
        {
            if(v[k]<num) ans+=size[l[k]]+w[k],k=r[k];
            else if(v[k]>num) k=l[k];
            else 
            {
                ans+=size[l[k]];
                return;
            }
        }
    }
    inline void get_num(int k,int num)
    {
        if(!k) return;
        while(size[l[k]]>=num||size[l[k]]+w[k]<num)
        {
            if(size[l[k]]>=num) k=l[k];
            else num-=size[l[k]]+w[k],k=r[k];
        }
        ans=v[k];
    }
    inline void get_pre(int k,int num)
    {
        if(!k) return;
        while(k)
        {
            if(v[k]<num) ans=max(ans,v[k]),k=r[k];
            else k=l[k];
        }
    }
    inline void get_suc(int k,int num)
    {
        if(!k) return;
        while(k)
        {
            if(v[k]>num) ans=min(ans,v[k]),k=l[k];
            else k=r[k];
        }
    }
}tr;
struct Segment_tree{
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    int root[maxn<<2],val[maxn<<2];
    void build(int l,int r,int rt)
    {
        for(int i=l;i<=r;i++)
        tr.insert(root[rt],val[i]);
        if(l==r) return;
        int mid=(l+r)>>1;
        build(lson);
        build(rson);
    }
    void change(int l,int r,int rt,int k,int x,int y)
    {
        if(k<=r&&k>=l) 
        {
            tr.del(root[rt],x);
            tr.insert(root[rt],y);
        }
        if(l==r) return;
        int mid=(l+r)>>1;
        if(k<=mid) change(lson,k,x,y);
        else change(rson,k,x,y);
    }
    void get_rank(int l,int r,int rt,int L,int R,int c)
    {
        if(l==L&&r==R)
        {
            tr.get_rank(root[rt],c);
            return;
        }
        int mid=(l+r)>>1;
        if(R<=mid) get_rank(lson,L,R,c);
        else if(L>mid) get_rank(rson,L,R,c);
        else{
            get_rank(lson,L,mid,c);
            get_rank(rson,mid+1,R,c);
        }
    }
    inline int get_num(int L,int R,int c)
    {
        int l=0,r=inf,mid,re;
        while(l<=r)
        {
            mid=(l+r)>>1;
            ans=1;get_rank(1,n,1,L,R,mid);
            if(ans<=c) re=mid,l=mid+1;
            else r=mid-1;
        }
        return re;
    }
    void get_pre(int l,int r,int rt,int L,int R,int c)
    {
        if(L==l&&R==r)
        {
            tr.get_pre(root[rt],c);
            return;
        }
        int mid=(l+r)>>1;
        if(R<=mid) get_pre(lson,L,R,c);
        else if(L>mid) get_pre(rson,L,R,c);
        else{
            get_pre(lson,L,mid,c);
            get_pre(rson,mid+1,R,c);
        }
    }
    void get_suc(int l,int r,int rt,int L,int R,int c)
    {
        if(L==l&&R==r)
        {
            tr.get_suc(root[rt],c);
            return;
        }
        int mid=(l+r)>>1;
        if(R<=mid) get_suc(lson,L,R,c);
        else if(L>mid) get_suc(rson,L,R,c);
        else{
            get_suc(lson,L,mid,c);
            get_suc(rson,mid+1,R,c);
        }
    }
    void dfs(int l,int r,int rt)
    {
        if(l==r)
        {
            cout<<val[l]<<" ";
            return;
        }
        int mid=(l+r)>>1;
        dfs(lson);
        dfs(rson);
    }
}seg_tree;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&seg_tree.val[i]);
    seg_tree.build(1,n,1);
    while(m--)
    {
        scanf("%d%d%d",&opt,&x,&y);
        ans=0;
        switch(opt)
        {
            case 1:
                ans=1;
                scanf("%d",&z);
                seg_tree.get_rank(1,n,1,x,y,z);
                printf("%d\n",ans);
                break;
            case 2:
                scanf("%d",&z);
                printf("%d\n",seg_tree.get_num(x,y,z));
                break;
            case 3:
                seg_tree.change(1,n,1,x,seg_tree.val[x],y);
                seg_tree.val[x]=y;
                break;
            case 4:
                scanf("%d",&z);
                seg_tree.get_pre(1,n,1,x,y,z);
                printf("%d\n",ans);
                break;
            case 5:
                ans=inf;
                scanf("%d",&z);
                seg_tree.get_suc(1,n,1,x,y,z);
                printf("%d\n",ans);
                break;
        }
    }
    return 0;
}```