CF2145E.Predicting Popularity

Imagine that you are working at Berflix — the largest streaming service in Berland, specialized in movie distribution. The audience of this service consists of $n$ users, and for each of them, some preferences are known: the level of action in a movie $a_i$ and the level of drama $d_i$.

Your current task is to try to predict the popularity of a certain movie. Let the movie you are interested in contain $ac$ "units" of action and $dr$ "units" of drama (data kindly provided by the analytics team). If both the action and drama levels in the movie meet or exceed the threshold values for a certain user, they will definitely watch the movie.

If the movie falls short in either action or drama, the user will hesitate. However, the popularity of the movie among other viewers may sway them to watch it. After lengthy discussions, your team has chosen the following model of events.

Let $p$ be the number of people who have already watched the movie (initially $p = 0$). We will consider that the movie is suitable for user $i$ if $\max(a_i - ac, 0) + \max(d_i - dr, 0) \le p$.

Users constantly check recommendations. Therefore, we will assume that as long as there exists a user who has not yet watched the movie but finds it suitable, they will definitely watch it. Watching the movie will increase its popularity $p$ by one and may make it suitable for other users.

This process will conclude when either everyone has watched the movie, or none of the remaining viewers find it suitable. Your task is to count how many people will watch the movie in total.

There is one last problem — the users' preferences are constantly changing. Specifically, there are $m$ requests to change the values of $a_k$ and $d_k$ for some user $k$, and you need to recalculate the final popularity of the movie $p$ after each change.

假设你在 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$。

The first line contains two numbers $ac$ and $dr$ ($1 \le ac, dr \le 10^6$) — the action and drama ratings of the movie.

The second line contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the number of users of Berflix.

The third line contains $n$ numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the users' preferences for action.

The fourth line contains $n$ numbers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^6$) — the users' preferences for drama.

The fifth line contains one integer $m$ ($1 \le m \le 3 \cdot 10^5$) — the number of changes in user preferences.

The following $m$ lines contain the changes in the format:

• "$k_j$ $na_j$ $nd_j$" ($1 \le k_j \le n$; $1 \le na_j, nd_j \le 10^6$), where $na_j$ is the new preference of user $k_j$ for action, and $nd_j$ — for drama.

第一行包含两个数 $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$ 表示其新的剧情类偏好值。

For each change request, output the total number of views of the movie $p$ after updating the information about the corresponding user.

对于每个修改请求，输出更新相应用户信息后电影 $p$ 的总浏览量。

Consider the first request. The first and third viewers already find the movie suitable, so they will watch it, increasing the popularity $p$ by $2$. With $p = 2$, the movie will become suitable for the second viewer. As a result, they will also watch it, increasing the popularity by another $1$. However, the $4$-th viewer still does not find the movie suitable, as $\max(30 - 20, 0) + \max(30 - 25, 0) \gt 3$.

Thus, after the first request, $3$ people will watch the movie.

考虑第一个请求。第一位和第三位观众已经认为这部电影合适，因此他们会观看，使人气值 $p$ 增加 $2$。当 $p = 2$ 时，这部电影将变得适合第二位观众。因此，他们也会观看，使人气值再增加 $1$。然而，第四位观众仍然认为这部电影不合适，因为 $\max(30 - 20, 0) + \max(30 - 25, 0) \gt 3$。

因此，在第一个请求之后，共有 $3$ 人会观看这部电影。