题目链接：https://www.luogu.com.cn/problem/P2617。

前言

在题解区看见了一个用分块写这个题的，但是在数据加强到 $10^5$ 后貌似已经过不去了（或许卡卡常还有救），难道分块真的就比不过这些树套树整体二分？不不不，分块的潜力远远不止这些！

分块无快读无 O2 评测记录。

正文

之前那篇分块题解的做法是二分答案，然后块内二分检验，这样做的时间复杂度是 $O(n\sqrt n\log n\log V)$ 的，其中 $V$ 是值域。然而二分跟分块就很不搭，我们考虑一个不需要二分也能求第 $k$ 小的方法。

先离散化，对序列分块，考虑维护块内每个数的出现次数，再将值域分块，维护每个块内每个值域块中数的出现次数。然后做前缀和，这样我们就能 $O(1)$ 查询一段块中每个数的出现次数以及每个值域块中数的出现次数。这部分的预处理是 $O(n\sqrt n)$ 的。

查询时考虑将散块中每个数及值域块中数的出现次数先记录下来，这部分是 $O(\sqrt n)$ 的，然后跳值域块，超过 $k$ 了就跳块内的数，直到找到正好超过 $k$ 的位置，这样可以 $O(\sqrt n)$ 查询第 $k$ 小。

修改时只要考虑对预处理的信息的影响即可，由于我们预处理的是前缀和，所以每次修改至多修改 $O(\sqrt n)$ 个块。

这样我们就得到了一个 $O(n\sqrt n)$ 的优秀算法，可以通过此题。

最后

这个做法是另一个题的 trick，有兴趣的可以去试一下：望月悲叹的最初分块。

最后给出代码，仅供参考：

#include <cstdio>
#include <cmath>
#include <algorithm>
using std::sort;
using std::unique;
using std::lower_bound;

#define N 100010

inline int min(int a,int b) {
    return a<b?a:b;
}

struct node{int opt,l,r,k;}q[N];
int n,m,a[N],b[N<<1],tot,l,r,k;
char opt;

int L[320],R[320];
int siz,szv,num,numsz;
int bl[N],blv[N<<1];
int sumc[320][N<<1];
int sums[320][450];

inline void modify(int x,int y) {
    for(int i=bl[x];i<=num;++i) {
        --sumc[i][a[x]];
        --sums[i][blv[a[x]]];
        ++sumc[i][y];
        ++sums[i][blv[y]];
    }
    a[x]=y;
}

int tmpa[N<<1],tmpc[450];
inline int query(int l,int r,int k) {
    int ans;
    if(bl[l]==bl[r]) {
        int vl,vr,tmp(0);
        for(int i=l;i<=r;++i)
            ++tmpa[a[i]],++tmpc[blv[a[i]]];
        for(int i=1;i<=numsz;++i) {
            tmp+=tmpc[i];
            if(tmp>=k) {
                tmp-=tmpc[i];
                vl=(i-1)*szv+1;
                vr=i*szv;
                break;
            }
        }
        for(int i=vl;i<=vr;++i) {
            tmp+=tmpa[i];
            if(tmp>=k) {
                ans=b[i];
                break;
            }
        }
        for(int i=l;i<=r;++i)
            tmpa[a[i]]=0,tmpc[blv[a[i]]]=0;
    } else {
        int vl,vr,tmp(0);
        for(int i=l;i<=R[bl[l]];++i)
            ++tmpa[a[i]],++tmpc[blv[a[i]]];
        for(int i=L[bl[r]];i<=r;++i)
            ++tmpa[a[i]],++tmpc[blv[a[i]]];
        for(int i=1;i<=numsz;++i) {
            tmp+=tmpc[i]+sums[bl[r]-1][i]-sums[bl[l]][i];
            if(tmp>=k) {
                tmp-=tmpc[i]+sums[bl[r]-1][i]-sums[bl[l]][i];
                vl=(i-1)*szv+1;
                vr=i*szv;
                break;
            }
        }
        for(int i=vl;i<=vr;++i) {
            tmp+=tmpa[i]+sumc[bl[r]-1][i]-sumc[bl[l]][i];
            if(tmp>=k) {
                ans=b[i];
                break;
            }
        }
        for(int i=l;i<=R[bl[l]];++i)
            tmpa[a[i]]=0,tmpc[blv[a[i]]]=0;
        for(int i=L[bl[r]];i<=r;++i)
            tmpa[a[i]]=0,tmpc[blv[a[i]]]=0;
    }
    return ans;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) {
        scanf("%d",a+i);
        b[++tot]=a[i];
    }
    for(int i=1;i<=m;++i) {
        scanf("\n%c%d%d",&opt,&l,&r);
        if(opt=='Q') {
            scanf("%d",&k);
            q[i]=(node){1,l,r,k};
        } else {
            q[i]=(node){2,l,r,0};
            b[++tot]=r;
        }
    }
    sort(b+1,b+tot+1);
    tot=unique(b+1,b+tot+1)-b-1;
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    
    siz=ceil(sqrt(n));
    szv=ceil(sqrt(tot));
    for(int i=1;i<=n;++i)
        bl[i]=(i-1)/siz+1;
    for(int i=1;i<=tot;++i)
        blv[i]=(i-1)/szv+1;
    num=bl[n],numsz=blv[tot];
    for(int i=1;i<=num;++i) {
        L[i]=R[i-1]+1;
        R[i]=min(L[i]+siz-1,n);
        for(int j=1;j<=tot;++j)
            sumc[i][j]=sumc[i-1][j];
        for(int j=1;j<=numsz;++j)
            sums[i][j]=sums[i-1][j];
        for(int j=L[i];j<=R[i];++j) {
            ++sumc[i][a[j]];
            ++sums[i][blv[a[j]]];
        }
    }
    
    for(int i=1;i<=m;++i) {
        if(q[i].opt==1)
            printf("%d\n",query(q[i].l,q[i].r,q[i].k));
        else modify(q[i].l,lower_bound(b+1,b+tot+1,q[i].r)-b);
    }
    return 0;
}