stdKonjac's Blog

An AC a day keeps the WA away ~

【Count】

【问题描述】

给定一个元素个数为n的整数数组a 和Q 个问题,每个问题有x,y 两个参数,请统计
共有多少个整数K 满足K在a[x]…a[y]中出现了恰好K 次。

【输入格式】

第一行两个整数n,Q,表示数组a 的元素个数和询问数;
接下来一行n给整数,描述数组a;
接下来Q 行,每行两个数xi,yi(1≤xi≤yi≤n),表示询问的左右边界;

【输出格式】

输出 Q行,每行一个整数表示满足询问的K 的个数。

【输入样例】

7 2
3 1 2 2 3 3 7
1 7
3 4

【输出样例】

3
1

【样例说明】

Q1: 1、2、3 分别满足,所以共有3个数满足要求。
Q2: 2满足,所以只有1个数满足要求。

【数据范围】

对 50%的输入数据:1≤n,Q≤1000
对100%的输入数据:1≤n,Q≤100000,1≤a[i]≤10^9

首先,一个数K如果在整个序列中不出现K次的话是一定不会有解的,所以说,有可能会成为答案的整数K是sqrt(n)级别的。

于是,离散化一下,记录离散后的数对应离散前的数是多少,对于每个出现了大于等于K次的整数K,线性扫一遍维护前缀和,再枚举每个询问查询即可。

时间复杂度:n*sqrt(n)

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.