ACdream 1427 Nice Sequence

Description

      Let us consider the sequence a₁, a₂,..., a_n of non-negative integer numbers. Denote as c_i,j the number of occurrences of the number i among a₁,a₂,..., a_j. We call the sequence k-nice if for all i₁<i₂ and for all j the following condition is satisfied: c_i1,j ≥ c_i2,j −k. 

      Given the sequence a₁,a₂,..., a_n and the number k, find its longest prefix that is k-nice.

Input

      The first line of the input file contains n and k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ 200 000). The second line contains n integer numbers ranging from 0 to n.

Output

      Output the greatest  l such that the sequence a  ₁, a  ₂,..., a  _l is k-nice.

Sample Input

10 1 0 1 1 0 2 2 1 2 2 3 2 0 1 0

Sample Output

8

0

线段树

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=500005;
int n,k,a[maxn],f[2][maxn],cnt[maxn],N;

int work(int x,int y,int z)
{
  if (x) return y>z?y:z;
  else return y<z?y:z;
}

void insert(int x,int y,int z)
{
  y+=N;
  f[x][y]=z;
  for (int i=(y>>1);i;i>>=1)
  {
    f[x][i]=work(x,f[x][i+i],f[x][i+i+1]);
  }
}

int get(int x,int l,int r)
{
  int ans;
  if (r==0) return 0x7FFFFFF;
  if (l==n+2) return -1;
  if (x) ans=0; else ans=0x7FFFFFF;
  for (l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1)
  {
    if (~l&1) ans=work(x,f[x][l^1],ans);
    if ( r&1) ans=work(x,f[x][r^1],ans);
  }
  return ans;
}

int main()
{
  int i;
  while (~scanf("%d%d",&n,&k))
  {
    memset(f,0,sizeof(f));
    memset(cnt,0,sizeof(cnt));
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    for (N=1;N<=n+1;N+=N);
    for (i=1;i<=n;i++)
    {
      int x=a[i]+1;
      int y=get(0,1,x-1);
      int z=get(1,x+1,n+1);
      cnt[x]++;
      if (cnt[x]-k>y||cnt[x]+k<z) break;
      insert(0,x,cnt[x]);
      insert(1,x,cnt[x]);
    }
    printf("%d\n",i-1);
  }
  return 0;
}