[BZOJ 5127][Lydsy1712月赛]数据校验

Description

题库链接

给你一个长度为 (n) 的序列。(m) 次询问，每次询问序列的一个区间 ([l,r])。对于 ([l,r]) 内的所有子区间，询问值域是否连续。若存在一个子区间不连续则输出 NO。

(1leq n,mleq 100000)

Solution

日常划水。

显然，满足条件的区间中任意两个相邻的数差值不超过 (1)。并且这个条件与原问题等价。

预处理出一个数组 (maxr_i) 表示第 (i) 位向右延伸的最远位置，这个数组是可以继承的，可以 (O(n)) 求出。对于询问，直接比较 (maxr_l) 与 (r) 的大小即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100000+5;

int n, m, b[N], l, r, maxr[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for (int i = 1; i <= n; i++) {
        if (maxr[i-1] >= i) maxr[i] = maxr[i-1];
        else {
            int loc = i;
            while (abs(b[loc]-b[loc+1]) <= 1) ++loc;
            maxr[i] = loc;
        }
    }
    while (m--) {
        scanf("%d%d", &l, &r);
        if (maxr[l] >= r) puts("YES");
        else puts("NO");
    }
    return 0;   
}