Make Rounddog Happy 启发式分治

//题意：给定一个序列，询问他有多少个合法子序列
//      合法条件：在区间内不会出现相同的数，同时 区间最大值-（区间长度）<= 给定常数k
//思路：启发式分治，详情见博客
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn = 3e5 + 10;
int a[maxn], st[maxn][21], lg[maxn], K, N; 
ll ans;
int A[maxn], B[maxn], vis[maxn];
int get(int L, int R)
{
    int k = lg[R - L + 1];
    return a[st[L][k]] >= a[st[R - (1 << k) + 1][k]] ? st[L][k] : st[R - (1 << k) + 1][k];
}
void solve(int L, int R) {
    if (L > R) return;
    int pos = get(L, R);//返回区间最大值位置
    if (pos - L < R - pos) {
        rep(i, L, pos) {
            int t = a[pos] - K, lR = i + t - 1;
            int fcy = min(R, B[i]);
            lR = max(lR, pos);
            if (lR > fcy) continue;
            ans += fcy - lR + 1;
        }
    }
    else {
        rep(i, pos, R) {
            int t = a[pos] - K, rL = i - t + 1;
            int fcy = max(L, A[i]);
            rL = min(rL, pos);
            if (rL < fcy) continue;
            ans += rL - fcy + 1;
        }
    }
    solve(L, pos - 1); solve(pos + 1, R);
}
int main() {
    int T;
    lg[0] = -1; rep(i, 1, maxn - 1) lg[i] = lg[i >> 1] + 1;//提前维护出log2
    cin >> T;
    while (T--) {
        cin >> N >> K; ans = 0;
        rep(i, 1, N) cin >> a[i];
        rep(i, 1, N) st[i][0] = i;//区间长度为1当然是自己最大啦
    
    rep(i, 1, 20) {
        for (int j = 1; j + (1 << i) - 1 <= N; j++) {
            st[j][i] = a[st[j][i - 1]] >= a[st[j + (1 << (i - 1))][i - 1]] ? st[j][i - 1] : st[j + (1 << (i - 1))][i - 1];
        }
    }//ST表维护出最大值的位置 

    rep(i, 1, N) vis[i] = 0;
    A[1] = 1; vis[a[1]] = 1;

    rep(i, 2, N) {
        if (vis[a[i]]) A[i] = max(A[i - 1], vis[a[i]] + 1);
        else A[i] = A[i - 1];
        vis[a[i]] = i;
    }

    rep(i, 1, N) vis[i] = 0;
    B[N] = N; vis[a[N]] = N;
    for (int i = N - 1; i >= 1; i--) {
        if (vis[a[i]]) B[i] = min(B[i + 1], vis[a[i]] - 1);
        else B[i] = B[i + 1];
        vis[a[i]] = i;
    }
        solve(1, N);
        cout << ans << endl;
    }
    return 0;
}