BZOJ-3048: [Usaco2013 Jan]Cow Lineup

Description

给你一个长度为n(1<=n<=100,000)的自然数数列，其中每一个数都小于等于10亿，现在给你一个k，表示你最多可以删去k类数。数列中相同的数字被称为一类数。设该数列中满足所有的数字相等的连续子序列被叫做完美序列，你的任务就是通过删数使得该数列中的最长完美序列尽量长。

就是找含有种类个数<=k+1的子区间中最多的同种元素个数。
可以对于一个r，贪心选择最小的l使得满足区间种类个数<=k+1，双指针即可。对于答案区间，一定能使得答案元素为最后一个元素，离散化+桶统计答案即可。时间复杂度O(nlogn)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,ans=1,a[101000],b[101000],c[101000],tot,num[101000];
int main()
{
    scanf("%d%d",&n,&m); ++m;
    for(int i=1;i<=n;++i) scanf("%d",a+i),b[i]=a[i];
    sort(b+1,b+n+1);
    c[++tot]=b[1];
    for(int i=2;i<=n;++i) if(b[i]!=b[i-1]) c[++tot]=b[i];
    for(int i=1;i<=n;++i) a[i]=lower_bound(c+1,c+tot+1,a[i])-c;
    int l=1,r=1,kin=1; num[a[1]]++;
    while(r<n)
    {
        ++r;
        kin+=(!num[a[r]]);
        num[a[r]]++;
        while(kin>m)
        {
            num[a[l]]--;
            kin-=(!num[a[l]]);
            ++l;
        }
        ans=max(ans,num[a[r]]);
    }
    printf("%d",ans);
    return 0;
}