c.cpp

#pragma comment(linker, "/stack:2000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define mp make_pair
#define pb push_back
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
#define f first
#define s second

using namespace std;
int n, m, k, a[1000000];
const int INF = (int)(1e9 + 7);
const int MAXN = (int)(5e5 + 7);
set <int> sta[2100000], sta2[2100000];
int t[MAXN * 4], t3[MAXN * 4], t2[MAXN * 4], dp[MAXN * 4];
pair <int, pair <int, int> > mas[MAXN];

void build (int v, int tl, int tr) {
    if (tl == tr){
        if (sta[a[tl]].upper_bound(-tl) == sta[a[tl]].end())
            t[v] = -INF;
        else
            t[v] = -(*sta[a[tl]].upper_bound(-tl));

        t2[v] = a[tl];
        t3[v] = a[tl];
    }
    else {
        int tm = (tl + tr) / 2;
        build (v*2, tl, tm);
        build (v*2+1, tm+1, tr);
        t[v] = max(t[v*2], t[v*2+1]);
        t2[v] = max(t2[v*2], t2[v*2+1]);
        t3[v] = min(t3[v*2], t3[v*2+1]);
    }
}

int get_max2(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return -INF;
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return max(get_max2 (v*2, tl, tm, l, min(r,tm)), get_max2 (v*2+1, tm+1, tr, max(l,tm+1), r));
}

int get_max(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return -INF;
    if (l == tl && r == tr)
        return t2[v];
    int tm = (tl + tr) / 2;
    return max(get_max (v*2, tl, tm, l, min(r,tm)), get_max (v*2+1, tm+1, tr, max(l,tm+1), r));
}

int get_min(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return INF;
    if (l == tl && r == tr)
        return t3[v];
    int tm = (tl + tr) / 2;
    return min(get_min (v*2, tl, tm, l, min(r,tm)), get_min (v*2+1, tm+1, tr, max(l,tm+1), r));
}

void update (int v, int tl, int tr, int pos) {
    if (tl == tr){
        if (sta[a[tl]].upper_bound(-tl) == sta[a[tl]].end())
            t[v] = -INF;
        else
            t[v] = -(*sta[a[tl]].upper_bound(-tl));

        t2[v] = a[tl];
        t3[v] = a[tl];
    }
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update (v*2, tl, tm, pos);
        else
            update (v*2+1, tm+1, tr, pos);
        t[v] = max(t[v*2], t[v*2+1]);
        t2[v] = max(t2[v*2], t2[v*2+1]);
        t3[v] = min(t3[v*2], t3[v*2+1]);
    }
}
map <int, int> ma;
int main() {
    IOS;
    int n;
    cin >> n;
    vector <int> vec;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        vec.pb(a[i]);
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++){
        cin >> mas[i].f >> mas[i].s.f >> mas[i].s.s;
        if (mas[i].f == 1){
            vec.pb(mas[i].s.s);
        }
    }
    sort(vec.begin(), vec.end());
    ma[vec[0]] = 1;
    int it = 1;
    for (int i = 1; i < vec.size(); i++)
        if (vec[i] - vec[i - 1] == 1)
        {
            it++;
            ma[vec[i]] = it;
        }
        else if (vec[i] - vec[i - 1] > 1){
            it += 2;
            ma[vec[i]] = it;
        }

    for (int i = 1; i <= n; i++)
        a[i] = ma[a[i]];

    for (int i = 1; i <= n; i++){
        sta[a[i]].insert(-i);
        sta2[a[i]].insert(i);
    }
    build(1, 1, n);
    for (int i = 1; i <= q; i++)
    {
        int type;
        type = mas[i].f;
        if (type == 1){

            int pos, val;
            pos = mas[i].s.f;
            val = ma[mas[i].s.s];
            sta[a[pos]].erase(-pos);
            sta2[a[pos]].erase(pos);
            int gg = a[pos];
            a[pos] = val;
            sta[val].insert(-pos);
            sta2[val].insert(pos);
            update(1, 1, n, pos);
            if (sta2[gg].upper_bound(pos) != sta2[gg].end())
                update(1, 1, n, *sta2[gg].upper_bound(pos));

            if (sta2[val].upper_bound(pos) != sta2[val].end())
                update(1, 1, n, *sta2[val].upper_bound(pos));
        }
        else{
            int l, r;
            l = mas[i].s.f;
            r = mas[i].s.s;
            int l1 = get_min(1, 1, n, l, r);
            int r1 = get_max(1, 1, n, l, r);
            int z = get_max2(1, 1, n, l, r);
            //cout << "~~~!! " << z << ' ' << l1 << ' ' << r1 << endl;
            if (z < l && r1 - l1 == r - l)
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
    return 0;
}
/*

5
1 3 2 5 4
8
2 1 3
2 1 4
2 1 5
1 4 4
2 1 4
2 2 5
1 4 5
2 2 5
*/