OIG XIV - wyc

// https://szkopul.edu.pl/problemset/problem/JNhvAh92A36wFYa5HfIZpcv_/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int sizik = 1000 * 1001, INF = 1e9 + 7;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

std::vector<int> arr;
std::map<int, std::set<int>> positions;

int d1[sizik];
struct Najszybsze {
    int ll = 1, n = 1;

    int op(int a, int b) { return std::max(a, b); }

    int getFirst(int v, int tl, int tr, int l, int r, int x) {
        if (tl > r || tr < l) return -1;
        if (d1[v] <= x) return -1;

        if (tl == tr) return tl;

        int tm = (tl + tr) / 2;

        int left = getFirst(2 * v, tl, tm, l, r, x);
        if (left != -1) return left;

        return getFirst(2 * v + 1, tm + 1, tr, l, r, x);
    }

    void update(int v, int a) {
        v += ll - 1;
        d1[v] = a;
        while (v > 1) {
            v /= 2;
            d1[v] = op(d1[2 * v], d1[2 * v + 1]);
        }
    }

    Najszybsze() {
        n = arr.size();
        while (ll < n) {
            ll *= 2;
        }

        for (int i = 0; i <= 2 * ll; i++) {
            d1[i] = 0;
        }

        for (int i = 0; i < n; i++) {
            d1[i + ll] = arr[i];
        }

        for (int i = ll - 1; i > 0; i--)
            d1[i] = op(d1[2 * i], d1[2 * i + 1]);
    }
};

std::multiset<int> d2[sizik];
struct Najtansze {
    int ll = 1, n = 1;

    int op(int a, int b) { return std::min(a, b); }

    void build(const std::vector<int>& arr, int v, int tl, int tr) {
        if (tl == tr) {
            std::multiset<int> temp;
            temp.insert(arr[tl - 1]);

            d2[v] = temp;
        } else {
            int tm = (tl + tr) / 2;
            build(arr, v * 2, tl, tm);
            build(arr, v * 2 + 1, tm + 1, tr);

            d2[v].insert(d2[2 * v].begin(), d2[2 * v].end());
            d2[v].insert(d2[2 * v + 1].begin(), d2[2 * v + 1].end());
        }
    }

    int query(int v, int tl, int tr, int l, int r, int x) {
        if (l > r) {
            return INF;
        }
        if (l == tl && r == tr) {
            auto ptr = d2[v].lower_bound(x);

            if (ptr == d2[v].end()) {
                return INF;
            }

            return *ptr;
        }

        int tm = (tl + tr) / 2;
        return op(query(v * 2, tl, tm, l, std::min(r, tm), x), query(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r, x));
    }

    void update(int v, int tl, int tr, int pos, int val) {
        d2[v].erase(d2[v].find(arr[pos - 1]));
        d2[v].insert(val);

        if (tl != tr) {
            int tm = (tl + tr) / 2;
            if (pos <= tm) {
                update(2 * v, tl, tm, pos, val);
            } else {
                update(2 * v + 1, tm + 1, tr, pos, val);
            }
        } else {
            auto& y = positions[arr[pos - 1]];
            y.erase(y.find(pos));

            arr[pos - 1] = val;

            auto& y2 = positions[arr[pos - 1]];
            y2.insert(pos);
        }

        return;
    }

    Najtansze() {
        n = arr.size();
        while (ll < n) {
            ll *= 2;
        }

        build(arr, 1, 1, ll);
    }
};

void solve() {
    int n, q;
    std::cin >> n >> q;

    for (int i = 0, a; i < n; i++) {
        std::cin >> a;
        arr.push_back(a);

        positions[a].insert(i + 1);
    }

    Najszybsze szybko;
    Najtansze tanio;

    for (; q > 0; q--) {
        std::string s;
        std::cin >> s;

        if (s[0] == 'z') {
            int d, c;
            std::cin >> d >> c;

            szybko.update(d, c);
            tanio.update(1, 1, tanio.ll, d, c);
        } else if (s[3] == 's') {
            int l, r, v;
            std::cin >> l >> r >> v;

            int ans = szybko.getFirst(1, 1, szybko.ll, l, r, v);

            if (ans == -1) {
                std::cout << "NIE\n";
            } else {
                std::cout << ans << '\n';
            }
        } else /*if(s[3] == 't')*/ {
            int l, r, v;
            std::cin >> l >> r >> v;

            int ans = tanio.query(1, 1, tanio.ll, l, r, v + 1);

            if (ans == INF) {
                std::cout << "NIE\n";
            } else {
                ans = *positions[ans].lower_bound(l);

                std::cout << ans << '\n';
            }
        }
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}