这道题很神。


首先有一个十分好想的做法。

直接记录对于每一个位置左边最近的恰好构成 $W$ 的前驱位置 $pre$ 。

然后修改的话,可能需要修改后面一串东西。

这样就显得十分的 $\text{naive}$ 了。

用一些比较有意思的优化。

对于一个小区间包含在大区间的情况,小区间完全优于大区间。

因此我们可以根据这个东西,优化掉后面一串东西,只修改后面第一个前驱为 $x$ 的。

set维护一下位置集合即可。

const int N = 5e5 + 5;

int mx[N << 2], a[N], w[N];
#define lc p << 1
#define rc p << 1 | 1

void upd(int p) {mx[p] = max(mx[lc], mx[rc]);}

void build(int p, int l, int r) {
    if (l == r) {mx[p] = a[l]; return ;}
    int mid = l + r >> 1;
    build(lc, l, mid); build(rc, mid + 1, r);
    upd(p);
}

void modify(int p, int l, int r, int x, int d) {
    if (l == r) {mx[p] = d; return ;}
    int mid = l + r >> 1;
    if (x <= mid) modify(lc, l, mid, x, d);
    else modify(rc, mid + 1, r, x, d);
    upd(p);
}

int query(int p, int l, int r, int L, int R) {
    if (L <= l && R >= r) return mx[p]; 
    int mid = l + r >> 1, val = 0; 
    if (L <= mid) val = query(lc, l, mid, L, R);
    if (R > mid) val = max(val, query(rc, mid + 1, r, L, R));
    return val;
} 

set<int> p[N]; int n, m, W;

int pre(int x) {
    set<int>::ite it1 = p[w[x]].lower_bound(x), it2 = p[W - w[x]].lower_bound(x);
    if (it2 == p[W - w[x]].begin()) return 0;
    if (it1 == p[w[x]].begin()) return *(--it2);
    if (*(--it1) > *(--it2)) return 0;
    return *it2;
}

void Debug(int x) {
    printf(": %d\n", x);
}    

void solve() {
    qr(n); qr(m), qr(W);
    rep (i, 1, n) qr(w[i]), p[w[i]].insert(i);
    rep (i, 1, n) a[i] = pre(i); build(1, 1, n);
    int cnt = 0;
    rep (i, 1, m) {
        int op, x, y; qr(op), qr(x), qr(y);
        if (op == 1) {
            set<int>::ite it1 = p[w[x]].lower_bound(x), it2 = p[W - w[x]].lower_bound(x), it = it1;
            ++it1; p[w[x]].erase(it); 
             if (it1 != p[w[x]].end()) {
                 //Debug(*it1); 
                modify(1, 1, n, *it1, pre(*it1));
             } if (it2 != p[W - w[x]].end()) {
                 //Debug(*it2); 
                 modify(1, 1, n, *it2, pre(*it2));    
             } w[x] = y; p[w[x]].insert(x);
             it1 = p[w[x]].lower_bound(x), it2 = p[W - w[x]].lower_bound(x);
             modify(1, 1, n, *it1, pre(*it1));
             ++it1; 
             if (it1 != p[w[x]].end()) {
                 //Debug(*it1); 
                 modify(1, 1, n, *it1, pre(*it1));
             } if (it2 != p[W - w[x]].end()) {
                 //Debug(*it2); 
                 modify(1, 1, n, *it2, pre(*it2));
             } 
        } else {
            x ^= cnt; y ^= cnt; if (x > y) swap(x, y);
            if (query(1, 1, n, x, y) >= x) puts("Yes"), ++cnt;
            else puts("No");     
        }
    }
}