BZOJ 3048: [Usaco2013 Jan]Cow Lineup 双指针

看到这道题的第一个想法是二分+主席树（好暴力啊）

实际上不用这么麻烦，用一个双指针+桶扫一遍就行了 ~

code:

#include <bits/stdc++.h>

#define N 100006

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

int n,k,ans=1,kind,a[N],bu[N],A[N];

int main()

{

    // setIO("input");

    int i,j;

    scanf("%d%d",&n,&k);

    for(i=1;i<=n;++i)    scanf("%d",&a[i]),A[i]=a[i];

    sort(A+1,A+1+n);

    for(i=1;i<=n;++i)    a[i]=lower_bound(A+1,A+1+n,a[i])-A;

    bu[a[1]]=kind=1;

    int l=1;

    for(int r=2;r<=n;++r)

    {

        if(!bu[a[r]]) ++kind;

        ++bu[a[r]];

        while(l<=r&&kind>k+1)

        {

            --bu[a[l]];

            if(bu[a[l]]==0)  --kind;

            ++l;

        }

        ans=max(ans,bu[a[r]]);

    }

    printf("%d\n",ans);

    return 0;

}