CF2145E Predicting Popularity

假设你正在 Berflix 工作——这是伯兰最大的流媒体服务平台，专注于电影分发。该服务有 $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$ 次对某个用户偏好的更改请求。对于每次更改后，你需要重新计算电影的最终受欢迎度 $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$），表示第 $k_j$ 位用户将动作偏好更改为 $na_j$，剧情偏好更改为 $nd_j$。

对于每次更改请求，输出一次更新后该电影的总观看人数 $p$。

以第一个更改请求为例。第 $1$ 和第 $3$ 位观众此时已经认为电影合适，他们会立即观看，此时受欢迎度 $p$ 增加 $2$。当 $p=2$ 时，第 $2$ 位观众觉得电影合适，也会观看，$p$ 再加 $1$。但第 $4$ 位观众不认为电影合适，因为 $\max(30-20,0)+\max(30-25,0)$ 大于 $3$。 因此，第一次更改后，最终共有 $3$ 个人观看该电影。 由 ChatGPT 5 翻译