ACdream 1427 Nice Sequence

全栈程序员站长

发布于 2022-07-06 10:04:44

2870

发布于 2022-07-06 10:04:44

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是全栈君。

主题链接：http://115.28.76.232/problem?

pid=1427

Nice Sequence

Time Limit: 12000/6000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Submit Statistic Next Problem

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 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
0

Source

Andrew Stankevich Contest 23

Manager

mathlover

Submit Statistic

用线段树维护 0到A[i]-1间的最小值。用F[A[i]] 统计频率。推断 0 到 A[i]-1范围内的最小值与F[A[i]]-K的大小就可以。

//#pragma comment(linker, "/STACK:36777216")
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
#define LL long long
#define MAXN 200100
struct Node{
    int left,right,v;
};Node Tree[MAXN<<2];
void Build(int id,int left,int right){
    Tree[id].v=0;
    Tree[id].left=left;
    Tree[id].right=right;
    if(left==right) return;
    int mid=(left+right)>>1;
    Build(id<<1,left,mid);
    Build(id<<1|1,mid+1,right);
}
void Update(int id,int pos,int add){
    int left=Tree[id].left,right=Tree[id].right;
    if(left==right){
        Tree[id].v+=add;
        return;
    }
    int mid=(left+right)>>1;
    if(mid>=pos)
        Update(id<<1,pos,add);
    else
        Update(id<<1|1,pos,add);
   Tree[id].v=min(Tree[id<<1].v,Tree[id<<1|1].v);
}
int Query(int id,int Qleft,int Qright){
    int left=Tree[id].left,right=Tree[id].right;
    if(left>=Qleft && right<=Qright)
        return Tree[id].v;
    int mid=(left+right)>>1;
    if(mid>=Qright)
        return Query(id<<1,Qleft,Qright);
    else if(mid<Qleft)
        return Query(id<<1|1,Qleft,Qright);
    int r1=Query(id<<1,Qleft,Qright),r2=Query(id<<1|1,Qleft,Qright);
    return min(r1,r2);;
}
int A[MAXN];
int F[MAXN];
int main(){
    int N,K;
    while(~scanf("%d%d",&N,&K)){
        for(int i=1;i<=N;i++)
            scanf("%d",&A[i]);
        Build(1,0,N);
        memset(F,0,sizeof(F));
        int i;
        for(i=1;i<=N;i++){
            F[A[i]]++;
            Update(1,A[i],1);
            if(A[i]==0)    continue;
            int ans=Query(1,0,A[i]-1);
            if(ans<F[A[i]]-K) break;
        }
        printf("%d\n",i-1);
    }
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/117309.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年1月7，如有侵权请联系 cloudcommunity@tencent.com 删除

java