7.21多校——5289RMQ_st + 二分搜索——Assignment

/*
题意：

RMQ_st算法
复杂度：预处理nlogn 查询O(1)
实现：
用DP的思想
mx[i][j] 定义为以i为起点长度为1<<j的区间内的最大值
状态转移方程 mx[i][j] = mx[i][j-1] + mx[i+(1<<(j-1))][j-1] 
把区间分成长度为1<<(j-1)的两个部分
总共处理的长度从1到log2(n),起点从1到n
所以总复杂度O(nlogn)

二分搜索位置
假定了l到r之间必定有一段
二分搜索从i到n，得到以该点开始能到右边最多多少
如果i到mid可以说明二分区域在另一块，另l = mid
因为有RMQ的存在能得到该区间是否满足，二分对于数列需单调的要求就是因为要使得端点为极值

*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAX = 100000 + 10;
int mx[MAX][20], mn[MAX][20];
int a[MAX]; 
int n;
void  rmq()
{
    for(int i = 1; i <= n; i++)
        mx[i][0] = mn[i][0] = a[i];
        int m = log2(n*1.0);
        for(int i = 1; i <= m; i++){
            for(int j = 1;j <= n; j++){
                if(j + (1 << (i - 1)) <= n)
                    mx[j][i] = max(mx[j][i-1], mx[j + (1 << (i - 1))][i - 1]);
                    mn[j][i] = min(mn[j][i-1], mn[j + (1 << (i - 1))][i - 1]);
                }
            }
}

int rmqmin(int l, int r)
{
    int m = log2(1.0*(r - l + 1));
    return min(mn[l][m], mn[r - (1 << m) + 1][m]);
}

int rmqmax(int l, int r)
{
    int m = log2(1.0*(r - l + 1));
    return max(mx[l][m], mx[r - (1 << m) + 1][m]);
}

int cal(int l, int r)
{
    return rmqmax(l, r) - rmqmin(l, r);
}

int main()
{
    int T, k;
    scanf("%d", &T);
    while(T--){
        long long  ans = 0;
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        rmq();
       // printf("%d %d\n",rmqmax(2, 2),rmqmin(1,5));
        int l, r, mid;
        for(int i = 1; i <= n; i++){
            l = i, r = n;
            while(l + 1 < r){
                 mid = (l + r) >> 1;
                if(cal(i, mid) < k)
                    l = mid;
                else r = mid;
            }
            if(cal(i, r) < k)
                ans = ans + (long long )(r - i + 1);
            else{
               ans = ans + (long long )(l - i + 1);
            }
        }
       printf("%lld\n", ans);
    }
    return 0;
}