巅峰对决

题意转化

我们可以看出，题目中就是让你求出一个区间内是否满足区间内是这么一种情况，在题面的最后我们知道了，数字互不相同，这样我们就可以大胆做了。

首先，我们可以看到上边那个等差数列可以转化为 ,因为上边的等差数列求和之后是，n*(区间长度) - (1+2+\dots +区间长度-1)。然后我们可以维护一个最大值，维护一个区间和。

code

#include <bits/stdc++.h>
#define N 110000
#define lson rt << 1
#define rson rt << 1 | 1
#define M 1010

using namespace std;
int n, m;
struct node {
    int max, sum;
}tree[N << 2];

int read() {
    int s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

void push_up(int rt) {
    tree[rt].sum = tree[lson].sum + tree[rson].sum;
    tree[rt].max = max(tree[lson].max, tree[rson].max);
}

void build(int rt, int l, int r) {
    if (l == r) {
        tree[rt].sum = tree[rt].max = read();
        return;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    push_up(rt);
}

void updata(int rt, int c, int l, int r, int pos) {
    if (l == r) {
        tree[rt].max = tree[rt].sum = c;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) updata(lson, c, l, mid, pos);
    else updata(rson, c, mid + 1, r, pos);
    push_up(rt);
}

int query_max(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) return tree[rt].max;
    int mid = (l + r) >> 1, ans = -1;
    if (L <= mid) ans = max(ans, query_max(lson, l, mid, L, R));
    if (R > mid) ans = max(ans, query_max(rson, mid + 1, r, L, R));
    return ans;
}

int query_sum(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) return tree[rt].sum;
    int mid = (l + r) >> 1, ans = 0;
    if (L <= mid) ans += query_sum(lson, l, mid, L, R);
    if (R > mid) ans += query_sum(rson, mid + 1, r, L, R);
    return ans;
}

int main() {
    n = read(), m = read();
    build(1, 1, n);
    for (int i = 1, opt, x, y; i <= m; i++) {
        opt = read();
        if (opt == 1) {
            x = read(), y = read();
            updata(1, y, 1, n, x);
        }
        if (opt == 2) {
            x = read(), y = read();
            int sy = (y - x + 1);
            sy = (sy - 1) * sy / 2;
            int sum = query_sum(1, 1, n, x, y), maxx = query_max(1, 1, n, x, y);
            if (maxx * (y - x + 1) - sy == sum) puts("YES");
            else puts("NO");
        }
    }
}

​```