P3380 【模板】二逼平衡树（树套树）

题目描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

查询k在区间内的排名
查询区间内排名为k的值
修改某一位值上的数值
查询k在区间内的前驱(前驱定义为严格小于x，且最大的数，若不存在输出-2147483647)
查询k在区间内的后继(后继定义为严格大于x，且最小的数，若不存在输出2147483647)

注意上面两条要求和tyvj或者bzoj不一样，请注意

输入输出格式

输入格式：

第一行两个数 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的后继

输出格式：

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

输入输出样例

输入样例#1：

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

输出样例#1：

说明

时空限制：2s，128M

n,m<=50000 保证有序序列所有值在任何时刻满足[0,10^8]

题目来源：bzoj3196/Tyvj1730 二逼平衡树，在此鸣谢

此数据为洛谷原创。（特别提醒：此数据不保证操作5、6一定存在，故请务必考虑不存在的情况）

//标程splay 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define N 200100
#define M 2333333
#define inf 1e8
int n,m,p,l,r,k,pos,tot,tmp,ans,top,L,R,mid,a[N],father[M],son[M][2],size[M],val[M];
struct tree{int l,r,root;}t[N];
void pushup(int x){if(x)size[x]=size[son[x][0]]+size[son[x][1]]+1;}
int leftmin(int x){if(!son[x][0])return x;return leftmin(son[x][0]);}
void newnode(int &x,int fa,int da){
    if(top)x=top,top=0;else x=++tot;
    father[x]=fa;
    son[x][0]=son[x][1]=0;
    val[x]=da;
    size[x]=1;
}
void rotate(int x,int k){
    int y=father[x];
    son[y][!k]=son[x][k];
    father[son[y][!k]]=y;
    son[father[y]][son[father[y]][1]==y]=x;
    father[x]=father[y];
    son[x][k]=y;
    father[y]=x;
    pushup(y);
}
void splay(int x,int goal,int &root){
    while(father[x]!=goal){
        int y=father[x],z=father[y],f=(son[z][0]==y);
        if(z==goal)rotate(x,son[y][0]==x);else{
            if(son[y][f]==x)rotate(x,!f);else rotate(y,f);
            rotate(x,f);
        }
    }
    pushup(x);
    if(!goal)root=x;
}
void kthfind(int x,int key){
    if(!x)return;
    if(key<=val[x])kthfind(son[x][0],key);else{
        tmp+=size[son[x][0]]+1;
        kthfind(son[x][1],key);
    }
}
int findit(int x,int key){
    if(key<val[x])return findit(son[x][0],key);
    if(key==val[x])return x;
    return findit(son[x][1],key);
}
void insert(int &root,int key){
    int x=root;
    if(!root){newnode(root,0,key);return;}
    while(son[x][key>val[x]])size[x]++,x=son[x][key>val[x]];
    size[x]++;
    newnode(son[x][key>val[x]],x,key);
    splay(son[x][key>val[x]],0,root);
}
void del(int &root,int key){
    int x=findit(root,key);
    splay(x,0,root);
    top=root;
    if(!son[x][1]){
        father[son[x][0]]=0;
        root=son[x][0];
    }else{
        splay(leftmin(son[x][1]),root,root);
        son[son[root][1]][0]=son[root][0];
        father[son[root][1]]=0;
        father[son[root][0]]=son[root][1];
        root=son[root][1];
    }
    pushup(root);
}
void pre(int x,int key){
    if(!x)return;
    if(val[x]<key){if(val[x]>ans)ans=val[x];pre(son[x][1],key);}
    else pre(son[x][0],key);
}
void suc(int x,int key){
    if(!x)return;
    if(val[x]>key){if(val[x]<ans)ans=val[x];suc(son[x][0],key);}
    else suc(son[x][1],key);
}
void change(int k,int x,int key,int last){
    del(t[k].root,last);
    insert(t[k].root,key);
    int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(l==r)return;
    if(x<=mid)change(k<<1,x,key,last);else change(k<<1|1,x,key,last);
}
void getk(int k,int x,int y,int key){
    int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(x==l&&r==y)kthfind(t[k].root,key);
    else{
        if(x>mid)getk(k<<1|1,x,y,key);
        else if(y<=mid)getk(k<<1,x,y,key);
        else {getk(k<<1,x,mid,key);getk(k<<1|1,mid+1,y,key);}
    }
}
void getpre(int k,int x,int y,int key){
    int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(x==l&&r==y)pre(t[k].root,key);else{
        if(x>mid)getpre(k<<1|1,x,y,key);
        else if(y<=mid)getpre(k<<1,x,y,key);
        else getpre(k<<1,x,mid,key),getpre(k<<1|1,mid+1,y,key);
    }
}
void getsuc(int k,int x,int y,int key){
    int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(x==l&&r==y)suc(t[k].root,key);else{
        if(x>mid)getsuc(k<<1|1,x,y,key);
        else if(y<=mid)getsuc(k<<1,x,y,key);
        else getsuc(k<<1,x,mid,key),getsuc(k<<1|1,mid+1,y,key);
    }
}
 
