qwq

https://www.luogu.com.cn/record/98416125

#include <bits/stdc++.h>
using namespace std;
const int N = 4e7 + 5, M = 1e5 + 5;
int n, q, qwq, cnt, a[M], l[M], r[M], k[M], t[M << 1], sum[N], Ls[N], Rs[N], T[N];
char opt[M];
inline int ls(int p) { return Ls[p] ? Ls[p] : Ls[p] = ++ cnt; }
inline int rs(int p) { return Rs[p] ? Rs[p] : Rs[p] = ++ cnt; }
inline int Rt(int p) { return T[p] ? T[p] : T[p] = ++ cnt; }
void modify(int p, int l, int r, int t, int k) {
    sum[p] += k;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (t <= mid) modify(ls(p), l, mid, t, k);
    else modify(rs(p), mid + 1, r, t, k);
}
int query(int p, int l, int r, int nl, int nr) {
    if (nl <= l && r <= nr) return sum[p];
    int mid = (l + r) >> 1, res = 0;
    if (nl <= mid) res += query(ls(p), l, mid, nl, nr);
    if (nr > mid) res += query(rs(p), mid + 1, r, nl, nr);
    return res;
}
void Modify(int p, int l, int r, int t, int k, int v) {
    modify(Rt(p), 1, n, t, v);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (k <= mid) Modify(ls(p), l, mid, t, k, v);
    else Modify(rs(p), mid + 1, r, t, k, v);
}
int Query(int p, int l, int r, int pl, int pr, int nl, int nr) {
    if (nl <= l && r <= nr) return query(Rt(p), 1, n, pl, pr);
    int mid = (l + r) >> 1, res = 0;
    if (nl <= mid) res += Query(ls(p), l, mid, pl, pr, nl, nr);
    if (nr > mid) res += Query(rs(p), mid + 1, r, pl, pr, nl, nr);
    return res;
}
int Kth(int p, int l, int r, int nl, int nr, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1, v = query(Rt(ls(p)), 1, n, nl, nr);
    if (v >= k) return Kth(ls(p), l, mid, nl, nr, k);
    else return Kth(rs(p), mid + 1, r, nl, nr, k - v);
}
int main() {
  	ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q, cnt = 1;
    for (int i = 1; i <= n; i ++)
        cin >> a[i], t[++ qwq] = a[i];
    for (int i = 1; i <= q; i ++) {
        cin >> opt[i];
        if (opt[i] != '3') cin >> l[i] >> r[i] >> k[i];
        if (opt[i] == '3') cin >> l[i] >> k[i];
		if (opt[i] != '2') t[++ qwq] = k[i]; 
    }
    sort(t + 1, t + 1 + qwq), qwq = unique(t + 1, t + 1 + qwq) - t - 1;
    for (int i = 1; i <= n; i ++)
    	a[i] = lower_bound(t + 1, t + 1 + qwq, a[i]) - t, Modify(1, 1, qwq, i, a[i], 1);
    for (int i = 1; i <= q; i ++) {
    	if (opt[i] != '2') k[i] = lower_bound(t + 1, t + 1 + qwq, k[i]) - t;
    	if (opt[i] == '1') cout << Query(1, 1, qwq, l[i], r[i], 1, k[i] - 1) + 1 << '\n';
        if (opt[i] == '2') cout << t[Kth(1, 1, qwq, l[i], r[i], k[i])] << '\n';
        if (opt[i] == '3') Modify(1, 1, qwq, l[i], a[l[i]], -1), a[l[i]] = k[i], Modify(1, 1, qwq, l[i], k[i], 1);
		if (opt[i] == '4') {
			int v = Query(1, 1, qwq, l[i], r[i], 1, k[i] - 1);
			if (1 <= v) cout << t[Kth(1, 1, qwq, l[i], r[i], v)] << '\n';
			else puts("-2147483647");
		}
		if (opt[i] == '5') {
			int v = Query(1, 1, qwq, l[i], r[i], 1, k[i]) + 1;
			if (v <= r[i] - l[i]) cout << t[Kth(1, 1, qwq, l[i], r[i], v)] << '\n';
			else puts("2147483647");
		} 
    }
    return 0;
}