题目：
某同学拿到一组数列 $ a_1, a_2, cdots , a_n $，他想知道存在多少个区间 $ [l, r] $ 同时满足下列两个条件：
1. $ r - l + 1 = k $;
2. 在 $ a_l, a_{l + 1}, cdots , a_r $ 中，存在一个数至少出现 t 次。
要求要做的就是输出满足条件的区间个数。
input
第一行输入三个整数 $ n, k, t (1 leqslant n, k, t leqslant 10^5) $
第二行输入 n 个整数， $ a_1, a_2, cdots, a_n(1 leqslant a_i leqslant 10^5) $
output
输出区间个数。
Example
input
5 3 2 3 1 1 1 2
output
3
hint
样例中，因为区间 $ [1, 3] $ 中 1 出现了 2 次，区间 $ [ 2, 4] $ 中 1 出现了 3 次， 区间 $ [3, 5] $ 中 1 出现了 2 次，所以一共有 3 个区间满足条件。
这是在群里看到的一个题，感觉应该是一个dp题，但由于我太渣，推半天转移方程推不出来。。。决定先写一个暴力的试试，或者感觉可以维护一个区间树、树状树或者线段树。。。
方法一：暴力算法太暴力，摒弃了。。。
方法二：下面是一个简单的模拟算法。。
#include <iostream>
#include <minmax.h>
const int N = 100001;
using namespace std;
int main()
{
int n, k, t, dp;
int a[N], b[N];
while (~scanf_s("%d %d %d", &n, &k, &t))
{
dp = 0;
memset(b, 0, sizeof(b));
for (int i = 0; i < n; i++)
{
cin >> a[i];
b[a[i]]++;
dp = max(dp, b[a[i]]);
}
if (k == 1) cout << n << endl;
else if (t == 1) cout << n - k + 1 << endl;
else if (k == n) if (dp == t) cout << "1" << endl;
else cout << "0" << endl;
else
{
dp = 0;
for (int j = 0; j < n - k + 1; j++)
{
memset(b, 0, sizeof(b));
for (int i = j; i < k + j; i++)
{
int c = ++b[a[i]];
b[0] = max(b[0], c);
}
if (b[0] >= t) dp++;
}
cout << dp << endl;
}
}
return 0;
}
测试效果：
5 4 4 3 1 1 1 2 0 5 4 4 1 1 1 1 1 2 5 4 4 2 1 1 1 1 1 5 4 3 3 1 1 1 2 2 5 5 4 3 1 1 1 1 1 5 5 4 3 1 1 1 2 0 6 3 2 2 1 1 2 1 2 4 6 3 3 2 1 1 2 1 2 0 6 4 2 2 1 1 2 1 2 3 6 4 3 2 1 1 2 1 2 1
算法分析：
算法处理了几种情况的边界问题，以加快对边界情况的效率。（下面算法不考虑 memset() 的时间费用）
case 1.显然当区间 $ k = 1 $ 时，$ t = 1 $ 才符合输入条件，如果 $ t eq 1 $ , 则不存在这样的区间满足条件。时间复杂度 $ O(1) $;
case 2.当 $ t = 1 $ 时，我的答案是输出按 $ k $ 划分的区间个数即可，这是显然的。所以答案是 $ n - k + 1 $ 。时间复杂度 $ O(1) $;
case 3.当 $ k = n $ 时，我们只需要知道给出的 $ n $ 个数中是否存在一个出现次数等于 t 的数，如果存在则输出 1，不存在输出 0 。时间复杂度 $ O(1) $;
case 4.当 $ k = t $ 时，我们就只需要判断每个 $ k $ 区间中，是否存在一个数的出现次数等于 t，如果存在则 +1 。 时间复杂度 $ O((n - k) cdot k) = O(n cdot k) $
case 5.其他情况，即 $ n eq k eq t eq 1 $ 时，我用了一个 $ O((n - k) cdot k^2) $ 的算法来移动区间并计算 dp。
case 4.其他情况，一个时间复杂度为 $ O((n - k)cdot k) = O(n cdot k - k^2) = O(n cdot k) $ 的算法，空间复杂度 $ O(n) $。
有趣的是，题目要求输入的 $ a_i geq 1 $ 所以，我可以放心的使用 $ b[0] $ 来记录每个区间出现最多的数的次数。
方法三：树状数组。
思路：将重复出现的数用 1 表示在树状数组中，只出现过一次的就置为 0，然后区间查询即可。
算法复杂度
空间复杂度：$ O(n) $。常数比前一个算法大一点儿。
时间复杂度：预处理部分花费 $ O(n) $ 开销，每次需要检查所有区间，最外层循环 $ n - k $，然后，每个区间查询利用树状数组的 `query()` 开销 $ O(lgk) $，故而整体的开销为 $ O(n cdot lgk) $。
代码：
#include <bits/stdc++.h>
using namespace std;
#define lowbits(x) (x&(-x))
const int N = 1000010;
int id[N], has[N], fenwick[N];
void upd(int n, int k, int x){while (k <= n) fenwick[k] += x, k += lowbits(k);}
int sum(int k)
{
int ans = 0;
while (k > 0) ans += fenwick[k], k -= lowbits(k);
return ans;
}
int ask(int l, int r){return sum(r) - sum(l - 1);}
int main()
{
int n, k, t, dots;
memset(fenwick, 0, sizeof(fenwick));
memset(has, 0, sizeof(has));
cin >> n >> k >> t;
for (int i = 1; i <= n; i++)
{
cin >> id[i];
if (!has[id[i]])
has[id[i]] = i;
else {
if (!fenwick[has[id[i]]])
upd(n, has[id[i]], 1);
upd(n, i, 1);
}
}
dots = 0;
for (int i = 1; i <= n - k + 1; i++)
if (ask(i, k + i - 1) >= t) dots++;
cout << dots << endl;
return 0;
}