1. 题目

传送门=￣ω￣=

更新：突然发现 LUOGU 上有这题（LUOGU – 2617），可以木有权限号刷～传送门=￣ω￣=

题目大意：

给你一个序列，要求资磁两个操作：

• 将某一个位置的数字改变
• 询问一段区间内第 k 小的数字

操作数和序列长度均在 10000 的范围内，无多组数据。

2. 题解

首先如果不带修改的区间第 k 小（大）问题我已经写过两个题解了：

• 主席树：传送门=￣ω￣=
• 二分答案套线段树：传送门=￣ω￣=

如果带修改怎么办呢？

1. 听说可以树状数组套主席树 $O(mlog_2^2n)$做，然而我不会 QvQ
2. 借鉴上面的二分答案套线段树的静态 k 小数做法，我们可以把线段树对应的那一段段数组区间换成一颗颗 splay 来资磁修改！

具体思路懒得讲了，上面那篇博客（二分套线段树）中讲过惹。。。

算法复杂度是 $O(mlog_2^3n)$

直接放代码吧（我懒你咬我啊？），我会附上注释的=。=

PS：没想到这玩意也不难打，一开始以为至少两三百行，结果最后才 140 多行，而且还一遍 AC 惹！爽啊♂～

代码：

#include <bits/stdc++.h>
#define SZ (10005)//数据范围
#define LS(a) (a<<1)//线段树节点 a 的左儿子的编号
#define RS(a) (a<<1|1)//线段树节点 a 的右儿子的编号
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;
}
struct N{int f,s[2],d,sz;}e[SZ*400];//splay 节点结构体
int cnt,n,m,a[SZ],data[SZ],td[2][SZ],lv[SZ],A,B,C,lim1,lim2;
//cnt 是 splay（已申请的）节点个数，data 是用来排序建 splay 的数组，td 是归并排序的暂存数组
//lv[i] 是对应区间 [i,i] 的线段树节点的编号（可以实现修改不递归），lim1 是二分答案下界，lim2 是上界
char opt[5];//存 Q 还是 C（操作类型）
stack<int> st;//splay 的垃圾回收栈
int MKN()//splay 的申请新节点操作
{
    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;}//判断 splay 中某一节点是左儿子还是右儿子
void pup(int a){e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+1;}//splay 的 push_up
void rot(int a)//splay 的 rotate
{
    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);
}
int build(int l,int r,int fa)//新建一颗 splay
{
    if(l>r)return 0;
    int a=MKN(),mid=(l+r)>>1;e[a].f=fa,e[a].d=data[mid];
    e[a].s[0]=build(l,mid-1,a),e[a].s[1]=build(mid+1,r,a),pup(a);
    return a;
}
struct splay_tree//splay 结构体
{
    int root;//根节点
    void splay(int a,int t)//splay 的 splay 操作=。=
    {
        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 find_by_key(int key,int a)//按键值找节点
    {
        if(!a)return 0;
        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)//删除值为 d 的节点（有多个则只删除一个）
    {
        int p=find_by_key(d,root),l,r;
        splay(p,0),l=e[p].s[0],r=e[p].s[1];
        e[p].s[0]=e[p].s[1]=e[l].f=e[r].f=0;
        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[r].s[0]=l,e[l].f=r,pup(l),pup(r),root=r,st.push(p);
    }
    void insert(int d,int fa,int&a)//插入一个值为 d 的节点
    {
        if(!a){a=MKN(),e[a].d=d,e[a].f=fa,e[a].sz=1,splay(a,0);return;}
        if(d<e[a].d)return insert(d,a,e[a].s[0]);
        return insert(d,a,e[a].s[1]);
    }
    int order_of_key(int d)//询问该 splay 中比 d 要小的数字有多少个（不含 d）
    {
        int a=root,tot=0;
        while(a)
            if(e[a].d<d)tot+=e[e[a].s[0]].sz+1,a=e[a].s[1];
            else a=e[a].s[0];
        return tot-1;//因为有哨兵节点所以要-1 返回
    }
}tree[SZ<<2];
void sbuild(int l,int r,int a)//线段树建树
{
    if(l==r)
    {
        int t1=data[l-1],t2=data[r+1];
        data[l-1]=INT_MIN,data[r+1]=INT_MAX;
        lv[l]=a,tree[a].root=build(l-1,r+1,0);//这里 l-1,r+1 是 splay 的哨兵节点
        data[l-1]=t1,data[r+1]=t2;
        return;
    }
    int mid=(l+r)>>1;
    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]=INT_MAX;
    for(int i=l,p=l,q=mid+1;i<=r;i++)
        if(td[0][p]<=td[1][q])data[i]=td[0][p++];
        else data[i]=td[1][q++];
    //上面是归并排序=。=
    int t1=data[l-1],t2=data[r+1];
    data[l-1]=INT_MIN,data[r+1]=INT_MAX;
    tree[a].root=build(l-1,r+1,0);//这里 l-1,r+1 是 splay 的哨兵节点
    data[l-1]=t1,data[r+1]=t2;
}
int query(int l,int r,int d,int L,int R,int a)//询问区间 l,r 中，小于 d 的数字有多少个
{
    if(l<=L&&R<=r)return tree[a].order_of_key(d);
    int mid=(L+R)>>1,tot=0;
    if(l<=mid)tot+=query(l,r,d,L,mid,LS(a));
    if(r>mid)tot+=query(l,r,d,mid+1,R,RS(a));
    return tot;
}
void update(int pos,int d)//修改序列的第 pos 项为 d
{
    for(int p=lv[pos];p;p>>=1)
        tree[p].del(a[pos]),tree[p].insert(d,0,tree[p].root);
    a[pos]=d,lim1=min(lim1,d),lim2=max(lim2,d);
}
void work()//询问操作
{
    int l=lim1,r=lim2,mid;
    while(l!=r)
    {
        mid=(l+r+1)>>1;
        int tmp=query(A,B,mid,1,n,1);
        if(tmp<C)l=mid;else r=mid-1;
    }
    printf("%d\n",l);
}
int main()
{
    IN(n),IN(m),lim1=INT_MAX,lim2=INT_MIN,e[0].d=INT_MAX;
    for(int i=1;i<=n;i++)
        IN(a[i]),data[i]=a[i],lim1=min(lim1,a[i]),lim2=max(lim2,a[i]);
    sbuild(1,n,1);
    while(m--)
    {
        scanf("%s",opt),IN(A),IN(B);
        if(opt[0]=='C')update(A,B);
        else IN(C),work();
    }
    return 0;
}