你有连续的 \(n\) 天假期，第 \(i\) 天的温度为 \(a_i\) 。你计划在这 \(n\) 天中选择连续的若干天去旅游，至少为 \(k\) 天。给定一个 \(q\) ，你需要确保你出去旅游的时间中每天的温度都 \(\leq q\) 。询问你有多少种计划旅游的方案。
不难用双指针找出所有连续子段 \([l, r]\) 满足 \(max_{i = l}^{n} a_i \leq q\) 。设某一段长度为 \(len\) ，当 \(len \geq k\) ：
- \(k\) 天的方案数为 \(len - k + 1\) ；
- \(k + 1\) 天的方案数为 \(len - k + 2\) ；
- \(len\) 天的方案数位 \(1\) 。
归纳出长度为 \(len\ (len \geq k)\) 的段贡献为 \(\frac{(len - k + 1)(len - k + 2)}{2}\) 。
view
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
int n, k, q; std::cin >> n >> k >> q;
std::vector<int> a(n+1);
for (int i = 1; i <= n; i++) std::cin >> a[i];
ll ans = 0;
for (int i = 1; i <= n; i++) {
int j = i;
if (a[j] > q) continue; // 双指针的这一步很关键，需要保证 j 是非法第一位，不产生回退
while (j <= n && a[j] <= q) j++;
j -= 1;
int seg = j - i + 1;
if (seg >= k) ans += 1LL * (seg - k + 1) * (seg - k + 2) / 2;
i = j;
}
std::cout << ans << '\n';
}
int main() {
#ifndef ONLINE_JUDGE
freopen("IO/in", "r", stdin); freopen("IO/out", "w", stdout);
#endif
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}