C.小苯的水果园

Link:Nowcoder

题目描述

小苯有一个果园，他在其中种了 $n$ 个果子，其中第 i 个果子的种类为 $a_i$​ 。

现在果子们成熟了，小苯会把它们“打下来”，具体来说：小苯会在第 $i$ 天早上会把所有总数量恰好为 $i$ 的同一种类的果子全都打下来（特别地，如果当前果园中不存在总数恰好为 $i$ 的同种类果子，则今天一个果子都不打。）

现在小苯提出了 $q$ 次询问，每次询问一个天数 $d$，请你来回答一下，到第 d 天晚上时果园里还剩多少果子吧。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≦T≦10^3)$ 代表数据组数，每组测试数据描述如下：

第一行输入两个正整数 $n,q(1≤n,q≤2×10^5)$ 代表果园中的果子个数、小苯的询问次数。 第二行输入 $n$ 个正整数 $a1​,a2​,…,an​(1≤ai​≤10^6)$ 代表果园中每个果子的种类。 第三行输入 $q$ 个正整数 $d1​,d2​,…,dq​(1≤di​≤10^9)$ 代表小苯问的是第几天晚上的果园情况。

除此之外，保证单个测试文件的 $n$ 和 $q$ 之和均不超过 $3×10^5$ 。

输出描述:

对于每一组测试数据，在单独的一行上输出 $q$ 个整数，表示对小苯每次询问的回答。

示例1

输入

1
8 3
1 2 3 3 2 3 4 4
1 2 4

输出

7 3 0

思路

这个题初看是用模拟，但是我们可以观察到此处询问的数据范围达到了$10^9$直接使用模拟会严重超时(实际上应该不会，因为此处最多的时间为$2*10^5$）

因此我们应该使用类似于前缀和之类的算法。

实际上直接使用前缀和维护第 $i$ 天除去的果子数量即可，对于询问超过第 $n$ 天的很明显是 $0$ 个，所以前缀和秒了。(我没做出来简直就是傻逼)

核心代码

int n, q; cin >> n >> q;
cnt.clear();
memset(kinds, 0, sizeof(kinds));
for (int i = 0; i < n; i++)
{
	int idx; cin >> idx;
	cnt[idx]++;
}
int s = 0;
for (auto x : cnt) kinds[x.second] += x.second;
for (int i = 1; i <= n; i++) kinds[i] += kinds[i - 1];
while (q--)
{
	int d; cin >> d;
	d = min(d, n);
	cout << n - kinds[d] << ' ';
}
cout << endl;