1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

namespace fast_io {
    //...
}using namespace fast_io;

const int MAXN = 50000;

int n,m,totn = 0;
int rt[MAXN],num[MAXN];

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

namespace prSegTree{
    int val[MAXN*50],ls[MAXN*50],rs[MAXN*50];
    int cnt = 0;int ll[MAXN],rr[MAXN],totx,toty;
    #define mid ((l+r) >> 1)
    void insert(int &nown,int pre,int l,int r,int pos,int d){
        nown = ++cnt;val[nown] = val[pre] + d;
        ls[nown] = ls[pre],rs[nown] = rs[pre];
        if(l == r) return;
        else{
            if(pos <= mid)
                insert(ls[nown],ls[pre],l,mid,pos,d);
            else if(pos >= mid+1)
                insert(rs[nown],rs[pre],mid+1,r,pos,d);
        }
    }
    void update(int pos,int v,int d){
        for(int i = pos;i<=totn;i += lowbit(i))
            insert(rt[i],rt[i],1,totn,v,d);
    }
    void add(int l,int r){
        totx = toty = 0;
        for(int i = l-1;i;i-=lowbit(i))
            ll[++totx] = rt[i];
        for(int i = r;i;i-=lowbit(i))
            rr[++toty] = rt[i];
    }
    int find_kth(int l,int r,int k){
        int sum = 0;
        if(l == r){
            return l;
        }
        else{
            for(int i = 1;i<=totx;i++) sum -= val[ls[ll[i]]];
            for(int i = 1;i<=toty;i++) sum += val[ls[rr[i]]];   
            if(k <= sum){
                for(int i = 1;i<=totx;i++)  ll[i] = ls[ll[i]];
                for(int i = 1;i<=toty;i++)  rr[i] = ls[rr[i]];
                return find_kth(l,mid,k);
            }
            else{
                for(int i = 1;i<=totx;i++)  ll[i] = rs[ll[i]];
                for(int i = 1;i<=toty;i++)  rr[i] = rs[rr[i]];
                return find_kth(mid+1,r,k-sum);
            } 
        }  
    }
    int query(int l,int r,int k){
        add(l,r);
        return find_kth(1,totn,k);
    }
}
 
map<int,int> S;int last[MAXN];

int op[MAXN],ql[MAXN],qr[MAXN],v[MAXN];

void init(){
    read(n),read(m);
    for(int i = 1;i<=n;i++)
        read(num[i]),S[num[i]] = 0;
    char t[23];
    for(int i = 1;i<=m;i++){
        read(t);read(ql[i]),read(qr[i]);
        if(t[0] == 'Q') op[i] = 1,read(v[i]);
        else S[qr[i]] = 0;
    }
    for(auto it = S.begin();it != S.end();it++)
        it->second = ++totn,last[totn] = it->first;
    for(int i = 1;i<=n;i++)
        prSegTree::update(i,S[num[i]],1);
}

void solve(){
    for(int i = 1;i<=m;i++){
        if(op[i] == 0)
            prSegTree::update(ql[i],S[num[ql[i]]],-1),
            prSegTree::update(ql[i],S[qr[i]],1),num[ql[i]] = qr[i]; 
        else
            print(last[prSegTree::query(ql[i],qr[i],v[i])]),print('\n');
    }
}


int main(){
    init();
    solve();
    flush();
    return 0;
}