题目类型说明

这是一道提交函数题。

你需要提交文件 crypto.cpp，实现以下两个函数：

void init(std::vector<int> prices);
int assumption(int day, int price);

你的代码中不应包含 main 函数，也不应从标准输入读入或向标准输出写出。

题目描述

Deni 将自己的一部分积蓄投资到了加密货币中。一次大规模数据泄露后，她获得了自己所持有的若干种加密货币在连续 N 天内的价格变动数据——即一个长度为 N 的数列，每天一个价格。

问题在于，她并不知道每个价格对应的是哪一种货币。她唯一知道的是：在这段时间里，市场在持续下跌，因此每一种货币的价格都会在之后的每一天严格下降。

为了判断自己的投资状况，Deni 想知道：这些数据最少可能对应多少种不同的加密货币。

当然，这份数据好得过头了，不可能完全真实。作为一个有经验的投资者，Deni 知道其中恰好有一天的数据是错误的。于是她提出了 Q 个猜测 day 和 price，表示：

• 第 day 天的真实价格应为 price。

对于每一个这样的猜测，你都需要求出：如果这个猜测成立，那么这些数据最少可能对应多少种不同的加密货币。

你需要实现的内容

1. init

函数原型：

void init(std::vector<int> prices);

评测程序会调用一次该函数，并传入参数 prices，表示泄露得到的价格序列，即第 1 天、第 2 天、……、第 N 天的价格。

2. assumption

函数原型：

int assumption(int day, int price);

参数表示：第 day 天的真实价格实际上是 price。

函数需要返回一个整数，表示在这一猜测成立的前提下，这些数据最少可能对应多少种不同的加密货币。

限制

• 1 ≤ N ≤ 2 × 10^4
• 1 ≤ Q ≤ 2 × 10^6
• 1 ≤ prices[i] ≤ 10^3
• 对于每个猜测：1 ≤ price ≤ 10^3

子任务

子任务	分值	N 范围	Q 范围	其他限制
1	0	—		样例测试
2	11	N ≤ 10^3	Q ≤ 10^4	—
3	16	N ≤ 2 × 10^4	Q ≤ 10^3
4	24	N ≤ 2 × 10^3	Q ≤ 2 × 10^6
5	22	N ≤ 2 × 10^4	Q ≤ 5 × 10^5
6	27		Q ≤ 2 × 10^6

只有通过某个子任务中的全部测试，才能获得该子任务的分数。

与评测程序的样例交互

调用 1

init({6, 8, 5, 7, 4, 6, 9});

说明：评测程序调用你的 init 函数，传入价格序列 6, 8, 5, 7, 4, 6, 9。

调用 2

assumption(6, 7);

正确返回值：

4

说明：此时 Deni 的猜测为，第 6 天的真实价格为 7，因此价格序列变为：

6, 8, 5, 7, 4, 7, 9

最小答案可以例如这样达到：

• 第 1 种货币：第 1 天、第 3 天
• 第 2 种货币：第 2 天、第 4 天、第 5 天
• 第 3 种货币：第 6 天
• 第 4 种货币：第 7 天

调用 3

assumption(7, 4);

正确返回值：

2

说明：此时价格序列变为：

6, 8, 5, 7, 4, 6, 4

最小答案可以这样达到：

• 第 1 种货币：第 1 天、第 3 天、第 5 天
• 第 2 种货币：第 2 天、第 4 天、第 6 天、第 7 天

注意，不能让同一种货币出现在第 1、3、5、7 天，因为第 7 天的价格必须严格低于第 5 天。

本地测试说明

原题提供了本地评测文件 Lgrader.cpp。将它与你的 crypto.cpp 放在同一目录下并一起编译，即可得到一个用于本地测试的程序。

该程序将从标准输入按如下格式读入：

• 第一行：一个正整数 N，表示天数；
• 第二行：N 个正整数，表示每天的价格；
• 第三行：一个正整数 Q，表示猜测次数；
• 接下来 Q 行：每行两个正整数 day 和 price，表示一个猜测。

程序会输出你对所有猜测给出的答案。