Nhận xét: Với mỗi đoạn ~[l,r]~, giả sử ~a[l+1], a[l+2],\ldots,a[r]~ cố định thì tồn tại hai số ~x~ và ~y~ sao cho nếu ~a[l]\lt x~ thì kết quả hàm ~play~ là ~x~, nếu ~a[l]\gt y~ thì kết quả là ~y~, còn không kết quả là ~a[l]~.

Từ nhận xét này ta có hướng giải của bài toán là sử dụng IT. Ta sẽ xây 2 IT khác nhau tương ứng với tính chẵn lẻ của ~l~ (hàm ~play~ sẽ duyệt qua từng cặp chỉ số liên tiếp). Mỗi nút trên cây sẽ lưu hai số ~x,y~ theo nhận xét ứng với đoạn tương ứng trên mảng.

Với hai nút con có ~x_1,y_1~ và ~x_2,y_2~ thì nút cha sẽ có giá trị ~x=\min(\max(x_1,x_2),y_2)~ và ~y=\max(\min(y_1,y_2),x_2)~. Việc cập nhật IT và lấy kết quả xin nhường cho bạn đọc.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 7, MINA = 1, MAXA = 1e9;

int a[MAXN], n, q, p, lf, rt, ok;
pair <int, int> segTree[2][MAXN * 4]; // pair <int, int>: min and max

void update(int h, int id, int l, int r, int p, int lf, int rt)
{
    if (p > r || p < l) return;
    if (l == r) return segTree[h][id] = {lf, rt}, void();
    int mid = (l + r) >> 1, g = id << 1;
    update(h, g, l, mid, p, lf, rt);
    update(h, g | 1, mid + 1, r, p, lf, rt);
    segTree[h][id] = {max(segTree[h][g].first, segTree[h][g | 1].first), min(segTree[h][g].second, segTree[h][g | 1].second)};
}

int travel(int h, int id, int l, int r, int i, int j)
{
    if (i > r || j < l) return 2;
    int ll = max(lf, segTree[h][id].first), rr = min(rt, segTree[h][id].second);
    if (l == r && ll > rr) return 0;
    if (l >= i && r <= j + 1 && ll <= rr)
    {
        lf = ll;
        rt = rr;
        p = l - 1;
        // if (p % 2 == h) ++p;
        return true;
    }
    int mid = (l + r) >> 1, g = id << 1;
    int t = travel(h, g | 1, mid + 1, r, i, j);
    if (t)
        return travel(h, g, l, mid, i, j);
    return false;
}

int main()
{
    if (fopen("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        // freopen("test.out", "w", stdout);
    }

    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i)
    {
        int mi = min(a[i], a[i + 1]), ma = max(a[i], a[i + 1]);
        update(i % 2, 1, 1, n - 1, i, mi, ma);
        update(1 - i % 2, 1, 1, n - 1, i, MINA - 1, MAXA + 1);
    }
    // cerr << "done" << '\n';
    while (q--)
    {
        // cerr << q << '\n';
        int o, l, r;
        cin >> o >> l >> r;

        if (o == 1)
        {
            a[l] = r;
            if (l > 1)
            {
                int mi = min(a[l - 1], a[l]), ma = max(a[l - 1], a[l]);
                update(1 - l % 2, 1, 1, n - 1, l - 1, mi, ma);
            }

            if (l < n)
            {
                int mi = min(a[l], a[l + 1]), ma = max(a[l], a[l + 1]);
                update(l % 2, 1, 1, n - 1, l, mi, ma);
            }
        }
        else 
        {
            if (r - l + 1 < 3) 
            {
                cout << a[l] << '\n';
                continue;
            }
            r -= (r - l + 1) % 2 == 0;
            ++l;
            --r;
            p = - 1;
            lf = MINA - 1;
            rt = MAXA + 1;
            // ok = 0;
            travel(l % 2, 1, 1, n - 1, l, r);
            // p += ok;
            if (a[p] < lf) cout << lf;
            else if (a[p] > rt) cout << rt;
            else cout << a[l - 1];
            cout << '\n';
            // cout << lf << ' ' << rt << ' ';
            // cout << p << '\n';
        }
    }

    return 0;
}