void buildtree(int k,int l,int r){
    t[k].l=l;t[k].r=r;char ch;
    for(int i=l;i<=r;i++)insert(t[k].root,a[i]);
    if(l==r)return;
    int mid=(l+r)>>1;
    buildtree(k<<1,l,mid);
    buildtree(k<<1|1,mid+1,r);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    buildtree(1,1,n);
    while(m--){
        scanf("%d",&p);
        if(p!=3){
            scanf("%d%d%d",&l,&r,&k);
            if(p==1){
                tmp=1;getk(1,l,r,k);
                printf("%d
",tmp);
            }else if(p==2){
                L=0;R=2147483647;
                while(L<=R){
                    mid=(L+R)>>1;
                    tmp=1;getk(1,l,r,mid);
                    if(tmp<=k)L=mid+1,ans=mid;else R=mid-1;
                }
                printf("%d
",ans);
            }else if(p==4){
                ans=-2147483647;
                getpre(1,l,r,k);
                printf("%d
",ans);
            }else if(p==5){
                ans=2147483647;
                getsuc(1,l,r,k);
                printf("%d
",ans);
            }
        }else{
            scanf("%d%d",&pos,&k);
            change(1,pos,k,a[pos]);
            a[pos]=k;
        }
    }
}

//树状数组套主席树 
#include<cstdio>
#include<cstring>
#include<algorithm>
#pragma GCC optimize("Ofast")//视编译器而定
#define IN inline  
using namespace std;
const int N=3e5+1;
struct node{
    int opt,c,d,e;
}q[N];
int a[N],b[N],tot,sz;
int n,m,root[N],bit[N],s[N];
int ls[N*20],rs[N*20],sum[N*20];
IN 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;
}
IN int lowbit(int x){
    return x&-x;
}
void change(int &rt,int last,int l,int r,int pos,int z){
    rt=++sz;
    ls[rt]=ls[last];
    rs[rt]=rs[last];
    sum[rt]=sum[last]+z;
    if(l==r) return ;
    int mid=l+r>>1;
    if(pos<=mid) change(ls[rt],ls[last],l,mid,pos,z);
    else change(rs[rt],rs[last],mid+1,r,pos,z);
}
IN int suml(int x){
    int ans=0;
    for(;x>0;x-=lowbit(x)) ans+=sum[ls[bit[x]]];
    return ans;
}
IN int sumr(int x){
    int ans=0;
    for(;x;x-=lowbit(x)) ans+=sum[rs[bit[x]]];
    return ans;
}
IN void movel(int l,int r) {
    for(;l;l-=lowbit(l)) bit[l]=ls[bit[l]];
    for(;r;r-=lowbit(r)) bit[r]=ls[bit[r]];
}
IN void mover(int l,int r) {
    for(;l;l-=lowbit(l)) bit[l]=rs[bit[l]];
    for(;r;r-=lowbit(r)) bit[r]=rs[bit[r]];
}
IN void init(int l,int r) {
    for(;l;l-=lowbit(l)) bit[l]=s[l];
    for(;r;r-=lowbit(r)) bit[r]=s[r];
}
int find(int rt,int last,int l,int r,int L,int R,int k){
    int ff=0;
    if(l==r) return -1;
    int mid=l+r>>1;
    if(k<=mid){
        int temp=suml(R)-suml(L);
        movel(L,R);
        ff=find(ls[rt],ls[last],l,mid,L,R,k);
        if(ff==-1) ff=temp+sum[ls[last]]-sum[ls[rt]];
    }
    else{
        int temp=sumr(R)-sumr(L);
        mover(L,R);
        ff=find(rs[rt],rs[last],mid+1,r,L,R,k);
        if(ff==-1) ff=temp+sum[rs[last]]-sum[rs[rt]];
    }
    return ff;
}
int rank(int rt,int last,int l,int r,int L,int R,int k){
    int rr=0;
    if(l==r) return 1;
    int mid=l+r>>1;
    if(mid>=k){
        movel(L,R);
        rr=rank(ls[rt],ls[last],l,mid,L,R,k);
    }
    else{
        rr=suml(R)-suml(L)+sum[ls[last]]-sum[ls[rt]];
        mover(L,R);
        rr+=rank(rs[rt],rs[last],mid+1,r,L,R,k);
    }
    return rr;
}
int select(int rt,int last,int l,int r,int L,int R,int k) {
    if(l==r) return l;
    int res=suml(R)-suml(L)+sum[ls[last]]-sum[ls[rt]];
    int mid=(l+r)>>1;
    if(res>=k){
        movel(L,R);
        return select(ls[rt],ls[last],l,mid,L,R,k);
    }
    else{
        mover(L,R);
        return select(rs[rt],rs[last],mid+1,r,L,R,k-res);
    }
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    memcpy(b,a,sizeof a);
    int cnt=n;
    for(int i=1;i<=m;i++){
        q[i].opt=read();
        if(q[i].opt==3){
            q[i].c=read();
            q[i].d=read();
            b[++cnt]=q[i].d;
        }
        else{
            q[i].c=read();q[i].d=read();q[i].e=read();
            if(q[i].opt!=2) b[++cnt]=q[i].e;
        }
    }
    sort(b+1,b+cnt+1);
    cnt=unique(b+1,b+cnt+1)-(b+1);
    for(int i=1;i<=n;i++){
        int p=lower_bound(b+1,b+cnt+1,a[i])-b;
        change(root[i],root[i-1],1,cnt,p,1);
    }
    for(int i=1;i<=n;i++) s[i]=root[0];
    for(int i=1;i<=m;i++){
        if(q[i].opt==3){
            int c=q[i].c,d=q[i].d;
            int p1=lower_bound(b+1,b+cnt+1,a[c])-b;
            int p2=lower_bound(b+1,b+cnt+1,d)-b;
            a[c]=d;
            for(int x=c;x<=n;x+=lowbit(x)) change(s[x],s[x],1,cnt,p1,-1);
            for(int x=c;x<=n;x+=lowbit(x)) change(s[x],s[x],1,cnt,p2,1);
        }
        else{
            int c=q[i].c,d=q[i].d,e=q[i].e,opt=q[i].opt;
            int p=lower_bound(b+1,b+cnt+1,e)-b;
            init(c-1,d);
            if(opt==1) printf("%d
",rank(root[c-1],root[d],1,cnt,c-1,d,p));            if(opt==2) printf("%d
",b[select(root[c-1],root[d],1,cnt,c-1,d,e)]);
            if(opt==4){
                int pos=rank(root[c-1],root[d],1,cnt,c-1,d,p);
                init(c-1,d);                
                if(pos==1) printf("-2147483647
");
                else printf("%d
",b[select(root[c-1],root[d],1,cnt,c-1,d,pos-1)]);
            }
            if(opt==5){
                int pos=rank(root[c-1],root[d],1,cnt,c-1,d,p);
                init(c-1,d);
                int P=find(root[c-1],root[d],1,cnt,c-1,d,p);
                init(c-1,d);
                if(pos+P>d-c+1) printf("2147483647
");
                else printf("%d
",b[select(root[c-1],root[d],1,cnt,c-1,d,pos+P)]);
            }
        }
    }
    return 0;
}