巅峰对决-题解

题目描述
世界第一名侦探牛牛与拥有***的牛能互为对方的知音与最强的对手，在某次对决中，牛能给出a[1],a[2],…,a[n]a[1],a[2],…,a[n]这nn个数字，而他会对牛牛进行qq次询问，每次询问的类型如下：

1：将a[x]a[x]的值改为yy。

2：询问[l,r][l,r]区间是否可以形成一段连续的数字。若对[l,r][l,r]区间的数字从小到大排序之后，有a[l]=a[l+1]-1=a[l+2]-2=…=a[r]-r+la[l]=a[l+1]−1=a[l+2]−2=…=a[r]−r+l，则认为该区间可以形成一段连续的数字。特别的，当ll等于rr时，也认为该区间可以形成一段连续的数字。
数据保证，任何时候这nn个数字均互不相同。请问牛牛对每个22类型询问的答案是什么？

思路：经典线段树，因为每个数字都不相同，那么我们只需要知道区间最大值和区间最小值是否等于区间大小就行了，然后区间修改，区间查询........
代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int a[100005],n,q;
int maxn[500005],minn[500005];
int pushup(int id)
{
    maxn[id]=max(maxn[id*2],maxn[id*2+1]);
    minn[id]=min(minn[id*2],minn[id*2+1]);
}
void build(int id,int l,int r)
{
    if(l==r){
        maxn[id]=minn[id]=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    pushup(id);
}
void update(int id,int l,int r,int pos,int w)
{
    if(l==r){
        maxn[id]=minn[id]=w;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid)update(id*2,l,mid,pos,w);
    else update(id*2+1,mid+1,r,pos,w);
    pushup(id);
    //printf("%d %d %d %d\n",l,r,minn[id],maxn[id]);
}
int querymax(int id,int l,int r,int ul,int ur)
{
    if(ul<=l&&ur>=r){
        return maxn[id];
    }
    int mid=(l+r)/2;
    int temp=0;
    if(ul<=mid)temp=max(temp,querymax(id*2,l,mid,ul,ur));
    if(ur>mid)temp=max(temp,querymax(id*2+1,mid+1,r,ul,ur));
    return temp;
}
int querymin(int id,int l,int r,int ul,int ur)
{
    if(ul<=l&&ur>=r){
        return minn[id];
    }
    int mid=(l+r)/2;
    int temp=0x3f3f3f3f;
    if(ul<=mid)temp=min(temp,querymin(id*2,l,mid,ul,ur));
    if(ur>mid)temp=min(temp,querymin(id*2+1,mid+1,r,ul,ur));
    //printf("%d\n",temp);
    return temp;
}
int main()
{
    memset(minn,0x3f3f3f3f,sizeof(minn));
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    while(q--){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1){
            update(1,1,n,x,y);
        }else{
            //printf("%d %d\n",querymax(1,1,n,x,y),querymin(1,1,n,x,y));
            if(querymax(1,1,n,x,y)-querymin(1,1,n,x,y)==y-x){
                printf("YES\n");
            }else printf("NO\n");
        }
    }
    return 0;
}