Ở subtask thứ ~2~, việc tính ra giá trị ~Mex~ trong đoạn ~[l; r]~ trên mảng ~a~ ta có thể dễ dàng thực hiện nếu với mỗi giá trị ~x~ (~0 \le x \le 30~) ta tính được mảng ~cnt_x~ là số lượng số ~x~ trong đoạn ~[l; r]~ trên mảng ~a~.

Có được mảng ~cnt~ này ta cứ thử lần lượt các giá trị x tăng dần từ ~0~ đến ~30~, nếu giá trị nào chưa xuất hiện trong mảng (~cnt_x = 0~) ta biết được ngay giá trị ~Mex~ cần tìm là ~x~. Còn không, mọi giá trị từ ~0~ đến ~30~ đều xuất hiện thì giá trị ~Mex~ sẽ là 31.

Từ đây để tính nhanh mảng ~cnt~, cùng với việc không có truy vấn update trong subtask này, ta có thể sử dụng prefix sum cho từng giá trị ~x~.

Độ phức tạp ~O(q \cdot 31)~.

Ở subtask ~3~, nhìn vào truy vấn sắp xếp, ta thấy rằng, vì giá trị của ~a_i~ khá nhỏ (~0 \le a_i \le 30~) cho nên ta có thể sử dụng ý tưởng counting sort.

Xét truy vấn sort tăng dần, sau khi sắp xếp đoạn ~[l; r]~ sẽ có dạng kiểu ~cnt_0~ số ~0~ ở đầu, sau đó là ~cnt_1~ số ~1~ tiếp theo, ~cnt_2~ số ~2~ liền sau đó, ~\cdots~, ~cnt_{30}~ số ~30~ ở cuối.

Để thực hiện nhanh được việc lấy ra số lượng ở ~1~ đoạn và gán nhanh ~1~ đoạn liên tiếp ~1~ giá trị nào đó, ta có thể sử dụng segment tree với lazy update. Ta sẽ có ~31~ cây segment tree để quản lý số lượng vị trí trên mảng ~a~ mà có giá trị x trong đoạn.

Bây giờ ở truy vấn sort, lúc đầu ta có thể tính ra được nhanh mảng ~cnt_x~ trong đoạn mà ta cần sort, sau đó là thực hiện counting sort như trên. Ta gán ~cnt_0~ vị trí đầu tiên từ ~l~ là số ~0~ tương đương với việc, đầu tiên là xoá hết mọi vị trí mà có giá trị là ~0~ cũ trong đoạn bằng cách gán mọi phần tử trong đoạn ~[l; r]~ trên cây segment tree ~0~ bằng ~0~, sau đó gán trên cây segment tree ~0~ từ ~l~ đến ~l + cnt_0 - 1~ bằng ~1~. Ta cứ tiếp tục làm như vậy với từng giá trị tiếp theo, xoá hết mọi vị trí mà có giá trị là ~1~ cũ trong đoạn bằng cách gán mọi phần tử từ ~l~ đến ~r~ bằng ~0~ trên cây segment tree ~1~, rồi sau đó gán từ ~l + cnt_0~ đến ~l + cnt_0 + cnt_1 - 1~ trên cây segment tree ~1~ bằng ~1~. Ta tiếp tục vậy với mọi giá trị đến 30 là xong. Còn ở việc giảm dần cũng tương tự như vậy.

Ở truy vấn tìm ~Mex~ ta có thể thực hiện giống như subtask ~2~ với mảng ~cnt_x~ ta có thể tính nhanh bằng cách sử dụng ~31~ cây segment tree mà ta đã có sẵn.

Độ phức tạp ~O(q \cdot log2(n) \cdot 31)~.

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 1;
const int MAX_VAL = 31 + 1;

int n;
int a[MAX_N];
int lastAns;
int ST[MAX_VAL][MAX_N << 2];
int lazy[MAX_VAL][MAX_N << 2];
int currCnt[MAX_VAL];

void down(int i, int id, int l, int r) {
    if (!lazy[i][id]) return;
    int k = lazy[i][id];

    if (k == 1) {
        ST[i][id << 1] = ST[i][id << 1 | 1] = 0;
    }
    else {
        int mid = (l + r) >> 1;
        ST[i][id << 1] = mid - l + 1;
        ST[i][id << 1 | 1] = r - mid;
    }

    lazy[i][id << 1] = k;
    lazy[i][id << 1 | 1] = k;

    lazy[i][id] = 0;
}

void update(int i, int id, int l, int r, int u, int v, int val) {
    if (u > r || v < l) return;

    if (u <= l && r <= v) {
        if (val) {
            ST[i][id] = r - l + 1;
        }
        else {
            ST[i][id] = 0;
        }
        lazy[i][id] = val + 1;
        return;
    }

    int mid = (l + r) >> 1;
    down(i, id, l, r);
    update(i, id << 1, l, mid, u, v, val);
    update(i, id << 1 | 1, mid + 1, r, u, v, val);

    ST[i][id] = ST[i][id << 1] + ST[i][id << 1 | 1];
}

int get(int i, int id, int l, int r, int u, int v) {
    if (u > r || v < l) return 0;

    if (u <= l && r <= v) {
        return ST[i][id];
    }

    int mid = (l + r) >> 1;
    down(i, id, l, r);
    return get(i, id << 1, l, mid, u, v) + get(i, id << 1 | 1, mid + 1, r, u, v);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        update(a[i], 1, 1, n, i, i, 1);
    }

    int numCases = 0;
    cin >> numCases;
    for (int testCase = 1; testCase <= numCases; testCase++) {
        char type;
        cin >> type;

        int x, y;
        cin >> x >> y;

        if (x > y) swap(x, y);

        if (type == '1') {
            int type;
            cin >> type;

            for (int val = 0; val <= 30; val++) {
                currCnt[val] = get(val, 1, 1, n, x, y);
                update(val, 1, 1, n, x, y, 0);
            }

            int i = x;
            int step = 1, currVal = 0;
            if (type == 2) step = -1, currVal = 30;

            while (i <= y) {
                if (currCnt[currVal]) {
                    update(currVal, 1, 1, n, i, i + currCnt[currVal] - 1, 1);
                }
                i += currCnt[currVal];
                currVal += step;
            }
        }
        else {
            for (int val = 0; val <= 31; val++) {
                if (!get(val, 1, 1, n, x, y)) {
                    cout << val << '\n';
                    lastAns = val;
                    break;
                }
            }
        }
    }

    return 0;
}

/*


*/