小y的序列

tag:

• st表o1查询套二分
• cf分段1800+

简单讲一下题意：

给定一个序列和k值
找到连续区间max-min = k的个数

解： 优先考虑st表，只要最大最小问题就先想一想能不能套st表。 然后发现，当起点固定的时候，他们的最大值是单调递增的，最小值是单调递减的。 有可能是单调队列，但我后面的想法更接近的是二分。

遵从单调性优先考虑二分。因此我立马反应过来这题的解法是二分+st表。 此时就要枚举起点，时间复杂度就成了$o(nlogn)o(nlogn)$

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
inline int read()
{
    char c = getchar(); int x = 0, f = 1;
    while (c < '0' || c>'9') { if (c == '-')f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}
int Max[MAXN][21];
int Min[MAXN][21];
#define ll long long
int lg[MAXN];
int Query(int l, int r)
{
    int k = lg[(r - l + 1)];
    return max(Max[l][k], Max[r - (1 << k) + 1][k]);//把拆出来的区间分别取最值 
}
int Query2(int l, int r)
{
    int k = lg[(r - l + 1)];
    return min(Min[l][k], Min[r - (1 << k) + 1][k]);//把拆出来的区间分别取最值 
}
int main()
{

    int N = read(), M = read();
    for (int i = 2; i <= N; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= N; i++)Min[i][0] =  Max[i][0] = read();
    for (int j = 1; j <= 21; j++)
        for (int i = 1; i + (1 << j) - 1 <= N; i++)//注意这里要控制边界 
         Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);//如果看不懂边界的话建议好好看看图 
    for (int j = 1; j <= 21; j++)
        for (int i = 1; i + (1 << j) - 1 <= N; i++)//注意这里要控制边界 
            Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);//如果看不懂边界的话建议好好看看图 
  /*  for (int i = 1; i <= M; i++)
    {
        int l = read(), r = read();
        printf("%d\n", Query(l, r));
    }*/
    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        int l = i, r = N+1;
        while (l < r) {
            int mid = l + r >> 1;
            int tmp1 = Query(i, mid);
            int tmp2 = Query2(i, mid);
            if (tmp1 - tmp2 >= M) {
                r = mid;
            }
            else l = mid + 1;
        }
       // cout << l - 1 << " ";
        ans -= l - 1;
        l = i, r = N + 1;
        while (l < r) {
            int mid = l + r >> 1;
            int tmp1 = Query(i, mid);
            int tmp2 = Query2(i, mid);
            if (tmp1 - tmp2 > M ) {
                r = mid;
            }
            else l = mid + 1;
        }
       // cout << l - 1 << " :::";
        ans += l - 1;
    }
    cout << ans << "\n";
    return 0;
}