本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-30 14:24:09

题目

考察：尺取法，桶。
题目简述：
给你长度为 $n$ 的一个序列 $c$，求序列中满足下列条件的子段 $[l,r]$ 个数：

• 序列长度（即 $r-l+1$）$\ge k$（题目中的 $l$）。
• 对于每个 $i$（$l\le i<r$），$c_i\ne c_{i+1}$。
• $c_l\ne c_r$。

$O(n^2)$ 暴力模拟肯定不行，我们可以往尺取法的方向想。

我们优先找到所有的 $c_i=c_{i+1}$ 的下标，将这个序列分段。
然后我们很容易发现，对于每个 $r$ 去找的合法的 $l$ 的个数，就是在 $r-k+1$ 之前 $l$ 的数量，减去等于 $c_r$ 的 $c_l$ 的数量。这两个数量都是很容易统计的，我们可以边做边维护桶。

这样基本就可以了，但是我们还要注意不能用 memset 清空桶。

代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int N=5e5+5;
int t,n,a[N],f[N],pr[N],cnt,l,sum,ans;
inl void solve(){
	cnt=ans=0;
	cin>>n>>l;
	rep(i,1,n) cin>>a[i];
	pr[++cnt]=0;
	rep(i,2,n)
		if(a[i-1]==a[i]) pr[++cnt]=i-1;
	pr[++cnt]=n;
\/\/	rep(i,1,cnt) cout<<pr[i]<<endl;
	rep(i,2,cnt){
		sum=0;
		rep(j,pr[i-1]+l,pr[i]){
			++f[a[j-l+1]];
			++sum;
			ans+=sum-f[a[j]];
		}
		rep(j,pr[i-1]+l,pr[i]) f[a[j-l+1]]=0;
	}
	cout<<ans<<endl;
}
signed main(){
	FAST;
	cin>>t;
	while(t--) solve();
	return 0;
}