Description
Let us consider the sequence a1, a2,..., an of non-negative integer numbers. Denote as ci,j the number of occurrences of the number i among a1,a2,..., aj. We call the sequence k-nice if for all i1<i2 and for all j the following condition is satisfied: ci1,j ≥ ci2,j −k.
Given the sequence a1,a2,..., an and the number k, find its longest prefix that is k-nice.
Input
Output
Sample Input
10 1
0 1 1 0 2 2 1 2 2 3
2 0
1 0
Sample Output
8
1
【题意】用线段树维护 0到A[i]-1间的最小值，用F[A[i]] 统计频率。判断 0 到 A[i]-1范围内的最小值与F[A[i]]-K的大小即可。
【思路】cnt[i]是当前i出现的次数。每次读入一个数a进来，cnt[a]++。只要c[1]...c[a-1]都满足c[i]+K>=c[a]就可以了，一旦不满足就结束程序并输出答案。
那么找c[1]...c[a-1]中最小的即可。如果最小的都满足不等式就不用验证其他的了。于是用线段树实现这个查询操作。
注意线段树建树从[0,N]开始，因为The second line contains n integer numbers ranging from 0 to n.
参考：http://blog.csdn.net/liao_jingyi/article/details/43531123
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int N=+;
int cnt[N];
int n,k;
struct node
{
int l,r,sum;
} tree[N*];
void build(int k,int l,int r)
{
tree[k].l=l;
tree[k].r=r;
if(l==r) return ;
int mid=l+r>>;
build(k*,l,mid);
build(k*+,mid+,r);
}
void update(int x,int k)
{
if(tree[k].l==tree[k].r)
{
tree[k].sum++;
return ;
}
int mid=(tree[k].l+tree[k].r)>>;
if(x<=mid) update(x,k*);
else update(x,k*+);
tree[k].sum=min(tree[k*].sum,tree[k*+].sum);
} int query(int x,int k)
{
if(x>=tree[k].r) return tree[k].sum;
int mid=(tree[k].l+tree[k].r)>>;
int ansl=query(x,k*);
int ansr=0x3f3f3f3f;
if(mid<x) ansr=query(x,k*+);
return min(ansl,ansr);
} int main()
{
scanf("%d%d",&n,&k);
build(,,n);
int ans=;
for(int i=; i<=n; i++)
{
int a;
scanf("%d",&a);
cnt[a]++;
update(a,);
if(query(a,)+k>=cnt[a])
ans=i;
else break;
}
printf("%d\n",ans); return ;
}