← 返回题目列表

Codeforces · 2145/E

E. 预测受欢迎程度

中文机器翻译题面 查看原题

假设您在 Berflix 工作,这是 Berland 最大的流媒体服务公司,专门从事电影发行。该服务的受众由 $$$n$$$ 用户组成,并且对于每个用户来说,一些偏好是已知的:电影中的动作级别 $$$a_i$$$ 和戏剧级别 $$$d_i$$$。

您当前的任务是尝试预测某部电影的受欢迎程度。让您感兴趣的电影包含 $$$ac$$$ 动作“单位”和 $$$dr$$$ 戏剧“单位”(数据由分析团队提供)。如果电影中的动作和戏剧水平都达到或超过某个用户的阈值,他们肯定会观看该电影。

如果电影在动作或戏剧方面不足,用户会犹豫。然而,这部电影在其他观众中的受欢迎程度可能会影响他们观看它。经过长时间的讨论,您的团队选择了以下活动模式。

设 $$$p$$$ 为已观看电影的人数(最初 $$$p = 0$$$)。我们会认为这部电影是 适合 对于用户 $$$i$$$ 如果 $$$\max(a_i - ac, 0) + \max(d_i - dr, 0) \le p$$$。

用户不断检查推荐。因此,我们假设只要存在一个尚未观看该电影但觉得合适的用户,他就一定会观看。观看这部电影会将其受欢迎度 $$$p$$$ 提高 1,并可能使其适合其他用户。

当每个人都看过这部电影,或者剩下的观众都不觉得它合适时,这个过程就会结束。你的任务是计算总共有多少人会观看这部电影。

最后一个问题 — 用户的偏好在不断变化。具体来说,有$$$m$$$请求更改某个用户$$$k$$$的$$$a_k$$$和$$$d_k$$$的值,并且每次更改后都需要重新计算电影的最终受欢迎程度$$$p$$$。

输入

第一行包含两个数字 $$$ac$$$ 和 $$$dr$$$ ($$$1 \le ac, dr \le 10^6$$$) - 电影的动作和戏剧评分。

第二行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — Berflix 的用户数量。

第三行包含 $$$n$$$ 数字 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) - 用户的操作偏好。

第四行包含 $$$n$$$ 数字 $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_i \le 10^6$$$) — 用户对戏剧的偏好。

第五行包含一个整数 $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — 用户偏好的变化次数。

以下 $$$m$$$ 行包含格式更改:

  • "$$$k_j$$$ $$$na_j$$$ $$$nd_j$$$" ($$$1 \le k_j \le n$$$; $$$1 \le na_j, nd_j \le 10^6$$$),其中 $$$na_j$$$ 是用户 $$$k_j$$$ 对操作的新偏好,并且$$$nd_j$$$ — 用于戏剧。

输出

对于每个更改请求,输出更新相应用户信息后电影 $$$p$$$ 的总观看次数。

示例

输入
复制

20 25
4
1 22 1 30
1 22 50 30
5
3 1 25
2 23 22
4 10 27
1 21 21
3 20 26

输出
复制

3
2
4
4
0

注意

考虑第一个请求。第一个和第三个观众已经觉得这部电影合适,所以他们会观看它,从而将受欢迎度 $$$p$$$ 提高 $$$2$$$。当 $$$p = 2$$$ 时,电影将适合第二个观众。因此,他们也会观看该节目,从而使受欢迎程度又增加了 $$$1$$$。然而,第 $$$4$$$ 观众仍然没有找到合适的电影,因为 $$$\max(30 - 20, 0) + \max(30 - 25, 0) \gt 3$$$。

因此,在第一个请求之后,$$$3$$$ 人将观看该电影。