自动搬运

查看原文

来自洛谷，原作者为

	Night_sea_64 距离省选还有 +inf 天。

搬运于2025-08-24 22:21:02，当前版本为作者最后更新于2023-10-29 13:10:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

以下的 $l$ 为左端点。题目中的 $l$ 用 $m$ 表示。

双指针。枚举左端点 $l$，双指针找出最后一个 $r$ 满足 $[l,r]$ 中没有连续两个相同的课的位置。这个过程中再维护每个种类的个数 $cnt$（只计算 $[l+m-1,r]$ 中的，如果 $l+m-1>r$ 就不计算）。最终左端点为 $l$ 的方案数即为 $\max(0,r-(l+m-1)-cnt(c_{l+m-1}))$。

代码挺短的，跑的也挺快，为 $O(n)$。

#include<algorithm>
#include<cstdio>
using namespace std;
int t,n,m,a[500010],cnt[500010];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        long long ans=0;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        int r=0;
        for(int l=1;l<=n;l++)
        {
            while((r<l||a[r]!=a[r+1])&&r<n)
                if(++r>=l+m-1)cnt[a[r]]++;
            ans+=max(0,r-(l+m-1)+1-cnt[a[l]]);
            if(r>=l+m-1)cnt[a[l+m-1]]--;
        }
        printf("%lld\n",ans);
    }
    return 0;
}