title: 「BalkanOI 2023 Day1」Weights

description:
**译自 [BalkanOI 2023](https://boi2023.zotks.si) Day1 T2「[Weights](https://boi2023.zotks.si/wp-content/uploads/day_1/d1_weights/en_EN.pdf)」**

给你 $N$ 个天平，每个天平有两个质量可以忽略不计的盘子。天平用从 $1$ 到 $N$ 的整数编号。每个盘子上要么放着另一个天平，要么放着一个质量不可忽略的砝码。编号为 $1$ 的天平放在地上，其他的天平都放在某个天平的盘子上。一共有 $N+1$ 个砝码。砝码用 $1$ 到 $N+1$ 的整数编号，每个砝码的质量用 $N+1$ 个整数 $w_{1}, w_{2} \cdots, w_{N+1}$ 表示。

下图给出了一个由三个天平和四个砝码组成的例子。正体字的数字表示天平和砝码的编号，斜体字的数字表示砝码的质量。例如，编号为 $2$ 的天平放在编号为 $1$ 的天平的左盘上，编号为 $2$ 质量为 $6$ 的砝码放在编号为 $1$ 的天平的右盘上。

![](https://cdn.luogu.com.cn/upload/image_hosting/6sw0vac1.png)

如果一个天平的左盘和右盘的总质量相等，我们说它是平衡的。如果一个天平是平衡的，并且它的两个盘子上要么都是超平衡的天平，要么都是砝码，我们说它是超平衡的。

在上图中，只有天平 $3$ 是平衡的（也是超平衡的），但是如果我们把砝码 $3$ 和 $4$ 的质量都增加到 $1.5$，那么三个天平都会变成超平衡的。然而，如果我们把砝码 $1$ 的质量增加到 $4$，天平 $1$ 会变成平衡的但不是超平衡的，因为天平 $2$ 仍然不平衡。

现在我们要处理 $Q$ 个两种类型的操作：

- $1\,k\,w$ : 把砝码 $k$ 的质量改成整数 $w$。
- $2\,s$ : 假设我们想让天平 $s$ 变成超平衡的。我们可以用魔法把一些砝码变得更重！注意新的质量不一定是整数。要让天平 $s$ 变成超平衡的，天平 $s$ 上的最小总质量是多少？由于这个数可能很大，输出它对 $998244353$ 取模的结果。可以证明在给定的限制下，结果总是一个整数。

注意，类型 $1$ 的操作会改变砝码的质量，而类型 $2$ 的操作不会。

inputFormat:
第一行包含两个整数 $N$ 和 $Q$。

接下来的 $N$ 行中的第 $i\ (1\leq i\leq N)$ 行包含两对字符和数字，每对描述了第 $i$ 个天平的一个盘子：字符是 `S`（天平）或 `W`（砝码），表示盘子上的物体的类型，整数是相应物体的编号。保证一个天平永远不会放在一个编号更大的天平上。

接下来的一行包含 $N+1$ 个整数 $w_{1}, w_{2}, \cdots, w_{N+1}$，表示砝码的质量。

最后的 $Q$ 行表示操作。每行要么是形如 $1\,k\,w$ 的，要么是形如 $2\,s$ 的，如问题描述中所述。

outputFormat: 对于每个类型 $2$ 的操作，在一行上输出相应的最小质量对 $998244353$ 取模的结果。

hint:
### 样例解释

为了让天平 $2$ 变成超平衡的，我们把砝码 $3$ 和 $4$ 的质量都增加到 $1.5$。这样，天平 $2$ 和 $3$ 都会变成平衡的，因此 $2$ 也就是超平衡的。天平 $2$ 上的总质量是 $3+1.5+1.5=6$。当我们这样做的时候，天平 $1$ 也会变成平衡的，所以它也是超平衡的，它的总质量是 $6+3+1.5+1.5=12$。当我们把砝码 $3$ 的质量改成 $2$ 的时候，这种方法就不行了。因此，为了让天平 $1$ 变成超平衡的，我们可以把砝码 $1$ 的质量改成 $4$，砝码 $2$ 的质量改成 $8$，砝码 $4$ 的质量改成 $2$。这样，天平 $1$ 上的总质量就是 $8+4+2+2=16$。

### 数据范围

对于所有输入数据，满足：

- $1 \leq N \leq 2 \cdot 10^{5}$
- $1 \leq Q \leq 2 \cdot 10^{5}$
- $1 \leq w_{i} \leq 10^{9}$
- 对于每个类型 $1$ 的操作：$1 \leq k \leq N+1$
- 对于每个类型 $1$ 的操作：$1 \leq w \leq 10^{9}$
- 对于每个类型 $2$ 的操作：$1 \leq s \leq N$

详细子任务附加限制及分值如下表所示。令砝码的深度表示它直接或间接所在的盘子的数量。

| 子任务编号 |  附加限制  | 分值 |
| :--: | :--: | :--: |
| $1$ | 每个天平的至少一个盘子上有砝码 | $9$ |
| $2$ | 每个砝码的深度相同 | $8$ |
| $3$ | 每个砝码的深度小于 $30$，且 $N, Q \leq 5000$ | $24$ |
| $4$ | 每个砝码的深度小于 $30$ | $14$ |
| $5$ | $N, Q \leq 5000$ | $14$ |
| $6$ | 无附加限制 | $31$ |


title: 「BalkanOI 2023 Day1」Permutations

type: P

description:
**译自 [BalkanOI 2023](https://boi2023.zotks.si) Day1 T3「[Permutations](https://boi2023.zotks.si/wp-content/uploads/day_1/d1_permutations/en_EN.pdf)」**

给你一个由数字 $1,2, \ldots, n$ 组成的排列 $p_{1}, p_{2}, \ldots, p_{n}$。你需要回答 $q$ 个查询。

第 $i\ (1\leq i\leq q)$ 个查询由两个数字 $L_{i},R_{i}\ (1 \leq L_{i} \leq R_{i} \leq n)$ 表示。你需要回答满足以下条件的排列个数：

- 排列的长度为 $n$；
- 以序列 $p_{L_{i}}, p_{L_{i}+1}, \ldots, p_{R_{i}-1}, p_{R_{i}}$ 作为开头；
- 排列的最长递减子序列的长度至多为 $2$。

由于答案可能很大，输出它们对 $10^{9}+7$ 取模的结果。

对于一个序列 $a_{1}, a_{2}, \ldots, a_{k}$，它的最长递减子序列的长度是最大的整数 $t$，使得存在 $t$ 个下标 $s_{1}, s_{2}, \ldots, s_{t}$，满足 $1 \leq s_{1}<s_{2}<\ldots<s_{t} \leq k$ 且 $a_{s_{1}}>a_{s_{2}}>\ldots>a_{s_{t}}$。

inputFormat:
第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $p_{1}, \ldots, p_{n}$，即区间 $[1, n]$ 中的 $n$ 个不同的整数。

第三行包含一个整数 $q$。

接下来的 $q$ 行每行描述了一个查询。第 $i\ (1\leq i\leq q)$ 行包含两个整数字 $L_{i}$ 和 $R_{i}$。

outputFormat: 对于每个查询输出单独的一行，表示打印排列的个数对 $10^{9}+7$ 取模的结果。


title: 「BalkanOI 2023 Day2」Super Tree

background: **请仔细阅读【提示说明】中的【评分方式】。**

description:
**译自 [BalkanOI 2023](https://boi2023.zotks.si) Day2 T1「[Super Tree](https://boi2023.zotks.si/wp-content/uploads/day_2/d2_tree/en.pdf)」**

给定一棵有 $n$ 个节点的有根树，节点用 $0, \ldots, n-1$ 的编号来标识。根节点的编号为 $0$。节点 $i\ (0\leq i\leq n-1)$ 被赋予一个整数 $a_{i}$。令 $f_{v}$ 为从节点 $v$ 到根节点的简单路径（包括 $x$ 和 $y$ 本身）上所有 $a_{i}$ 的**按位与**（以下用 $\&$ 表示）的值。令树的能量为

$$
\sum_{0 \leq u, v<n} f_{u} \cdot f_{v}
$$

的值，令树的超能量为（注意范围的区别）

$$
\sum_{0 \leq u<v<n} f_{u} \cdot f_{v}
$$

的值。为了说明清楚，可以参考下面的样例解释。

我们说一个节点 $u$ 属于另一个节点 $v$ 的子树，如果 $v$ 在从节点 $u$ 到根节点的简单路径上。注意，一个节点 $x$ 的子树包括 $x$ 本身。

给定 $q$ 次更新。每次更新由两个整数 $v$ 和 $x$ 描述，要求你对节点 $v$ 的子树中的每个节点 $u$，令 $a_{u}=a_{u} \& x$。在每次更新后，你应该输出当前树的能量和超能量。

由于输出值可能很大，你只需要求出答案对 $10^{9}+7$ 取模的结果。

inputFormat:
第一行包含两个整数 $n$ 和 $q$。

第二行包含 $n-1$ 个整数 $p_{1}, p_{2}, \ldots, p_{n-1}$。$p_{i}\ (0\leq i\leq n-1)$ 是节点 $i$ 的父节点的编号，且满足 $0 \leq p_{i}<i$。

第三行包含 $n$ 个整数 $a_{0}, a_{1}, \ldots, a_{n-1}$。这些是赋给节点的值。

接下来的 $q$ 行，每行包含两个整数 $v$（$0 \leq v<n$）和 $x$。这些整数指定了各个更新。

outputFormat: 输出 $q+1$ 行。每行包含两个用空格分隔的整数。第一行，输出初始树的能量和超能量对 $10^{9}+7$ 取模的结果。在剩下的 $q$ 行中，第 $i\ (1\leq i\leq q)$ 行输出第 $i$ 次更新后的树的能量和超能量对 $10^{9}+7$ 取模的结果。


title: 「BalkanOI 2023 Day2」Save the Vine!

description:
**译自 [BalkanOI 2023](https://boi2023.zotks.si) Day2 T2「[Save the Vine!](https://boi2023.zotks.si/wp-content/uploads/day_2/d2_vine/en.pdf)」**

一群又臭又丑的绿色小人准备毒死 450 年历史的葡萄藤，这是马里博尔的象征！他们正在 Kodžak 纪念碑周围聚集，制定他们的计划，准备向 Drava 河左岸的著名 Lent 街上的房子进军，那里就是那棵古老的葡萄藤生长的地方！你，强大的紫色战士，被召唤来在他们实施致命的行动之前消灭敌人！

一共有 $n$ 个敌人，每个敌人都有三个属性：臭度、绿度和丑度。对于每个 $i \in\{1, \ldots, n\}$，整数 $a_{i}, b_{i}$ 和 $c_{i}$ 分别决定了第 $i$ 个敌人的臭度、绿度和丑度。而你有两个属性：力量 $X$ 和紫度 $Y$。

作为一个自豪的马里博尔人，你的紫度 $Y$ 在你出生时就已经确定，永远不会改变。但是，通过击败敌人，你的力量 $X$ 会增加。特别地，当你击败敌人 $i$ 时，$X$ 会增加该敌人的丑度 $c_{i}$。你可以按任意顺序一个一个地击败敌人，但你只能在你的力量大于他的臭度（$X \geq a_{i}$）且你的紫度大于他的绿度（$Y \geq b_{i}$）时击败敌人 $i$。另外，你只能击败每个敌人一次。

你肯定想知道，为了击败至少 $k$ 个敌人，你最初的力量和紫度（即 $X+Y$）的最小和是多少。编写一个程序来找到这个值！

inputFormat: 第一行包含整数 $n$ 和 $k$。接下来的 $n$ 行中的第 $i\ (1\leq i\leq n)$ 行包含整数 $a_{i}, b_{i}$ 和 $c_{i}$。

outputFormat: 输出至少击败 $k$ 个敌人所需的 $X+Y$ 的最小初始值。

hint:
### 样例解释

为了击败至少四个敌人，只需要从 $X=5$ 和 $Y=7$ 开始。首先，你击败敌人 $2$，将你的 $X$ 提升到 $8$。现在，你可以摧毁敌人 $1$，并达到 $X=12$。有了这样的力量，你可以击败敌人 $5$，达到 $X=21$。你完成你的任务，消灭敌人 $4$。

### 数据范围

对于所有输入数据，满足：

- $1 \leq n \leq 2 \cdot 10^{5}$
- $1 \leq k \leq n$
- $0 \leq a_{i}, b_{i}, c_{i} \leq 10^{9}$

详细子任务附加限制及分值如下表所示。

| 子任务编号 | 附加限制 | 分值 |
| :--: | :--: | :--: |
| $1$ | $n \leq 1000$ | $19$ |
| $2$ | $b_{i}=0\ (1\leq i\leq n)$ | $15$ |
| $3$ | $c_{i}=0\ (1\leq i\leq n)$ | $24$ |
| $4$ | 无附加限制 | $42$ |


title: 「BalkanOI 2023 Day2」Aliens

description:
**译自 [BalkanOI 2023](https://boi2023.zotks.si) Day2 T3「[Aliens](https://boi2023.zotks.si/wp-content/uploads/day_2/d2_aliens/en.pdf)」**

马里博尔刚刚被外星人拜访了！他们与你分享了他们的技术和历史。

有 $N+1$ 个行星，从 $0$ 到 $N$ 编号，地球的编号为 $N$。每个行星都有一个唯一的人口数 $P_{i}\ (0\leq i\leq N)$。行星之间用 $N$ 个双向传送门连接，你可以只用这些传送门在任意两个行星之间旅行。传送门 $i$（$0\leq i\leq N-1$）连接了行星 $U_{i}$ 和 $V_{i}$。两个行星之间的距离是旅行所需的最少传送门数。

你从地球出发，想要去游览 $K$ 个其他行星 $A_{0}, A_{1}, \ldots, A_{K-1}$。这些被称为**起源行星**。每个起源行星和地球只有一个传送门连接。你的旅程为从地球出发，访问所有起源行星以及沿途所有行星的最短路线。令 $S$ 为所有访问过的行星的集合。

现在，外星人决定通过向你提问 $Q$ 个以下两种类型的问题来测试地球是否有资格加入他们的超级文明：

- 类型 $1$：集合 $S$ 的大小是多少？
- 类型 $2$：他们从 $S$ 中选出一个行星 $x$，一个距离 $d$，和一个数字 $r$。他们问你，在距离 $x$ 为 $d$ 的行星中，按人口数从小到大排列的第 $r$ 个行星是哪个。（例如，如果 $r=1$ 答案就是距离 $x$ 为 $d$ 的星球中人口数最少的行星。这个行星可以也可以不属于集合 $S$。）

只有一个类型 $1$ 的查询。

inputFormat:
第一行包含三个整数 $N, K, Q$。

第二行包含 $N+1$ 个整数 $P_{0}, \ldots, P_{N}$。

第三行包含 $K$ 个整数 $A_{0}, \ldots, A_{K-1}$。

接下来的 $N$ 行中的第 $i\ (1\leq i\leq N-1)$ 行包含两个整数 $U_{i}$ 和 $V_{i}$。

接下来的 $Q$ 行满足以下格式之一：

- $1$ 表示一个类型 $1$ 的查询；
- $2\,x\,d\,r$ 表示一个类型 $2$ 的查询。

outputFormat: 对于每个查询，输出一行。对于类型 $1$ 的查询，输出游览期间访问的行星数；对于类型 $2$ 的查询，输出距离 $x$ 为 $d$ 的行星中按人口数排列的第 $r$ 个行星。

hint:
### 样例 1 解释

![](https://cdn.luogu.com.cn/upload/image_hosting/7q7mu3wl.png)

只有一个起源行星，我们在游览中访问了行星 $S=\{1,3,4,5\}$。类型 $2$ 的查询有：

- $x=4, d=2, r=1$
- 距离行星 $4$ 为 $2$ 的只有行星 $1$。
- $x=3, d=2, r=1$
- 距离行星 $3$ 为 $2$ 的有行星 $0,2,5$。其中，行星 $0$ 的人口数最少。
- $x=4, d=1, r=3$
- 距离行星 $4$ 为 $1$ 的有行星 $0,2,3,5$，它们按人口数的顺序是 $3,0,2,5$。其中第三个是行星 $2$。
- $x=5, d=2, r=3$
- 距离行星 $5$ 为 $2$ 的有行星 $0,2,3$，它们按人口数的顺序是 $3,0,2$。其中第三个是行星 $2$。

### 样例 2 解释

![](https://cdn.luogu.com.cn/upload/image_hosting/sytqzdyc.png)

### 数据范围

对于所有输入数据，满足：

- $1 \leq N \leq 10^5$
- $1 \leq K \leq 10$
- $1 \leq Q \leq 10^5$
- $1 \leq P_{i} \leq 10^{9}\ (0 \leq i \leq N)$；
- 所有的 $P_{i}$ 都是不同的
- $0 \leq A_{i} \leq N-1\ (0 \leq i \leq K-1)$
- $0 \leq U_{i}, V_{i} \leq N\ (0 \leq i \leq N-1)$
- $K$ 个起源行星和地球只有一个传送门连接
- 对于每个类型 $2$ 的查询，满足 $x \in S, d \geq 1$，且 $r \geq 1$
- 保证距离 $x$ 为 $d$ 的行星至少有 $r$ 个

详细子任务附加限制及分值如下表所示。

| 子任务编号 | 附加限制 | 分值 |
| :--: | :--: | :--: |
| $1$ | $Q=1$ | $3$ |
| $2$ | $N \leq 2000, Q \leq 2000$ | $14$ |
| $3$ | $K=1$ | $21$ |
| $4$ | $N \leq 10000$ | $12$ |
| $5$ | $Q \leq 10000$ | $13$ |
| $6$ | 无附加限制 | $37$ |


title: [GESP202409 三级] 平衡序列

type: B

description:
小杨有一个包含 $n$ 个正整数的序列 $a$。他认为一个序列是平衡的当且仅当存在一个正整数 $i$（$1 \leq i < n$）使得序列第 $1$ 到第 $i$ 个 数字的总和等于第 $i + 1$ 到第 $n$ 个数字的总和。

小杨想请你判断序列 $a$ 是否是平衡的。

inputFormat:
**本题单个测试点内包含多组测试数据**。第一行是一个正整数 $t$，表示测试用例组数。

接下来是 $t$ 组测试用例。对每组测试用例，一共两行。

第一行包含一个正整数 $n$，表示序列长度。
第二行包含 $n$ 个正整数，代表序列 $a$。

outputFormat: 对每组测试用例输出一行一个字符串。如果 $a$ 是平衡的，输出 $\texttt{Yes}$，否则输出 $\texttt{No}$。

hint:
### 样例 1 解释

- 对第一组测试用例，令 $i = 2$，有 $i + 2 = 3$，因此序列是平衡的。
- 对第二组测试用例，令 $i = 2$，哟 $2 + 3 = 1 + 4$，因此序列是平衡的。
- 对第三组测试用例，不存在满足要求的 $i$。

### 数据规模与约定

对全部的测试数据，保证 $1 \leq t \leq 100$，$1 \leq n, a_i \leq 10000$。


title: [GESP202409 三级] 回文拼接

description:
一个字符串是回文串，当且仅当该字符串从前往后读和从后往前读是一样的，例如，$\texttt{aabaa$ 和 $\texttt{ccddcc}$ 都是回文串，但 $\texttt{abcd}$ 不是。

小杨有 $n$ 个仅包含小写字母的字符串，他想请你编写程序判断每个字符串是否由两个长度至少为 $2$ 的回文串前后拼接而成。

inputFormat:
第一行包含一个正整数$n$，代表字符串数量。
接下来 $n$ 行，每行一个仅包含小写字母的字符串。

outputFormat: 对于每个字符串输出一行，如果该字符串由两个长度至少为 的回文串前后拼接而成则输出 Yes，否则输出 No。

hint:
### 样例 1 解释

对于第 $1,3,4$ 个字符串，都不是由两个长度至少为 $2$ 的回文串前后拼接而成。
第 $2$ 个字符串由回文串 $\texttt{aa}$ 和 $\texttt{bbb}$ 前后拼接而成，并且两个回文串长度都至少为 $2$。

### 数据规模与约定

对全部的测试数据，保证 $1 \leq n \leq 10$，且每个字符串的长度均不超过 $100$。


title: [GESP202409 四级] 黑白方块

description:
小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。
小杨想知道网格图中是否存在一个满足如下条件的子矩形：
- 子矩形由 $4$ 行 $4$ 列组成；
- 子矩形的第 $1$ 行和第 $4$ 行只包含白色格子；
- 对于子矩形的第 $2$ 行和第 $3$ 行，只有第 $1$ 个和第 $4$ 个格子是白色的，其余格子都是黑色的；

请你编写程序帮助小杨判断。

inputFormat:
第一行包含一个正整数 $t$，代表测试用例组数。
接下来是 $t$ 组测试用例。对于每组测试用例，一共 $n+1$ 行。
第一行包含两个正整数 $n,m$，含义如题面所示。
之后 $n$ 行，每行一个长度为 $m$ 的 $01$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $0$，则对应格子为白色，否则为黑色。

outputFormat: 对于每组测试用例，如果存在，输出 Yes，否则输出 No。


title: [GESP202409 四级] 区间排序

description:
小杨有一个包含 $n$ 个正整数的序列 $a$。

小杨计划对序列进行多次升序排序，每次升序排序小杨会选择一个区间 $[l,r]$（$l \leq r$）并对区间内所有数字，即进行升序$a_l, a_{l + 1}, \dots a_r$ 排序。每次升序排序会在上一次升序排序的结果上进行。

小杨想请你计算出多次升序排序后的序列。

inputFormat:
第一行包含一个正整数 $n$，含义如题面所示。
第二行包含 $n$ 个正整数 $a_1, a_2, \dots a_n$，代表序列 $a$。
第三行包含一个正整数 $q$，代表排序次数。
之后 $q$ 行，每行包含两个正整数 $l, r$，代表将区间 $[l_i, r_i]$ 内所有数字进行升序排序。

outputFormat: 输出一行包含 $n$ 个正整数，代表多次升序排序后的序列。

hint:
### 样例 1 解释

- 第一次升序排序后，序列为 $[3,4,5,1,2]$；
- 第二次升序排序后，序列为 $[3,4,1,5,2]$；
- 第三次升序排序后，序列为 $[1,3,4,5,2]$；

### 数据规模与约定

对于全部的测试数据，保证 $1 \leq n, a_i, q \leq 100$，$1 \leq l_i \leq r_i \leq n$。


title: 【模板】基于值域预处理的快速离散对数

background: 模板题，无背景。

description:
给定质数 $P$ 以及它的一个原根 $g$。

有 $q$ 组询问，每组询问给出整数 $y$，你需要找到最小的非负整数 $x$ 使得 $g^x\equiv y\pmod P$。

inputFormat:
第一行两个整数 $P,g$，描述质数 $P$ 及其一个原根 $g$。

第二行一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行一个整数 $y$，表示每次询问的值。

outputFormat: 输出共 $q$ 行，每行一个整数表示答案。

hint:
### 数据范围及约束

- 对于前 $15\%$ 的数据，满足 $1\le g < P\le 100$，$1\le q\le 100$；
- 对于前 $30\%$ 的数据，满足 $1\le g < P\le 10^9+7$，$1\le q\le 100$；
- 另有 $15\%$ 的数据，满足 $y_i=i$；
- 另有 $15\%$ 的数据，满足 $P=998244353$，$g=3$；
- 对于全部数据，满足 $1\le g,y_i<P\le 10^9+7$，$1\le q\le 5\times 10^5$。

请注意读入效率对程序运行速度的影响。


title: [ROIR 2018 Day1] 提高成绩

description:
**译自 ROI 2018 Regional. Day1 T1.** ***[Квадраты и кубы](http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-regional-2018-day1.pdf)***

在中学的计算机课上，学生的答案会被评为 $2$ 到 $5$ 分的整数分数。计算机课的最终成绩是所有课上分数的算术平均值，四舍五入到最接近的整数。如果平均值正好在两个整数之间，则向上取整。

以下是分数四舍五入的示例：

| 课上分数 | 算术平均值 | 最终成绩 |
| :---: | :---: | :---: |
| $2,3,5$ | $\frac{2+3+5}{3}=3 \frac{1}{3}$ | $3$ |
| $3,3,4,4$ | $\frac{3+3+4+4}{4}=3 \frac{1}{2}$ | $4$ |
| $5,5,5,3,5$ | $\frac{5+5+5+3+5}{5}=4 \frac{3}{5}$ | $5$ |

所有中学的学生都希望计算机课的最终成绩不低于 $4$ 分。不幸的是，有一个学生在课上得了 $a$ 个 $2$ 分，$b$ 个 $3$ 分和 $c$ 个 $4$ 分。现在他计划获得一些 $5$ 分，以确保最终成绩不低于 $4$ 分。他需要知道，至少需要获得多少个 $5$ 分才能达到目标。

需要编写一个程序，根据给定的非负整数 $a$、$b$ 和 $c$，确定学生至少需要获得多少个 $5$ 分，才能使他的计算机课最终成绩不低于 $4$ 分。

inputFormat: 输入包含三行。第一行包含一个非负整数 $a$，第二行包含一个非负整数 $b$，第三行包含一个非负整数 $c$ $(0 \leq a, b, c \leq 10^{15}, a+b+c \geq 1)$。

outputFormat: 输出一个整数，表示学生至少需要获得的 $5$ 分的数量，以确保最终成绩不低于 $4$ 分。


title: [ROIR 2018 Day1] 平方与立方

description:
**译自 ROI 2018 Regional. Day1 T2.** ***[Квадраты и кубы](http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-regional-2018-day1.pdf)***

数学家们研究了「自然数的平方的分布」与「自然数的立方的分布」之间的关系。

已知非负整数 $a,b,k$。考虑集合 $S=\{a,a+1,\ldots,b\}$，该集合的「$k$ 密度」表示的是 $T$ 中元素的个数，其中 $T=\{(x,y)|$ $x\in\mathbb{N},$ $y\in\mathbb{N},$ $x^2\in S,$ $y^3\in S,$ $|x^2 - y^3| ≤ k\}$。请求出 $S$ 的 $k$ 密度。

inputFormat: 输入包含三行，分别为 $a,b,k$。

outputFormat: 输出一行，表示答案。


title: [ROIR 2018 Day1] 电梯

description:
**译自 ROI 2018 Regional. Day1 T3.** ***[Лифт](http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-regional-2018-day1.pdf)***

某公司有一座大厦，大厦有 $m$ 层，自底向上依次称作 $1\ldots m$ 楼（层）。

有 $n$ 名雇员在大厦中工作，其编号分别为 $1\ldots n$。每天下班时，所有雇员都需坐电梯下到一楼，并离开大厦。已知开始时 $i$ 号雇员位于 $a_i$ 层，该雇员在第 $t_i$ 秒到达该层的电梯口。

每层都有可能有人在等电梯。当一名雇员到达电梯口时，如果这层已经有人摁电梯了，他会等电梯；如果这层没人摁电梯，则他会去摁电梯。摁电梯会给电梯主控发送一个请求信号。

开始时电梯空闲，位于一楼。电梯每秒可以上升 / 下降一层。当第一次有人摁电梯时，电梯会响应该信号，到达对应楼层。如果电梯同时接受到多个信号，则它会响应编号较小的员工的请求信号。

电梯上升至对应楼层时，所有在这层楼等电梯的人都会进入电梯，然后电梯以同样的速度下降，直到电梯到达一楼。对于电梯下降过程中会经过的楼层，如果电梯到达该楼层时该楼层有请求信号，则电梯会在该楼层停，所有在该楼层等电梯的人都会进入电梯。

如果电梯空闲时有至少一个未响应的信号，则电梯会响应最早者。如果有多个最早者，则响应编号最小者。电梯会持续运作，直到 $n$ 名雇员全部到达一楼。

雇员进出电梯的时间忽略不计。每一秒开始时，人们先摁电梯，然后进行对应的行为。（电梯上升 / 下降一层，人们进出电梯，电梯决定响应哪个信号）

请求出每位雇员何时到达一楼。

inputFormat:
- 第一行：$n,m$
- 接下来 $n$ 行，每行两个整数，表示 $t_i,a_i$

outputFormat: $n$ 行，每行一个整数，表示答案。


title: [ROIR 2018 Day1] 管道监控

description:
**译自 ROI 2018 Regional. Day1 T4.** ***[Мониторинг труб](http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-regional-2018-day1.pdf)***

某输气系统包含 $n$ 个节点，编号分别为 $1\ldots n$，某些节点间有单向管道连接。$1$ 号节点是中央储气设施。

节点系统可用数列 $p_2,$ $p_3,$ $\ldots,$ $p_n$ 来表示。对于 $i\in[\;\!2,n\;\!],$ $p_i$ 号节点会有一条通向 $i$ 号节点的单向管道。已知中央储气设施可以将气体输送到系统中的所有节点。输气系统包含不同种类的管道，用英文小写字母 $\texttt{a}\sim\texttt{z}$ 来表示。$p_i$ 号节点通向 $i$ 号节点的管道的类型为 $c_i$。

有一种特殊的机器人被用来检查管道的质量。我们把「机器人从一个节点沿着一根管道前行到另一个节点，且机器人前进方向与气体方向一致」称作「一次移动」。

机器人会先被放在一个节点中，然后它会进行一次或多次移动，最后被人从输气系统中取出。这被称为「机器人进行了一次执勤」。

每次执勤时都需遵循 $m$ 种「规格」中的其中一种，这些规格的编号分别为 $1\ldots m$。每种规格都用一个由英文小写字母组成的字符串 $st_k$ 来表示。如果在一次执勤中机器人遵循了 $k$ 号规范，则在这次执勤中，机器人移动的次数与 $\mathrm{len}(st_k)$ 相等，并且对于 $j\in[1,\mathrm{len}(st_k)],$ $st_{k\:\!,\;\!j}$ 等于机器人第 $j$ 次经过的管道的类型。

若某次执勤遵循了 $t$ 号规格，则这次的花费为 $w_t$。

请问，要想让所有的管道都至少被检查一次，至少需要花费多少钱，并给出执勤路线的方案。

inputFormat:
第一行：$n,m,t$，$t$ 的含义在【输出格式】中。

接下来 $n-1$ 行：$p_i,$ $c_i$ 。

接下来 $m$ 行：$w_i,$ $st_i$。

outputFormat:
第一行包含一个整数，表示最小花费。若无解请输出 $-1$。

若 $t=0$ 就不用管后续了，若 $t=1$ 且有解则需输出方案。

输出方案时，在第一行输出最小花费之后，第二行应包含方案中路径的数量 $k$，接下来 $k$ 行，每行包括三个整数 $a_i,$ $b_i,$ $c_i$，依次表示一条执勤路线的起点、终点，以及这次执勤所使用的规格。

samples:
7 3 1
1 a
2 a
3 b
3 b
1 b
6 b
3 aab
5 b
2 ab


title: [ROIR 2018 Day2] 删除数字

description:
**译自 ROI 2018 Regional. Day2 T1.** ***[Удаление чисел](http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-regional-2018-day2.pdf)***

给定一个从 $1$ 到 $n$ 的自然数序列和一个自然数 $k$。通过一个或多个操作删除序列中的数字。在每一个操作中，按升序查看剩余的数字，每隔 $k$ 个数字删除一个。如果在某一个操作之后剩余的数字少于 $k$ 个，则删除过程结束。

需要确定在第几个操作删除数字 $n$，或者判断在删除过程结束前数字 $n$ 是否不会被删除。

例如，设 $n=13, k=2$。

- 第一个操作将删除数字 $2, 4, 6, 8, 10, 12$，剩下的数字是 $1, 3, 5, 7, 9, 11, 13$。
- 第二个操作将删除数字 $3, 7, 11$，剩下的数字是 $1, 5, 9, 13$。
- 第三个操作将删除数字 $5, 13$，剩下的数字是 $1, 9$。
- 第四个操作将删除数字 $9$，剩下的数字是 $1$。由于只剩下一个数字，删除过程结束。

因此，数字 $13$ 将在第三个操作被删除。

需要编写一个程序，根据给定的 $n$ 和 $k$ 确定数字 $n$ 在第几个操作被删除。

inputFormat:
第一行输入包含一个整数 $n$ $(3 \leq n \leq 10^{18})$。

第二行输入包含一个整数 $k$ $(2 \leq k \leq 100, k < n)$。

outputFormat: 输出一个整数，表示数字 $n$ 被删除的操作编号；如果数字 $n$ 不会被删除，则输出 $0$。


title: [ROIR 2018 Day2] 书页

description:
**译自 ROI 2018 Regional. Day2 T2.** ***[Старая книга](http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-regional-2018-day2.pdf)***

一群年轻的考古学家正在发掘一座古图书馆。他们偶然发现了一本旧书的残片。经过研究，他们得出了以下结论。

每一页上要么全是文本（称为文本页），要么全是插图（称为插图页）。已知前 $k$ 页全是插图页。这本书有页码，但只在文本页注明页码。已知注明的页码的总和为 $s$。

很可惜，考古学家既无法确定这本书有多少页，也无法确定哪些页面是插图页。不过，考古学家想知道，这本书最少有几个插图页。

inputFormat: 第一行一个整数 $k$，第二行一个整数 $s$。

outputFormat: 输出一行，表示这本书最少有几个插图页。


title: [ROIR 2018 Day2] 分形

description:
**译自 ROI 2018 Regional. Day2 T3.** ***[Красота фейерверка](http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-regional-2018-day2.pdf)***

已知一棵包含 $n$ 个元素的有根树 $T^1$。定义 $T^m$ 为一棵树，生成方式是在 $T^{m-1}$ 的每个叶结点下面连一棵 $T^1$ 而得。

![](https://cdn.luogu.com.cn/upload/image_hosting/s596ep9z.png)

试求 $T^m$ 的直径的长度（这里的长度指的是直径上的点数）。

inputFormat:
第一行 $n,m$。
第二行 $p_2\ldots p_n,\ \ $ $p_i$ 表示结点 $p_i$ 与结点 $i$ 有边连接。

outputFormat: 输出一行一个整数，表示答案。


title: [ROIR 2018 Day2] 大数据处理

description:
**译自 ROI 2018 Regional. Day2 T4.** ***[Обработка больших данных](http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-regional-2018-day2.pdf)***

某实验室正在研发一种能处理大规模数据的新型超级计算机。

这台超算的内存包含 $2^k$ 个存储单元，依次编号为 $0\ldots 2^k-1.$ 用内存段 $[L,R]$ 表示编号 $≥L$ 且 $≤R$ 的所有存储单元，该内存段的长度为 $R-L+1.$

定义：如果内存段 $[L,R]$ 的长度是 $2$ 的整数次幂（不妨假设是 $2^i$），且 $L$ 是 $2^i$ 的整数倍，那么这个内存段是「正确的内存段」。

若 $k=3,$ 则正确的内存段为 $[0,7],$ $[0,3],$ $[4,7],$ $[0,1],$ $[2,3],$ $[4,5],$ $[6,7],$ $[0,0],$ $[1,1],$ $[2,2],$ $[3,3],$ $[4,4],$ $[5,5],$ $[6,6]$ 和 $[7,7].$

现在，每个存储单元所存储的值均为 0. 你需要给每个存储单元赋值。简单起见，我们用游程编码的形式给出每个单元上的值。开头的 $c_1$ 个单元中存储的值为 $v_1,$ 接下来 $c_2$ 个单元中存储的的值为 $v_2,$ 以此类推，最后的 $c_n$ 个单元中存储的值为 $c_n,$ $1≤v_i≤m.$

举个例子，如果 $k = 3,$ $n = 3,$ $m = 2,$ $c = \{1,$ $2,$ $5\},$ $v = \{1,$ $2,$ $1\},$ 那么内存将被赋值为 $[1,$ $2,$ $2,$ $1,$ $1,$ $1,$ $1,$ $1].$

你只有一种方法给单元赋值：$\mathtt{STORE}([l,r],x).$ 该函数表示将内存段 $[l,r]$ 中所有单元全部赋值为 $x.$ 注意，$[l,r]$ 必须是合法的内存段。

试求至少需要多少次操作才能达成要求。

inputFormat:
第一行三个整数 $k,n,m$。
接下来的 $n$ 行，每行两个整数 $c_i,v_i$。

outputFormat: 输出一行一个整数，表示至少的次数。


title: [JOIG 2024] 三連続 / Three Consecutive

description:
给定长度为 $N$ 的字符串 $S$，$S$ 中的每个字符都是 `o` 或 `x`。

判断 $S$ 中是否包含**连续**的 $3$ 个 `o`。

inputFormat:
第一行输入一个整数 $N$。

第二行输入一个字符串 $S$。

outputFormat: 输出一行一个字符串 `Yes` 或 `No`：如果是 `Yes` 表示 $S$ 中存在连续的 $3$ 个 `o`，反之亦然。

hint:
#### 【样例解释 #1】

$S$ 中第 $3\sim 5$ 个字符是连续的 $3$ 个 `o`。

该样例满足子任务 $1,2$ 的限制。

#### 【样例解释 #2】

$S$ 中不存在连续的 $3$ 个 `o`。

该样例满足子任务 $1,2$ 的限制。

#### 【样例解释 #3】

$S$ 中不存在连续的 $3$ 个 `o`。

该样例满足子任务 $2$ 的限制。

#### 【样例解释 #4】

$S$ 中第 $1\sim 3$ 个字符是连续的 $3$ 个 `o`。

注意，$3$ 个连续的 `o` 旁边可能有其他的 `o`。

该样例满足子任务 $2$ 的限制。

#### 【样例解释 #5】

该样例满足子任务 $2$ 的限制。

#### 【样例解释 #6】

该样例满足子任务 $2$ 的限制。

#### 【数据范围】

- $1\le N\le 10^5$；
- $S$ 是长度为 $N$ 且仅包含小写字符 `o` 和 `x` 的字符串。

#### 【子任务】

1. （$40$ 分）$N=5$；
2. （$60$ 分）无附加限制。


title: [JOIG 2024] ダンス / Dance

description:
一所中学的一个班级有 $2N$ 名学生，第 $i(1\le i\le 2N)$ 名学生的身高是 $A_i$。

在即将开始的体育课上，学生们将两两配对，形成 $N$ 组进行舞蹈。

要跳出优美的舞蹈，每一对舞伴之间的身高差必须小于或等于 $D$。

给定每个学生的身高，确定能否跳出优美的舞蹈。

inputFormat:
第一行输入两个整数 $N,D$。

第二行输入 $2N$ 个整数 $A_1,A_2,\ldots,A_{2N}$。

outputFormat: 输出一行一个字符串，如果可以跳出优美的舞蹈输出 `Yes`，否则输出 `No`。

hint:
#### 【样例解释 #1】

只有一种配对方案，满足 $|2-7|\le 5$，符合条件。

该样例满足子任务 $1,3$ 的限制。

#### 【样例解释 #2】

无论如何都没法进行配对，使得任意一对舞伴的身高差 $\le 0$。

该样例满足子任务 $2,3$ 的限制。

#### 【样例解释 #3】

### 输出示例 3

考虑如下配对方案：

- 身高 $39$ 的学生和身高 $42$ 的学生配对；
- 身高 $22$ 的学生和身高 $23$ 的学生配对；
- 身高 $16$ 的学生和身高 $17$ 的学生配对；
- 身高 $32$ 的学生和身高 $36$ 的学生配对；
- 身高 $15$ 的学生和身高 $18$ 的学生配对；
- 身高 $30$ 的学生和身高 $30$ 的学生配对。

符合条件。

该样例满足子任务 $3$ 的限制。

#### 【数据范围】

- $1\le N\le 100$；
- $0\le D\le 100$；
- $1\le A_i\le 100(1\le i\le 2N)$。

#### 【子任务】

1. （$20$ 分）$N=1$；
2. （$40$ 分）$D=0$；
3. （$40$ 分）无附加限制。


title: [JOIG 2024] 座席 2 / Seats 2

description:
今年，JOI 国将主办 IOI（国际信息学奥林匹克竞赛）。届时将有 $N$ 名选手参赛，编号从 $1$ 到 $N$。

每位选手的国籍由一个介于 $1$ 和 $10^9$ 之间的整数表示：选手 $i(1\le i\le N)$ 来自国家 $C_i$。保证 $N$ 个选手的国籍**不完全相同**（即存在 $i\ne j(1\le i,j\le N)$ 使得 $C_i\ne C_j$）。

选手的座位排成一条直线，选手 $i(1\le i\le N)$ 的座位在 $X_i$ 处。选手 $i(1\le i\le N)$ 和选手 $j(1\le j\le N)$ 之间的**座位距离**为 $|X_i-X_j|$。

每个选手都想知道在与其他选手交流时，与离自己最近的异国选手的座位距离。

给定每个选手的国籍和座位位置，请为每个选手 $i(1\le i\le N)$ 求出与其来自不同国家的选手中，座位离选手 $i$ 最近的选手与 $i$ 的座位距离。

inputFormat:
第一行输入一个整数 $N$。

接下来 $N$ 行，每行输入两个整数 $C_i,X_i$。

outputFormat: 输出 $N$ 行，第 $i$ 行输出一个整数，表示座位离选手 $i$ 最近的选手与 $i$ 的座位距离。

hint:
#### 【样例解释 #1】

- 选手 $1$ 来自国家 $2$，选手 $2, 3$ 和他 / 她来自不同国家。在这些选手中，与选手 $1$ 座位距离最小的是选手 $3$，座位距离为 $3$。因此，答案为 $3$；
- 选手 $2$ 来自国家 $1$，选手 $1$ 是唯一和他 / 她来自不同国家的选手。选手 $2$ 和选手 $1$ 之间的座位距离为 $4$；
- 选手 $3$ 来自国家 $1$，选手 $1$ 是唯一和他 / 她来自不同国家的选手。选手 $3$ 和选手 $1$ 之间的座位距离为 $3$。

该样例满足子任务 $1,2,3$ 的限制。

#### 【样例解释 #2】

该样例满足子任务 $1,2,3$ 的限制。

#### 【样例解释 #3】

该样例满足子任务 $1,2,3$ 的限制。

#### 【数据范围】

- $2\le N \le 3\times 10^5$；
- $1\le C_i\le 10^9(1\le i\le N)$ 且 $C_i$ 不完全相同；
- $1\le X_i\le 10^9(1\le i\le N)$。

#### 【子任务】

1. （$20$ 分）$N\le 1000$；
2. （$40$ 分）$C_i\le 10(1\le i\le N)$；
3. （$40$ 分）无附加限制。


title: [JOIG 2024] たくさんの数字 / Many Digits

description:
JOI 高中的 Aoi 决定在 $N\times N$ 的表格中写下 $N^2$ 个非负整数。具体地，给定两个长度为 $N$ 的序列 $A,B$，她会在第 $i$ 行第 $j$ 列的格子上写下 $A_i+B_j$。

Aoi 想知道写出这些数需要多少个字符。也就是说，你需要求出写出的 $N^2$ 个整数在十进制下的位数的和。

inputFormat:
第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

第三行输入 $N$ 个整数 $B_1,B_2,\ldots,B_N$。

outputFormat: 输出一行一个整数表示答案。


title: [JOIG 2024] 名前 / Name

description:
JOI 君和 IOI 君决定养一只狗。经过讨论，他们决定给狗取一个满足以下所有条件的名字：

1. 名字必须仅包含大写字母和小写字母；
2. JOI 君最喜欢的字符串是长度为 $N$ 的字符串 $S$，名字必须包含 $S$ 作为子序列；
3. IOI 君最喜欢的字符串是长度为 $M$ 的字符串 $T$，名字必须包含 $T$ 作为子序列；
4. 名字中任意两个相同的字符之间必须间隔至少 $K$ 个其他字符。

以上的所有条件**区分大小写**，例如，我们将 `A` 和 `a` 视为不同的字符。

一个字符串的子序列定义为删除其中若干个字符（可以为 $0$ 个）形成的字符串。例如该字符串为 `algorithm`，那么 `ai` 和 `lgtm` 是它的子序列，而 `joi` 和 `logarithm` 不是。

由于他们都认为名称越短越好，所以他们决定选用满足上述四个条件的且最短的名字。

给定字符串 $S,T$ 和整数 $K$，请你求出满足条件的名字的最短长度。

inputFormat:
第一行输入三个整数 $N,M,K$。

第二行输入一个字符串 $S$。

第三行输入一个字符串 $T$。

outputFormat: 输出一行一个整数表示最小长度。

hint:
#### 【样例解释 #1】

字符串 `hottokeiki` 满足条件。可以证明，不存在长度更小的字符串满足条件，故答案为 $10$。

该样例满足子任务 $1,3,4,7,8$ 的限制。

#### 【样例解释 #2】

相较于上一个样例，仅有 $K$ 的值发生变化。

在该样例中，上一个样例的输出 `hottokeiki` 不满足第四个条件（任意两个相同的字符之间必须间隔至少 $K$ 个其他字符），因为两个 `t` 中没有其他字符。

而字符串 `hotNtokeiki` 满足条件，可以证明，不存在长度更小的字符串满足条件，故答案为 $11$。

该样例满足子任务 $2,3,5,6,7,8$ 的限制。

#### 【样例解释 #3】

相较于前两个样例，仅有 $K$ 的值发生变化。

在该样例中，上一个样例的输出 `hotNtokeiki` 不满足第四个条件（任意两个相同的字符之间必须间隔至少 $K$ 个其他字符），因为两个 `t` 之间仅有 $1$ 个字符，两个 `k` 之间仅有 $2$ 个字符，两个 `i` 之间仅有 $1$ 个字符。

而字符串 `hotarutokeiyuki` 满足条件，可以证明，不存在长度更小的字符串满足条件，故答案为 $15$。

该样例满足子任务 $3,8$ 的限制。

#### 【样例解释 #4】

字符串 `OJouhorinpikku` 满足条件。可以证明，不存在长度更小的字符串满足条件，故答案为 $14$。

请注意上面的条件区分大小写，因此诸如 `jouhorinpikku`（长度为 $13$）这样的字符串**不**符合条件。

该样例满足子任务 $4,7,8$ 的限制。

#### 【样例解释 #5】

字符串 `CoMaMiTeRTeRaCe` 是长度最小且满足条件的字符串，故答案为 $14$。

该样例满足子任务 $5,6,7,8$ 的限制。

#### 【样例解释 #6】

字符串 `JOIGEIGOI` 是长度最小且满足条件的字符串，故答案为 $9$。

该样例满足子任务 $7,8$ 的限制。

#### 【数据范围】

- $1\le N,M\le 500$；
- $0\le K\le 3$；
- $S,T$ 中仅包含大写字母和小写字母。

#### 【子任务】

1. （$2$ 分）$S=T$，$K=0$；
2. （$7$ 分）$S=T$，$K=1$；
3. （$16$ 分）$S=T$；
4. （$17$ 分）$K=0$；
5. （$13$ 分）$K=1$，$N,M\le 25$；
6. （$15$ 分）$K=1$；
7. （$20$ 分）$K\le 2$；
8. （$10$ 分）无附加条件。


title: [JOIG 2024] 感染シミュレーション / Infection Simulation

description:
昨天，$N$ 位顾客光顾了 EGOI 自助餐厅。顾客编号从 $1$ 到 $N$，顾客 $i(1\le i\le N)$ 到达时间为 $L_i$，离开时间为 $R_i$。今天，我们发现有一位顾客来店时感染了目前在 JOI 国流行的新型传染病 X。

传染病 X 的**传染性**用整数 $x$ 表示。具体来说，对于 $1\le i\le N$，当顾客 $i$ 与一个或多个感染者同时进入餐厅的累计总时间至少达到 $x$ 时，顾客 $i$ 就会成为新感染者。

现在，由于 JOI 国采取了严格的感染控制措施，因此必须确定感染者人数。然而，问题在于调查组并不知道哪些人感染了传染病，而代表传染性的整数 $x$ 的值也是未知数。

因此，EGOI 自助餐厅经理理惠决定对于 $Q$ 种情况，分别求出最终会有多少顾客被感染。在第 $j(1\le j\le Q)$ 种情况下，最初只有顾客 $P_j$ 受到感染，传染性为 $X_j$。

根据到店顾客的信息，求出每种情况下最终的感染人数。注意，即使受感染的人数是在他们离开餐厅时被感染的，也应包括在内。此外，还假定一旦顾客感染了传染病 X，他就不能再被感染。

inputFormat:
第一行输入一个整数 $N$。

接下来 $N$ 行，每行两个整数 $L_i,R_i$。

接下来一行输入一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $P_i,X_i$。

outputFormat: 输出 $Q$ 行，第 $i$ 行一个整数表示第 $i$ 种情况下的最终感染人数。

hint:
#### 【样例解释 #1】

在第 $1$ 个询问中，初始的感染者是顾客 $1$，传染性为 $15$，因此感染的传播方式如下

- 在时间 $10$，顾客 $1$ 到达餐厅；
- 在时间 $20$，顾客 $2$ 到达餐厅；
- 在时间 $35$，顾客 $2$ 与顾客 $1$ 同时出现在餐厅累计时间为 $15$，顾客 $2$ 被感染；
- 在时间 $40$，顾客 $1$ 离开餐厅；
- 在时间 $45$，顾客 $3$ 到达餐厅；
- 在时间 $60$，顾客 $3$ 与顾客 $2$ 同时出现在餐厅累计时间为 $15$，顾客 $3$ 被感染；与此同时，顾客 $3$ 离开餐厅；
- 在时间 $70$，顾客 $4$ 到达餐厅；
- 在时间 $80$，顾客 $2$ 离开餐厅；
- 在时间 $95$，顾客 $4$ 与顾客 $2$ 同时出现在餐厅累计时间为 $10$，因此顾客 $4$ 未感染；与此同时，顾客 $4$ 离开餐厅。

最终顾客 $1,2,3$ 被感染，共 $3$ 人，故第 $1$ 个询问答案为 $3$。

该样例满足子任务 $4,5,6,8,9,10$ 的限制。

#### 【样例解释 #2】

- 在第 $1$ 个询问中，$7$ 个顾客 $1,2,3,4,6,7,8$ 最终被感染，答案为 $7$。
- 在第 $2$ 个询问中，$1$ 个顾客 $1$ 最终被感染，答案为 $1$。
- 在第 $3$ 个询问中，$5$ 个顾客 $2,3,4,7,8$ 最终被感染，答案为 $5$。

该样例满足子任务 $2,3,4,5,6,10$ 的限制。

#### 【样例解释 #3】

该样例满足子任务 $1,2,3,5,6,8,10$ 的限制。

#### 【样例解释 #4】

该样例满足子任务 $4,5,6,9,10$ 的限制。

#### 【样例解释 #5】

该样例满足子任务 $4,5,6,7,8,9,10$ 的限制。

#### 【样例解释 #6】

该样例满足子任务 $4,5,6,7,8,10$ 的限制。

#### 【样例解释 #7】

该样例满足子任务 $4,5,6,7,9,10$ 的限制。

#### 【数据范围】

- $1\le N\le 10^5$；
- $0\le L_i<R_i\le 10^9(1\le i\le N)$；
- $1\le Q\le 10^5$；
- $1\le P_j\le N(1\le j\le Q)$；
- $1\le X_j\le 10^9(1\le j\le Q)$。

#### 【子任务】

1. （$2$ 分）$L_i=0(1\le i\le N)$，$R_i=10(1\le i\le N)$，$Q\le 5$；
2. （$3$ 分）$L_i=0(1\le i\le N)$，$Q\le 5$；
3. （$6$ 分）$L_i=0(1\le i\le N)$；
4. （$10$ 分）$N\le 500$，$Q\le 5$，$R_i\le 500(1\le i\le N)$，$X_j\le 500(1\le j\le Q)$；
5. （$11$ 分）$N\le 500$，$Q\le 5$；
6. （$16$ 分）$Q\le 5$；
7. （$13$ 分）$P_j=1(1\le j\le Q)$，$L_1<L_2<\cdots<L_N$，$R_1<R_2<\cdots<R_N$；
8. （$14$ 分）$P_j=1(1\le j\le Q)$；
9. （$15$ 分）$R_i-L_i(1\le i\le N)$ 的最小值大于或等于 $X_j(1\le j\le Q)$ 的最大值；
10. （$10$ 分）无附加限制。