P6465 [传智杯 #2 决赛] 课程安排 讲解
zrl123456
·
·
题解
题目
考察：尺取法，桶。
题目简述：
给你长度为 n 的一个序列 c，求序列中满足下列条件的子段 [l,r] 个数：
- 序列长度（即 r-l+1）\ge k（题目中的 l）。
- 对于每个 i（l\le i<r），c_i\ne c_{i+1}。
-
我们优先找到所有的 $c_i=c_{i+1}$ 的下标，将这个序列分段。
然后我们很容易发现，对于每个 $r$ 去找的合法的 $l$ 的个数，就是在 $r-k+1$ 之前 $l$ 的数量，减去等于 $c_r$ 的 $c_l$ 的数量。这两个数量都是很容易统计的，我们可以边做边维护桶。
这样基本就可以了，但是我们还要注意不能用 memset 清空桶。
代码：
```cpp
#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;
}
```