没人用ST表么?他比线段树快。
考虑先把ST表跑下来,然后循环一遍区间的起点,看一下这个区间的最大值,和 \(t\) 比较一下即可。
然后这题就做完了。ST表裸题。
int f[2000010][21], Logn[2000010], n, t, c;
void preLog() {
Logn[1] = 0;
Logn[2] = 1;
rep(i, 3, 2000000) Logn[i] = Logn[i / 2] + 1;
}
void preF() {
rep(j, 1, 21)
for(int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int main() {
int ans = 0;
read(n), read(t), read(c);
rep(i, 1, n) read(f[i][0]);
preLog();
preF();
rep(i, 1, n - c + 1) {
int x = i, y = i + c - 1;
int s = Logn[y - x + 1];
if((max(f[x][s], f[y - (1 << s) + 1][s])) <= t) ++ans;
}
print(ans);
return 0;
}