题意：让你维护一个序列，支持区间询问第 $K$ 小，单点修改，在某个数前插入一个数。

你发现这个数据范围很小，于是你可以随意地整一个 $O(n\sqrt n\text{polylog } n)$ 的算法。

于是还是传统艺能地块状链表，你先分块，分成 $B$ 块，然后插入就适当地自动分裂。

然后你每个块都记录一个排序好的结果，动态维护这个东西。

然后每次你询问一个区间的时候就二分判定一个数是否是第 $K$ 小。

判定时就把散块的数处理掉，整块的东西再用二分掏出来即可。

复杂度 $O(n\sqrt n\log n\log V)$，$V$ 代表值域。

#define maxn 70010
#define B 1024
int n,m;
int a[B][B*2],b[B][B*2];
int lst,l,r,x,k;
char ch[2];
int nxt[B];
const int blo=512;
int pos[maxn],L[B],R[B],tot,siz[B];
int ask(int l,int r,int k){
  int p=1,q=1;
  while(siz[p]<l)l-=siz[p],p=nxt[p];
  while(siz[q]<r)r-=siz[q],q=nxt[q];
  int tl=0,tr=70000,mid;
  while(tl<=tr){
    mid=(tl+tr)>>1;
    int t=0;
    if(p==q)rep(i,l,r)t+=a[p][i]<mid;
    else{
      rep(i,l,siz[p])t+=a[p][i]<mid;
      rep(i,1,r)t+=a[q][i]<mid;
      int pos=nxt[p];
      while(pos!=q){
        t+=lower_bound(b[pos]+1,b[pos]+siz[pos]+1,mid)-b[pos]-1;
        pos=nxt[pos];
      }
    }
    if(t<k)tl=mid+1;
    else tr=mid-1;
  }
  return tr;
}
void change(int x,int y){
  int p=1,k;
  while(siz[p]<x)x-=siz[p],p=nxt[p];
  rep(i,1,siz[p])if(b[p][i]==a[p][x]){
    k=i;
    break;
  }
  b[p][k]=a[p][x]=y;
  while(k>1&&b[p][k]<b[p][k-1])swap(b[p][k],b[p][k-1]),k--;
  while(k<siz[p]&&b[p][k]>b[p][k+1])swap(b[p][k],b[p][k+1]),k++;
}
void make(int x){
  rep(i,1,siz[x])b[x][i]=a[x][i];
  sort(b[x]+1,b[x]+siz[x]+1);
}
void insert(int x,int y){
  x--;
  int p=1;
  while(siz[p]<x)x-=siz[p],p=nxt[p];
  per(i,siz[p],x+1)a[p][i+1]=a[p][i];
  siz[p]++;
  a[p][x+1]=y;
  b[p][siz[p]]=y;
  if(siz[p]==2*blo){
    nxt[++tot]=nxt[p];
    nxt[p]=tot;
    rep(i,1,blo)a[tot][i]=a[p][i+blo];
    siz[p]=siz[tot]=blo;
    make(p),make(tot);
  }else{
    int k=siz[p];
    while(k>1&&b[p][k]<b[p][k-1])swap(b[p][k],b[p][k-1]),k--;
  }
}
signed main(){
  cin>>n;
  tot=n>>9;
  if(n&511)tot++;
  rep(i,1,tot){
    L[i]=R[i-1]+1;
    R[i]=L[i]+blo-1;
  }R[tot]=n;
  rep(i,1,tot){
    siz[i]=R[i]-L[i]+1;
    rep(j,L[i],R[i])
    cin>>a[i][j-L[i]+1],pos[j]=i;
    if(i<tot)nxt[i]=i+1;
    make(i);
  }
  cin>>m;
  while(m--){
    cin>>ch;
    cin>>l>>r;l^=lst,r^=lst;
    if(ch[0]=='Q'){
      cin>>k,k^=lst;
      cout<<(lst=ask(l,r,k))<<endl;
    }
    if(ch[0]=='M')change(l,r);
    if(ch[0]=='I')insert(l,r);
  }
}

$O(n\sqrt n\log n\log V)$ 跑得比 $O(n\log^2n)$ 快/kk

思路和别人差不多，lxl牛逼。主要得使劲卡。等哪天试试进1000ms。

