#C241001C. 简单计数
标签（Label）
- 哈希
- 线段树
网址（Website）
题目（Problem）
详情如下
题目描述
小 C 有一个长度为 $n$ 的序列 $a$，他定义区间 $[l, r]$ 是好的，当且仅当区间 $[l, r]$ 内的每个元素的出现次数都恰好为 $k$。
请求出所有的好区间的数量。
输入格式
从文件 count.in 中读入数据，每组数据包含多个测试点。
每个测试点的第一行包含两个正整数 $n, k$，表示序列长度和要求的元素出现次数。
接下来一行包含 $n$ 个正整数，代表序列 $a$。
输出格式
输出到文件 count.out 中。
对每一个测试点，输出一行一个正整数，代表好区间的数量。
样例
输入数据 1
1
10 2
3 1 2 2 1 3 3 1 2 1输出数据 1
8【样例1解释】
区间 $[3,4], [6,7], [2,5], [5,8], [1,6], [2,7], [3,8], [4,9]$ 都是好区间。
【输入输出样例2】
见选手目录下的 count/count2.in 与 count/count2.ans。
数据规模与约定
对于所有数据，有 $1 \leq \sum n \leq 2 \times 10^5, 1 \leq a_i \leq 10^9, 1 \leq k \leq n$。
| 测试点 | $\sum n \leq$ | 特殊性质1 | 特殊性质2 |
|---|---|---|---|
| $1 \sim 4$ | $2 \times 10^3$ | 无 | 无 |
| $5 \sim 7$ | $2 \times 10^5$ | $k = 2$ | 无 |
| $8 \sim 10$ | $2 \times 10^5$ | $k = 3$ | $a_i \leq 20$ |
| $11 \sim 20$ | $2 \times 10^5$ | 无 | 无 |
题解（Solution）
$\qquad$我采用的是 $\text{Hash}$ 做法。
$\qquad$首先将每一种颜色离散化，并且对于每个颜色，钦定这个颜色对应的 $\mathrm{Hash}$ 值（建议打双哈希），然后从前往后扫，算出每个位置的前缀 $\mathrm{Hash}$ 值，同时记录每个数出现的次数，每当这个次数是 $k$ 的整数倍时，就在前缀 $\mathrm{Hash}$ 值中减去当前这个数的这 $k$ 次贡献，容易发现，如果对于一个合法区间，如果前缀 $\mathrm{Hash}$ 相等，这个区间里面所有的元素个数一定都分别是 $k$ 的整数倍，那我们只需要判断这个区间里面每种元素的出现次数刚好是 $k$ 次而不是 $k$ 的倍数次就好了，这也是比较好处理的，记录每一个 $a[i]$ 在数组中出现的位置，记录当前位置往前数 $k$ 个相同的数后的第一个位置，所有在这个位置前面的位置都不能和 $i$ 这个位置组成区间。
$\qquad$时间复杂度 $O(n\log n)$ 。
算法分析
对于 $a_i$，记向后和它数值相同的第 $k-1$ 个数的下标为 $l$，第 $k$ 个数的下标为 $r$，则我们记以数字 $a_i$ 作为区间内该数值的开头的合法右端点区间为 $[l, r+1]$。
若区间 $[L, R]$ 合法，则对于每一种数值的开头位置 $k$，必须满足 $R$ 在 $k$ 所定义的合法区间内。
在左端点固定的条件下，我们可以看出区间 $[L, R]$ 合法的充要条件：
- $[L, R]$ 内的数值种类数必须与包含 $R$ 的合法区间数目相同（每一种数值只能产生一个合法区间）
考虑找到每一个位置上的数作为开头数值时的合法区间，可以倒序枚举，用 $\text{map}$ 套 $\text{vector}$ 存储每一个数值出现的位置，若加入位置 $i$ 的数满足 $\text{vector}$ 长度 $\geq k$，则可以直接求出对应的合法区间 $[l, r]$。
考虑枚举区间左端点 $i$，那么一种暴力算法是找出 $[L, n]$ 区间内所有数值的开头位置，并对于每一个开头位置 $i$，将 $[i, n]$ 区间 $+1$，代表以这个区间内某个数作为右端点 $R$ 时数值种类数会多 $1$。同时将对应的合法区间 $[l, r]$ 区间 $-1$，则上述充要条件等价于位置 $R$ 的数值为 $0$。可以利用线段树维护区间加法。
上面算法的瓶颈在于每一次要重新找数值的开头位置，倒序枚举左端点，用 $\text{map}$ 套 $\text{vector}$ 存储每一个数值出现的位置，若 $\text{vector}$ 长度不小于 $2$，则撤销上一次的区间修改操作，复杂度均摊 $O(n \log n)$。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<map>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 501234;
bool ST;
inline P operator+(P a,P b){return {a.x+b.x,a.y+b.y};}
inline P operator-(P a,P b){return {a.x-b.x,a.y-b.y};}
inline P operator*(int a,P b){return {a*b.x,a*b.y};}
struct HASH{
int mod1=1e9+9,mod2=998244353;
int bas1=1331,bas2=997;
int a[N],b[N];
void init(){a[0]=b[0]=1;For(i,1,2e5) a[i]=a[i-1]*bas1%mod1, b[i]=b[i-1]*bas2%mod2;}
inline P to(int x){return {a[x],b[x]};}
}H;
map<P,vector<int>> g;
int n,k,a[N];
map<int,int> mp;int tot;
vector<int> buc[N];
int lst[N],ans;
void calc(vector<int> v){
queue<int> q;
for(auto i:v){
while(q.size() && q.front() < lst[i]) q.pop();
ans += q.size(), q.emplace(i);
}
}
void Solve(){
mp.clear(),g.clear();
ans = tot = 0;
For(i,1,n){
buc[i].clear();
lst[i] = 0;
}
n = rd(), k = rd();
For(i,1,n){
a[i] = rd();
if(!mp.count(a[i])) mp[a[i]] = ++tot;
a[i] = mp[a[i]];
}
P leijia = {0,0};
g[leijia].emplace_back(0);
For(i,1,n){
leijia = leijia + H.to(a[i]);
buc[a[i]].emplace_back(i);
lst[i] = lst[i-1];
if(buc[a[i]].size()%k==0){
leijia = leijia - k*H.to(a[i]);
}
if((int)buc[a[i]].size()>k){
lst[i] = max(buc[a[i]][ buc[a[i]].size()-k-1 ], lst[i]);
}
g[leijia].emplace_back(i);
}
for(auto p:g) calc(p.y);
printf("%lld\n",ans);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
int T=rd();double Tim=clock();
H.init();while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
