传送门:

BZOJ

洛谷


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可能为负数


解题思路:

我们考虑位置线段树套平衡树,每一个线段树有一棵splay,不过要注意的是不能是结构体里开maxn的数组,那肯定会MLE,我们记一个tot,然后在结构体外面开数组,大小在maxn*25左右就好了。

对于操作一、四、五,我们在线段树上找到区间[l,r],然后查询就好了。

对于操作二,我们考虑二分,将原问题转化为区间内排名为k的是否为二分出来的这个值,用操作一去判就好了。

对于操作三,因为我们并没有将val数组像之间在每一个splay里都建好来修改,我们存的是位置,而val数组是一个全局变量,我们只需要将原本要修改的位置上的点删掉,然后直接修改val数组,然后重新插入这个位置就好了。

Code:

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5e4+10;
const int inf=2147483647;
int n,m,tot,val[maxn],fa[maxn*25],pos[maxn*25],size[maxn*25],ch[maxn*25][2];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
struct Splay{
    int root,top;
    bool check(int x){return ch[fa[x]][1]==x;}
    void update(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+1;}
    void rotate(int x){
        int y=fa[x],z=fa[y],k=check(x),son=ch[x][check(x)^1];
        ch[x][k^1]=y;ch[y][k]=son;
        if(son)fa[son]=y;fa[x]=z;
        if(fa[x])ch[fa[x]][check(y)]=x;fa[y]=x;
        update(y);update(x);
    }
    void splay(int x,int goal=0){
        while(fa[x]!=goal){
            int y=fa[x],z=fa[y];
            if(z!=goal){
                if(check(x)==check(y))rotate(y);
                else rotate(x);
            }rotate(x);
        }if(!goal)root=x;
    }
    void insert(int x){
        if (!root){size[root=x]=1;return;}
        int now=root;
        while("Luvwgyx loves wyx"){
            size[now]++;
            if (val[pos[x]]<=val[pos[now]]){
                if(!ch[now][0]){fa[ch[now][0]=x]=now;break;}
                now=ch[now][0];
            }else{
                if(!ch[now][1]){fa[ch[now][1]=x]=now;break;}
                now=ch[now][1];
            }
        }splay(x);
    }
    int find(int x,int now){
        if(!x||!now) return 0;
        if(size[ch[now][0]]+1==x)return now;
        if(x<=size[ch[now][0]])return find(x,ch[now][0]);
        return find(x-size[ch[now][0]]-1,ch[now][1]);
    }
    int pre(){int now=ch[root][0];while(ch[now][1])now=ch[now][1];return now;}
    void del(int x){
        splay(x);
        if (!(ch[x][0]&&ch[x][1])){
            fa[root=ch[x][0]+ch[x][1]]=0;
            size[x]=fa[x]=ch[x][0]=ch[x][1]=0;
            return ;
        }int now=pre();splay(now);
        size[fa[ch[now][1]=ch[x][1]]=now]--;
        size[x]=fa[x]=ch[x][0]=ch[x][1]=0;
    }
    int rank1(int x){
        int now=root,ans=0;
        while(now){
            if(val[pos[now]]<x)ans+=size[ch[now][0]]+1,now=ch[now][1];
            else now=ch[now][0];
        }return ans;
    }
    int rank2(int x){
        int now=root,ans=0;
        while(now){
            if(val[pos[now]]<=x)ans+=size[ch[now][0]]+1,now=ch[now][1];
            else now=ch[now][0];
        }return ans;
    }
    void build(int l,int r){for(int i=l;i<=r;i++)pos[++tot]=i,insert(tot);}
    int get_pre(int x){int tmp=find(rank1(x),root);return tmp?val[pos[tmp]]:-inf;}
    int get_nxt(int x){int tmp=find(rank2(x)+1,root);return tmp?val[pos[tmp]]:inf;}
}S[maxn<<2];
struct Segment_Tree{
    void build(int k,int l,int r){
        S[k].top=tot+1;S[k].build(l,r);
        if(l==r)return ;int mid=(l+r)>>1;
        build(k<<1,l,mid);build(k<<1|1,mid+1,r);
    }
    void change(int k,int l,int r,int x){
        S[k].del(S[k].top+x-l);S[k].insert(S[k].top+x-l);
        if(l==r)return ;int mid=(l+r)>>1;
        if(x<=mid)change(k<<1,l,mid,x);
        else change(k<<1|1,mid+1,r,x);
    }
    int query_rak(int k,int l,int r,int x,int y,int v){
        if(x<=l&&r<=y)return S[k].rank1(v);
        int mid=(l+r)>>1,ret=0;
        if(x<=mid)ret+=query_rak(k<<1,l,mid,x,y,v);
        if(mid<y)ret+=query_rak(k<<1|1,mid+1,r,x,y,v);
        return ret;
    }
    int query_pre(int k,int l,int r,int x,int y,int v){
        if(x<=l&&r<=y)return S[k].get_pre(v);
        int mid=(l+r)>>1,ret=-inf;
        if(x<=mid)ret=max(ret,query_pre(k<<1,l,mid,x,y,v));
        if(mid<y)ret=max(ret,query_pre(k<<1|1,mid+1,r,x,y,v));
        return ret;
    }
    int query_nxt(int k,int l,int r,int x,int y,int v){
        if(x<=l&&r<=y)return S[k].get_nxt(v);
        int mid=(l+r)>>1,ret=inf;
        if(x<=mid)ret=min(ret,query_nxt(k<<1,l,mid,x,y,v));
        if(mid<y)ret=min(ret,query_nxt(k<<1|1,mid+1,r,x,y,v));
        return ret;
    }
}T;
void solve(int x,int y,int k){
    int l=1,r=inf,ans=0;
    while(l<=r){
        int mid=(l+r)>>1,ret=T.query_rak(1,1,n,x,y,mid)+1;
        if(ret<=k)l=mid+1,ans=mid;
        else r=mid-1;
    }write(ans);
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)val[i]=read();
    T.build(1,1,n);
    while(m--){
        int opt=read(),x=read(),y=read();
        if(opt==1)write(T.query_rak(1,1,n,x,y,read())+1);
        if(opt==2)solve(x,y,read());
        if(opt==3)val[x]=y,T.change(1,1,n,x);
        if(opt==4)write(T.query_pre(1,1,n,x,y,read()));
        if(opt==5)write(T.query_nxt(1,1,n,x,y,read()));
    }
    return 0;
}