本文移植自个人的原博客（原文）

题目链接

COGS 1594

题目描述

题目描述

题解

本题正解有很多种，较常见的为树状数组套主席树，SPLAY套线段树，TREAP套线段树，其中实际时间复杂度最低的是树状数组套主席树和用归并进行可持久化的SPLAY套线段树，而较容易实现的是SPLAY套线段树。

此处只介绍树状数组套主席树和SPLAY套线段树的方法。

树状数组套主席树

区间$K$大，修改数值都是树状数组套主席树所支持的基本操作，而对于操作二，同样可以通过二分答案实现，对于需要前驱后继的操作，可以通过操作一，二结合实现，即先找到该数值的排名$K$，在寻找排名$K−1$或$K+1$的数值，对于数值重复的问题需要根据题目进行特殊判断。

SPLAY套线段树

对于每个线段树中代表区间的节点建一颗SPLAY树，存储原数列中下标在该节点包含的区间内的信息，对于每一个下标，需要在$logn$个节点中存储，则实际的SPLAY空间只需要$2nlogn$的大小。对于大多数操作，均可以利用归并的的思想求解，而对于操作二，可以二分答案，找到最小的满足数列中$A[mid]$的排名为$k$的值。

对于SPLAY来说，其中寻找前驱后继和排名的操作如果每次插入新点的话，将会导致时间复杂度大大提高。所以此处采用的是递归寻找的方法。

#include<iostream>
#include<cstdio>
#include<cstring>
#define pd(i) (i>='0'&&i<='9')
using namespace std;
const int N = 5e4+1;
const int inf = 0x7fffffff;
const int M = N*40;

int son[M][2],n,m,fa[M],w[M],s[M],L[M],R[M],num[M],root[M],tot,a[N];

int in()
{
    int t=0,f=1;
    char ch=getchar();
    while (!pd(ch))
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (pd(ch)) t=(t<<3)+(t<<1)+ch-'0',ch=getchar();
    return f*t;
}

void up(int x){s[x]=s[son[x][0]]+s[son[x][1]]+num[x];}

void rotate(int x)
{
    int y=fa[x],z=fa[y],t=son[y][0]==x;
    fa[y]=x;fa[x]=z;
    if(z)son[z][son[z][1]==y]=x;
    son[y][!t]=son[x][t];fa[son[x][t]]=y;
    son[x][t]=y;
    up(y);up(x);
}

void splay(int i,int x,int f)
{
    while(fa[x]!=f)
    {
        int y=fa[x],z=fa[y];
        if(z!=f)
        {
            if(son[y][0]==x^son[z][0]==y)rotate(x);
            else                        rotate(y);
        }
        rotate(x);
    }
    if(!f)root[i]=x;
}

void insert(int i,int &x,int f,int val)
{
    if(!x)
    {
        x=++tot;fa[x]=f;
        son[x][0]=son[x][1]=0;
        w[x]=val;s[x]=num[x]=1;
        splay(i,x,0);
        return;
    }
    if(w[x]==val){s[x]++;num[x]++;splay(i,x,0);return;}
    insert(i,son[x][val>w[x]],x,val);
    up(x);
}

int get(int i,int val)
{
    int x=root[i];
    while(x&&w[x]!=val)x=son[x][val>w[x]];
    return x;
}

void delet(int i,int x)
{
    x=get(i,x);splay(i,x,0);
    if(num[x]>1){num[x]--;s[x]--;return;}
    if(son[x][0]*son[x][1]==0)root[i]=son[x][0]+son[x][1];
    else
    {
        int y=son[x][1];while(son[y][0])y=son[y][0];
        splay(i,y,x);
        fa[son[x][0]]=y;
        son[y][0]=son[x][0];
        root[i]=y;
        son[x][0]=son[x][1]=0;
    }
    fa[root[i]]=0;
    up(root[i]);
}

void build(int now,int l,int r,int x,int val)
{
    L[now]=l;R[now]=r;
    insert(now,root[now],0,val);
    if(l==r)return;
    int mid=l+r>>1;
    if(x<=mid)     build(now*2,l,mid,x,val);
    else        build(now*2+1,mid+1,r,x,val);
    return;
}

int rk(int i,int val)
{
    int x=root[i],ret=0;
    while(x)
    {
        if(w[x]<val)ret+=s[son[x][0]]+num[x],x=son[x][1];
        else    x=son[x][0];
    }
    return ret;
}

int getrk(int now,int x,int y,int k)
{
    int l=L[now],r=R[now];
    if(x<=l&&r<=y)return rk(now,k);
    int mid=l+r>>1;int ret=0;
    if(x<=mid)    ret+=getrk(now*2,x,y,k);
    if(y>mid)    ret+=getrk(now*2+1,x,y,k);
    return ret;
}

int kth(int x,int y,int k)
{
    int l=0,r=inf;
    while(l!=r)
    {
        int mid=l+r+1>>1;
        if(getrk(1,x,y,mid)+1<=k)
                l=mid;
        else    r=mid-1;
    }
    return l;
}

void change(int now,int x,int val,int __val)
{
    int l=L[now],r=R[now];
    delet(now,__val);insert(now,root[now],0,val);
    if(l==r)return;
    int mid=l+r>>1;
    if(x<=mid)    change(now*2,x,val,__val);
    else        change(now*2+1,x,val,__val);
    return;
}

int pre(int i,int val)
{
    int x=root[i],ret=-inf;
    while(x)
    {
        if(w[x]>=val)x=son[x][0];
        else    ret=max(ret,w[x]),x=son[x][1];
    }
    return ret;
}

int ne(int i,int val)
{
    int x=root[i],ret=inf;
    while(x)
    {
        if(w[x]>val)ret=min(ret,w[x]),x=son[x][0];
        else    x=son[x][1];
    }
    return ret;
}

int getpre(int now,int x,int y,int val)
{
    int l=L[now],r=R[now];
    if(x<=l&&r<=y)return pre(now,val);
    int mid=l+r>>1,ret=-inf;
    if(x<=mid)     ret=max(ret,getpre(now*2,x,y,val));
    if(y>mid)    ret=max(ret,getpre(now*2+1,x,y,val));
    return ret;
}

int getne(int now,int x,int y,int val)
{
    int l=L[now],r=R[now];
    if(x<=l&&r<=y)return ne(now,val);
    int mid=l+r>>1,ret=inf;
    if(x<=mid)    ret=min(ret,getne(now*2,x,y,val));
    if(y>mid)    ret=min(ret,getne(now*2+1,x,y,val));
    return ret;
}

int main()
{
    freopen("psh.in","r",stdin);
    freopen("psh.out","w",stdout);
    n=in();m=in();
    for(int i=1;i<=n;++i)
    {
        a[i]=in();
        build(1,1,n,i,a[i]);
    }
    for(int i=1,op,x,y,k,pos;i<=m;++i)
    {
        op=in();
        switch(op)
        {
            case 1:x=in();y=in();k=in();printf("%d\n",getrk(1,x,y,k)+1);break;
            case 2:x=in();y=in();k=in();printf("%d\n",kth(x,y,k));break;
            case 3:pos=in();k=in();change(1,pos,k,a[pos]);a[pos]=k;break;
            case 4:x=in();y=in();k=in();printf("%d\n",getpre(1,x,y,k));break;
            case 5:x=in();y=in();k=in();printf("%d\n",getne(1,x,y,k));break;
        }
    }
}