[传智杯 #2 决赛] 课程安排

Bulyly · 2023-09-08 15:07:35 · 题解

这是一篇清真的 two-pointer 题解。好想也好写，并且不需要用到其他的奇奇怪怪的东西。

先不考虑 l 的限制。我们需要做的是求出相邻两两不相等，且头尾也不相等的序列。考虑继续弱化限制，先不考虑头尾不等。我们从左开始枚举左端点 L，发现每个 L 对应的最大的 R 是单调不减的。我们可以通过双指针求出对于每个 L 的最大 R。[L,R] 都可作为合法的右端点。都是接着考虑头尾相等的区间。我们开一个桶来实时维护 [L,R] 区间中各课程出现的次数。显然有 Ans=R-L+1-(cnt_{a_L}-1)。加 1 是因为不包括 L 本身。

接着考虑限制 l。实际是限制了序列长度在 [l,n] 之间。利用前缀和思想用 [1,n] 的贡献减去 [1,l-1] 的贡献即可。

具体实现可以看看代码帮助理解。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5+10;
int T,n,l,r,a[N],cnt[N];
void solve() {
    scanf("%d%d",&n,&l);ll res1=0,res2=0;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),cnt[i]=0;
    r=0;
    for(int i=1;i<=n;i++) {
        if(i>r) r++,cnt[a[r]]++;
        while(r<n&&a[r]!=a[r+1]) ++r,++cnt[a[r]];
        --cnt[a[i]];
        res1+=r-i+1-cnt[a[i]];
    } 
    r=0;
    for(int i=1;i<=n;i++) {
        if(i>r) ++r,cnt[a[r]]++;
        while(r<n&&a[r]!=a[r+1]&&r+1-i+1<l) ++r,++cnt[a[r]];
        --cnt[a[i]];
        res2+=r-i+1-cnt[a[i]];
    } 
    printf("%lld\n",res1-res2); 
}
int main() {
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}