线段树

巅峰对决

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
using namespace std;
int MAX, MIN, y, Max[400005], Min[400005];
void build(int p, int l, int r) {//建立线段树,p为下标
    if (l == r) {
        cin >> y;
        Max[p] = Min[p] = y;
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build((p << 1) + 1, mid + 1, r);
    Max[p] = max(Max[p << 1], Max[(p << 1) + 1]);//+可以改为|;左移一位最后一位肯定为0
    Min[p] = min(Min[p << 1], Min[(p << 1) + 1]);
}

void update(int l, int r, int L, int R, int p) {//线段树的更新;p为下标
    if (l >= L && r <= R) {
        Max[p] = Min[p] = y;//更新是直接修改值得操作
        return;
    }
    int mid = (l + r) >> 1;
    if (mid >= L)update(l, mid, L, R, p << 1);
    if (mid < R)update(mid + 1, r, L, R, (p << 1) + 1);
    Max[p] = max(Max[p << 1], Max[(p << 1) + 1]);
    Min[p] = min(Min[p << 1], Min[(p << 1) + 1]);
}
void search(int l, int r, int L, int R, int p) {//线段树的搜索
    if (l >= L && r <= R) {
        MAX = max(Max[p], MAX);
        MIN = min(Min[p], MIN);
        return;
    }
    int mid = (l + r) >> 1;
    if (mid >= L)search(l, mid, L, R, p << 1);
    if (mid < R)search(mid + 1, r, L, R, (p << 1) + 1);
}
int main()
{
    ios;
    int n, q;
    cin >> n >> q;
    build(1, 1, n);
    int cmd;
    while(q--) {
        cin >> cmd;
        if (cmd == 1) {
            int x;
            cin >> x >> y;
            update(1, n, x, x, 1);
        }
        else if (cmd == 2) {
            int l, r;
            cin >> l >> r;
            MAX = 0;
            MIN = INT_MAX;
            search(1, n, l, r,1);
            if (MAX - MIN == r - l)puts("YES");
            else puts("NO");
        }
    }
}