题意就是说问有多少个区间，其中有至少一种种类的宝珠出现的次数恰好为x次。
先预处理出每一个位置的宝珠下一个出现与其同种类的宝珠位置next和上一个出现与其同种类的位置pre
考虑在第i个位置的宝珠，要使其出现恰好x次，我们可以找到在i之后恰好出现了x次的位置j，这步操作可以用一定的技巧优化到O(1),那么对于区间[l,r],l∈[pre[i],i],r∈[j,next[j]],都满足题目要求的答案。
如何统计呢，可以把每次可行的区间看作一个矩形，底为[pre[i],i],高位[j,next[j]]，那么最后的答案就是这些矩形并的面积了
那么就是经典的线段树问题了，时间复杂度O(nlogn)
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;
const int N = ;
struct g{
int l,r,typ,h;
}v[N];
long long ans;
int n,i,j,a[N],x,tot;
int Next[N],pre[N],flag[N],s[N];
map<int,int> pos,tmp;
bool cmp(g a,g b)
{
return a.h<b.h;
}
void change(int x,int a,int b,int l,int r,int c)
{
if ((a<=l)&&(r<=b))
{
flag[x]+=c;
if (flag[x]) s[x]=r-l;else s[x]=s[*x]+s[*x+];
return;
}
int m=(l+r)>>;
if (a<m) change(*x,a,b,l,m,c);
if (m<b) change(*x+,a,b,m,r,c);
if (flag[x]) s[x]=r-l;
else s[x]=s[*x]+s[*x+];
}
int main()
{
int test;
scanf("%d",&test);
while (test--)
{
scanf("%d%d",&n,&x);
pos.clear();tmp.clear();
memset(flag,,sizeof(flag));
memset(pre,,sizeof(pre));
memset(Next,,sizeof(Next));
memset(s,,sizeof(s));
tot=;ans=;
for (i=;i<=n;i++)
{
scanf("%d",&a[i]);
Next[pos[a[i]]]=i;
pre[i]=pos[a[i]];
pos[a[i]]=i;
}
for (i=;i<=n+;i++)
if (Next[i]==) Next[i]=n+;
for (i=;i<=n;i++)
{
if (tmp[a[i]]==)
{
tmp[a[i]]=i;
for (j=;j<x;j++)
tmp[a[i]]=Next[tmp[a[i]]];
}
else
tmp[a[i]]=Next[tmp[a[i]]];
if (tmp[a[i]]!=n+)
{
v[++tot].l=pre[i]+;v[tot].r=i;v[tot].h=tmp[a[i]];v[tot].typ=;
v[++tot].l=pre[i]+;v[tot].r=i;v[tot].h=Next[tmp[a[i]]];v[tot].typ=-;
}
}
sort(v+,v++tot,cmp);
for (i=;i<=tot;i++)
{
ans+=(long long)(v[i].h-v[i-].h)*s[];
change(,v[i].l-,v[i].r,,n,v[i].typ);
}
printf("%I64d\n",ans);
}
}