When numerous queries each admit a binary search solution, but performing binary search individually for every query is too slow, we can process all queries together using a technique known as simultaneous binary search (also called "parallel binary search" or "global binary search").

This approach requires:

1. Queries to be handled offline.
2. Updates to be independent and additive.
3. The answer space to support binary search (i.e., monotonic decision function).

Global k-th Smallest Element

Given a static array, answer multiple queries asking for the k-th smallest value in the entire array.

We maintain a value range [l, r] that potentially contains the answer for a group of queries. Let mid = (l + r) / 2. Using a Fanwick tree (Binary Indexed Tree), we count how many elements are ≤ mid. If this count ≥ k, the answer lies in [l, mid]; otherwise, it lies in (mid, r].

Each query participates in at most O(log U) recursive splits (where U is the value range), and each split processes all active queries in O(log n) time via the Fenwick tree. Total complexity: O(q log U log n).

void partition(int low, int high, int q_start, int q_end) {
    if (q_start > q_end) return;
    if (low == high) {
        for (int i = q_start; i <= q_end; ++i)
            result[queries[i].id] = low;
        return;
    }

    int mid = (low + high) >> 1;
    int left_cnt = 0, right_cnt = 0;

    // Evaluate each query against mid
    for (int i = q_start; i <= q_end; ++i) {
        if (fenw_query(mid) >= queries[i].k)
            left_buf[++left_cnt] = queries[i];
        else
            right_buf[++right_cnt] = queries[i];
    }

    // Reorder queries: left group first, then right
    for (int i = 1; i <= left_cnt; ++i)
        queries[q_start + i - 1] = left_buf[i];
    for (int i = 1; i <= right_cnt; ++i)
        queries[q_start + left_cnt + i - 1] = right_buf[i];

    partition(low, mid, q_start, q_start + left_cnt - 1);
    partition(mid + 1, high, q_start + left_cnt, q_end);
}

Range k-th Smallest Element

For queries asking the k-th smallest in subarray [L, R], treat the initial array as n point updates (position i gets value a[i]). During each binary search step over the value domain [l, r], only consider updates with value ≤ mid—add 1 at their positions in the Fenwick tree.

For a query [L, R, k], compute t = sum(R) - sum(L-1). If t ≥ k, the answer is in [l, mid]; otherwise, reduce k by t and search in (mid, r].

All operations (initial values and queries) are stored in one list and processed together during recursion.

Dynamic Range k-th Smallest

To support point updates (e.g., change a[x] = y), represent each modification as two operations: remove the old value and insert the new one. These are interleaved with queries in the global operation list.

During each recursive call on value range [l, r]:

• For update operations: if the value ≤ mid, apply the delta (+1 or -1) to the Fenwick tree and route the operation to the left half; else, route to the right.
• For query operations: compute current count in [L, R] from values ≤ mid. Decide direction based on comparison with k, adjusting k if going right.

After processing the left group, undo the Fenwick tree updates to maintain correctness for subsequent recursions.

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

const int MAXN = 300005;
const int MAXM = 300005;

struct Operation {
    int pos, val, k, id, type;
    // type=1: update; type=2: query
};

Operation ops[MAXM], left_ops[MAXM], right_ops[MAXM];
int arr[MAXN], fenw[MAXN];
int answers[MAXM];
int N, M, total_ops = 0, query_count = 0;

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

void bit_update(int idx, int delta) {
    for (int i = idx; i <= N; i += bit_lowbit(i))
        fenw[i] += delta;
}

int bit_prefix_sum(int idx) {
    int s = 0;
    for (int i = idx; i > 0; i -= bit_lowbit(i))
        s += fenw[i];
    return s;
}

int bit_range_sum(int l, int r) {
    return bit_prefix_sum(r) - bit_prefix_sum(l - 1);
}

void solve(int val_low, int val_high, int op_l, int op_r) {
    if (op_l > op_r) return;
    if (val_low == val_high) {
        for (int i = op_l; i <= op_r; ++i)
            if (ops[i].type == 2)
                answers[ops[i].id] = val_low;
        return;
    }

    int mid = (val_low + val_high) >> 1;
    int l_cnt = 0, r_cnt = 0;

    for (int i = op_l; i <= op_r; ++i) {
        if (ops[i].type == 1) {
            if (ops[i].val <= mid) {
                left_ops[++l_cnt] = ops[i];
                bit_update(ops[i].pos, ops[i].k); // k is +1 or -1
            } else {
                right_ops[++r_cnt] = ops[i];
            }
        } else {
            int cnt = bit_range_sum(ops[i].pos, ops[i].val);
            if (ops[i].k <= cnt) {
                left_ops[++l_cnt] = ops[i];
            } else {
                ops[i].k -= cnt;
                right_ops[++r_cnt] = ops[i];
            }
        }
    }

    // Undo Fenwick updates from left group
    for (int i = 1; i <= l_cnt; ++i)
        if (left_ops[i].type == 1)
            bit_update(left_ops[i].pos, -left_ops[i].k);

    // Rebuild ops segment
    for (int i = 1; i <= l_cnt; ++i)
        ops[op_l + i - 1] = left_ops[i];
    for (int i = 1; i <= r_cnt; ++i)
        ops[op_l + l_cnt + i - 1] = right_ops[i];

    solve(val_low, mid, op_l, op_l + l_cnt - 1);
    solve(mid + 1, val_high, op_l + l_cnt, op_r);
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &arr[i]);
        ops[++total_ops] = {i, arr[i], 1, 0, 1};
    }

    for (int i = 0; i < M; ++i) {
        char cmd[2];
        scanf("%s", cmd);
        if (cmd[0] == 'Q') {
            int L, R, K;
            scanf("%d %d %d", &L, &R, &K);
            ops[++total_ops] = {L, R, K, ++query_count, 2};
        } else {
            int idx, new_val;
            scanf("%d %d", &idx, &new_val);
            ops[++total_ops] = {idx, arr[idx], -1, 0, 1}; // remove old
            ops[++total_ops] = {idx, new_val, 1, 0, 1};   // add new
            arr[idx] = new_val;
        }
    }

    solve(0, 1000000000, 1, total_ops);

    for (int i = 1; i <= query_count; ++i)
        printf("%d\n", answers[i]);

    return 0;
}