Nice Sequence
Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
Submit Status
Problem 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
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 a1, a2,..., al 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
题目大意：给出n，k。n表示长度为n的序列，且序列中的值都是0---n的。定义ci,j表示数字i在a1，a2...aj中出现的次数，定义k-nice序列，即i1<i2且满足不等式ci1,j ≥ ci2,j −k。
解题思路：我们将序列映射到线段树的叶子上。那么对于ai来说，我们单点更新数字ai出现的次数，然后从1---ai中查询某数字出现最少的次数，如果不满足的不等式，那么就直接结束了。其实只需要用线段树维护每个数字出现的次数即可。
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
const int INF=0x3f3f3f3f;
const int maxn=3*(1e5);
struct SegTree{
int v;
}segtrees[maxn*4];
int a[maxn],times[maxn];
void build(int rt,int L,int R){
if(L==R){
segtrees[rt].v=0;
return ;
}
build(lson);
build(rson);
}
void PushUp(int rt){
segtrees[rt].v=min(segtrees[rt*2].v,segtrees[rt*2+1].v);
}
void update(int rt,int L,int R,int key){
if(L==R){
segtrees[rt].v++;
return ;
}
if(key<=mid)
update(lson,key);
else
update(rson,key);
PushUp(rt);
}
int query(int rt,int L,int R,int l_ran,int r_ran){
if(l_ran<=L&&R<=r_ran){
return segtrees[rt].v;
}
int ret=INF;
if(l_ran<=mid){
ret =min(ret,query(lson,l_ran,r_ran));
}
if(r_ran>mid){
ret = min(ret,query(rson,l_ran,r_ran));
}
return ret;
}
int main(){
int n,k;
while(scanf("%d%d",&n,&k)!=EOF){
memset(times,0,sizeof(times));
build(1,0,n);
int flag=0;
int ans=n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(flag) continue;
times[a[i]]++;
update(1,0,n,a[i]);
int xx=query(1,0,n,0,a[i]);
if(xx<times[a[i]]-k){
ans=i-1;
flag=1;
}
}
printf("%d
",ans);
}
return 0;
}