luogu 2617

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>

using namespace std;

#define LL long long

#define gc getchar()
inline int read() {int x = 0; char c = gc; while(c < ‘0‘ || c > ‘9‘) c = gc;
while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘,c = gc; return x;}
inline LL read_LL() {LL x = 0; char c = gc; while(c < ‘0‘ || c > ‘9‘) c = gc;
while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘,c = gc; return x;}
#undef gc

const int N = 1e5 + 10;

struct Node {int opt,l,r,k;} Ask[N];

int n,m;
int A[N],Num[N << 1],Length;

int root[N],Lson[N * 400],Rson[N * 400],W[N * 400];
int root_add[30],root_cut[30];
int jsadd,jscut;

int Lowbit(int x) {return (x & (-x));}

int Hjt;

void Poi_G(int &rt,int l,int r,int k,int val) {
    if(!rt) rt = ++ Hjt;
    W[rt] += val;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(k <= mid) Poi_G(Lson[rt],mid,val);
    else Poi_G(Rson[rt],mid + 1,val);
}

void Pre_Poi_G(int x,int val) {
    int k = lower_bound(Num + 1,Num + Length + 1,A[x]) - Num;
    for(int i = x; i <= n; i += Lowbit(i)) Poi_G(root[i],1,val);
}

int Sec_A(int l,int k) {
    if(l == r) return l;
    int sum = 0;
    for(int i = 1; i <= jsadd; i ++) sum += W[Lson[root_add[i]]];
    for(int i = 1; i <= jscut; i ++) sum -= W[Lson[root_cut[i]]];
    int mid = (l + r) >> 1;
    if(k <= sum) {
        for(int i = 1; i <= jsadd; i ++) root_add[i] = Lson[root_add[i]];
        for(int i = 1; i <= jscut; i ++) root_cut[i] = Lson[root_cut[i]];
        return Sec_A(l,k);
    } else {
        for(int i = 1; i <= jsadd; i ++) root_add[i] = Rson[root_add[i]];
        for(int i = 1; i <= jscut; i ++) root_cut[i] = Rson[root_cut[i]];
        return Sec_A(mid + 1,k - sum);    
    }
}

int Pre_Sec_A(int l,int k) {
    memset(root_add,0,sizeof root_add);
    memset(root_add,sizeof root_add);
    jsadd = jscut = 0;
    for(int i = r; i; i -= Lowbit(i)) root_add[++ jsadd] = root[i];
    for(int i = l - 1; i; i -= Lowbit(i)) root_cut[++ jscut] = root[i];
    return Sec_A(1,k);
}

int main() {
    n = read(),m = read();
    for(int i = 1; i <= n; i ++) A[i] = read(),Num[++ Length] = A[i];
    for(int i = 1; i <= m; i ++) {
        char c[2]; scanf("%s",c);
        Ask[i].opt = (c[0] == ‘Q‘ ? 1 : 0);
        if(Ask[i].opt == 1) Ask[i].l = read(),Ask[i].r = read(),Ask[i].k = read();
        else {Ask[i].l = read(),Ask[i].k = read(),Num[++ Length] = Ask[i].k;}
    }
    sort(Num + 1,Num + Length + 1);
    Length = unique(Num + 1,Num + Length + 1) - Num - 1;
    for(int i = 1; i <= n; i ++) Pre_Poi_G(i,1);
    for(int i = 1; i <= m; i ++) {
        if(Ask[i].opt == 1) {
            int Ans = Num[Pre_Sec_A(Ask[i].l,Ask[i].r,Ask[i].k)];
            printf("%dn",Ans);
        } else {
            Pre_Poi_G(Ask[i].l,-1);
            A[Ask[i].l] = Ask[i].k;
            Pre_Poi_G(Ask[i].l,1);
        }
    }
    return 0;
}