分析

因为保证在任何时候数字不重复，当一个区间满足 时这个区间就是合法的。对于每个询问只需要求出区间 就可以了，用线段树维护，时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+100,inf = 0x3f3f3f3f;
int read() {int x;scanf("%d",&x);return x;}
int mx[N],mi[N],n,m,size;
void pushup(int u) {
    mx[u] = max(mx[u<<1],mx[u<<1|1]);
    mi[u] = min(mi[u<<1],mi[u<<1|1]);
}
void update(int u,int l,int r,int pos,int d) {
    int mid = l + r >> 1;
    if(l == r) {mx[u] = mi[u] = d;return;}
    if(pos <= mid) update(u<<1,l,mid,pos,d);
    else update(u<<1|1,mid+1,r,pos,d);
    pushup(u);
}
int ask1(int u,int l,int r,int L,int R) {
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) return mx[u];
    int mid = l + r >> 1;
    return max(ask1(u<<1,l,mid,L,R),ask1(u<<1|1,mid+1,r,L,R));
}
int ask2(int u,int l,int r,int L,int R) {
    if(l > R || r < L) return inf;
    if(L <= l && r <= R) return mi[u];
    int mid = l + r >> 1;
    return min(ask2(u<<1,l,mid,L,R),ask2(u<<1|1,mid+1,r,L,R));
}
int main()
{
    n = read();m = read();
    for(int i = 1;i <= n;i++) {
        int val = read();update(1,1,n,i,val);
    }
    while(m--) {
        int opt = read(),x = read(),y = read();
        if(opt == 1) update(1,1,n,x,y);
        else {
            int R = ask1(1,1,n,x,y),L = ask2(1,1,n,x,y);
            if(R-L == y-x) puts("YES");
            else puts("NO");
        }
    }
}