#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cstdio>
#include <map>
#include <set>
#define u32 unsigned
using namespace std;
#define il inline
#define ri register
#define getcha() (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 20, stdin), SS == TT) ? EOF : *SS++)
#define isint(a) ((a >= '0') && (a <= '9'))
#define isch(a) ((a >= 'A') && (a <= 'Z'))
char BB[1 << 20], *SS = BB, *TT = BB;
inline u32 read() {
    u32 s = 0;
    char ch = getcha();

    while (!isint(ch))
        ch = getcha();

    while (isint(ch))
        s = (s << 3) + (s << 1) + (ch ^ 48), ch = getcha();

    return s;
}
inline u32 rad() {
    char ch = getcha();

    while (!isch(ch))
        ch = getcha();

    return (ch == 'Q' ? 1 : (ch == 'M' ? 2 : 3));
}
const u32 siz = 600;
const u32 zis = 1300;
const u32 blo = 300;
const u32 mxval = 70003;
const u32 vsiz = 512;
const u32 vblo = 303;
struct ee {
    u32 len;
    u32 ab[zis + 30];
    u32 ba[mxval], baa[vblo];
    il void ins(u32 a) {
        ++ba[a], ++baa[a >> 9];
    }
    il void del(u32 a) {
        --ba[a], --baa[a >> 9];
    }
    il void insert(u32 x, u32 bb) {
        for (u32 i = len; i >= x; --i)
            ab[i + 1] = ab[i];

        ++len, ab[x] = bb, ins(bb);
    }
} a[blo], tm;
struct mi {
    u32 aa, bb;
    mi(const u32 &_aa, const u32 &_bb) : aa(_aa), bb(_bb) {}
};
u32 pos[blo], lock;
il mi getpos(u32 x) {
    for (u32 i = 1; i <= lock; ++i)
        if (x <= a[pos[i]].len)
            return mi(i, x);
        else
            x -= a[pos[i]].len;

    return mi(0, 0);
}
il void modi(u32 x, u32 bb) {
    for (u32 i = 1; i <= lock; ++i)
        if (x <= a[pos[i]].len) {
            u32 k = a[pos[i]].ab[x];
            a[pos[i]].ab[x] = bb;

            for (u32 j = i; j <= lock; ++j)
                a[pos[j]].ins(bb), a[pos[j]].del(k);

            return;
        } else
            x -= a[pos[i]].len;
}
il void split(u32 x) {
    if (a[pos[x]].len <= zis)
        return;

    ++lock;
    u32 eee = pos[x];

    for (u32 j = 0; j <= 70000; ++j)
        a[lock].ba[j] = a[eee].ba[j];

    for (u32 j = 0; j <= 140; ++j)
        a[lock].baa[j] = a[eee].baa[j];

    for (u32 i = siz + 1; i <= a[eee].len; ++i)
        a[lock].ab[i - siz] = a[eee].ab[i], a[eee].del(a[eee].ab[i]);

    a[lock].len = a[eee].len - siz, a[eee].len = siz;

    for (u32 i = lock; i > x + 1; --i)
        pos[i] = pos[i - 1];

    pos[x + 1] = lock;
}
il void insert(u32 x, u32 bb) {
    for (u32 i = 1, k; i <= lock; ++i)
        if (x <= a[pos[i]].len + 1) {
            k = pos[i];

            for (u32 i = a[k].len; i >= x; --i)
                a[k].ab[i + 1] = a[k].ab[i];

            ++a[k].len, a[k].ab[x] = bb, a[k].ins(bb);

            // a[pos[i]].insert(x, bb);
            for (u32 j = i + 1; j <= lock; ++j)
                a[pos[j]].ins(bb);

            split(i);
            return;
        } else
            x -= a[pos[i]].len;
}
u32 b[100005];
char ab[700000];
u32 wh, st[20], top;
il void print(u32 x) {
    while (x >= 10)
        st[++top] = x % 10, x /= 10;

    st[++top] = x;

    while (top)
        ab[wh++] = st[top] + '0',
                   --top;

    ab[wh++] = '\n';
}
main() {
    u32 n = read();

    for (u32 i = 1; i <= n; ++i)
        ++a[i / siz].len, a[i / siz].ab[a[i / siz].len] = read(), a[i / siz].ins(a[i / siz].ab[a[i / siz].len]);

    lock = n / siz + 1;

    for (u32 i = 1; i <= lock; ++i)
        pos[i] = i - 1;

    for (u32 i = 1; i < lock; ++i) {
        for (u32 j = 0; j <= 70000; ++j)
            a[i].ba[j] += a[i - 1].ba[j];

        for (u32 j = 0; j <= 140; ++j)
            a[i].baa[j] += a[i - 1].baa[j];
    }

    u32 m = read();

    for (u32 i = 1, lastans = 0, opt, l, r, k; i <= m; ++i) {
        opt = rad();
        l = (read() ^ lastans), r = (read() ^ lastans);

        if (opt == 1) {
            k = (read() ^ lastans);
            lastans = 0;
            mi a1 = getpos(l), a2 = getpos(r);

            if (a1.aa == a2.aa) {
                for (u32 j = a1.bb, kkk = a1.bb, tmp = a2.bb; j <= tmp; ++j)
                    b[j - kkk + l] = a[pos[a1.aa]].ab[j];

                nth_element(b + l, b + l + k - 1, b + r + 1);
                lastans = b[l + k - 1];
            } else {
                for (u32 j = a1.bb, tmp = a[pos[a1.aa]].len; j <= tmp; ++j)
                    tm.ins(a[pos[a1.aa]].ab[j]);

                for (u32 j = a2.bb; j >= 1; --j)
                    tm.ins(a[pos[a2.aa]].ab[j]);

                u32 res = -1;

                for (u32 j = pos[a1.aa], tmp = pos[a2.aa - 1], aaa = 0, bbb; aaa <= 140; ++aaa) {
                    bbb = tm.baa[aaa] + a[tmp].baa[aaa] - a[j].baa[aaa];

                    if (k > tm.baa[aaa] + a[tmp].baa[aaa] - a[j].baa[aaa])
                        res += vsiz, k -= bbb;
                    else {
                        bbb = tm.ba[res + 1] + a[tmp].ba[res + 1] - a[j].ba[res + 1];

                        while (k > bbb)
                            k -= bbb, ++res, bbb = tm.ba[res + 1] + a[tmp].ba[res + 1] - a[j].ba[res + 1];

                        ++res;
                        break;
                    }
                }

                for (u32 j = a1.bb, tmp = a[pos[a1.aa]].len; j <= tmp; ++j)
                    tm.del(a[pos[a1.aa]].ab[j]);

                for (u32 j = a2.bb; j >= 1; --j)
                    tm.del(a[pos[a2.aa]].ab[j]);

                lastans = res;
            }

            print(lastans);
        } else if (opt == 2)
            modi(l, r);
        else
            insert(l, r);
    }

    fwrite(ab, 1, wh, stdout);
    return 0;
}