对于给定的数组，我们先从一个子数组出发，如果当前 $a_i$ 在当前子数组中出现的次数超过了 $k$，那么不管它是不是众数，当前子数组一定是合法子数组，因为就算当前 $a_i$ 不是众数，众数也要超过 $a_i$ 的出现次数。所以这个问题其实可以不用考虑众数。 我们考虑数字的贡献，对于当前位置 $r$，我们尝试找到一个最近（从左往右）的满足条件的左端点 $l$，使得数字 $a_r$ 出现至少 $k$ 次，对于这样的 $l$ ，我们可以取遍所有的 $1 \sim l$ 作为左端点，这些区间必定是符合条件的，即答案增加 $l$ 。

代码实现：由于数据量为 $10^5$ ，我们用 map 离散化 $a_i$， 用命名为 V 的 vector 存离散化后相同的数的下标，假设某个数字被离散化之后对应的数字是 $x$，那么 V[x] 就表示所有这个数字的出现下标。 这样我们只需要判断 V[x].size() 是否大于等于 $k$ 就可以知道当前 $a_r$ 是否出现次数不小于 $k$，对于这样的 $r$，他最近的 $l$ 就是 max(l,V[x][V[x].size()-k] 如果当前 $a_r$ 不符合超过 $k$ 次那么我们左端点依旧是上次的 $l$，因为可以作为上个合法子数组的最后一位，即贡献为l。

spq使用线段树莽过：

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,k;
int x;
int a[N];
int cnt=1;
unordered_map<int,int> m;
long long sum=0;
int f[N];
int t[N];


struct node{
	int l,r;
	int maxx;
};
node tr[400005];
void build(int p,int l,int r){
	tr[p].l=l;
	tr[p].r=r;
	if(l==r){
		tr[p].maxx=t[l];
		return ;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tr[p].maxx=max(tr[p*2].maxx,tr[p*2+1].maxx);
}
void ch(int p,int x,int s){
	if(tr[p].l==x&&tr[p].r==x){
		tr[p].maxx=s;
		return ;
	}
	int mid=(tr[p].l+tr[p].r)/2;
	if(x<=mid){
		ch(p*2,x,s);
	}
	else{
		ch(p*2+1,x,s);
	}
	tr[p].maxx=max(tr[p*2].maxx,tr[p*2+1].maxx);
}
int ask(int p,int l,int r){
	if(l<=tr[p].l&&r>=tr[p].r){
		return tr[p].maxx;
	}
	int mid=(tr[p].l+tr[p].r)/2;
	int val=0;
	if(l<=mid){
		val=max(ask(p*2,l,r),val);
	}
	if(r>mid){
		val=max(ask(p*2+1,l,r),val);
	} 
	return val;
}


int main(){
	//freopen("sb.txt","r",stdin);
	scanf("%d",&n);
	scanf("%d",&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		if(m[x]==0){
			m[x]=cnt;
			cnt++;
		}
		a[i]=m[x];
	}
	cnt--;
	int l=1,r=1;
	t[a[l]]++;
	build(1,1,cnt);
	while(l<=n&&r<=n){
		while(ask(1,1,cnt)<k&&r<=n){
			r++;
			t[a[r]]++;
			ch(1,a[r],t[a[r]]);
		}
		if(r>n){
			break;
		}
		sum+=n-r+1;
		t[a[l]]--;
		ch(1,a[l],t[a[l]]);
		l++;
	}
	cout<<sum;
	return 0;
}
//