D 巅峰对决

D 巅峰对决

线段树：单点更新+区间查询。
既然任何时候这个数字均互不相同,那么就维护这个区间的最大值或者最小值即可。

#include <bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
using namespace std;
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;
typedef  long long ll;
ll a[maxn<<2];
ll n,m,q,op1,x,y,l,r;

struct sa{
    ll mn;
    ll mx;
}tr[maxn<<2];

inline void pushup(ll i)
{
    tr[i].mn = min(tr[i<<1].mn,tr[i<<1|1].mn);
    tr[i].mx = max(tr[i<<1].mx,tr[i<<1|1].mx);
}

void bulid(ll i,ll l,ll r)
{
    if(l==r){
        tr[i].mn=a[l];
        tr[i].mx=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    bulid(i<<1,l,mid);
    bulid(i<<1|1,mid+1,r);
    pushup(i);
}

inline void update (ll i,ll l,ll r,ll x,ll y)
{
    if(l>x||r<x) return;
    if(l==x&&l==r) {
        tr[i].mn=y;
        tr[i].mx=y;
        return;
    }
    ll mid=(l+r)>>1;
    update(i<<1,l,mid,x,y);
    update(i<<1|1,mid+1,r,x,y);
    pushup(i);
}

ll query_min(ll i,ll l,ll r,ll x,ll y)
{
    ll res=inf;
    if(l>y||r<x) return 0;
    if(l>=x&&r<=y) return tr[i].mn;
    ll mid=(l+r)>>1;
    if(x<=mid) res=min(res,query_min(i<<1,l,mid,x,y));
    if(y>mid)  res=min(res,query_min(i<<1|1,mid+1,r,x,y));
    return res;
}

ll query_max(ll i,ll l,ll r,ll x,ll y)
{
    ll res=-inf;
    if(l>y||r<x) return 0;
    if(l>=x&&r<=y) return tr[i].mx;
    ll mid=(l+r)>>1;
    if(x<=mid) res=max(res,query_max(i<<1,l,mid,x,y));
    if(y>mid)  res=max(res,query_max(i<<1|1,mid+1,r,x,y));
    return res;
}

namespace IO{
    char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;
    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);
    inline char gc(){
        if(ip!=ip_)return *ip++;
        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);
        return ip==ip_?EOF:*ip++;
    }
    inline void pc(char c){
        if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;
        *op++=c;
    }
    inline ll read(){
        register ll x=0,ch=gc(),w=1;
        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;
        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;
        return w*x;
    }
    template<class I>
    inline void write(I x){
        if(x<0)pc('-'),x=-x;
        if(x>9)write(x/10);pc(x%10+'0');
    }
    class flusher_{
    public:
        ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}
    }IO_flusher;
}
using namespace IO;

int main()
{
    n=read();q=read();
    rep(i,1,n)  a[i]=read();
    bulid(1,1,n);
    rep(i,1,q){
        op1=read();x=read();y=read();
        if(op1==1){
            update(1,1,n,x,y);
        }
        if(op1==2){
            l=query_min(1, 1, n, x, y);
            r=query_max(1, 1, n, x, y);
            if(y-x==r-l) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}