Nice Sequence_线段树***

时间：2021-05-17 21:28:06

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 a 1, a 2,..., 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

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 ;

}

相关文章