题意：

给你n个数字，求有多少个子区间满足
1.区间最大值 - 区间长度 ≤ \le ≤ k
2.区间内各元素不相同

题解：

今天学了启发式分治，这道题就可以用这个算法
1.每次找到该区间的最大值的位置，以此作为分割点，枚举区间短的部分作为端点，统计答案，然后两个区间再分治，再统计两个区间的答案
2.找区间最大值，我们可以直接用ST表，然后还要预处理出以每个点作前缀和后缀不同元素区间最长长度
具体看代码实现

AC_code:

#include<bits/stdc++.h>

using namespace std;
const int maxn = 1e6+5;
int a[maxn], pre[maxn], suf[maxn], vis[maxn];
int st[maxn][21], lg[maxn];
long long ans;
int n, k;
int cnt = 0;
int getmax(int l, int r) {
    int h = lg[r-l+1];
    if(a[st[l][h]] >= a[st[r-(1<<h)+1][h]]) {
        return st[l][h];
    } else {
        return st[r-(1<<h)+1][h];
    }
}
void init() {//预处理出每个值是2的几次方
    lg[0] = -1;
    for(int i = 1; i < maxn; i++) {
        lg[i] = lg[i>>1] + 1;
    }
}
void ST() {//ST表预处理
    for(int i = 1; i <= n; i++) {
        st[i][0] = i;
    }
    for(int i = 1; i <= 20; i++) {
        for(int j = 1; j <= n+1-(1<<i); j++) {
            if(a[st[j][i-1]] >= a[st[j+(1<<(i-1))][i-1]]) {
                st[j][i] = st[j][i-1];
            } else {
                st[j][i] = st[j+(1<<(i-1))][i-1];
            }
        }
    }
}
void pre_suf() {//预处理前缀不同数的最大长度 后缀不同数的最大长度
    for(int i = 1; i <= n; i++) {
        vis[i] = 0;
    }
    pre[1] = 1;
    vis[a[1]] = 1;
    for(int i = 2; i <= n; i++) {
        if(vis[a[i]]) {
            pre[i] = max(pre[i-1], vis[a[i]]+1);
        } else {
            pre[i] = pre[i-1];
        }
        vis[a[i]] = i;
    }
    for(int i = 1; i <= n; i++) {
        vis[i] = 0;
    }
    suf[n] = n;
    vis[a[n]] = n;
    for(int i = n-1; i >= 1; i--) {
        if(vis[a[i]]) {
            suf[i] = min(suf[i+1], vis[a[i]]-1);
        } else {
            suf[i] = suf[i+1];
        }
        vis[a[i]] = i;
    }
}
void merge(int l, int r) {
    if(l > r) {
        return ;
    }
    int pos = getmax(l, r);//以a[pos]为最大值
// printf("%d %d------\n", l, r);
// printf("%d\n", pos);
    if(pos - l < r - pos) { //枚举区间小的
        for(int i = l; i <= pos; i++) { //以i为左端点
            int t = a[pos] - k;
            int rr = i + t - 1;
            int R = min(r, suf[i]); //右端点最大可以取的值
            rr = max(rr, pos);//右端点最小可以取的值
            if(rr > R) {
                continue;
            }
            ans += R - rr + 1; //右端点可以取的值的长度
        }
    } else {
        for(int i = pos; i <= r; i++) {//以i为右端点
            int t = a[pos] - k;
            int ll = i - t + 1;
            int L = max(l, pre[i]); //右端点最大可以取的值
            ll = min(ll, pos);//右端点最小可以取的值
            if(ll < L) {
                continue;
            }
            ans += ll - L + 1; //右端点可以取的值的长度
        }
    }
    merge(l, pos-1);
    merge(pos+1, r);
}
int main() {
    int t;
    scanf("%d", &t);
    init();
    while(t--) {
        scanf("%d%d", &n, &k);
        ans = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        ST();
        pre_suf();
        merge(1, n);
        printf("%lld\n", ans);
    }
    return 0;
}