1. 题目

传送门=￣ω￣=

2. 题解

感觉就是 Dynamic Rankings 那题的加强版。

还是老样子搞个线段树套 splay 就行了，具体解法见我写的那个 Dynamic Rankings 的题解：

传送门=￣ω￣=

PS：之前在 BZOJ 提交好多次都WA掉了，最后发现读入优化写错了（手抖 c==’-‘ 写成了 c==-‘-‘），mmp 调我这么久=。=

代码：

#include <bits/stdc++.h>
#define NS (50005)
#define INF (2147483647)
#define LS(a) (a<<1)
#define RS(a) (a<<1|1)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
int n,m,D[NS],data[NS],cnt,td[2][NS],opt,lim1=INF,lim2=-INF;
stack<int> st;
struct N{int f,s[2],d,sz;}e[NS*80];
int MKN()
{
    int tmp;
    if(st.empty())tmp=++cnt;
    else tmp=st.top(),st.pop();
    memset(&e[tmp],0,sizeof(N));
    return tmp;
}
int pos(int a){return e[e[a].f].s[1]==a;}
void pup(int a){e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+1;}
struct splay_tree
{
    int root,l,r;
    void rot(int a)
    {
        int f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
        e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
        if(e[f].s[p])e[e[f].s[p]].f=f;
        if(e[a].f=g)e[g].s[q]=a;
        pup(f),pup(a);
    }
    void splay(int a,int t)
    {
        for(;e[a].f!=t;rot(a))if(e[e[a].f].f!=t)
            if(pos(a)^pos(e[a].f))rot(a);
            else rot(e[a].f);
        if(!t)root=a;
    }
    int order_of_key(int d)
    {
        int a=root,tot=0;
        while(a)
            if(d<=e[a].d)a=e[a].s[0];
            else tot+=e[e[a].s[0]].sz+1,a=e[a].s[1];
        return tot-1;
    }
    int find_by_key(int key,int a)
    {
        if(key==e[a].d)return a;
        if(key<e[a].d)return find_by_key(key,e[a].s[0]);
        return find_by_key(key,e[a].s[1]);
    }
    void del(int d)
    {
        int a=find_by_key(d,root);splay(a,0);
        int l=e[a].s[0],r=e[a].s[1];
        e[l].f=e[r].f=e[a].s[0]=e[a].s[1]=0,st.push(a);
        while(e[l].s[1])l=e[l].s[1];
        while(e[r].s[0])r=e[r].s[0];
        splay(l,0),splay(r,0);
        e[l].f=r,e[r].s[0]=l,root=r,pup(r);
    }
    void insert(int d,int fa,int&a)
    {
        if(!a){a=MKN(),e[a].d=d,e[a].f=fa,splay(a,0);return;}
        if(d<e[a].d)insert(d,a,e[a].s[0]);
        else insert(d,a,e[a].s[1]);
    }
    int pre(int d)
    {
        int a=root,MX=-INF;
        while(a)
            if(e[a].d<d)MX=e[a].d,a=e[a].s[1];
            else a=e[a].s[0];
        return MX;
    }
    int nxt(int d)
    {
        int a=root,MX=INF;
        while(a)
            if(e[a].d>d)MX=e[a].d,a=e[a].s[0];
            else a=e[a].s[1];
        return MX;
    }
}t[NS<<2];
int build(int l,int r,int fa)
{
    if(l>r)return 0;
    int a=MKN(),mid=(l+r)>>1;e[a].d=data[mid],e[a].f=fa;
    e[a].s[0]=build(l,mid-1,a),e[a].s[1]=build(mid+1,r,a);
    pup(a);return a;
}
void sbuild(int l,int r,int a)
{
    int t1=data[l-1],t2=data[r+1],mid=(l+r)>>1;
    t[a].l=l,t[a].r=r;
    if(l==r)
    {
        data[l-1]=-INF,data[r+1]=INF;
        t[a].root=build(l-1,r+1,0);
        data[l-1]=t1,data[r+1]=t2;
        return;
    }
    sbuild(l,mid,LS(a)),sbuild(mid+1,r,RS(a));
    for(int i=l;i<=mid;i++)td[0][i]=data[i];
    for(int i=mid+1;i<=r;i++)td[1][i]=data[i];
    td[0][mid+1]=td[1][r+1]=INF;
    for(int i=l,x0=l,x1=mid+1;i<=r;i++)
        if(td[0][x0]<td[1][x1])data[i]=td[0][x0++];
        else data[i]=td[1][x1++];
    data[l-1]=-INF,data[r+1]=INF;
    t[a].root=build(l-1,r+1,0);
    data[l-1]=t1,data[r+1]=t2;
}
int query_order(int l,int r,int d,int a)
{
    if(l<=t[a].l&&t[a].r<=r)return t[a].order_of_key(d);
    int tot=0;
    if(l<=t[LS(a)].r)tot+=query_order(l,r,d,LS(a));
    if(r>=t[RS(a)].l)tot+=query_order(l,r,d,RS(a));
    return tot;
}
int query_pre(int l,int r,int d,int a)
{
    if(l<=t[a].l&&t[a].r<=r)return t[a].pre(d);
    int MX=-INF;
    if(l<=t[LS(a)].r)MX=max(MX,query_pre(l,r,d,LS(a)));
    if(r>=t[RS(a)].l)MX=max(MX,query_pre(l,r,d,RS(a)));
    return MX;
}
int query_nxt(int l,int r,int d,int a)
{
    if(l<=t[a].l&&t[a].r<=r)return t[a].nxt(d);
    int MX=INF;
    if(l<=t[LS(a)].r)MX=min(MX,query_nxt(l,r,d,LS(a)));
    if(r>=t[RS(a)].l)MX=min(MX,query_nxt(l,r,d,RS(a)));
    return MX;
}
void work_order_of_key()
{
    int l,r,k;
    IN(l),IN(r),IN(k);
    printf("%d\n",query_order(l,r,k,1)+1);
}
void work_find_by_order()
{
    int a,b,k,l=lim1,r=lim2,mid,tmp;
    IN(a),IN(b),IN(k);
    while(l<r)
    {
        mid=(l+r+1)>>1,tmp=query_order(a,b,mid,1);
        if(k>tmp)l=mid;else r=mid-1;
    }
    printf("%d\n",l);
}
void work_update()
{
    int pos,k,a=1,mid;
    IN(pos),IN(k);
    while(a)
    {
        t[a].del(D[pos]),t[a].insert(k,0,t[a].root),mid=(t[a].l+t[a].r)>>1;
        if(t[a].l==t[a].r)break;
        if(pos<=mid)a=LS(a);else a=RS(a);
    }
    D[pos]=k,lim1=min(lim1,k),lim2=max(lim2,k);
}
void work_query_pre()
{
    int l,r,k;
    IN(l),IN(r),IN(k);
    printf("%d\n",query_pre(l,r,k,1));
}
void work_query_nxt()
{
    int l,r,k;
    IN(l),IN(r),IN(k);
    printf("%d\n",query_nxt(l,r,k,1));
}
int main()
{
    IN(n),IN(m);
    for(int i=1;i<=n;i++)
        IN(D[i]),data[i]=D[i],lim1=min(lim1,D[i]),lim2=max(lim2,D[i]);
    sbuild(1,n,1);
    while(m--)
        if(IN(opt),opt==1)work_order_of_key();
        else if(opt==2)work_find_by_order();
        else if(opt==3)work_update();
        else if(opt==4)work_query_pre();
        else work_query_nxt();
    return 0;
}