P6465

Night_sea_64 · 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;
}