2021牛客暑期多校训练营5 K、King of Range

题目大意

给你长度为的序列，并且有次查询，每次查询给出一个，询问在中有多少个区间的最大值减掉最小值严格大于。

Solution

考点：双指针+表

考虑到区间不会修改，那么查找区间最值这个问题就用表维护就可以。

然后再看最大值减掉最小值严格大于，如果在这个区间符合要求，那么是不是在这些右区间都是合法的，因为随着数的加入，区间最大值一定不会变小，区间最小值一定不会变大，所以并不会变得不符合要求。

那么我们从左到右枚举，可以看出这个也是单调的，我们用表维护这个就可以了。

时间复杂度。

const int N = 1e5 + 7;

int st1[N][21], st2[N][21], Log2[N], a[N];

void pre() {
    Log2[1] = 0;
    Log2[2] = 1;
    for (int i = 3; i < N; ++i)    Log2[i] = Log2[i >> 1] + 1;
}

int queryMax(int l, int r) {
    int s = Log2[r - l + 1];
    return max(st1[l][s], st1[r - (1 << s) + 1][s]);
}

int queryMin(int l, int r) {
    int s = Log2[r - l + 1];
    return min(st2[l][s], st2[r - (1 << s) + 1][s]);
}

void sol() {
    pre();
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)   a[i] = st1[i][0] = st2[i][0] = read();
    int t = Log2[n]; //区间最长的2次方
    for (int j = 1; j <= t; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            st1[i][j] = max(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]),
            st2[i][j] = min(st2[i][j - 1], st2[i + (1 << (j - 1))][j - 1]);
    while (m--) {
        int k = read();
        ll ans = 0;
        int r = 1;
        for (int i = 1; i <= n; ++i) {
            while (r <= n && queryMax(i, r) - queryMin(i, r) <= k)
                ++r;
            if (r == n + 1)    break;
            //cout << r << endl;
            ans += n - r + 1;
        }
        print(ans);
    }
}