title: 「MCOI-08」Photoelectric Effect

description:
有一棵 $n$（$1\le n\le 10^5$）个点的树以及 $k$（$2\le k\le 5$）个颜色，根节点为 $1$。同时，给定一个颜色合并函数 $a\otimes b$，满足当 $1\le a,b\le k$，有 $1\le a\otimes b\le k$。

请问有多少个方案对所有点染色，使得当点对 $u,v$ 之间没有祖先关系，有：

 - $u$ 和 $v$ 最近公共祖先的颜色为点 $u$ 的颜色和点 $v$ 的颜色之并。

答案对 $10^9+7$ 取模。

inputFormat:
本题有多组数据，第一行一个正整数 $t$（$1\le t\le 10^3$），为数据组数。接下来 $t$ 组数据，其中对于每一组数据：

第一行两个正整数 $n,k$。

接下来 $k$ 行，每行 $k$ 个正整数。第 $i$ 行第 $j$ 个数为 $i\otimes j$ 的值。

接下来 $n-1$ 个正整数 $f_2,f_3,\dots,f_n$，其中 $f_i$ 是 $i$ 的父亲节点。

outputFormat:
对于每一组数据：

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

hint:
#### 样例 1 解释

树的形态如下：

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

设 $w_i$ 为第 $i$ 个点的点权，则有如下 $4$ 种分配方式：

- $w_i=\{1,1,1,1,1\}$；
- $w_i=\{2,2,2,1,1\}$；
- $w_i=\{2,1,1,2,2\}$；
- $w_i=\{1,2,2,2,2\}$。

#### 数据规模与约定

**本题采用捆绑测试。**

对于 $100\%$ 的数据，$1\le n,\sum n\le10^5$，$2\le k\le 5$，$1\le f_i<i$。

对于 $100\%$ 的数据，$1\le t\le 1000$。

 - Subtask 1（5 pts）：$n\le5$；
 - Subtask 2（11 pts）：树上任何节点孩子个数至多为 $2$；
 - Subtask 3（23 pts）：树上任何节点孩子个数至多为 $3$；
 - Subtask 4（13 pts）：$k=2$；
 - Subtask 5（17 pts）：$k\le3$；
 - Subtask 6（31 pts）：无特殊限制。


title: [COCI2020-2021#6] Bold

type: P

description:
Paula 给 Daniel 写了一封信，她需要加粗文本的字体，以便视力恶化的 Daniel 阅读。

信可以用 `.` 和 `#` 组成的矩阵表示。对于所有信中原有的 `#`，Paula 需要将其向右下方扩展为 $2 \times 2$ 的 `#`。

inputFormat:
第一行两个整数 $n, m$，表示信的尺寸。

接下来 $n$ 行，每 $m$ 个字符，表示信的内容。

保证最后一行与最后一列中没有 `#`。

outputFormat: $n$ 行，每行 $m$ 个字符，表示加粗后的信。

hint:
#### 数据规模与约定

对于 $100\%$ 的数据，$2 \le n, m \le 10^3$。保证信中只包含 `.` 和 `#`。

------------

#### 说明

**本题分值按 COCI 原题设置，满分 $50$**。

**题目译自 [COCI2020-2021](https://hsin.hr/coci/archive/2020_2021/) [CONTEST #6](https://hsin.hr/coci/archive/2020_2021/contest6_tasks.pdf) _T1 Bold_**。


title: [COCI2020-2021#6] Alias

description:
Novak 和 Rafael 在玩一个猜单词的游戏。

Rafael 脑中有一个包含 $n$ 个单词的数据库。数据库中还有 $m$ 对形如 $x, y, t$ 的链接，表示如果他记起或听到了单词 $x$，他会在 $t$ 毫秒后记起单词 $y$。

游戏将进行 $q$ 轮，每轮游戏相互独立。每一轮游戏开始时，Novak 将说出初始单词 $a$。他想知道，多少毫秒后 Rafael 会记起目标单词 $b$？

inputFormat:
第一行两个整数 $n, m$。

接下来 $m$ 行每行两个字符串 $x_i, y_i$ 和一个整数 $t_i$，表示一对链接。

接下来一行一个整数 $q$。

接下来 $q$ 行，每行两个字符串 $a_i, b_i$，表示第 $i$ 轮游戏中的初始单词和目标单词。

outputFormat:
共 $q$ 行，表示每轮游戏的答案。

如果 Rafael 能记起目标单词，输出一个整数，表示所需要的时间。否则，输出 `Roger`。

samples:
3 2
novak goat 1
goat simulator 3
2
novak simulator
simulator goat

samples:
3 3
kile legend 4
legend beer 5
beer kile 6
2
kile beer
legend kile

samples:
4 5
rafael me 5
me ow 6
ow ausopenfinal 2012
ausopenfinal me 2
rafael ausopenfinal 2
3
rafael me
me rafael
ow me

hint:
#### 样例 1 解释

第一轮游戏中，Novak 说出单词 `novak`。$1$ 毫秒后，Rafael 记起单词 `goat`。又过了 $3$ 毫秒，他记起目标单词 `simulator`。

第二轮游戏中，Novak 说出单词 `simulator`，但 Rafael 不会记起任何其他单词。

------------

#### 数据规模与约定

对于 $20$ 分的数据，$n \le 10$。
对于 $40$ 分的数据，$n \le 100$。
对于 $100\%$ 的数据，$2 \le n \le 10^3$，$1 \le m \le 10^3$，$1 \le t_i \le 10^9$，$1 \le q \le 10^3$。保证单词的长度不超过 $20$ 且仅含小写字母。

------------

#### 说明

**本题分值按 COCI 原题设置，满分 $70$**。

**题目译自 [COCI2020-2021](https://hsin.hr/coci/archive/2020_2021/) [CONTEST #6](https://hsin.hr/coci/archive/2020_2021/contest6_tasks.pdf) _T2 Alias_**。


title: [COCI2020-2021#6] Anagramistica

description:
Biljana 喜欢出字谜游戏。

如果一个单词可以由另一个单词交换字母顺序得到，则称它们是「相似」的。

现在，她有 $n$ 个单词。她希望选出一些单词，使得其中恰好有 $k$ 对单词是「相似」的。请你帮她计算可行的方案数，对 $10^9 + 7$ 取模。

inputFormat:
第一行两个整数 $n$，$k$。

接下来 $n$ 行，每行一个字符串，表示一个单词。

outputFormat: 一行一个整数，表示可行的方案数，对 $10^9 + 7$ 取模。


title: [COCI2020-2021#6] Geometrija

description:
平面内有不共线的 $n$ 个点。如果两条线段 $\overline{AB}$  和 $\overline{CD}$ 有异于 $A, B, C, D$ 的公共点，则称他们「相交」。

记 $S$ 为 $n$ 个点两两相连得到的线段的集合。求不与 $S$ 中任意其他线段相交的线段数量。

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

接下来 $n$ 行，每行两个整数 $x_i, y_i$，表示第 $i$ 个点的坐标。

outputFormat: 一行一个整数，表示满足要求的线段的数量。

hint:
#### 样例 1 解释

符合要求的线段如图所示：

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

#### 样例 2 解释

符合要求的线段如图所示：

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

------------

#### 数据规模与约定

**本题采用捆绑测试**。

| Subtask | 分值 | 数据规模与约定 |
| :----------: | :----------: | :----------: |
| $1$ | $20$ | $3 \le n \le 40$ |
| $2$ | $30$ | $3 \le n \le 200$ |
| $3$ | $60$ | 无附加约定 |

对于 $100\%$ 的数据，$3 \le n \le 10^3$，$-10^9 \le x_i, y_i \le 10^9$。

------------

#### 说明

**本题分值按 COCI 原题设置，满分 $110$**。

**题目译自 [COCI2020-2021](https://hsin.hr/coci/archive/2020_2021/) [CONTEST #6](https://hsin.hr/coci/archive/2020_2021/contest6_tasks.pdf) _T4 Geometrija_**。


title: [COCI2020-2021#6] Index

description:
「H 指数」可以衡量学者论文的数量与引用量。一位学者的「H 指数」为最大的整数 $h$，满足他至少有 $h$ 篇论文被引用了不少于 $h$ 次。

Mirko 一共发表了 $n$ 篇论文，而他有 $q$ 个疑问：如果他只发表了第 $l_i$ 篇至第 $r_i$ 篇论文，他的「H 指数」会是多少？

inputFormat:
第一行两个整数 $n, q$。

第二行 $n$ 个整数 $p_i$，其中 $p_i$ 表示他的第 $i$ 篇论文的引用量。

接下来 $q$ 行，每行两个整数 $l_i, r_i$，表示一个疑问。

outputFormat: 共 $q$ 行。每行一个整数，表示一个疑问的答案。


title: [省选联考 2021 A/B 卷] 卡牌游戏

description:
Alice 有 $n$ 张卡牌，第 $i$（$1 \le i \le n$）张卡牌的正面有数字 $a_i$，背面有数字 $b_i$，初始时所有卡牌正面朝上。

现在 Alice 可以将不超过 $m$ 张卡牌翻面，即由正面朝上改为背面朝上。Alice 的目标是让最终朝上的 $n$ 个数字的极差（最大值与最小值的差）尽量小。请你帮 Alice 算一算极差的最小值是多少。

inputFormat:
第一行，两个正整数 $n, m$，代表卡牌张数与至多翻面张数。
第二行，$n$ 个正整数，第 $i$ 个数字表示 $a_i$。
第三行，$n$ 个正整数，第 $i$ 个数字表示 $b_i$。

数据保证卡牌上的 $2 n$ 个数字互不相同，且卡牌按照 $a_i$ 升序给出。

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

samples:
见附件中的 card/card2.in。
见附件中的 card/card2.ans。

samples:
见附件中的 card/card3.in。
见附件中的 card/card3.ans。


title: [省选联考 2021 A 卷] 矩阵游戏

description:
Alice 有一个 $n \times m$ 的矩阵 $a_{i, j}$（$1 \le i \le n$，$1 \le j \le m$），其每个元素为大小不超过 ${10}^6$ 的非负整数。

Bob 根据该矩阵生成了一个 $(n - 1) \times (m - 1)$ 的矩阵 $b_{i, j}$（$1 \le i \le n - 1$，$1 \le j \le m - 1$），每个元素的生成公式为

$$ b_{i, j} = a_{i, j} + a_{i, j + 1} + a_{i + 1, j} + a_{i + 1, j + 1} $$

现在 Alice 忘记了矩阵 $a_{i, j}$，请你根据 Bob 给出的矩阵 $b_{i, j}$ 还原出 $a_{i, j}$。

inputFormat:
**本题有多组数据。**

第一行，一个整数 $T$，表示数据组数。对于每组数据：

第一行，两个正整数 $n, m$，表示矩阵 $a_{i, j}$ 的大小。
接下来 $n - 1$ 行，每行 $m - 1$ 个非负整数，表示 $b_{i, j}$。

outputFormat:
对于每组数据：

1. 若矩阵 $b_{i, j}$ 无法被生成，则输出一行一个字符串 `NO`。
2. 若矩阵 $b_{i, j}$ 可被生成，则先输出一行一个字符串 `YES`，接下来输出 $n$ 行每行 $m$ 个（用单个空格分隔的）大小不超过 ${10}^6$ 的非负整数表示 $a_{i, j}$。

若有多个矩阵 $a_{i, j}$ 可生成给出的 $b_{i, j}$，输出其中任意一个即可。


title: [USACO21OPEN] Maze Tac Toe S

description:
奶牛 Bessie 喜欢玩走迷宫。她同样喜欢玩井字棋（更准确地说，奶牛版的井字棋，马上会进行介绍）。Farmer John 找到了一种全新的方式，可以使她同时玩到这两种游戏！

首先，奶牛井字棋：与在 $3 \times 3$ 棋盘内放置 `X` 和 `O` 不同，奶牛当然是在 $3 \times 3$ 棋盘内放置 `M` 和 `O`。在一方的回合内，玩家可以选择将一个 `M` 或一个 `O` 放在任意一个空格内（这是另一个与标准井字棋的不同之处，标准的井字棋中一名玩家始终放 `X` 而另一名玩家始终放 `O`）。奶牛井字棋的胜利方是首位拼出 `MOO` 的玩家，可以是同行、同列或对角线。倒着拼出也是可以的，例如一名玩家在棋盘的一行内拼出 `OOM` 也可以获胜。如同标准井字棋一样，有可能最后没有玩家取得胜利。奶牛井字棋的一次行动通常用 3 个字符表示，`Mij` 或 `Oij`，其中 $i$ 和 $j$ 在范围 $1 \ldots 3$ 之间，表示放置 `M` 或 `O` 的行与列。

为了给 Bessie 增加一些挑战，Farmer John 设计了一个由 $N \times N$ 个方格组成的正方形迷宫（$3 \leq N \leq 25$）。某些方格，包括所有的边界方格，有巨大的草堆，使得 Bessie 不能移动到这些方格。Bessie 可以沿东南西北四个方向在迷宫内的所有其他方格内自由行动。某些方格内有一张纸，上面写有奶牛井字棋的一次行动。当 Bessie 在迷宫中移动时，任何时刻她停留在这样的方格上，她都必须于迷宫中移动之时在同时进行的奶牛井字棋游戏内做出对应的行动（除非奶牛井字棋中对应的方格已经被填上了，在这种情况下她不进行行动）。在奶牛井字棋游戏内没有与她对阵的玩家，但迷宫中的某些方格可能会不利于她最终拼出 `MOO`。

如果 Bessie 在获胜之时就会立刻停止奶牛井字棋，请求出她可以通过适当的方式在迷宫中移动而完成的不同的胜利状态棋盘数量。

inputFormat:
输入的第一行包含 $N$。

以下 $N$ 行，每行包含 $3N$ 个字符，描述迷宫。每个方格用 3 个字符表示，`###` 代表墙，`...` 代表空格，`BBB` 代表 Bessie 所在的一个非墙方格，或者一个奶牛井字棋的行动，表示 Bessie 必须进行对应行动的一个非墙方格。恰好一个方格为 `BBB`。

outputFormat: 输出 Bessie 可以通过在迷宫中行动并在获胜时立刻停止而产生的不同的胜利状态下的奶牛井字棋盘数量（可能为 $0$）。

hint:
#### 样例说明

在这个样例中，Bessie 最终可能达成 $8$ 种胜利的棋盘状态：

```plain
O.M
.O.
MOM

O..
.O.
.OM

O.M
.O.
.OM

O..
.O.
MOM

O..
...
OOM

..M
.O.
OOM

...
.O.
OOM

...
...
OOM
```

对其中一种情况进行说明：

```plain
O..
...
OOM
```

在这里，Bessie 可以先移动到 `O11` 方格，然后移动到下方并通过 `O32`、`M33` 和 `O31`。此时游戏结束，因为她获得了胜利（例如她不能再前往位于她当前所在的 `O31` 方格北面的 `M11` 方格）。

#### 说明

供题：Brian Dean


title: [USACO21OPEN] Do You Know Your ABCs? S

description:
Farmer John 的奶牛正在 mooZ 视频会议平台上举行每日集会。她们发明了一个简单的数字游戏，为会议增添一些乐趣。

Elsie 有三个正整数 $A$、$B$ 和 $C$（$1\le A\le B\le C$）。这些数字是保密的，她不会直接透露给她的姐妹 Bessie。她告诉 Bessie $N$（$4\le N\le 7$）个不同的整数 $x_1,x_2,\ldots,x_N$（$1\le x_i\le 10^9$），并宣称每一个 $x_i$ 都是 $A$、$B$、$C$、$A+B$、$B+C$、$C+A$ 或 $A+B+C$ 之一。然而，Elsie 可能在撒谎；这些整数 $x_i$ 可能并没有对应任何一组合法的 $(A,B,C)$。

Bessie 百思不得其解，所以需要靠你来求出与 Elsie 给出的数相符合的三元组 $(A,B,C)$ 的数量。

每个输入包含 $T$（$1\le T\le 100$）组需要独立求解的测试用例。

inputFormat:
输入的第一行包含 $T$。

每个测试用例的第一行包含 $N$，为 Elsie 给 Bessie 的整数的数量。

每个测试用例的第二行包含 $N$ 个不同的整数 $x_1,x_2,\ldots,x_N$。

outputFormat: 对于每个测试用例，输出与 Elsie 给出的数相符合的三元组 $(A,B,C)$ 的数量。


title: [USACO21OPEN] Acowdemia S

description:
由于对计算机科学的热爱，以及有朝一日成为 「Bessie 博士」的诱惑，奶牛 Bessie 开始攻读计算机科学博士学位。经过一段时间的学术研究，她已经发表了 $N$ 篇论文（$1 \leq N \leq 10^5$），并且她的第 $i$ 篇论文得到了来自其他研究文献的 $c_i$ 次引用（$0 \leq c_i \leq 10^5$）。

Bessie 听说学术成就可以用 $h$ 指数来衡量。$h$ 指数等于使得研究员有至少 $h$ 篇引用次数不少于 $h$ 的论文的最大整数 $h$。例如，如果一名研究员有 $4$ 篇论文，引用次数分别为 $(1,100,2,3)$，则 $h$ 指数为 $2$，然而若引用次数为 $(1,100,3,3)$ 则 $h$ 指数将会是 $3$。

为了提升她的 $h$ 指数，Bessie 计划写至多 $K$ 篇综述（$0 \leq K \leq 10^5$），并在每篇综述中引用许多她曾经写过的论文。然而，由于页数限制，她至多可以在一篇综述中引用 $L$ 篇论文（$0 \leq L \leq 10^5$）。当然，一篇综述中她只能引用一篇论文至多一次（但是一篇论文可以在多篇综述中被引用）。

请帮助 Bessie 求出在写完这些综述后她可以达到的最大 $h$ 指数。Bessie 不可以在一篇综述中引用她写的其他综述。

注意 Bessie 的导师可能会告知她纯粹为了提升 $h$ 指数而写综述存在违反学术道德的嫌疑；我们不建议其他学者模仿 Bessie 的行为。

inputFormat:
输入的第一行包含 $N$、$K$ 和 $L$。

第二行包含 $N$ 个空格分隔的整数 $c_1,\ldots, c_N$。

outputFormat: 输出最大可以达到的 $h$ 指数。

hint:
#### 样例说明

在这个样例中，Bessie 可以写至多一篇综述。如果 Bessie 引用她的第一、第三、第四篇论文中的任意一篇，她的 $h$ 指数会变为 $2$。

#### 测试点性质：

- 测试点 $1 \sim 6$ 满足 $N\le 100$。
- 测试点 $7 \sim 16$ 没有额外限制。

#### 说明

供题：Dhruv Rohatgi


title: [省选联考 2021 A/B 卷] 图函数

description:
对于一张 $n$ 个点 $m$ 条边的有向图 $G$（顶点从 $1 \sim n$ 编号），定义函数 $f(u, G)$：

1. 初始化返回值 $cnt = 0$，图 $G' = G$。
2. 从 $1$ 至 $n$ 按顺序枚举顶点 $v$，如果当前的图 $G'$ 中，从 $u$ 到 $v$ 与从 $v$ 到 $u$ 的路径都存在，则将 $cnt + 1$，并在图 $G'$ 中删去顶点 $v$ 以及与它相关的边。
3. 第 $2$ 步结束后，返回值 $cnt$ 即为函数值。

现在给定一张有向图 $G$，请你求出 $h(G) = f(1, G) + f(2, G) + \cdots + f(n, G)$ 的值。

更进一步地，记删除（按输入顺序给出的）第 $1$ 到 $i$ 条边后的图为 $G_i$（$1 \le i \le m$），请你求出所有 $h(G_i)$ 的值。

inputFormat:
第一行，两个整数 $n,m$，表示图的点数与边数。
接下来 $m$ 行，每行两个整数，第 $i$ 行的两个整数 $x_i, y_i$ 表示一条有向边 $x_i \to y_i$。

数据保证 $x_i \neq y_i$ 且同一条边不会给出多次。

outputFormat: 输出一行 $m + 1$ 个整数，其中第一个数表示给出的完整图 $G$ 的 $h(G)$ 值。第 $i$（$2 \le i \le m + 1$）个整数表示 $h(G_{i-1})$。

samples:
见附件中的 graph/graph2.in。
见附件中的 graph/graph2.ans。


title: [JOISC 2021 Day1] 曲芸飛行

background:
**本题是提交答案题。**

SPJ modified by wlzhouzhuan

description:
在一个平面直角坐标系上，有 $N$ 个点 $(X_i,Y_i)$，小 B 从一个点出发，任意选择一个点作为终点走直线路径过去，并重复这个过程 $N-1$ 次，不难发现这个过程会形成由 $N$ 条线段组成的折线，除了第一个点和最后一个点之外的每一个点都会形成一个夹角 $\alpha_i\ (2 \le i \le n-1)$（小于等于 $180^\circ$ 的那个角，$i$ 即代表第 $i$ 个经过的点），小 B 要求你通过策划折线路径经过的点的顺序求得下面这个式子的最大值：

$$\min\limits_{i=2}^{n-1}\{\alpha_i\}$$

inputFormat:
第一行两个整数 $N,Z_0$ 代表点数和评分参数（见下方数据规模与约定和评测说明）。

接下来 $N$ 行每行两个整数 $X_i,Y_i$ 代表一个点。

outputFormat: $N$ 行每行一个整数 $P_k$ 代表第 $k$ 个经过的点的编号。

hint:
#### 样例 1 解释

如下图所示：

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

最小的夹角在点 $6$ 处，为 $68.19859\cdots^\circ$，根据 $Z_0=90$ 和下方评测方式中的评分参数说明，这个输出可以得到 $61.5\%$ 的分数。

#### 数据规模与约定

对于 $100\%$ 的数据，$3 \le N \le 1000$，$\sqrt{X_i^2+Y_i^2} \le 10^7$，任意两点不重合，$1 \le Z_0 \le 179$。

具体地，**本题为提交答案题**，共有 $6$ 个测试点：

- 输入文件为 `input_01.txt` 到 `input_06.txt`。
- 输出文件为 `output_01.txt` 到 `output_06.txt`。
- 每一个测试点的 $N$，$Z_0$ 和分数分别为：

|测试点编号|$N$|$Z_0$|分数|
|:-:|:-:|:-:|:-:|
|$1$|$15$|$100$|$10$|
|$2$|$200$|$143$|$15$|
|$3$|$200$|$134$|$15$|
|$4$|$1000$|$156$|$20$|
|$5$|$1000$|$150$|$20$|
|$6$|$1000$|$153$|$20$|

#### 评测参数

**本题采用 Special Judge。**

感谢 @[035966_L3](https://www.luogu.com.cn/user/365654) 提供的 [Special Judge](https://www.luogu.com.cn/blog/12322655-4/p7558spj)。

如果您的输出格式有误或者输出的数不是 $1 \sim N$ 等其他错误，您抱铃。

如果您的输出格式是正确的，假设您得到的最小夹角是 $Z$，则您的分数如下：

- 如果 $Z \ge Z_0$，您将得到满分。
- 如果 $Z < Z_0$，设该测试点分数为 $S$，您将得到 $S \times \frac{f(Z/180)}{f(Z_0/180)}$。

定义函数 $f(\alpha)\ (0 \le \alpha \le 1)$ 为：

$$f(\alpha)=4\alpha^4+\alpha$$

#### 评测库

我们额外提供评测库（在文件 `aerobatics.h` 中），您可以用他计算三个点形成的夹角度数。

调用格式如下：

- `double GetAngle(int xb,int yb,int xa,int ya,int xc,int yc) ` 或 `double GetAngle(int xb,int yb,int xc,int yc,int xa,int ya)`
	- 这个函数计算 $\angle ABC$，误差足够小。
    - **请保证顺序正确。**
    - $(xa,ya)$ 为点 $A$。
    - $(xb,yb)$ 为点 $B$。
    - $(xc,yc)$ 为点 $C$。
    - 如果 $(xa,ya)=(xb,yb)$ 或 $(xa,ya)=(xc,yc)$，那么，嘿，嘿嘿。

#### 附加文件说明

1. 名称：下方附件中的 `aerobatics-dist.zip`。
	- in & out：样例输入输出。
	- aerobatics.h：评测库。
2. 名称：下方附件中的 `aerobatics-data.zip`：
	- in：输入数据。

#### 说明

翻译自 [第２０回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Day1 A 曲芸飛行 (Aerobatics) 的英文版本](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/aerobatics-en.pdf)。


title: [JOISC 2021 Day1] IOI 熱の感染拡大

background: 本题数据保留一部分，请在 [此处](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/fever-data.zip) 获取完整数据。

description:
JOI 王国有 $N$ 个宫殿，第 $i$ 个宫殿坐标为 $(X_i,Y_i)$，每个宫殿居住着一个王子，第 $i$ 个宫殿里的王子为 $i$ 号王子。从第 $0$ 时刻开始，每个王子将会从自己的宫殿出发开始走动，他们可以选择东南西北：

- 如果选择东，则 $t$ 时刻过后坐标位置从 $(x,y)$ 变为 $(x+t,y)$。
- 如果选择西，则 $t$ 时刻过后坐标位置从 $(x,y)$ 变为 $(x-t,y)$。
- 如果选择南，则 $t$ 时刻过后坐标位置从 $(x,y)$ 变为 $(x,y-t)$。
- 如果选择北，则 $t$ 时刻过后坐标位置从 $(x,y)$ 变为 $(x,y+t)$。

$t$ 不一定是整数。

方向不会给定，你可以自己规划。

不幸的是，$1$ 号王子染上了 IOVID-114514 病毒，在 $0$ 时刻只有 $1$ 号王子感染了该病毒。

IOVID-114514 病毒按照如下方式进行传播：

- 如果某一个时刻 $a$ 号王子和 $b$ 号王子在同一个坐标上，且 $a$ 号王子感染了病毒，$b$ 号王子没有感染病毒，则 $a$ 号王子会将病毒传染给 $b$ 号王子。

IOVID-114514 病毒没有其他传染方式，可怜的国王 JOI 114514 世也没有发现治愈方法。

（消毒水也不能治愈！）

JOI 114514 世想问问你求第 $10^{100}$ 个时刻的时候最多会有多少个王子感染 IOVID-114514 病毒。

inputFormat:
第一行一个整数 $N$ 代表宫殿个数。

接下来 $N$ 行每行两个整数 $X_i,Y_i$ 代表一个宫殿的坐标。

outputFormat: 一行一个整数代表答案。

hint:
#### 样例 1 解释

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

我们规划 $1$ 号王子向东，$2$ 号王子向西。

不难发现，不论怎么移动 $1$ 都无法与 $2$ 相遇，只有 $1$ 号王子一个感染者。

#### 样例 2 解释

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

我们规划 $1$ 号王子向东，$2$ 号王子向北，$3$ 号王子向西。

- 时刻 $0$，$1$ 号王子是感染者。
- 时刻 $1$，$1$ 号王子与 $2$ 号王子坐标重合，$2$ 号王子感染。
- 时刻 $2$，$2$ 号王子与 $3$ 号王子坐标重合，$3$ 号王子感染。

#### 样例 3 解释

我们规划 $1$ 号王子向北，$2$ 号王子向南。

- 时刻 $0$，$1$ 号王子是感染者。
- 时刻 $0.5$，$1$ 号王子和 $2$ 号王子坐标重合，$2$ 号王子感染。

#### 数据规模与约定

**本题采用捆绑测试。**

- Subtask 1（5 pts）：$N \le 7$，满足性质 A。
- Subtask 2（8 pts）：$N \le 15$，满足性质 A。
- Subtask 3（6 pts）：$N \le 100$，满足性质 A 和 B。
- Subtask 4（6 pts）：$N \le 100$，满足性质 A。
- Subtask 5（12 pts）：$N \le 3000$。
- Subtask 6（32 pts）：满足性质 A。
- Subtask 7（31 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le X_i,Y_i \le 5 \times 10^8$，宫殿坐标互不重合。

其中性质分别为：

- 性质 A：$X_i \ne X_j$，$Y_i \ne Y_j$。
- 性质 B：$1$ 号宫殿坐标为原点。

#### 说明

翻译自 [第２０回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Day1 B IOI 熱の感染拡大 (IOI Fever) 的英文版本](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/fever-en.pdf)。


title: [JOISC 2021 Day2] 道路の建設案 (Road Construction)

description:
JOI 国是一个 $x\times y$ 的二维平面，王国里有 $n$ 个城镇，分别编号为 $1, 2, \cdots, n$，其中第 $i$ 个城镇的 **坐标** 为 $(x_i, y_i)$。

在 JOI 国，正计划修建连接两座城镇的路（下文简称：**「修路的项目」**），路有 $k$ 条。连接两个不同的城镇 $a$ 和 $b$ 将花费 $|x_a − x_b| + |y_a − y_b|$ 元。若有一条连接 $c$，$d$ 的路，则不需要也不可以在建一条连接 $d$，$c$ 的路，因为它们是相同的。

你要管理这个「修路的项目」，为了计算花费情况，你得弄明白连接一些城镇所需的花费。在这 $\dfrac{n\cdot(n-1)}{2}$ 条道路中，你想了解最便宜的 $k$ 条道路的花费。

给你城镇的坐标以及 $k$，请计算最便宜的 $k$ 条路所需要的钱。

inputFormat:
输入数据共 $n+1$ 行。

第一行，$2$ 个正整数 $n, k$，$n$ 表示城镇的数量，$k$ 含义见 **「题目描述」** 部分。

接下来的第 $2 \sim n+1$ 行，每行 $2$ 个正整数，分别是 $x_i$ 和 $y_i$，其中 $1\le i \le n$，表示第 $i$ 个城镇的坐标。

outputFormat:
输入数据共 $k$ 行。

对于第 $k$ 行，有一个整数表示第 $k$ 便宜的路需要的日元。


title: [JOISC 2021 Day4] イベント巡り 2 (Event Hopping 2)

background: **因洛谷限制，本题不予评测每个 Subtask 的第 1 ~ 20 个测试点，您可以 [点此](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/event2-data.zip) 下载所有数据自行评测或在 [这里](https://www.luogu.com.cn/problem/U159034) 测试，若您希望写本题题解，建议您在通过 [本题](https://www.luogu.com.cn/problem/P7562) 与 [每个 Subtask 前 20 个测试点](https://www.luogu.com.cn/problem/U159034) 之后再写题解。**

description:
IOI Park 将有 $n$ 场活动。

这些活动的编号从 $1$ 到 $n$。 活动 $i$ 从时间 $L_i+10^{-1}$ 到时间 $R_i-10^{-1}$ 举行。数据保证 $L_i$ 和 $R_i$ 是整数。

JOI 君决定参加其中的 $k$ 个活动。但是，JOI 君不能在中间加入或离开每个活动。**在两个活动场所间移动的时间忽略不计**。

JOI 君希望参加编号较小的活动。严格来说，JOI 君参加的 $k$ 个活动的编号依次为 $a_1,\cdots,a_k$，其中 $1 \le a_1 < \cdots < a_k \le n$。如果序列 $(a_1, \cdots, a_k)$ 的编号小于 $(b_1, \cdots, b_k)$，当且仅当存在 $j\ (1 \le j \le k)$ 满足在区间 $[1,j-1]$ 里的所有 $l$ 都有 $a_l=b_l$ 和 $a_j<b_j$。

给出每个活动的信息和 JOI 君参加的活动个数 $k$，判断 JOI 君是否可以参加 $k$ 个活动，如果可以，输出所有的 $k$ 个活动的编号。

inputFormat:
第一行，两个正整数 $n,k$。

第 $2 \sim n + 1$ 行，每行 $2$ 个正整数，$L_i, R_i$。

outputFormat:
如果 JOI 君可以参加 $k$ 个活动：
- 输出 $k$ 行。
- 我们设 JOI 君参与的 $k$ 个活动的编号为 $a_1, a_2, \cdots, a_k\ (1\le a_1 < \cdots < a_k \le n）$，你需要在第 $j$ 行输出 $a_j\ (1\le j \le k)$。 请注意，序列 $(a_1, \cdots, a_k)$ 必须是 **最小字典序**。

如果 JOI 君无法参加 $k$ 个活动，输出 $\texttt{-1}$。

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

有 $2$ 种方式可以参加正好 $4$ 个活动。

- 参加 $1, 3, 4, 5$；
- 参加 $2, 3, 4, 5$。

数列 $(1,3,4,5)$ 比数列 $(2, 3, 4, 5)$ 字典序小，所以输出 $1, 3, 4, 5$。

#### 样例 #2 解释

无论怎么选择都不可能正好参加 $3$ 个活动，所以输出 $\tt -1$。

#### 样例 #3 解释

本样例满足所有 Subtask 的条件。

#### 数据规模与约定

**因洛谷限制，本题不予评测每个 Subtask 的第 $1\sim 20$ 个测试点。**

**本题采用 Subtask 计分法。**

| Subtask | 分值占比百分率 | $n$ | $L_i$ |
| :----: | :----: | :----: | :----:|
| $1$ | $7\%$ | / | $L_i \le L_{i+1}\ (1 \le i \le n − 1)$ |
| $2$ | $1\%$ | $\le20$ | / |
| $3$ | $31\%$ | $\le 3 \times 10^3$ |/ |
| $4$ | $61\%$ | / | / |

**注：斜线表示无特殊限制。**

对于 $100\%$ 的数据：
- $1\le n\le 10^5$；
- $1 \le k \le n$；
- $1\le L_i < R_i \le 10^9 (1\le i \le n)$。

#### 说明

本题译自 [第２０回日本情報オリンピック 2020/2021春季トレーニング合宿 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [競技 4 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/2021-sp-d4-notice.pdf) [T1 日文题面](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/event2.pdf)。

tags: 珂朵莉树,颜色段均摊,ODT


title: [JOISC 2021 Day1] フードコート

background: 本题数据保留一部分，请在 [此处](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/foodcourt-data.zip) 获取完整数据。

description:
有 $N$ 家书虫食品店，有 $M$ 个家庭来享受用书虫制作的美味食物。

因为食品店十分火爆，所以顾客需要排队，刚开始所有队列都是空的。

今天食品店又全部开张了，发生了 $Q$ 个事件：

- **加入事件**：编号位于区间 $[L,R]$ 内的所有食品店中，都有编号为 $C$ 的家庭加入队尾，每个满足要求的食品店队尾都加入了 $K$ 个人。
- **离开事件**：编号位于区间 $[L,R]$ 内的所有食品店中，如果队列有超过 $K$ 个人，那么队列的前 $K$ 个人离开队列，否则队列里的所有人离开队列。
- **白嫖事件**：如果编号为 $A$ 的食品店的队列中有大于等于 $B$ 个人，那么食品店就会赠送从队列开头开始数第 $B$ 个人一份秘制书虫，否则店员会吃掉书虫。

求每次 **白嫖事件** 是否有顾客被赠送了秘制书虫，如果有的话，求顾客所在的家庭。

inputFormat:
第一行三个整数 $N,M,Q$ 代表食品店个数，家庭个数和事件个数。

接下来 $Q$ 行，每行首先一个整数 $T$：

- $T=1$，接下来四个整数 $L,R,C,K$ 描述 **加入事件**。
- $T=2$，接下来三个整数 $L,R,K$ 描述 **离开事件**。
- $T=3$，接下来两个整数 $A,B$ 描述 **白嫖事件**。

outputFormat:
对于所有 **白嫖事件**，一行一个整数：

- 如果有顾客被送了秘制书虫，输出他所在的家庭。
- 如果店员吃掉了书虫，输出 $0$。

hint:
#### 样例 1 解释

我们用 $Q_i(a_1,a_2,\cdots,a_k)$ 代表第 $i$ 个食品店的队列，$a_1$ 为队首，$a_k$ 为队尾，其中 $a_i=p$ 就代表第 $i$ 个位置的人来自第 $p$ 个家庭。特殊地，$Q_i()$ 就代表当前队列为空。

根据样例 1 的这几个事件：

- 第 $1$ 个 **加入事件**：

$$Q_1(),Q_2(5,5),Q_3(5,5)$$

- 第 $2$ 个 **加入事件**：

$$Q_1(2,2,2,2),Q_2(5,5,2,2,2,2),Q_3(5,5)$$

- 第 $3$ 个 **白嫖事件**，第 $2$ 个食品店的第 $3$ 个人（第 $2$ 个家庭）被送上秘制书虫。
- 第 $4$ 个 **离开事件**：

$$Q_1(2),Q_2(2,2,2),Q_3()$$

- 第 $5$ 个 **白嫖事件**，第 $1$ 个食品店不够 $2$ 个人，店员会吃掉书虫。
- 第 $6$ 个 **加入事件**：

$$Q_1(2),Q_2(2,2,2,4,4),Q_3(4,4)$$

- 第 $7$ 个 **白嫖事件**，第 $3$ 个食品店的第 $2$ 个人（第 $4$ 个家庭）被送上秘制书虫。

#### 数据规模与约定

**本题采用捆绑测试。**

- Subtask 1（2 pts）：$N,Q \le 2000$，满足性质 A。
- Subtask 2（5 pts）：$N,Q \le 2000$。
- Subtask 3（7 pts）：$N,Q \le 65000$，满足性质 B。
- Subtask 4（21 pts）：$M=1$。
- Subtask 5（15 pts）：$N,Q \le 65000$，满足性质 A。
- Subtask 6（13 pts）：$N,Q \le 65000$，满足性质 C。
- Subtask 7（26 pts）：$N,Q \le 65000$。
- Subtask 8（11 pts）：无特殊限制。

对于 $100\%$ 的数据：

- $1 \le N,M,Q \le 25 \times 10^4$。
- $T \in \{1,2,3\}$。
- 对于所有 **加入事件**，$1 \le L \le R \le N$，$1 \le C \le M$，$1 \le K \le 10^9$。
- 对于所有 **离开事件**，$1 \le L \le R \le N$，$1 \le K \le 10^9$。
- 对于所有 **白嫖事件**，$1 \le A \le N$，$1 \le B \le 10^{15}$。
- 至少有一个 **白嫖事件**。

有以下若干个性质：

- 性质 A：对于所有 **加入事件** 和 **离开事件**，有 $K=1$。
- 性质 B：对于所有 **加入事件**，有 $R-L \le  10$ 和 $K=1$。
- 性质 C：只有 **加入事件** 和 **白嫖事件**。

#### 说明

翻译自 [第２０回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Day1 C フードコート (Food Court) 的英文版本](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/foodcourt-en.pdf)。


title: [省选联考 2021 B 卷] 数对

description: 给定 $n$ 个正整数 $a_i$，请你求出有多少个数对 $(i, j)$ 满足 $1 \le i \le n$，$1 \le j \le n$，$i \ne j$ 且 $a_i$ 是 $a_j$ 的倍数。

inputFormat:
第一行，一个整数 $n$，表示数字个数。
第二行，$n$ 个整数，表示 $a_i$。

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

samples:
见附件中的 pair/pair2.in。
见附件中的 pair/pair2.ans。


title: [省选联考 2021 A 卷] 支配

description:
给定一张 $n$ 个点 $m$ 条边的有向图 $G$，其顶点从 $1$ 到 $n$ 编号。

对于任意两个点 $u, v$，若从顶点 $1$ 出发到达顶点 $v$ 的所有路径都需要经过顶点 $u$，则称顶点 $u$ 支配顶点 $v$。特别地，每个顶点支配其自身。

对于任意一个点 $v$，我们将图中支配顶点 $v$ 的顶点集合称为 $v$ 的受支配集 $D_v$。

现在有 $q$ 次互相独立的询问，每次询问给出一条有向边，请你回答在图 $G$ 中加入该条边后，有多少个顶点的受支配集发生了变化。

inputFormat:
第一行，三个整数 $n, m, q$，分别表示图中的顶点数、边数，以及询问数。
接下来 $m$ 行，每行两个整数 $x_i,y_i$，表示一条有向边从 $x_i$ 到 $y_i$。
接下来 $q$ 行，每行两个整数 $s_i,t_i$，表示每次询问加入的边从 $s_i$ 到 $t_i$。

数据保证给出的图 $G$ 中，从 $1$ 号点出发能到达所有其他点，并且图中不包含重边与自环。

outputFormat: 对于每个询问，输出一行，一个整数，表示答案。

samples:
见附件中的 dominator/dominator2.in。
见附件中的 dominator/dominator2.ans。

samples:
见附件中的 dominator/dominator3.in。
见附件中的 dominator/dominator3.ans。


title: [省选联考 2021 A/B 卷]  宝石

background: **链的部分分官方数据有误。这里已经修改，如仍有误请反馈。**

description:
欧艾大陆上有 $n$ 座城市，城市从 $1 \sim n$ 编号，所有城市经由 $n - 1$ 条无向道路互相连通，即 $n$ 座城市与 $n - 1$ 条道路构成了一棵树。

每座城市的集市上都会出售宝石，总共有 $m$ 种不同的宝石，用 $1 \sim m$ 编号。$i$ 号城市的集市出售的是第 $w_i$ 种宝石，一种宝石可能会在多座城市的集市出售。

K 神有一个宝石收集器。这个宝石收集器能按照顺序收集至多 $c$ 颗宝石，其收集宝石的顺序为：$P_1, P_2, \ldots , P_c$。更具体地，收集器需要先放入第 $P_1$ 种宝石，然后才能再放入第 $P_2$ 种宝石，之后再能放入第 $P_3$ 种宝石，以此类推。其中 $P_1, P_2, \ldots , P_c$ 互不相等。

K 神到达一个城市后，如果该城市的集市上出售的宝石种类和当前收集器中需要放入的种类相同，则他可以在该城市的集市上购买一颗宝石并放入宝石收集器中；否则他只会路过该城市什么都不做。

现在 K 神给了你 $q$ 次询问，每次给出起点 $s_i$ 与终点 $t_i$，他想知道如果从 $s_i$ 号城市出发，沿最短路线走到 $t_i$ 号城市后，他的收集器中最多能收集到几个宝石？（在每次询问中，收集器内初始时没有任何宝石。起点与终点城市集市上的宝石可以尝试被收集）

inputFormat:
第一行，包含三个正整数 $n, m, c$，分别表示城市数，宝石种类数，收集器的容量。
第二行，包含 $c$ 个正整数 $P_i$。数据保证 $1 \le P_i \le m$ 且这些数互不相等。
第三行，包含 $n$ 个正整数 $w_i$，表示每个城市集市上出售的宝石种类。
接下来 $n - 1$ 行，每行两个正整数 $u_i, v_i$，表示一条连接 $u_i$ 和 $v_i$ 号城市的道路。
接下来一行，包含一个正整数 $q$，表示询问次数。
接下来 $q$ 行，每行两个正整数 $s_i, t_i$，表示该次询问的起点与终点。

outputFormat: 按输入顺序输出 $q$ 行，每行一个整数，表示询问的答案。

samples:
见附件中的 gem/gem2.in
见附件中的 gem/gem2.ans

samples:
见附件中的 gem/gem3.in
见附件中的 gem/gem3.ans


title: [省选联考 2021 A/B 卷] 滚榜

description:
封榜是 ICPC 系列竞赛中的一个特色机制。ICPC 竞赛是实时反馈提交结果的程序设计竞赛，参赛选手与场外观众可以通过排行榜实时查看每个参赛队伍的过题数与排名。竞赛的最后一小时会进行“封榜”，即排行榜上将隐藏最后一小时内的提交的结果。赛后通过滚榜环节将最后一小时的结果（即每只队伍最后一小时的过题数）公布。

Alice 围观了一场 ICPC 竞赛的滚榜环节。本次竞赛共有 $n$ 支队伍参赛，队伍从 $1 \sim n$ 编号，$i$ 号队伍在封榜前通过的题数为 $a_i$。排行榜上队伍按照过题数从大到小进行排名，若两支队伍过题数相同，则编号小的队伍排名靠前。

滚榜时主办方以 $b_i$ 不降的顺序依次公布了每支队伍在封榜后的过题数 $b_i$（最终该队伍总过题数为 $a_i + b_i$），并且每公布一支队伍的结果，排行榜上就会实时更新排名。Alice 并不记得队伍被公布的顺序，也不记得最终排行榜上的排名情况，只记得每次公布后，本次被公布结果的队伍都成为了新排行榜上的第一名，以及所有队伍在封榜后一共通过了 $m$ 道题（即 $\sum_{i = 1}^{n} b_i = m$）。

现在 Alice 想请你帮她算算，最终排行榜上队伍的排名情况可能有多少种。

inputFormat:
第一行，包含两个正整数 $n, m$，表示队伍数量与它们封榜后的总过题数。
第二行，包含 $n$ 个正整数，表示 $a_i$。

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


title: [JOISC 2021 Day4] 最悪の記者 4 (Worst Reporter 4)

background: B 太郎不可爱。

description:
B 太郎是一名主要写关于 OI 的报道的记者。再过几天，就要举行 IOI 了，B 太郎决定写一篇关于 IOI 的文章。

比赛将有 $n$ 名选手参加，每位选手的编号从 $1$ 到 $n$。每位选手都有一个 Rating，这是衡量其实力的标准。Rating 用 $1$ 至 $10^9$ 之间的整数表示。

B 太郎采访了每位选手，并获得了以下信息：

- 选手 $i\ (1\le i\le N)$ 的 Rating 大于等于选手 $a_i\ (1\le a_i \le n)$ 的 Rating（$a_i$ 可以等于 $i$）。

在所有的采访结束后，B 太郎从管理 Rating 系统的公司收到了一张表格，上面有每个选手的 Rating。 表上写着以下信息：

- 选手 $i\ (1 \le i \le n)$ 的 Rating 是 $h_i$。

当 B 太郎试图根据这些信息写一篇文章时，他发现每个选手的 Rating 表可能存在错误。

由于临近截止时间，没有时间去弄正确的 Rating 表。因此，B 太郎决定重写表中选手的 Rating，使其与采访中获得的信息不相矛盾。

B 太郎在表中改写选手 $i\ (1\le i \le n)$ 的 Rating 需要 $c_i$ 日元。

也就是说，B 太郎可以通过支付 $c_i$ 日元，将列表中选手 $i$ 的 Rating 更改为 $1$ 到 $10^9$ 之间的任意整数。为了在截止日期前完成任务，B 太郎想要最小化更改列表中 Rating 的总成本。

编写一个程序，给定选手的数量、采访获得的信息、Rating 列表、和更改每个选手 Rating 所用的花费。请你计算不与采访信息矛盾的情况下，最少需要花费多少日元。

inputFormat:
第一行，一个正整数 $n$。

第 $2 \sim n + 1$ 行，每行三个正整数，$a_i,\ h_i,\ c_i$。

outputFormat: 仅一行一个正整数，表示不与采访信息矛盾的情况下，最少需要花费的日元钱数。


title: [省选联考 2021 B 卷] 取模

description: 给定 $n$ 个正整数 $a_i$，请你在其中选出三个数 $i, j, k$（$i \ne j$，$i \ne k$，$j \ne k$），使得 $(a_i + a_j) \bmod a_k$ 的值最大。

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

samples:
见附件中的 mod/mod2.in。
见附件中的 mod/mod2.ans。


title: [JOISC 2021 Day3] ボディーガード

background: 因为数据包过大，所以请在 [此处](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day3/bodyguard-data.zip) 获取完整数据。

description:
在一条数轴上，有 $N$ 个人，他们都是书虫保镖公司的顾客，第 $i$ 个人会在第 $T_i$ 个时刻从第 $A_i$ 个位置移动到第 $B_i$ 个位置，他们的速度是每一个时刻一个单位长度。

如果一个保镖与一个顾客同时在一个位置上，就称保镖在保护这个顾客。设这个保镖从 $a$ 时刻开始保护一个顾客 $i$，从 $b$ 时刻停止保护，那么区间 $[a,b]$ 就称为这个顾客的保护时间，时刻 $a$ 称为保护开始时间，时刻 $b$ 称为保护停止时间。**其中 $a$ 和 $b$ 不必是整数**。特殊地，如果一个保镖与两个顾客同时在一个位置上，保镖只能保护一个顾客。

保镖可以在数轴上以最多每一个时刻一个单位长度最少静止不动的速度随意移动，当保镖停止保护一个顾客的时候，他可以到另一个位置上保护另一个顾客。如果一个保镖保护第 $i$ 个顾客一起走过的路径长度为 $L$，那么顾客 $i$ 将会以 $C_i$ 津巴布韦币每单位长度给这个保镖 $ L \times C_i$ 津巴布韦币作为他的工资。

书虫作为书虫保镖公司的老板，他手里紧握着 $Q$ 份策划保护的方案，其中，第 $j$ 个方案，一个保镖从时刻 $P_j$ 开始从第 $X_j$ 个位置出发开始进行工作。

求对于每个方案，每个保镖获得的总工资数量最多是多少津巴布韦币。

inputFormat:
第一行两个整数 $N,Q$ 代表顾客数和策划保护的方案数。

接下来 $N$ 行每行四个整数 $T_i,A_i,B_i,C_i$ 描述一位顾客。

接下来 $Q$ 行每行两个整数 $P_j,X_j$ 描述一个策划保护的方案。

outputFormat: $Q$ 行每行一个整数代表每个方案保镖会得到的总工资最多是多少津巴布韦币。

hint:
#### 样例 1 解释

- 保护方案 $1$ 中保镖可以按照下面的方式得到 $4+4=8$ 津巴布韦币：
	- 在时刻 $1$ 从 $2$ 位置开始行动。
    - 从时刻 $1$ 到时刻 $2$ 保护顾客 $1$，一起走过的路径长度为 $1$，得到 $4 \times 1=4$ 津巴布韦币。
    - 时刻 $2$ 到时刻 $3$ 停留在 $1$ 位置。
    - 从时刻 $3$ 到时刻 $5$ 保护顾客 $2$，一起走过的路径长度为 $2$，得到 $2 \times 2=4$ 津巴布韦币。
- 保护方案 $2$ 中保镖可以按照下面的方式得到 $2$ 津巴布韦币：
	- 在时刻 $3$ 从 $3$ 位置开始行动。
    - 时刻 $3$ 到时刻 $4$ 从 $3$ 位置移动到 $2$ 位置。
    - 从时刻 $4$ 到时刻 $5$ 保护顾客 $2$，一起走过的路径长度为 $1$，得到 $2 \times 1=2$ 津巴布韦币。

#### 样例 2 解释

- 保护方案 $1$ 中保镖可以按照下面的方式得到 $4+1+8+2=15$ 津巴布韦币：
	- 在时刻 $2$ 从 $2$ 位置开始行动。
    - 时刻 $2$ 到时刻 $2.5$ 从 $2$ 位置移动到 $2.5$ 位置。
    - 从时刻 $2.5$ 到时刻 $3.5$ 保护顾客 $2$，一起走过的路径长度为 $1$，得到 $4 \times 1=4$ 津巴布韦币。
    - 从时刻 $3.5$ 到时刻 $4$ 保护顾客 $1$，一起走过的路径长度为 $0.5$，得到 $2 \times 0.5=1$ 津巴布韦币。
    - 从时刻 $4$ 到时刻 $6$ 保护顾客 $3$，一起走过的路径长度为 $2$，得到 $4 \times 2=8$ 津巴布韦币。
    - 从时刻 $6$ 到时刻 $7$ 保护顾客 $1$，一起走过的路径长度为 $1$，得到 $2 \times 1=2$ 津巴布韦币。
- 保护方案 $2$ 中保镖无论怎么走都得不到工资，只能得到 $0$ 津巴布韦币。

#### 数据规模与约定

**本题采用捆绑测试。**

- Subtask 1（6 pts）：$T_i,A_i,B_i,P_j,X_j \le 3000$。
- Subtask 2（7 pts）：$Q=1$。
- Subtask 3（15 pts）：$Q \le 3000$。
- Subtask 4（20 pts）：$Q \le 4 \times 10^4$。
- Subtask 5（52 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N \le 2800$，$1 \le Q \le 3 \times 10^6$，$1 \le T_i,A_i,B_i,C_i \le 10^9$，$A_i \ne B_i$，$C_i$ 为偶数，$1 \le P_j,X_j \le 10^9$。

#### 说明

翻译自 [第２０回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Day3 B ボディーガード (Bodyguard) 的英文版本](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day3/bodyguard-en.pdf)。


title: [JOISC 2021 Day3] ビーバーの会合 2

background: 原限制 25s & 4096MB，但看起来不需要

description:
给定一棵有 $N$ 个点的树，每一个点上有一个人，这些人要开秘密会议。

假设一次秘密会议有 $P$ 个人参加，这 $P$ 个人分别在第 $p_1,p_2,\cdots,p_P$ 个点上。如果点 $k$ 满足下面这个值最小（$d(a,b)$ 为点 $a$ 到点 $b$ 的距离，$k$ 不需要满足 $k \in \{p_1,p_2,\cdots,p_P\}$）：

$$\sum\limits_{i=1}^Pd(k,p_i)$$

那么就称第 $k$ 个点为可期待的，这场会议的期待值即为所有点中中可期待点的个数。

对于每个 $j \in [1,N]$，求当会议里有 $j$ 个人的时候，会议的期待值的最大值是多少。

inputFormat:
第一行一个整数 $N$ 代表树的点数。

接下来 $N-1$ 行每行两个整数 $A_i,B_i$ 代表一条边。

outputFormat: $N$ 行每行一个整数，第 $j$ 行代表会议有 $j$ 个人时的答案。

hint:
#### 样例 1 解释

下文我们称 $\displaystyle\beta_k=\sum\limits_{i=1}^Pd(k,p_i)$。

拿样例 1 中的树举个例子，假设这一次会议参加者为第 $1$ 个点上的人和第 $3$ 个点上的人，则：

- $P=2$，$p_i=\{1,3\}$。
- $\beta_1=2$。
- $\beta_2=2$。
- $\beta_3=2$。
- $\beta_4=4$。
- $\beta_5=4$。

$\min\limits_{i=1}^5\{\beta_i\}=2$，满足要求的点为 $1,2,3$，该会议的期待值为 $3$。

#### 数据规模与约定

**本题采用捆绑测试。**

- Subtask 1（4 pts）：$N \le 16$。
- Subtask 2（16 pts）：$N \le 4000$。
- Subtask 3（80 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N \le 2 \times 10^5$，$1 \le A_i,B_i \le N$。

#### 说明

翻译自 [第２０回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Day3 C ビーバーの会合 2 (Meetings 2) 的英文版本](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day3/meetings2-en.pdf)。


title: 「MCOI-05」幂积

background:
书虫有 $10^{10}$ 块金牌！

书虫正在整理他的 $n$ 块金牌。他的金牌分四类，依次为：NOI 金牌，IOI 金牌，IMO 金牌，ICPC WF 金牌。他在第 $1$ 到第 $n$ 天中各 AK 了一场比赛，得到以上类金牌之一。对于给定参数 $k$，第 $i$ 天得到的金牌的价值为 $1$ 如果 $k=0$，为 $i$ 如果 $k=1$。

书虫每天会通过奇妙手段选择他当天应该 AK 什么比赛。对于第 $i$ 天，令 $i=p_1\times p_2\times\dots p_k$，其中 $p_1,p_2,\dots,p_k$ 均为质数。书虫会计算 $x$，其中 $x$ 是 $p_1+p_2+\dots+p_k$ 对 $4$ 取模的余数，并且 AK 第 $x+1$ 类比赛，得到一个第 $x+1$ 类比赛的金牌。

书虫的金牌实在太多了，于是他邀请您帮他计算，他这 $n$ 个金牌里，每一类中的**价值**之和。但是书虫不满足于这个，于是他给您 $m$ 和 $k$，请您对每一个 $1\le i\le\lfloor\sqrt m\rfloor$ 计算当 $n=\lfloor\frac mi\rfloor$ 时候的答案。

description:
定义函数 $f(\prod p_i^{a_i})=\sum a_ip_i$，其中 $p_i$ 为质数。特别，$f(1)=0$。

对于 $k\in\{0,1\}$，定义函数 $g$ 为：

$$g(n,k,r)=\sum_{i=1}^ni^k[f(i)\equiv r\pmod 4]$$

给定 $m$ 和 $k$，请对所有 $1\le i\le\lfloor\sqrt m\rfloor$，计算所有 $0\le r<4$ 的 $g(\lfloor\frac mi\rfloor,k,r)$ 值。

inputFormat:
第一行一个正整数 $m$。
第二行一个非负整数 $k$。

outputFormat:
输出 $\lfloor\sqrt m\rfloor$ 行。
第 $i$ 行包含四个非负整数，第 $r$ 非负整数为 $g(\lfloor\frac mi\rfloor,k,r)$。


title: 「Wdsr-2.7」天才⑨与数学递推式

description:
生活在雾之湖的冰精琪露诺，向来以智慧而著称。作为寺子屋的老学员，琪露诺可是对数学递推式了如指掌。

有一天，慧音老师想要考一考琪露诺。于是她写出了一个长度为 $m$ 的递推公式：

$$F_t=\sum_{i=1}^m K_i\times F_{t-i} \quad (t> m)$$

其中 $m,\{K_i\}$ 都是被给定的。不过，由于这个序列 $\{F_i\}$ 的初始 $m$ 项并没有被确定，所以可能存在无穷个满足这个递推式，但是初始 $m$ 项并不一致的递推数列。慧音打算选择其中 $q$ 个 $F$ ，来考考琪露诺对数列知识的掌握。

具体而言，慧音会依次告诉琪露诺，若干个 $\{F_i\}$ 的起始 $m$ 项。显然，这样就能生成无穷序列 $\{F_i\}$ 了。尽管如此，生成这么多序列并不好玩。于是慧音又创造了一个答案序列 $\{A_i\}$ ，满足初始时 $A_i=0$ 。

每当给出一个新的 $\{F_i\}$ ，慧音都要琪露诺使 $\{A_i\}$ 的第 $a,a+1,\cdots b-1,b$ 项分别加上 $F_1,F_2,F_3,\cdots,F_{b-a+1}$ 。

当然，慧音老师不想为难琪露诺，于是对于所有数字，只要输出其对 $p$ 取模的值即可。其中 $p$ 是一个被给定的常数。

---

形式化地讲述题面：给定 $n,q,m,p,\{K_1,K_2,\cdots ,K_m\}$ 。有 $q$ 次操作，每次给定一组 $a,b,\{G_1,G_2\cdots G_m\}$ ，求出无穷序列 $\{F_i\}$ ：

$$F_t=\begin{cases}
G_t & t\le m \cr
\sum_{i=1}^m K_iF_{t-i} & t>m
\end{cases}$$

然后令 $\forall i\in [a,b] ,A_i\gets A_i+F_{i-a+1}$ 。最后分别输出 $\{A_i\}$ 的前 $n$ 项对 $p$ 取模后的结果。

inputFormat:
- 第一行有四个正整数 $n,q,m,p$ ，含义如题面所示。

- 第二行有 $m$ 个整数 $\{K_1,K_2,\cdots ,K_m\}$ ，表示递推式中的系数。

- 接下来 $q$ 行，每行 $2+m$ 个整数 $a,b,\{G_1,G_2,\cdots G_m\}$ ，描述一次操作。

outputFormat: - 共一行， $n$ 个整数，输出 $A_i \bmod p$ 的值。


title: 「Wdsr-2.7」八云蓝自动机 Ⅱ

background:
**注意：本题题意和 八云蓝自动机Ⅰ 并不一致，请仔细阅读**。

作为八云紫的式神，八云蓝有着不同于其他一般式神的强大的计算能力。也就是说，八云蓝可以用自己的心算能力模拟出一台在现世中的确定性状态自动机。通过上一次的练习，八云蓝自动机变得更加强大了。

而这，就是传说中的

$$\textbf{\textsf{「八云蓝自动机$^{\text{plus}}$」}}$$

由于八云蓝自动机通过心算的方式进行运算，因此她还支持一项特异功能，就是一次对一整块数据进行操作。这加强了八云蓝自动机的优越性。

当然，尽管八云蓝的计算能力可以用于模拟一台计算机的操作，但是由于其中并没有设定任何的程序，于是可以实现的功能只能通过学习得到。而作为幻想乡的闲者，八云紫教会了蓝有关于数组的知识。一个数组由若干个存储单元组成，每个单元都可以存储一个整数。

而为了检测这种「八云蓝自动机」的可靠性，紫准备了一条非常简单的模拟题，用于测试蓝的心算能力。

然而，尽管蓝可以很快（ $<10^{-10^{9961}}s$ ）得出结果，但是八云紫实在是懒得去构造标准答案了。因此，你被钦定计算出这条题目的答案。

description:
八云蓝自动机维护了一个长度为 $n$ 的序列 $A$ ，每个元素都有一个初始值。同时自动机会支持以下三种操作：

- $\colorbox{f0f0f0}{\verb!1 l r k!}$ ：将区间 $[l,r]$ 内的所有数字全都变为 $k$ ，即 $A_l\gets k,A_{l+1}\gets k,\cdots ,A_r\gets k$ 。

- $\colorbox{f0f0f0}{\verb!2 x y!}$ ：交换 $A_x$ 与 $A_y$ 的值。

- $\colorbox{f0f0f0}{\verb!3 x!}$ ：查询 $A_x$ 的值。

为了测试八云蓝自动机的效率，紫需要进行非常非常多次的测试。为了生成每个测试的所有操作，紫构造出了一个长度为 $m$ 的**操作序列** $B$ ， $B$ 中的元素就是八云蓝自动机可以执行的一个操作。

设 $\Upsilon(l,r)$ 表示从初始状态开始，依次执行 $B_l,B_{l+1},\cdots B_r$ 操作后，所有操作 $3$ 的结果之和。特别地，如果这些操作中没有操作 $3$ ，那么 $\Upsilon(l,r)=0$ 。

紫会向八云蓝自动机发起 $q$ 次询问，每次给出一组 $(l,r,p)$ ，八云蓝自动机需要计算出

$$\left(\sum_{i=l}^r \Upsilon(i,p)\right) \mod 2^{32}$$

inputFormat:
- 第一行两个整数 $n,m$ ，含义如题面所示。

- 第二行 $n$ 个整数，表示序列 $A$ 的初始值。

- 接下来 $m$ 行，描述操作序列 $B$ 。对于每个操作，首先是一个整数 $op$ 描述操作的种类。

  - 如果 $op = 1$，接下来三个整数 $l,r,k$ ，描述一个操作 $1$ 。

  - 如果 $op = 2$，接下来两个整数 $x,y$ ，描述一个操作 $2$ 。

  - 如果 $op = 3$，接下来一个整数 $x$ ，描述一个操作 $3$ 。

- 接下来一行，一个整数 $q$，表示八云紫发起的询问总数。

- 接下来 $q$ 行，每行有三个整数 $l,r,p$，描述一次询问，具体执行方式如题面所示。

outputFormat: - 共 $q$ 行，每行一个整数，表示此次询问的结果。

hint:
- 本题**有且仅有一个** $\textbf{Subtask}$ 。在本 $\text{Subtask}$ 中，前几组数据满足 $n,m,q \le 5 \times 10^3$，可供检验你的算法的正确性。

- 对于 $100\%$ 的数据，满足：

  - $1 \le n,m,q \le 3 \times 10 ^ 5$。

  - $1 \le a_i,k \le 10^9;1 \le op \le 3;1 \le x,y \le n;x \neq y$。

  - 对于所有操作，$1 \le l \le r \le n$；对于所有查询 $1 \le l \le r \le p \le m$。


title: 「EZEC-10」Equalization

description:
给你一个长为 $n$ 的数组 $a_1,a_2,\ldots,a_n$。

你可以任选三个整数 $l,r,x\ (1\le l\le r\le n$，$x\in \mathbb Z)$，并将 $a_l,a_{l+1},\ldots,a_r$ 均加上 $x$，称为一次操作。

问最少进行几次操作，才能使 $a$ 中所有元素均相等？并求出能使操作次数最少的不同方案数。

由于方案数可能很大，请对 $10^9+7$ 取模。

**两种方案相同，当且仅当两方案每次操作选择的 $(l,r,x)$ 均相同。**

**特别地，不进行任何操作也算一种方案。**

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

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

outputFormat:
第一行一个整数，表示最少操作次数。

第二行一个整数，表示方案数对 $10^9+7$ 取模的结果。

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

一种可行的方案为：$(l,r,x)=(1,1,1),(3,3,-1)$。

**【数据规模与约定】**

**本题采用捆绑测试。**

-  Subtask 1（1 point）：$n=2$。
-  Subtask 2（5 points）：$n=3$。
-  Subtask 3（14 points）：保证 $a$ 单调不升或单调不降。
-  Subtask 4（20 points）：$n\le 10$。
-  Subtask 5（20 points）：$n\le 16$。
-  Subtask 6（40 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le 18$，$-10^9\le a\le 10^9$。


title: [JRKSJ R2] 你的名字。

description: 给你一个长为 $n$ 的序列 $a$，有 $m$ 次查询，每次查询区间 $[l,r]$ 模 $k$ 意义下的最小值。

inputFormat:
第一行两个整数 $n,m$。

第二行 $n$ 个整数表示 $a$。

下面 $m$ 行，每行三个整数 $l,r,k$ 表示一次询问。

outputFormat: 对于每个查询操作，每行输出一个答案。


title: 魔女的茶会

background:
“原来如此，这就是你欲望的根本吗，真有意思呢…”

声音在墓穴中传开来，昴猛然回头，眼前的景象却骤然大变：他的四周由昏黑的墙壁变为了一望无际的草坪，起伏着大大小小的山丘；而原本应该是墓穴入口的地方，却有着一张茶桌和两张座椅，与之一齐处在遮阳伞的荫庇下的，还有一位端坐着的黑衣女子。

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

“我好久没有跟人类对话了，就兴奋了点… 我叫艾姬多娜。「强欲魔女」，这样说比较好懂吧？” 女子浅笑着说道。

“… 这是哪里！？我应该在一个黑暗的遗迹中，你是什么时候把我转移过来的？” 昴咬紧了牙，问道。

“很遗憾，你搞错了。你并不是肉体经历了转移，只是被邀请参加我的茶会而已。”

“茶会…？”

“是魔女的茶会哦。”

**[管理员 Mivik 更改了时间线]**

description:
“那么… 你还准备在那里站多久？趁着茶还没凉赶紧入座吧。”

“可恶… 知道啦知道啦！” 昴走上前去，坐在了魔女对面。桌上除了两杯茶外，还有一副黑白交错的棋盘。

“这是…？” 昴指着棋盘，问道。

“这是魔女棋哦。我请你过来是为了解答我沉思多年都无法解决的一个问题。如果你解决了它，我就会给你和爱蜜莉雅参加试炼的权利… 否则…”令人不安的笑容浮现在魔女脸上，“你可能就会在圣域里无穷地轮回哦…？”

昴出了一身冷汗，战战兢兢地问道：“那么问题是？”

魔女拾起了身边的一个棋子，缓缓说道：“如你所见，这是一张 $n\times n$ 的棋盘，由 $n^2$ 个方格组成，每个方格上最多只能存在一个棋子。**不同于普通的棋盘，这个棋盘是循环的，也就是说，第 $i$ 行 $n$ 列的格子右边是第 $i$ 行 $1$ 列的格子，第 $n$ 行 $i$ 列的格子下面是第 $1$ 行 $i$ 列的格子，以此类推。** 我手中的棋子名叫「大罪司教」，它一步可以向任意斜线方向移动任意多格。一个棋子能一步走到的格子称为其掌控的格子。如果一个棋子掌控了另一个棋子所在的方格，则这种棋盘布局是不稳定的，反之称其为稳定的。现在，请问你能否向棋盘中放入恰好 $m$ 个「大罪司教」，使得整个棋盘布局是稳定的呢？”

![示例](https://cdn.luogu.com.cn/upload/image_hosting/8d8481wr.png)

[上图高清版](https://cdn.luogu.com.cn/upload/image_hosting/np9zk0t4.png)

昴沉思了一会儿，随后在棋盘上操作，很快就完成了魔女的任务，说道：“那么快给我参加试炼的权利吧！”

魔女说：“不行啦… 我还有一个问题没有解决呢…”

昴：“靠北，你耍赖啊！”

魔女没有理会昴，继续说道：“现在问题是，一共有多少种本质不同的稳定的布局方案，使得布局中恰好有 $m$ 个「大罪司教」呢？两种方案本质不同，当且仅当存在任意一格在一种方案中有棋子而在另一种方案中没有哦。”

昴更加生气，因为他不会做了，他转而求助于你。你只需要告诉他答案对 $998244353$ 取模的结果即可。

inputFormat: 一行两个正整数 $n,m$，代表棋盘的大小和你需要放置的棋子数目。

outputFormat: 一行一个正整数，代表答案对 $998244353$ 取模的结果。

hint:
样例一：将一个棋子放入 $1\times1$ 的棋盘中显然只有一种方案。

样例二：一共有以下四种稳定的布局（用 `.` 代表空位，`o` 代表「大罪司教」）：

```plain
oo .o .. o.
.. .o oo o.
```

样例三：所有 $18$ 种稳定的布局可以在 [这里](https://www.luogu.com.cn/paste/obkotkqb) 查看。

### 数据范围

对于全部数据，有 $1\le n<998244353$，$0\le m\le\min\{n,10^7\}$。

Subtask 1 (5 pts)：保证 $m=0$。

Subtask 2 (10 pts)：保证 $m=1$。

Subtask 3 (10 pts)：保证 $1\le n\le 4$。

Subtask 4 (20 pts)：保证 $n$ 是奇数。

Subtask 5 (25 pts)：保证 $n\le 10^7$。

Subtask 6 (30 pts)：无特殊限制。


title: Cytoid

background:
![Welcome to Cytoid!](https://cdn.luogu.com.cn/upload/image_hosting/zzg1blb0.png)

众所周知，尽管很菜，但 colazcy 仍然很喜欢玩 Cytus。

description:
一天，colazcy 又在越级打谱。不到一分钟，colazcy 把手机一摔，骂道：“什么垃圾铺面！” 于是他准备在 Cytoid 上面做一个自制铺恶心别人。

colazcy 准备上一波劲爆 $m$ 押，共有 $n$ 排。也就是说，他的铺面是一个 $n\times m$ 的矩阵，其中每一个位置可以是 Drag 也可以是 Click。colazcy 已经确定了其中一些位置应该是什么元素，但剩下的还没有确定。

但是 colazcy 发现，他铺面对应的矩形如果有一个子矩形中所有元素都是 Drag，那么玩家就可以一直按住糊过去。colazcy 定义一张铺面的简单度为这张铺面对应的矩形中全都是 Drag 的子矩形个数。

现在 colazcy 把他还未完成的铺面给了你，希望你告诉他：如果他等概率随机地把剩下没有决定的元素填成 Drag / Click，最终铺面简单度的期望是多少。不难观察到答案总是一个有理数，你只需要输出这个答案对 $998244353$ 取模的结果。如果你不知道如何将一个有理数对质数取模，可以参考 [有理数取模](https://www.luogu.com.cn/problem/P2613)。

inputFormat:
第一行两个正整数 $n,m$，分别代表矩阵的行数和列数。

接下来 $n$ 行，第 $i$ 行有一个长度为 $m$ 的字符串，其第 $j$ 位为 `o` 代表这个位置被确定为 Drag，为 `x` 代表其被确定为 Click，为 `?` 表示这个位置还没有确定。

outputFormat: 一行一个整数，代表简单度的期望对 $998244353$ 取模的结果。

hint:
### 样例解释

样例一：整个铺面已经确定，而简单度 = 全是 Drag 的子矩阵数目 = $5$。

样例二：只有一个位置没有确定：当这个位置填 Drag 时，简单度为 $9$；当这个位置填 Click 时，简单度为 $5$。则期望简单度为 $\dfrac{9+5}2=7$。

### 数据范围

对于全部数据，有 $1\le n,m\le 100$。

Subtask 1 (15 pts)：保证没有尚未确定的元素（即输入没有 `?`）。

Subtask 2 (15 pts)：保证尚未确定的元素个数 $\le 3$。

Subtask 3 (30 pts)：保证 $n\le 30$。

Subtask 4 (40 pts)：无特殊限制。


title: Shelter

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

> It's a long way forward, so trust in me
>
> I'll give them shelter, like you've done for me
>
> And I know, I'm not alone
>
> You'll be watching over us, until you're gone

description:
在太空里的时间，Rin 除了在虚拟世界里自由创作，每天还会进行一个有趣的小游戏。

最初来到太空时，她的父亲留给她了一个由英文小写字母组成的非空的字符串 $s$，其长度为 $n$。每天，Rin 都会找到一个最大的整数 $i$（$0\le i<|s|$）使得字符串的长度为 $i$ 的前缀与其长度为 $i$ 的后缀相同（注意 $i$ 可能为 $0$），并将这个 前缀 / 后缀 追加在整个字符串的最后面形成新的字符串。例如，当字符串为 `mivikismivik` 时，最大的 $i=5$（字符串长为 $5$ 的前缀后缀皆为 `mivik`），于是 Rin 将 `mivik` 追加在字符串后面形成新字符串 `mivikismivikmivik`。

在太空中度过 $K$ 天后，这个字符串已经变得很长，Rin 突然很好奇这个字符串的长度现在是多少，你能帮帮她吗？由于答案可能很大，你只需要告诉她答案对 $998244353$ 取模的结果即可。

inputFormat:
第一行两个正整数 $n,K$，分别代表最初字符串的长度和 Rin 在太空中度过的天数。

第二行一个长度为 $n$ 的小写英文字母组成的字符串 $s$，代表 Rin 的父亲留给她的字符串。

outputFormat: 一行一个整数，代表 $K$ 天后字符串的长度对 $998244353$ 取模的结果。

hint:
### 样例解释

样例一：操作一次后得到字符串 `abcdabcabc`，长度为 $10$。

样例二：操作一次后得到字符串 `ioioiioi`，再操作一次得到 `ioioiioiioi`，长度为 $11$。

### 数据范围

对于全部数据，有 $1\le n\le 2\cdot 10^6$，$1\le K\le 10^{18}$。

Subtask 1 (15 pts)：保证 $s$ 只由一种字母构成。

Subtask 2 (20 pts)：保证 $s$ 有长度不为 $|s|$ 的整周期（即长度是 $|s|$ 的约数的周期）。

Subtask 3 (65 pts)：无特殊限制。


title: ⎌ Nurture ⎌

background:
![Nurture](https://mivik.gitee.io/image/nurture_wallpaper.jpg)

> "I realized I shouldn't write music with the expectation that the productivity or achievement will fix my problems, but instead with the hope that my honest expression will move people the way music moves me."
>
> — Robinson in a letter to his fans

description:
Mivik 正在听 Nurture，但这时教练走了进来，Mivik 便假装自己在做这道题。

你有一个长度为 $n$ 的序列 $v$，你每次可以 **取出** 两个数 $a,b$，并把 $a-b$ 添加到序列中。重复操作直到序列中只剩下一个数，你需要求出这个数的最大值。

~~（结果教练一眼秒了这水题，Mivik 因没事刷水题被批判了一番）~~

inputFormat:
第一行一个正整数 $n$，代表序列的长度。

第二行 $n$ 个整数，第 $i$ 个整数 $v_i$ 代表序列第 $i$ 项的元素。

outputFormat: 一行一个整数，代表最终剩下的数的最大值。

hint:
### 样例解释

样例一：第一步取出 $1,2$，并把 $1-2=-1$ 添加到序列中，此时序列为 $[3,-1]$；然后取出 $3,-1$，将 $3-(-1)=4$ 添加到序列中，此时序列只剩下一个数 $4$。可以证明不存在使剩下的数更大的操作方式。

### 数据范围

对于全部数据，有 $1\le n\le 3\cdot 10^5$，$|v_i|\le 10^9$。

Subtask 1 (15 pts)：保证 $n\le 3$。

Subtask 2 (30 pts)：保证 $v_i\ge0$。

Subtask 3 (55 pts)：无特殊限制。


title: 「EZEC-8」猜树 加强版

background: 这是一道交互题。

description:
有一棵以 $1$ 为根的 $n$ 个点的有根树，您需要通过若干次询问得到这棵树的结构。

您可以使用两种询问：

1. `? 1 u v` 通过这种询问，您可以获得 $u$ 和 $v$ 之间的距离。
2. `? 2 u` 通过这种询问，您可以获得 $u$ 子树的大小和 $u$ 子树中的所有节点。

请通过使交互库输出不超过 $40000$ 个数，得到这棵树的结构。

### 交互方式

输入树的大小 $n$ 以开始交互。

交互过程中，您可以进行题目描述中的两种询问。

对于第一种询问，交互库将会返回一个非负整数，表示 $u$ 节点和 $v$ 节点间的距离。

对于第二种询问，交互库将会先返回一个正整数 $num$，表示 $u$ 子树的大小。接下来会在同一行中返回 $num$ 个正整数，表示 $u$ 子树中的所有节点（节点顺序会被打乱）。

在您确定答案后，请以 `! fa[2] fa[3] ... fa[n]` 的形式输出一行，停止交互。其中 $fa[i]$ 表示这棵树中 $i$ 号节点的父节点。

在您输出一行后，请清空缓冲区：

- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。
- 在 Pascal 中，使用 `flush(output)`。
- 在 Python 中，使用 `stdout.flush()`。
- 其它语言请自行查阅文档。

inputFormat: 见「交互方式」。

outputFormat: 见「交互方式」。

hint: 对于 $100\%$ 的数据：$2 \leq n \leq 5000$，$1\le u,v\le n$。


title: 「MCOI-05」多宇

description:
Dream 将时空抽象为一颗 $n$ 节点有向有根树，其中树根为节点 $1$ 并且所有边的方向都为浅往深。
Dream 用他的超能力在这颗树上额外添加 $m$ 条有向边，但最终的图仍然是无环图。
Dream 进而将一个事件抽象为图上的一个节点，将一个时代抽象为图上的一个简单路径。
Dream 认为一对事件 $(i,j)$ **可行** 当且仅当存在一个时代，使得时代的首事件是 $i$，末事件是 $j$。
Dream 不满足于统计普通可行对。他认为超能力添加的额外边十分重要。
Dream 认为一对事件 $(i,j)$ **条件可行** 当且仅当 $(i,j)$ 可行并且所有额外边去掉之后 $(i,j)$ 非可行。
Dream 现在有 $q$ 组询问。第 $i$ 组询问用两个正整数 $l_i$ 与 $r_i$ 表示，其中 $l_i\le r_i$。
Dream 想知道，对每一组询问，有多少对 **条件可行** 事件 $(i,j)$，使得 $l\le i<j\le r$。

inputFormat:
第一行两个整数 $n,m$。
接下来一行 $n-1$ 个正整数描述树的结构。第 $i$ 个数代表 $i+1$ 号节点的父亲的编号 $f_i$，也就是说存在一个 $f_i$ 往 $i$ 的一条边。
接下来 $m$ 行，每行两个正整数 $u,v$，表示一条 $u$ 往 $v$ 额外添加的边。
接下来一个正整数 $q$。
接下来 $q$ 行，每行两个正整数 $l,r$，表示一组询问。

outputFormat: 输出 $q$ 行，每行一个整数，表示对应组询问的答案。

hint:
 - Subtask 1（3 pts）：$n,q\le 1000$，3s；
 - Subtask 2（29 pts）：$n,q\le2\times10^5$，$m\le50$，3s；
 - Subtask 3（31 pts）：$m\le 50$，5s；
 - Subtask 4（37 pts）：无额外限制，5s。

对于 $100\%$ 的数据，$2\le n\le7\times10^5$，$1\le q\le3\times10^5$，$0\le m\le100$。


title: 「MCOI-Zero / AC6-M03」 Sipli Field

background:
You've been ordered to start the mission now.

The interception op was a success, enemy air units around Khesed have been weakened, and the Republic of Emmeria's military has taken advantage of this prime opportunity to initiate a counterattack operation with all forces participating.

Enemy forces have established a wide-scale defensive line around Sipli Field, consisting largely of tank battalions.

Our ground forces are set up to cross the river and penetrate it, and eventually gain control of Khesed.

Garuda Team, we need you to support our advancing ground units, and eliminate all enemy forces. Multiple units will be simultaneously carrying out various operations on the ground.

Pay attention to the airspace above each operation area, and provide support as needed.

This must be the first time you've ever participated in a mission of this scale.

The battle simulator is a good way to get some practical experience under your belt.

Godspeed.

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 03} \\\Large\text{Sipli Field}\\\tiny -\textit{ Fortunes of War
 }-$$

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

description:
给定一个 $n$ 个点的树，和两个常数 $L,R$。

请对于每一个点 $u$ 求出有多少条路径过 $u$ 且长度 $d\in [L,R]$。

inputFormat:
第一行三个整数 $n,L,R$。

接下来 $n-1$ 个整数，第 $i$ 个整数 $f_i$ 代表存在一条 $f_i\leftrightarrow i+1$ 的双向边。

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

hint:
样例 1 解释：

- 过 1 的路径：1-2, 1-3, 1-4, 1-5, 2-3, 4-3, 5-3
- 过 2 的路径：2-1, 2-3, 2-4, 2-5, 1-4, 1-5, 3-4, 3-5, 4-5
- 过 3 的路径：3-1, 3-2, 3-4, 3-5
- 过 4 的路径：4-1, 4-2, 4-3, 4-5
- 过 5 的路径：5-1, 5-2, 5-3, 5-4

---

- Subtask 1（3 pts）：$R=1$。
- Subtask 2（7 pts）：$R\leq 2$。
- Subtask 3（10 pts）：$n\leq 100$。
- Subtask 4（10 pts）：$n\leq 2\times 10^3$。
- Subtask 5（15 pts）：$n\leq 10^5,L=1,R=n$。
- Subtask 6（15 pts）：$n\leq 10^5,L=R$。
- Subtask 7（20 pts）：$n\leq 10^5$。
- Subtask 8（20 pts）：无特殊限制。

对于 $100\%$ 的数据，满足 $1\leq n\leq 10^6$，$1\leq L\leq R\leq n$。

idea：\_Solowing\_ClCN，solution：\_Solowing\_ClCN，code：\_Solowing\_ClCN，data：\_Solowing\_ClCN


title: 「Wdsr-2.7」百花齐放的太阳花田

background:
> 春天到来，花儿盛开……只是这次开花比起以往多上许多，甚至所有季节的花都开了。

$$\kern{1pt}\tag*{\small\text{——东方花映冢}}$$

今年的太阳花田，因为各种各样花朵的开放而显得格外热闹。尽管这是一场有关于花的异变，但是太阳花田的主人风见幽香却格外享受由鲜花带来的五彩缤纷的花田——毕竟，向来冷清的花田因为各种妖精的活跃而变得热闹了起来。

幽香非常喜欢这些花朵。每朵花都有它自己的种类，也代表了一种性格。比如向日葵，比如蒲公英，比如天人菊……

奇怪的是，有些花朵可能会属于同一种类，但由于相关因素（比如年龄、营养等），使得每种花都有一个高度。

幽香非常感兴趣，因为这些花朵高高低低形形色色，使得太阳花田呈现出了别样的景色。兴致之余，幽香选取了一些花朵，希望你帮助她解决一个问题。

description:
一开始，幽香选择了太阳花田当中的 $n$ 朵花朵。每朵花有一个高度 $h_i$ ，以及它属于的类别 $t_i$ 。它们排成了一列，并且被标号为 $1,2,3\cdots n$ 。幽香有 $m$ 次操作，分为两种：

- $\colorbox{f0f0f0}{\verb!1 l r x!}$ ：考虑区间 $[l,r]$ 内的所有花朵。我们取出其中所有高度不超过 $x$ 的花朵（即 $h_i\le x$ 的花朵），**依次排列**（即不改变花朵在原序列中的顺序），可以根据它们的种类划分为若干段（比如，$\{\underline{1,}\ \underline{2,2},\underline{1,1},\underline {3,}\ \underline{4,4,4}\}$ 就能分为 $5$ 段）。幽香希望你告诉她一共有多少段。

- $\colorbox{f0f0f0}{\verb!2 x y!}$ ：幽香挑选了一朵高度为 $x$ ，种类为 $y$ 的花朵，拼接在末尾。

**强制在线。**

inputFormat:
- 第一行三个整数 $n,m,k$ 。$n,m$ 含义如上，而 $k$ 为**强制在线参数**。

- 接下来两行，第一行是 $n$ 个整数，表示 $\{h_1,h_2\cdots h_n\}$ ；第三行 $n$ 个整数，表示序列 $t_1,t_2\cdots t_n\}$ 。含义如题所示。

- 接下来 $m$ 行，每行首先一个整数 $op$ ，表示本次操作的种类。

  - 如果 $op = 1$，接下来三个整数 $l',r',x'$，描述一次查询。

  - 如果 $op = 2$，接下来两个整数 $x',y'$，表示一次修改。

- 在所有操作中，真正的 $l,r,x,y$ 都是输入的 $l',r',x',y'$ 异或上 $k \times last$ 后的值。其中， $last$ 表示最后一次查询的答案，初始为 $0$。

outputFormat: - 共有若干行。对于每个操作 $1$ ，每行输出一个整数，表示答案。

hint:
$n'$ 表示进行所有操作后的序列长度。

$$
\def{\arraystretch}{1.5}
\begin{array}{|c|c|c|c|}\hline
\bf{Subtask} & \bm{n',m} & \textsf{\textbf{特殊性质}} & \textsf{\textbf{分值}} \cr\hline
1 & 1\le n',m \le 10^3 & \text{无} & 10 \cr\hline
2 & 1\le n',m \le 3\times 10^5 & k=0 & 20\cr\hline
3 & 1\le n',m \le 3\times 10^5 & l=1 & 25\cr\hline
4 & 1\le n',m \le 10^5 & \text{无} & 15\cr\hline
5 & 1\le n',m \le 3\times 10^5 & \text{无} & 20\cr\hline
6 & \text{无特殊限制} & \text{时限 3s，空限 300MB} & 10\cr\hline
\end{array}$$

- 对于 $100\%$ 的数据：

   $1 \le n',m \le 5 \times 10 ^ 5$。

   $1 \le h_i,t_i,x,y \le 10^9$，$1 \le l \le r \le n'$。

   $1 \le op \le 2$，$0 \le k \le 10^3$。

提示：请注意常数优化。


title: 「Wdsr-2.7」八云蓝自动机 Ⅰ

background:
**注意：本题题意和 八云蓝自动机Ⅱ 并不一致，请仔细阅读**。

作为八云紫的式神，八云蓝有着不同于其他一般式神的强大的计算能力。也就是说，八云蓝可以用自己的心算能力模拟出一台在现世中的确定性状态自动机。

而这，就是传说中的

$$\textbf{\textsf{「八云蓝自动机」}}$$

当然，尽管八云蓝的计算能力可以用于模拟一台计算机的操作，但是由于其中并没有设定任何的程序，于是可以实现的功能只能通过学习得到。而作为幻想乡的闲者，八云紫教会了蓝有关于数组的知识。一个数组由若干个存储单元组成，每个单元都可以存储一个整数。

而为了检测这种「八云蓝自动机」的可靠性，紫准备了一条非常简单的模拟题，用于测试蓝的心算能力。

然而，尽管蓝可以很快（ $<10^{-9961}s$ ）得出结果，但是八云紫实在是懒得去构造标准答案了。因此，你被钦定计算出这条题目的答案。

description:
八云蓝自动机维护了一个长度为 $n$ 的序列 $A$ ，每个元素都有一个初始值。同时自动机会支持以下三种操作：

- $\colorbox{f0f0f0}{\verb!1 x k!}$ ：将 $A_x$ 的值修改为 $k$。

- $\colorbox{f0f0f0}{\verb!2 x y!}$ ：交换 $A_x$ 与 $A_y$ 的值。

- $\colorbox{f0f0f0}{\verb!3 x!}$ ：查询 $A_x$ 的值。

为了测试八云蓝自动机的效率，紫需要进行非常非常多次的测试。为了生成每个测试的所有操作，紫构造出了一个长度为 $m$ 的**操作序列** $B$ ， $B$ 中的元素就是八云蓝自动机可以执行的一个操作。

紫会向蓝发起一共 $q$ 次测试。每次测试，紫会给出一个二元组 $(l,r)$ ，含义是让八云蓝自动机**依次**执行 $B_l,B_{l+1},\cdots B_r$ 这一共 $(r-l+1)$ 个操作。当然，紫不希望自动机的输出会太长，于是对于每次测试，你只要告诉她这些操作中所有操作 $3$ 的结果之和即可。注意：任意两次测试并**不会互相干扰**，每次操作结束后数列 $A$ 会回到初始状态。

此外，紫不希望用非常非常大的数字刁难你，于是答案对 $2^{32}$ 取模就行了（即 $\text{unsigned int}$ 自然溢出）。

inputFormat:
- 第一行两个整数 $n,m$ ，含义如题面所示。

- 第二行 $n$ 个整数，表示序列 $A$ 的初始值。

- 接下来 $m$ 行，描述操作序列 $B$ 。对于每个操作，首先是一个整数 $op$ 描述操作的种类。

  - 如果 $op = 1$，接下来两个整数 $x,k$ ，描述一个操作 $1$ 。

  - 如果 $op = 2$，接下来两个整数 $x,y$ ，描述一个操作 $2$ 。

  - 如果 $op = 3$，接下来一个整数 $x$ ，描述一个操作 $3$ 。

- 接下来一行，一个整数 $q$，表示八云紫发起的测试总数。

- 接下来 $q$ 行，每行有两个整数 $l,r$，描述一次测试，具体的执行方式如题面所示。

outputFormat: - 共 $q$ 行，每行一个整数，表示此次测试的结果。

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

$$\def{\arraystretch}{1.5}\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n,m,q} & \textbf{特殊性质} & \textbf{分值}\cr\hline
1 & 1\le n,m,q\le 10^3 & \text{无} & 10 \cr\hline
2 & \text{无特殊限制} & \text{无操作 1} & 20\cr\hline
3 & \text{无特殊限制} & \text{无操作 2} & 20\cr\hline
4 & \text{无特殊限制} & \text{操作 3 次数}\le 10 & 20 \cr\hline
5 & \text{无特殊限制}& \text{无}& 30 \cr\hline
\end{array}$$

- 对于 $100\%$ 的数据，满足：

  - $1 \le n,m,q \le 2 \times 10 ^ 5$ 。

  - $1 \le a_i,k \le 10^9;1 \le op \le 3;1 \le x,y \le n;x \neq y $ 。

  - $1 \le l \le r \le m$ 。


title: 「MCOI-05」追杀

description:
Dream SMP 具有 $m$ 位玩家，编号为 $1$ 至 $m$。初始时，每一位玩家生命数量为 $3$。一位玩家 **公认活着**（canonically alive） 当且仅当生命值非零。

Dream SMP 经常发生大型战争，于是会有玩家杀（PvP）别的玩家。对于活着玩家 $u$ 与 $v$，如果 $u$ 杀 $v$，$v$ 的生命数量扣除一次。注意，如果 $u$ 或 $v$ 不为公认活着，杀没有影响。

总共按时序记录了 $n$ 次追杀 $1,2,\dots,n$，其中第 $k$ 次追杀为 $u_k$ 杀 $v_k$。

DreamXD（玩家 $0$）解锁了时空穿越超能力。他现在可以选取任何 $i,v$ 使得 $1\le i\le n+1$ 并且 $1\le v\le m$，穿越到第 $i-1$ 次追杀之后与第 $i$ 次追杀之前，并追杀玩家 $v$。$i=n+1$ 表示穿越到第 $n$ 次追杀后。

不同 $i$ 和 $v$ 可能导致最终活着玩家集合不同。对于每一个 $x$ 使得 $0\le x\le m$，DreamXD 想知道，有多少种 $i,v$ 使最后公认活着玩家集合恰好含有 $x$ 位玩家？

inputFormat:
第一行两个正整数 $n,m$。
接下来 $n$ 行，第 $k$ 行两个正整数 $u_k,v_k$，表示在第 $k$ 时刻，$u_k$ 追杀 $v_k$。

outputFormat: 输出一行 $m+1$ 个正整数，其中第 $x$ 个为最终有 $x-1$ 位玩家活（不包含 Dream）的方案数。

hint:
#### 样例 2 解释

本样例对应 Dream SMP 当前（4/26/2021) 情况，仅包含公认死亡，即对应剧本，的次数：

 - Aug 2, 2020: Tommy killed by Dream
 - Aug 2, 2020: Fundy killed by George
 - Aug 2, 2020: Wilbur killed by Punz
 - Aug 2, 2020: Tubbo killed by Sapnap
 - Aug 2, 2020: Tommy killed by Dream
 - Sep 2, 2020: Wilbur killed by Punz
 - Oct 16, 2020: Tubbo killed by Techno
 - Oct 16, 2020: Schlatt killed by Techno
 - Oct 17, 2020: Schlatt killed by Quackity
 - Nov 16, 2020: Wilbur killed by Philza
 - Nov 16, 2020: Schlatt killed by Schlatt
 - Dec 6, 2020: Karl killed by Karl
 - Dec 14, 2020: Mexican Dream killed by Natural Causes
 - Dec 14, 2020: Mexican Dream killed by Natural Causes
 - Dec 14, 2020: Mexican Dream killed by Dream
 - Dec 16, 2020: Quackity killed by Techno
 - Jan 20, 2021: Dream killed by Tommy
 - Jan 20, 2021: Dream killed by Tommy
 - Mar 1, 2021: Tommy killed by Dream
 - Mar 12, 2021: Connor killed by Ranboo
 - Mar 23, 2021: Ponk killed by Sam
 - Apr 18, 2021: Skeppy killed by Bad
 - Apr 26, 2021: Foolish killed by Bad

**本题采用捆绑测试。**

 - Subtask 1（5 pts）：$n\le5$，$m=1$。
 - Subtask 2（11 pts）：$n,m\le100$。
 - Subtask 3（41 pts）：$n\le10^3$。
 - Subtask 4（43 pts）：没有特殊限制。

对于 $100\%$ 的数据，$1\le n\le6\times10^4$，$1\le m\le10^3$，$1\le u_i,v_i\le m$。


title: 「MCOI-Zero / AC6-M14」Gracemeria Patrol

background:
「Talisman，一会你能不能和 Avalanche 一起出去而不是我？」

「我今晚想一个人静静。」

「我的妻女都死了。
　刚刚确认的……」

 「我保护了我的国家，
　但我却守护不了我的家庭。」

  「什么样的王牌
　连自己的家庭都保护不了？」

 「Monica……
　还有 Jessica……」

**「How could I let this happen！！」**

 「这个任务结束之后，
　我将离开空军。」

  「我受够了。
　我没有继续飞行的理由了。」

 ……

「一个不明物体正在高速飞行
　在东北方。」

「这是战机？在这个时候？！」

「在雷达上确认未知物体，
　这不是战机，它的速度太快了！」

「未知物体在雷达上消失了。
　等一下……」

「一些物体在相同的方向上飞行。我认为这是……」

「我看到了，这些是导弹！」

「Ghost Eye，
　我们遭到巡航导弹袭击了！」

「全机，拦截那些巡航导弹！
　保护我们的城市！」

……

「资料检查……
　增援的隐形飞机正在接近。」

「这些人不懂得放弃吗？」

『我们为了你而回来了，Emmeria！』

「这些人到底是怎么了？还觉得死的人不够多吗？！」

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 14} \\\Large\text{Gracemeria Patrol}\\\tiny -\textit{ City Lights }-$$

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

description:
给定一个 $n\times m$ 的 01 矩阵，每一次操作可以改变一个位置以及其上面、左边、右边的值。如果原值是 $0$，则改变之后变成 $1$；否则变成 $0$。

例如下面矩阵在改变中括号表明的位置之后的形态：

$$\begin{bmatrix}0&1&0&1&1\\1&0&[0]&1&0\\0&0&0&0&1\end{bmatrix}\rightarrow \begin{bmatrix}0&1&1&1&1\\1&1&1&0&0\\0&0&0&0&1\end{bmatrix}$$

**特别的，如果操作点在边界上，那么仅改变未超出边界的部分。**

现给定 $q$ 组询问，每组询问一个区间 $[l,r]$ 和一个常数 $k$，请你对行号在 $l,r$ 内的 01 子矩阵求出通过选出一些位置进行一次操作使其变为全 $0$ 的方案中，第 $k$ 行被操作了几次。

特别的，如果没有或者有多种选择操作位置的方法，输出 $-1$。

询问之间相互独立。

inputFormat:
第一行三个整数 $n,m,q$。

接下来 $n$ 行，每行 $m$ 个字符，给出 01 矩阵。

接下来 $q$ 行，每行三个整数表示询问的 $l,r,k$。

outputFormat: $q$ 行，每行一个整数表示对应询问的答案。

hint:
- Subtask 1（10 pts）：$n,m\leq 3,q\leq 10$。
- Subtask 2（20 pts）：$n,m,q\leq 10$。
- Subtask 3（20 pts）：$n,q\leq 50,m\leq 10$。
- Subtask 4（20 pts）：$n,q\leq 10^4,m\leq 10$。
- Subtask 5（30 pts）：无特殊限制。

对于 $100\%$ 的数据，满足 $1\leq n\leq 5\times 10^4$，$1\leq m\leq 50$，$1\leq q\leq 5\times 10^5$，$1\leq l\leq k\leq r\leq n$。

idea：Sol1，solution：Sol1 & ethan\_zhou，code：Sol1，data：Sol1

---

 「Talisman……」

 「一个天使不会交出它的翅膀除非
　跳完最后一支舞，对不对？」


title: 「Wdoi-3」夜雀 cooking

background:
**本题为交互题。**

作为幻想乡的大厨，米斯蒂娅当然能用准备的食材制作出各色各样的饭菜。晚上，就是夜雀餐厅营业的时间，凭着这些料理，餐厅总是生意兴隆——甚至一些「特殊顾客」也会前来！

特殊顾客就是一些幻想乡里大家再熟悉不过的角色啦，顾名思义，她们会提出特殊要求，不过如果满足了她们的要求，她们也会好好地奖励小夜雀。

不幸的是，紫决定做一个恶作剧，她悄悄使用能力清除了米斯蒂娅的部分记忆，现在她分不清哪些顾客是特殊顾客，哪些顾客是普通顾客了！看着米斯蒂娅快要哭了，于心不忍的紫决定和米斯蒂娅做一个数学游戏，她将特殊顾客的编号隐藏在了数字之中。米斯蒂娅对数学一窍不通，于是她只能向你求助了......

description:
紫给出了一个长度为 $n$ 的数列，其第 $i$ 项就对应了编号为 $i$ 的顾客。她将所有普通顾客对应的位置染上蓝色，把特殊顾客对应的位置染上紫色。紫告诉了米斯蒂娅特殊顾客一共有 $m$ 位。并且，由于特殊顾客非常的特殊，所以紫色位置数量很少，而且**基本均匀随机**。

接下来，她给数列的每一项赋上了值。第 $i$ 项的值 $a_i$ 可以用如下的式子推出：（$s$ 和 $k$ 紫都会给出）
  $$a_i=\begin{cases} s & i=1\cr a_{i-1}+k & i>1\end{cases}$$

米斯蒂娅可以向紫提出形如 `l r` 的问题，然后紫就会迅速算出区间 $[l,r]$ 内所有被染成蓝色位置的 $a_i$ 的和。当然啦，你需要输出 `l r` 来告诉米斯蒂娅她该如何提问，如果你成功找出了所有特殊顾客的编号（即所有紫色点的位置），那么你需要输出 `-1 p1 p2 ... pm` 来告诉米斯蒂娅所有特殊顾客的编号，注意要保证 $p_i\le p_{i+1}(1\le i<m)$。

**注意：在进行这两种操作后，需要刷新缓存区，下面是一些常见语言的刷新缓存区方式：**

- C++：`fflush(stdout)` 或 `cout.flush()`。
- C: `fflush(stdout)`。
- Java: `System.out.flush()`。
- Python: `stdout.flush()`。
- Pascal: `flush(output)`。
- 其他语言：请参考对应语言的帮助文档。

inputFormat:
**本题有多组数据。**

第一行是一个正整数 $T$，表示数据组数。

接下来进行每组数据。首先夜雀会传达紫所说的信息，也就是 $n,m,s,k$ 的值，接着你可以发起若干次询问，直到你告诉了米斯蒂娅所有特殊顾客的编号。此时该组数据结束，进入到下一组。

outputFormat:
输出若干行。你可以向标准输出中发起询问来得到米斯蒂娅的回答。

**注意：** 如果你在询问过程中出了问题（包括但不限于询问次数过多，询问越界等），此时米斯蒂娅会告诉你 $-1$（代表紫不想理她了）。此时你应立即停止，否则可能会出现奇怪的状况。

hint:
#### 样例解释

神秘顾客的编号为 $\{4,7,10,11\}$ 。这个样例象征性地抽取了 $3$ 个询问，以便选手理解交互的过程。

- 对于第一次询问 $[10,12]$ ，结果为 $13=13$。
- 对于第二次询问 $[2,7]$ ，结果为 $3+4+6+7=20$。
- 对于第三次询问 $[4,8]$ ，结果为 $6+7+9=22$。

---

#### 数据范围及约定

$$\def{\arraystretch}{1.8}
\begin{array}{|c|c|c|}\hline
\textbf{Subtask} & \textbf{特殊性质} & \textbf{分值} \cr\hline
1 & m=1 & 5 \cr\hline
2 & - & 95 \cr\hline
\end{array}$$

- 对于所有数据，满足 $1\le T\le 500$，$1 \leq \sum n_i \leq 10^5$，$1 \leq \sum m_i \leq \min\{ n,100\}$，$1\le s,k\le 10^9$。

每一个 Subtask 的得分为当前 Subtask 所有测试点的最低分。

#### 判分方式

令 $q_i$ 为对于第 $i$ 组数据你所用的询问次数，你需要满足 $\sum q_i \leq 200 \times T$ ，并且每组询问的结果都是正确的，你才能获得该测试点的满分。

- 如果询问次数满足 $1000 \times T<\sum q_i \leq 2000 \times T$，可以拿到 $20\%$ 的分数。
- 如果询问次数满足 $600 \times T<\sum q_i \leq 1000 \times T$，可以拿到 $40\%$ 的分数。
- 如果询问次数满足 $400 \times T<\sum q_i \leq 600 \times T$，可以拿到 $50\%$ 的分数。
- 如果询问次数满足 $300 \times T<\sum q_i \leq 400 \times T$，可以拿到 $60\%$ 的分数。
- 如果询问次数满足 $200 \times T<\sum q_i \leq 300 \times T$，可以拿到 $80\%$ 的分数。

#### 说明

选择 $m$ 个点染为紫色的生成方式是对一个 $1 \sim n$ 的排列调用 `random_shuffle`，然后取前 $m$ 项的数值作为特殊顾客的编号。一个可被参考的代码如下：

```cpp
namespace Gen{
	typedef unsigned int       u32;
	typedef unsigned long long u64;
	u32 MT[624],idx;
	void iit(u32 seed){
    	MT[0]=seed; idx=0; for(u32 i = 1;i < 624;++ i)
    	MT[i]=(0x6c078965U * (MT[i - 1] ^ ((MT[i - 1]) >> 30)) + i);
	}
	void gen(){
		u32 x; for(u32 i = 0;i < 624; ++ i){
			x = (MT[i] & 0x80000000U) +
				(MT[(i + 1) % 624] & 0x7fffffffU );
			MT[i] = MT[(i + 397) % 624] ^ (x >> 1);
			if(x & 1) MT[i] ^= 0x9908b0dfU;
		}
	}
	u32  clc(){
		if(!idx) gen(); u32 x = MT[idx];
		x ^= x >> 11, x ^= (x << 7) & 0x9d2c5680U;
		x ^= (x << 15) & 0xefc60000U,x ^= x >> 18;
		idx = (idx + 1) % 624; return x;
	}
	u32  clc(u32 n){	//均匀随机地返回 [0,n) 内的整数
		return 1ull * n * clc() >> 32;
	}
	void sfl(int n, int *A) {
		for(int i = n;i >= 1; --i) swap(A[clc(i) + 1], A[i]);
	}
	void gen(u32 seed,int n, int *A) {
		iit(seed); for(int i = 1;i <= n; ++i) A[i] = i; sfl(n, A);
	}
}
```

**注**：该代码片段会使用符合标准的梅森旋转算法生成随机数。其生成随机数的周期为 $2^{19937}-1$ ，生成的随机数是均匀随机的。因此你大可不必担心我们在里面做了任何手脚。

调用 `gen(seed,n,A)` 可以生成一个长度为 $n$ 的**基本均匀随机**序列，我们将会取其前 $m$ 项作为特殊顾客的编号。例如，对于样例，我们调用了 `gen(9961U,12,A)` ，并选取了 $A$ 的前 $4$ 项 $\{4,7,10,11\}$ 作为神秘顾客的编号。


title: 「Wdsr-2.7」文文的摄影布置

background:
作为幻想乡知名的记者射命丸文，文文常常需要为文文新闻采集相关的照片素材。

具体而言，文文会采集一大串的图片，用于为新的一期报纸提供图片。作为一份简短的快报，文文会从素材库中使用**三张**图片，第一张放在开头，第三张放在结尾，用于激发读者的阅读兴趣（毕竟，报纸的开头和结尾是最容易被看到的）；第二张，则是为了帮助读者理解相关内容。

可是作为无双风神，文文收集的照片实在是太多了，以至于一时半会儿处理不过来。按照惯例，文文找到了在一旁吃瓜的你，希望你能帮她解决困难。

description:
尽管图片非常多，但幸运的是，文文已经将它们排成了一列，从左到右分别编号为 $1 \sim n$，文文选取的三张图片，**应该是一个长度为 $\bf 3$ 的子序列**。（不妨设选取的照片的序号为 $i,j,k$ ，则必须要有 $i<j<k$ ）。

此外，文文给每张照片定了一个**吸引度** $A_i$ 与**大小** $B_i$ 。

因为报纸版面太大会降低读者的兴趣，于是选定两张照片 $i,k$ 后，规定必须选择最小的 $B_j$。

形式化地说，规定 $\psi(i,k) = A_i + A_k - \min(B_j)$，其中需要满足 $i < j < k$。

摸清了照片价值的计算，文文会告诉你共 $m$ 个操作，可以分为以下三种：

- $\colorbox{f0f0f0}{\verb!1 x y!}$ ：照片的吸引度发生变化。文文要将 $A_x$ 修改为 $y$ 。

- $\colorbox{f0f0f0}{\verb!2 x y!}$ ：照片的大小发生变化。文文要将 $B_x$ 修改为 $y$ 。

- $\colorbox{f0f0f0}{\verb!3 l r!}$ ：文文打算利用素材库的第 $l$ 到第 $r$ 张中的图片，你要告诉她 $\psi(x,y)$ 的**最大值**（ $l\le x\le x+1<y \le r$ ）。

inputFormat:
第一行两个整数 $n,m$，分别表示照片数量和操作次数。

第二行 $n$ 个整数，表示序列 $A$，描述每张照片的吸引度。

第三行 $n$ 个整数，表示序列 $B$，描述每张照片的大小。

接下来 $m$ 行，每行描述一个操作，格式如上所述。

outputFormat: 对于每个操作三，输出一行一个整数，表示答案。

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

$$\def{\arraystretch}{1.5}\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n,m} & \textbf{特殊性质} & \textbf{分值}\cr\hline
1 & 1\le n,m\le 300 & \text{无} & 10\cr\hline
2 & 1\le n,m\le 5\times 10^3 & \text{无} & 20\cr\hline
3 & 1\le n,m\le 5\times 10^5 & \text{仅有操作 3} & 20\cr\hline
4 & 1\le n,m\le 10^5 & \text{无} & 20\cr\hline
5 & \text{无特殊限制} & \text{无} & 30\cr\hline
\end{array}$$

- 对于 $100\%$ 的数据：

   $1 \le n,m \le 5 \times 10^5$。

   $1 \leq A_i,B_i,y \leq 10^8$，$1 \le x \le n$，$1 \le l \le r \le n$。

   保证 $r-l+1 \geq 3$，即询问的区间长度大于等于 $3$


title: [Ynoi2003] 樋口円香

description:
给定两个序列 $a_1,\dots,a_n$，$b_1,\dots,b_n$，一开始 $b_i=0$；

你需要进行 $m$ 次操作：

每次操作，给出 $l,r,L$，需要对于$k\in[l,r]$，将 $b_{L+k-l}$ 增加 $a_k$；

最后输出经过所有操作后的序列 $b_1,\dots,b_n$。

inputFormat:
第一行一个整数 $n$；

第二行 $n$ 个整数 $a_1,\dots,a_n$；

第三行一个整数 $m$；

之后 $m$ 行每行三个整数 $l\;r\;L$，表示一个询问。

outputFormat: 输出 $n$ 行，表示操作后的 $b_1,\dots,b_n$。

hint:
Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据满足 $0\le a_i\le 1000$；$1\le n\le 10^5$；$1\le m\le 10^6$。


title: [USACO21OPEN] United Cows of Farmer John G

description:
农夫约翰合牛国（The United Cows of Farmer John，UCFJ）将要选派一个代表队参加国际牛学奥林匹克（International bOvine olympIad，IOI）。

有 $N$
头奶牛参加了代表队选拔。她们站成一行，奶牛 $i$ 的品种为 $b_i$。

代表队将会由包含至少两头奶牛的连续区间组成——也就是说，对于满足 $1\le l<r\le N$
的奶牛 $l\dots r$。最边上的奶牛会被指定为**领队**。为了避免种内冲突，每一名领队都必须与代表队的其他成员（**包括领队**）品种不同。

请帮助 UCFJ 求出他们可以选派参加 IOI 的代表队的方法数。

inputFormat:
输入的第一行包含 $N$。

第二行包含 $N$ 个整数 $b_1,b_2,\dots,b_N$，均在范围 $[1,N]$ 之间。

outputFormat: 输出一行表示可能的代表队的数量。


title: [USACO21OPEN] Portals G

description:
Bessie 位于一个由 $N$ 个编号为 $1\dots N$ 的结点以及 $2N$ 个编号为 $1\cdots 2N$ 的传送门所组成的网络中。每个传送门连接两个不同的结点 $u$ 和 $v$（$u≠v$）。可能有多个传送门连接同一对结点。

每个结点 $v$ 与四个不同的传送门相连。与 $v$ 相连的传送门列表由 $p_v=[p_{v,1},p_{v,2},p_{v,3},p_{v,4}]$ 给出。

你的当前位置可以用有序对（当前结点，当前传送门）表示；即一个有序对 $(v,p_{v,i})$
，其中 $1\le v\le N$ 以及 $1\le i\le 4$。你可以使用以下任一操作来改变你的当前位置：

- 1. 由穿过当前传送门来改变当前结点。
- 2. 改变当前传送门。在每一个结点上，列表的前两个传送门是配对的，后两个传送门也是配对的。也就是说，如果你的当前位置是 $(v,p_{v,2})$，你可以转而使用传送门 $(v,p_{v,1})$，反之亦然。类似地，如果你的当前位置是 $(v,p_{v,3})$，你可以转而使用传送门 $(v,p_{v,4})$，反之亦然。没有其他改变传送门的方式（例如，你**不能**从传送门 $p_{v,2}$ 转去传送门 $p_{v,4}$ ）。

总共有 $4N$ 个不同的位置。不幸的是，并不一定每一个位置都可以从另外的每一个位置经过一系列操作而到达。所以，以 $c_v$ 哞尼的代价，你可以以任意顺序重新排列与 $v$ 相邻的传送门列表。在此之后，列表中的前两个传送门互相配对，同时后两个传送门也互相配对。

例如，如果你将与 $v$ 相邻的传送门以 $[p_{v,3},p_{v,1},p_{v,2},p_{v,4}]$ 的顺序重新排列，这意味着如果你位于结点 $v$ ，
- 如果你当前位于传送门 $p_{v,1}$ ，你可以转而使用传送门 $p_{v,3}$，反之亦然。
- 如果你当前位于传送门 $p_{v,2}$ ，你可以转而使用传送门 $p_{v,4}$，反之亦然。
你不再能够从传送门 $p_{v,1}$
转至传送门 $p_{v,2}$，或从传送门 $p_{v,3}$ 转至 $p_{v,4}$ ，反之亦然。

计算修改这一网络使得每一个位置都可以从另外的每一个位置到达所需要花费的哞尼的最小数量。输入保证存在至少一种修改网络的合法方式。

inputFormat:
输入的第一行包含 $N$。

以下 $N$ 行每行描述一个结点。第 $v+1$ 行包含五个空格分隔的整数 $c_v,p_{v,1},p_{v,2},p_{v,3},p_{v,4}$。

输入保证对于每一个 $v$ ，$p_{v,1},p_{v,2},p_{v,3},p_{v,4}$ 各不相同，且每个传送门出现在**恰好两个结点**的邻接表中。

outputFormat: 输出一行，包含修改这一网络使得每一个位置都可以从另外的每一个位置到达所需要花费的哞尼的最小数量。


title: [USACO21OPEN] Permutation G

description:
Bessie 在二维平面上有 $N$ 个最爱的不同的点，其中任意三点均不共线。对于每一个 $1\le i\le N$，第 $i$ 个点可以用两个整数 $x_i$ 和 $y_i$ 表示。

Bessie 按如下方式在这些点之间画一些线段：

- 1. 她选择这 $N$ 个点的某个排列 $p_1,p_2,\dots,p_N$ 。
- 2. 她在点 $p_1$ 和 $p_2$ 、$p_2$ 和 $p_3$、$p_3$ 和 $p_1$ 之间画上线段。
- 3. 然后依次对于从 $4$ 到 $N$ 的每个整数 $i$，对于所有 $j<i$，她从 $p_i$ 到 $p_j$ 画上一条线段，只要这条线段不与任何已经画上的线段相交（端点位置相交除外）。

Bessie 注意到对于每一个 $i$ ，她都画上了恰好三条新的线段。计算 Bessie 在第 $1$ 步可以选择的满足上述性质的排列的数量，结果对 $10^9+7$ 取模。

inputFormat:
输入的第一行包含 $N$。

以下 $N$ 行，每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。

outputFormat: 输出一行一个整数表示方案数对 $10^9+7$ 取模后的结果。

hint:
#### 样例一解释

没有排列满足该性质

#### 样例二解释

所有排列均满足该性质

#### 样例解释三

一个满足该性质的排列为 $(0,0),(0,4),(4,0),(1,2),(1,1)$ 。对于这个排列，

- 首先，她在 $(0,0),(0,4)$ 和 $(4,0)$ 两两之间画上线段。
- 然后她从 $(1,2)$ 向 $(0,0)$ ，$(0,4)$ 和 $(4,0)$ 画上线段。
- 最后，她从 $(1,1)$ 向 $(1,2)$ ，$(4,0)$ 和 $(0,0)$ 画上线段。

![](http://usaco.org/current/data/fig_permutation_gold_open21.png)

### 数据范围与约定

$3\le N \le 40$，$0\le x_i,y_i \le 10^4$


title: [USACO21OPEN] United Cows of Farmer John P

description:
农夫约翰合牛国（The United Cows of Farmer John，UCFJ）将要选派一个代表队参加国际牛学奥林匹克（International bOvine olympIad，IOI）。

有 $N$ 头奶牛参加了代表队选拔。她们站成一行，奶牛 $i$ 的品种为 $b_i$。

代表队将会由包含至少三头奶牛的连续区间组成——也就是说，对于满足 $1\le l<r\le N$ 且 $r−l\ge 2$ 的奶牛
$l\dots r$。选定区间内的三头奶牛将会被指定为领队。出于法律原因，最边上的两头奶牛必须是领队。此外，为了避免种内冲突，每一名领队都必须与代表队的其他成员（包括领队）品种不同。

请帮助 UCFJ 求出（由于纳税原因）他们可以选派参加 IOI 的代表队的方法数。如果两个代表队拥有不同的成员或不同的领队，则被认为是不同的。

outputFormat: 输出一行一个整数表示可能的代表队的数量。


title: [USACO21OPEN] Routing Schemes P

description:
考虑一个由 $N$ 个编号为 $1\dots N$ 的结点组成的网络。每个结点被指定为发送者（sender）、接收者（receiver）或两者均不是。发送者的数量 $S$ 与接收者的数量相等（$S≥1$）。

这一网络中结点间的连接关系可以用一系列形式为 $i→j$
的有向边表示，代表由结点 $i$ 可以路由到结点 $j$。有趣的是，所有的边满足性质 $i<j$，除了 $K$ 条满足 $i>j$（$0≤K≤2$）。网络中没有自环（$i→i$ 形式的边）。

一个「**路由方案**」的描述由 $S$ 条从发送者到接收者的有向路径组成，其中没有两条路径有相同的起止点。也就是说，这些路径将不同的发送者连接到不同的接收者。一条从发送者 $s$ 到接收者 $r$ 的路径可以用一个结点序列
$s=v_0→v_1→v_2→⋯→v_e=r$ 表示，其中对于所有 $0≤i<e$，有向边 $v_i→v_{i+1}$ 均存在。一个结点可能在同一条路径中出现多于一次。

计算使得每条有向边恰好使用一次的路由方案数量。由于答案可能非常大，输出答案对 $10^9+7$ 取模的结果。输入保证存在至少一种路由方案符合条件。

每个输入包含 $T$ 组需要独立求解的测试用例。

inputFormat:
输入的第一行包含 $T$，为测试用例的数量。

每个测试用例的第一行包含整数 $N$ 和 $K$。注意 $S$ 并不会在输入中明确给出。

每个测试用例的第二行包含一个长为 $N$ 的字符串。如果第 $i$ 个结点是发送者，则字符串的第 $i$ 个字符为 $\texttt{S}$，如果第 $i$ 个结点是接收者则为 $\texttt{R}$，如果第 $i$ 个结点两者均不是则为 $\texttt{.}$。字符串中 $\texttt{R}$ 的数量等于 $\texttt{S}$ 的数量，且至少有一个 $\texttt{S}$。

每个测试用例的以下 $N$ 行每行包含一个长为 $N$ 的 01 字符串。如果从结点 $i$ 到结点 $j$ 存在一条有向边，则第 $i$ 行的第 $j$ 个字符为 $1$，否则为 $0$。由于不存在自环，矩阵的主对角线仅包含 $0$。除此之外，在主对角线以下恰好有 $K$ 个 $1$ 。

为提高可读性，相邻的测试用例之间用一个空行隔开。

outputFormat: 对每个测试用例，输出每条边使用恰好一次的路由方案的数量，结果对 $10^9+7$ 取模。输入保证对每个测试用例存在至少一种合法的路由方案。


title: [USACO21OPEN] Balanced Subsets  P

description:
Farmer John 的草地可以被看作是由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘），对于每一个 $1≤i≤N$、$1≤j≤N$，方格可以用有序对 $(i,j)$ 表示。某些方格中含有草。

方格的一个非空子集被称为是「平衡的」，如果以下条件成立：

- 1. 所有子集中的方格均含有草。
- 2. 子集是四连通的。换句话说，从子集中的任一方格到另一方格均存在一条路径使得路径中的相邻方格均水平或竖直方向上相邻。
- 3. 如果方格 $(x_1,y)$ 和 $(x_2,y)$（$x_1≤x_2$）存在于子集中，那么所有满足 $x_1≤x≤x_2$ 的方格 $(x,y)$ 也存在于子集中。
- 4. 如果方格 $(x,y_1)$ 和 $(x,y_2)$（$y_1≤y_2$）存在于子集中，那么所有满足 $y_1≤y≤y_2$ 的方格 $(x,y)$ 也存在于子集中。

计算平衡的子集数量模 $10^9+7$ 的结果。

inputFormat:
输入的第一行包含 $N$。

以下 $N$ 行每行包含一个长为 $N$ 的字符串。如果方格 $(i,j)$ 中有草，则第 $i$ 行的第 $j$ 个字符为 $\texttt{G}$，否则为$\texttt{.}$。

outputFormat: 输出平衡的子集数量模 $10^9+7$ 的结果。

hint:
#### 样例一解释

对于这个测试用例，所有的四连通子集均是平衡的。

```
G.  .G  ..  ..  GG  .G  ..  G.  GG  .G  G.  GG  GG
.., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG
```

#### 样例二解释

以下是一个符合第二个条件（四连通）但不符合第三个条件的子集的例子：

```
GG..
.G..
GG..
....
```

#### 数据范围与约定

$1\le N \le 150$ 。


title: 「Stoi2033」分裂

background:
> 趁时间没发觉 让我带着你离开
> 没有了证明 没有了空虚
> 基于两种立场我会罩着你
> 趁时间没发觉 让我带着你离开
> 这不是顽固 这不是逃避
> 没人绑着你走才快乐
> ——《分裂》

description:
有一个 $n \times m \times 2$ 的棋盒（四周为棋盒壁）与黑、红各 $nm$ 颗棋。棋子有若干种类，红色的一种棋子个数和黑色的该种棋子个数相等。棋子种类用特征值 $v_{i,j}$ 标记。特征值相同的棋子种类相同，特征值不同的棋子种类不同。红色棋子摆放在棋盒的下层，已经摆好。现在 Vinsta 要将黑棋按照规定顺序摆放在棋盒上层。设棋盒内坐标以左上角为 $(1,1)$，右下角为 $(n,m)$，依此第 $i$ 行第 $j$ 列为 $(i,j)$，则每颗摆进去的黑棋必须摆在满足以下要求的位置：

1. 其摆放位置没有黑棋子且下方为与其种类相同的红棋；

2. 在 1. 的要求下，若有多个，令一个位置的 **紧密度** 为其四边有黑棋子相邻或为棋盒壁的个数，则选择 **紧密度** 最大的一个；

3. 在 2. 的要求下，若还有多个，则设此位置的坐标为 $(i,j)$，要求 $i+j$ 最小；

4. 在 3. 的要求下，若还有多个，要求 $i$ 最小。

给出红棋的摆放情况和黑棋放入的顺序，她想请你帮忙求出每个位置的黑棋子被放入的顺序。

inputFormat:
第一行两个整数 $n,m$。

接下来 $n$ 行 $m$ 列，第 $i$ 行第 $j$ 列表示 $v_{i,j}$。

接下来一行 $nm$ 个整数，表示按顺序每次放入的棋子的种类。

outputFormat: 输出 $n$ 行 $m$ 列，每个位置上的数 $k_{i,j}$ 表示 $(i,j)$ 上的棋是第 $k_{i,j}$ 个被放进去的。

hint:
对于 $30\%$ 的数据，$1 \le n,m \le 70$；

对于另外 $30\%$ 的数据，$v_{i,j}=1$；

对于 $100\%$ 的数据，$1 \le n,m \le 10^3, 1 \le v_{i,j} \le 10$，保证每种棋子黑色与红色数量相等。


title: [COCI2021-2022#3] Ekoeko

description:
给定一个正整数 $n$ 和一个由 $2n$ 个小写字母组成的字符串。

交换字符串的相邻两个字母视为一次操作。求使得原串的前 $n$ 个小字母和后 $n$ 个完全相同所需的最少操作次数。

inputFormat:
第一行，一个正整数 $n$。

第二行，一个由 $2n$ 个小写字母组成的字符串。数据保证每个字母均出现偶数次。

outputFormat: 输出最少操作次数。

hint:
**【样例 3 解释】**

一种操作次数最少的方案：

$\texttt{soolnlsn} \to \texttt{so\red{lo}nlsn} \to \texttt{sol\red{no}lsn} \to \texttt{\red{os}lnolsn} \to \texttt{o\red{ls}nolsn}$

**【数据规模与约定】**

**本题采用子任务捆绑测试。**

- Subtask 1（10 pts）：字符串前 $n$ 个字母均为 $\texttt a$，后 $n$ 个均为 $\texttt b$。
- Subtask 2（20 pts）：每个字母在字符串中至多出现两次。
- Subtask 3（20 pts）：前 $n$ 个字母和后 $n$ 个字母的组成完全相同，但顺序可能不同。
- Subtask 4（20 pts）：$1 \le n \le 1000$。
- Subtask 5（40 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^5$。

**【提示与说明】**

**题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _Task 4 Ekoeko_。**

**本题分值按 COCI 原题设置，满分 $110$。**


title: 「Stoi2029」以父之名

background:
> 以父之名判决
> 那感觉没有适合字汇
> 就像边笑边掉泪
> 凝视着完全的黑
> 阻挡悲剧蔓延的悲剧会让我沉醉
> ——《[以父之名](https://www.bilibili.com/video/BV1fx411N7bU?p=36)》

description:
地狱里有 $n$ 个罪人在等待判决，编号为 $1$ 至 $n$。罪人们之间有 $m$ 条罪的联系，编号为 $1$ 至 $m$，每条联系 的值为 $1$ 或 $2$ 且恰好连接两个罪人。

称一个罪人的自负度为他和其他所有罪人之间联系的值之和。两个罪人之间可能不止有一条联系，此时这些联系的值都应该被计算。由于这些罪人承受了太多的罪恶，他们变得不和谐。具体地，每个罪人的自负度都是奇数。

现在，神明将要对他们进行判决。判决的具体方式为：将每条联系都进行定向，使得这条联系所连接的两个罪人中的一个受到惩罚，另一个受到救赎，它们的值均为这条联系的值。

由于神明秉承父的仁慈，希望罪人们更加均等地接受惩罚和救赎，于是他规定判决后每个罪人所受到的惩罚和救赎值总和之差的绝对值必须恰好为 $1$。

由于神明工作繁忙，因此他以父之名要求你为他找到一种判决的方法。由于父的指示不会有错，所以一定存在一种这样的方法。

---

#### 题意简述

给定一个 $n$ 个点 $m$ 条边的无向图，边权均为 $1$ 或 $2$。保证每个点所相连的边权值之和均为奇数。你需要将这些边定向，使每个点的入边权值和与出边权值和之差的绝对值恰为 $1$。保证有解。输出任意一种方案。

inputFormat:
第一行两个正整数：$n,m$，表示有 $n$ 个罪人和 $m$ 条罪的联系。

接下来 $m$ 行，第 $i+1$ 行为三个正整数：$u_i,v_i,w_i$，表示第 $i$ 条联系连接 $u_i$ 与 $v_i$ 且值为 $w_i$。

outputFormat: 共一行 $m$ 个数字，第 $i$ 个数字为 $0$ 表示使 $u_i$ 受到惩罚，使 $v_i$ 受到救赎；为 $1$ 表示使 $v_i$ 受到惩罚，使 $u_i$ 受到救赎。

hint:
#### 样例解释

定向后的图如下：

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

更多样例详见题目附件 `trial_sample.zip`。

------

#### 数据范围

**本题采用捆绑测试。**

- 特殊性质 A：边权均为 $1$，且任意两点之间只存在一条简单路径，且没有重边。
- 特殊性质 B：同一个点至多只有一条边权为 $1$ 和一条边权为 $2$ 的边相连。

| Subtask | 分值 | $1\le n \le$ | $1\le m \le$ | 特殊性质 |
| :-: | :-: | :-: | :-: | :-: |
| $1$ | $7$ | $10$ | $15$ | 无 |
| $2$ |  $20$ |$10^3$ | $3\times10^3$ | 无 |
| $3$ |  $20$ |$3 \times 10^5$ | $3 \times 10^5$ | A |
| $4$ | $20$ |$3 \times 10^5$ | $3 \times 10^5$ | B |
| $5$ |  $33$ |$10^6$ | $3 \times 10^6$ | 无 |

对于 $100\%$ 的数据，$1 \le u_i,v_i \le n \le 10^6$，$1 \le m \le 3 \times 10^6$，$w_i \in \{1,2\}$。

在题目附件 `trial_sample.zip` 中：

- `trial_sample1.in` 即为样例 #1。
- `trial_sample2.in` 满足特殊性质 A。
- `trial_sample3.in` 满足特殊性质 B。
- `trial_sample4.in` 不满足特殊性质。

另外该目录下还有 `checker.exe`。

------

#### 提示

**本题输入输出量较大，请使用较快的输入输出方式。**

本题提供 [Special Judge 源码](https://www.luogu.com.cn/paste/7albhubs)和 `checker.exe`，供选手调试。Windows 下使用方法为:
命令行在目标文件夹输入指令：
```
checker.exe data.in data.out data.out
```
其中 `data.in` 是输入数据文件，`data.out` 是程序运行结果文件。观察评判结果即可。

- `Perfect answer.` 表示答案正确。
-  `Wrong answer on node x, and the difference is d.` 表示答案错误，其中节点 $x$ 的入边权值和与出边权值和之差的绝对值为 $d$ 而不为 $1$。
- `Invalid answer.` 表示输出的字符串长度不正确或输出非法字符。

请务必保证**输出格式正确**，否则 Special Judge 可能会返回 Unknown Error 等不可预估的结果。


title: 20

description:
对于每一个 $0\le i,j<4$，给定 $x(i,j)$ 使得：

 1. 交换律：$x(i,j)=x(j,i)$
 2. 结合律：$x(x(i,j),k)=x(i,x(j,k))$。
 3. 单元：$x(0,i)=i$。

定义函数 $f(n)$，使得：

 1. $f(p^k)=pk\bmod 4$
 2. 当 $\gcd(a,b)=1$，$f(ab)=x(f(a),f(b))$。

特别，$f(1)=0$。

定义函数 $g$ 为：

$$g(n,k,r)=\sum_{i=1}^ni^k[f(i)=r]$$

给定 $m$ 和 $k$，请对所有 $1\le i\le\lfloor\sqrt m\rfloor$，计算所有 $0\le r<4$ 的 $g(\lfloor\frac mi\rfloor,k,r)$ 值。答案对 $998244353$ 取模。

inputFormat:
第一行两个整数 $n$，$k$。
接下来 $4$ 行每行 $4$ 个整数，第 $i$ 行第 $j$ 整数为 $x(i-1,j-1)$。

hint:
本题不采用捆绑测试，数据略微有梯度。

对于 $16\%$ 的数据，$n\le10^6$。

对于 $100\%$ 的数据，$1\le n\le 10^{10}$，$0\le k\le 1000$。


title: [BalticOI 2021 Day1] A Difficulty Choice

background:
**本题为交互题。**

感谢交互库与 checker 的提供者 [Hi_chocolate](https://www.luogu.com.cn/user/193198) 为本题做出的巨大贡献。

### 特别提示

**在洛谷提交本题时的一些注意事项（与原题面不同之处请以此处为准）：**

1. 提交时请在程序里加入以下函数声明语句：

```cpp
extern "C" long long skim (int i);
extern "C" void answer (std::vector<int> v);
extern "C" void impossible ();
```

你实现的 `solve` 函数应为：

```cpp
extern "C" void solve (int N, int K, long long A, int S);
```

2. 程序开头不用，也不应该包含 `books.h` 头文件。
3. 仅支持 `C++`（含 `C++`，`C++11`，`C++14`，`C++17`）提交。

description:
您致力于 AK BalticOI，而 AK BalticOI 的方式就是学习。您走进了一家书店，架子上有 $N$ 本书，编号为 $1$ 到 $N$，第 $i$ 本的难度为 $x_i$。您要从这 $N$ 本书中挑选出 $K$ 本书用来学习，您不希望学到太简单或太难的东西，所以您想要保证这 $K$ 本书的难度之和位于 $[A,2A]$ 的区间内。

可惜的是，您并不知道 $x_i$ 的具体数值，所以您要浏览这些书籍以得知他们的难度。书店老板有洁癖，他不希望您浏览太多的书籍，所以他规定您最多只能浏览 $S$ 本书，然后确定这些书的难度。幸运的是，您被告知这 $N$ 本书按照编号的增加，难度呈单调递增。

请编写一个程序，通过浏览书籍，购买您需要的书籍，或者指出无解。

### 交互格式

本题为交互题，您需要编写 `void solve (int N, int K, long long A, int S)` 函数，$N,K,A,S$ 在上面已经定义，并且保证 $x_1<x_2<\cdots<x_n$，该函数只被调用一次。

您还可以调用如下的函数：

- `long long skim (int i)` 浏览第 $i$ 本书以获取他的难度 $x_i$。
- `void answer (vector<int> v)` 买您所需要的书。其中 $v=\{i_1,i_2,\cdots,i_K\}$，并且需要满足：
$$A \le \sum\limits_{j=1}^K i_j \le 2A$$
- `void impossible ()` 指出不可能按照要求买下 $K$ 本书。

如果存在满足要求的 $K$ 本书，您必须准确地调用 `answer` 函数一次；否则您需要准确地调用 `impossible` 函数一次。调用过后，程序会自动停止。

如果您的函数调用不符合上面的格式，或者调用了超过 $S$ 次 `skim` 函数，程序会自动停止，这个测试点会判为 **Not correct**；你不能在标准输出中输出任何东西，否则会被判为 **Security violation**。

如果您使用 C++ 编码，请调用 `books.h` 头文件，如果您想检验您的程序的正确性，可以在下方附件中下载 `sample_grader.cpp` 与 `books_sample.cpp`，分别为您提供检验正确性和示例说明的作用。

如果您使用 Python 编码，可以在下方附件中下载 `books_sample.py` 检验。

交互库希望标准输入里有两行：

- 第一行四个整数，$N,K,A,S$。
- 第二行 $N$ 个整数，$x_1,x_2,\cdots,x_N$。

随后，交互库会调用您的程序，最后，交互库会在标准输出中返回信息：

|信息|意义|
|:-:|:-:|
|**Invalid input.**|标准输入的格式错误|
|**Invalid skim.**|`skim` 函数调用无效|
|**Out of books to skim.**|`skim` 函数调用超过 $S$ 次|
|**Invalid answer.**|`answer` 函数调用无效|
|**Wrong answer.**|`answer` 函数调用的 $v$ 不满足要求|
|**No answer.**|`solve` 函数没有调用 `answer` 函数和 `impossible` 函数中的任意一个|
|**Impossible (not checked): s book(s) skimmed.**|上述事件都没有发生，调用了 $S$ 次 `skim` 函数，并在有答案的时候调用了 `impossible` 函数|
|**Correct: s book(s) skimmed.**|上述事件都没有发生，调用了 $S$ 次 `skim` 函数|

针对上面若干个错误的情况，交互库仅会返回 **Not correct**，或者正确的时候返回 **Correct**。每当出现上面的若干个错误，或者您的程序调用了 `answer` 或 `impossible` 函数时，程序会被自动停止。

inputFormat: 见「交互格式」。

outputFormat: 见「交互格式」。

hint:
#### 样例 1 解释

$N=15$，$K=3$，$A=42$，$S=8$，下面是可能的两种会被判为通过的调用结果：

示例 1：

|你的程序|返回值|
|:-:|:-:|
|`skim(1)`|$1337$|
|`impossible`|-|

示例 2：

|你的程序|返回值|
|:-:|:-:|
|`skim(1)`|$7$|
|`skim(15)`|$21$|
|`answer({11,15,7})`|-|

#### 数据规模与约定

**本题采用捆绑测试。**

- Subtask 1（5 pts）：$S=N$，$170 \le N \le 1000$，$K=3$。
- Subtask 2（15 pts）：$S=N$，$N \ge 170$。
- Subtask 3（10 pts）：$S \ge 170$，$x_{i+1}-x_i \le \frac A K$。
- Subtask 4（15 pts）：$S \ge 170$，$x_{i+1}-x_i \le A$。
- Subtask 5（15 pts）：$S \ge 170$。
- Subtask 6（20 pts）：$S \ge 40$，$x_{i+1}-x_i \le A$。
- Subtask 7（20 pts）：$S \ge 40$。

对于 $100\%$ 的数据，$K \le N$，$3 \le N,S \le 10^5$，$1 \le A,x_i \le 10^{17}$，$3 \le K \le 10$。

#### 说明

翻译自 [BalticOI 2021 Day1 A A Difficulty Choice](https://boi.cses.fi/files/boi2021_day1.pdf)。


title: [COCI2012-2013#1] LJUBOMORA

description:
一家弹珠厂向一所幼儿园捐赠了一些弹珠，弹珠一共有 $M$ 种颜色，每颗弹珠都有一种颜色。老师需要把所有的弹珠分给 $N$ 个孩子。每个孩子得到的所有弹珠都必须是**相同的颜色**，而且可以有一些孩子一颗弹珠也没得到。

我们把**嫉妒值**定义为分给一个孩子最多的弹珠数量。请你帮助老师分弹珠，使得嫉妒值**最小**。

例如，如果有 $4$ 个红色的弹珠（$\texttt{RRRR}$）和 $7$ 个蓝色的弹珠（$\texttt{BBBBBBB}$），要分给 $5$ 个孩子，那么我们可以这样划分：$\texttt{RR}$，$\texttt{RR}$，$\texttt{BB}$，$\texttt{BB}$，$\texttt{BBB}$。这样分的嫉妒值为 $3$，是最小的。

inputFormat:
输入共 $M+1$ 行。

第一行包含两个正整数 $N,M$，分别表示孩子数和弹珠的颜色总数。

接下来 $M$ 行的第 $i$ 行包含一个正整数 $x$（$x \in [1,10^9]$），表示有 $x$ 个颜色为 $i$ 的弹珠。

outputFormat: 输出一行一个整数，表示最小的嫉妒值。

hint:
#### 【数据范围】

对于 $100\%$ 的数据，保证 $1 \le M \le 3 \times 10^5$，$1 \le N \le 10^9$，$M \le N$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $120$。

题目译自 **[COCI2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST #1](https://hsin.hr/coci/archive/2012_2013/contest1_tasks.pdf)** ___T4 LJUBOMORA___。


title: [COCI2012-2013#1] SNAGA

description:
从一个正整数 $N$ 开始，找到不能被 $N$ 整除的最小正整数。如果我们用得到的正整数重复这个过程，我们最终会得到 $2$。

定义 $\operatorname{strength}(N)$ 为结果序列的长度。例如 $N = 6$，可以得到由 $4$ 个数字组成的结果序列 $6,4,3,2$，包含 $4$ 个整数，所以 $\operatorname{strength}(6) = 4$。

给定两个正整数 $A,B$，请计算：

$$ \sum\limits_{i=A}^B \operatorname{strength}(i)$$

inputFormat: 输入共一行，包含两个用空格分隔的整数 $A,B$。

outputFormat: 输出一行一个整数，表示结果。

hint:
#### 【数据范围】

对于 $100\%$ 的数据，保证 $3 \le A < B \le 10^{17}$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $140$。

题目译自 **[COCI2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST #1](https://hsin.hr/coci/archive/2012_2013/contest1_tasks.pdf)** ___T5 SNAGA___。


title: [BalticOI 2021 Day1] Inside information

description:
有 $N$ 个服务器，第 $i$ 个服务器存储着第 $i$ 块数据，现在有若干种操作：

- `S a b` 第 $a$ 个服务器与第 $b$ 个服务器共享数据，即这两个服务器同时拥有这两个服务器本身拥有的数据块的和，并自动去重（可以理解为数据块之并）。
- `Q a d` 查询第 $a$ 个服务器是否拥有第 $d$ 块数据。
- `C a` 查询存储数据块 $a$ 的服务器数量。

S 操作有 $N-1$ 次，如果把共享看做连边，那么最后将形成以 $N$ 个服务器为点的一棵树；Q 操作和 C 操作一共有 $K$ 次。

求对于每个 Q 操作和 C 操作返回的结果。

inputFormat:
第一行两个整数 $N,K$ 代表服务器个数和操作个数。

接下来 $N+K-1$ 行每行代表一个操作。

outputFormat:
$K$ 行：

- 对于 Q 操作，输出 `yes` 或 `no` 代表是否拥有第 $d$ 块数据；
- 对于 C 操作，输出一个整数代表服务器数量。

hint:
#### 数据规模与约定

**本题采用捆绑测试。**

- Subtask 1（5 pts）：$N \le 4000$。
- Subtask 2（5 pts）：第 $1$ 个服务器与第 $2,3,\cdots,N$ 个服务器共享数据。
- Subtask 3（10 pts）：如果 $|A-B|=1$，那么第 $A$ 个服务器和第 $B$ 个服务器共享数据。
- Subtask 4（20 pts）：如果 $A<B$ 且 $2A=B$ 或 $2A+1=B$，那么第 $A$ 个服务器和第 $B$ 个服务器共享数据。
- Subtask 5（25 pts）：每个服务器最多与 $5$ 个服务器共享数据。
- Subtask 6（35 pts）：无特殊限制。

对于 $100\%$  的数据，$1 \le N,K \le 1.2 \times 10^5$。

#### 说明

翻译自 [BalticOI 2021 Day1 B Inside information](https://boi.cses.fi/files/boi2021_day1.pdf)。


title: [COCI2012-2013#1] MARS

description:
科学家在火星上发现了一些奇怪的细菌，正在研究它们。他们注意到细菌的数量是 $2$ 的次方，因为每一种细菌都会分裂成两种新的细菌，而初始有一种细菌。因此，在第一代中只有一种细菌，第二代中有两种细菌，第三代中有四种细菌，以此类推，直到第 $K + 1$ 代中有 $2^K$ 种细菌。

科学家们用 $1$ 至 $2^K$ 之间的整数给细菌进行了编号，方法如下：

- 第 $K$ 代细菌的后代按顺序分别为：$\{1,2\},\{3,4\},\{5,6\},\cdots,\{2^K-1,2^K\}$
- 第 $K - 1$ 代细菌的后代按顺序分别为：$\{1,2,3,4\},\{5,6,7,8\},\cdots,\{2^K-3,2^K-2,2^K-1,2^K\}$
- 第 $K - 2$ 代细菌的后代按顺序分别为：$\{1,2,3,4,5,6,7,8\},\cdots,\{2^K-7,2^K-6,2^K-5,2^K-4,2^K-3,2^K-2,2^K-1,2^K\}$
- $\cdots$
- 第 $1$ 代细菌的后代按顺序分别为：$\{1,2,\cdots,2^{K-1}\},\{2^{K-1}+1,2^{K-1}+2,\cdots,2^K\}$

其中花括号表示一个细菌的一组后代。

也就是说，对当前这一代的 $2^K$ 个细菌进行编号，使得任何较老细菌的后代都有连续的编号。**注意这些细菌存在许多种不同的 仍然满足任何较老细菌的后代都有连续编号的条件 的排列。**

科学家想把细菌排列成一个**长度尽可能短**的序列。细菌序列的长度是**所有相邻的细菌对之间的距离的总和**。

确切地说，每两个细菌之间都有一定的**排斥值**。如果它们在序列中相邻，这个排斥值就是它们之间的最小距离（序列中不相邻的细菌之间的排斥值不起作用）。给定所有细菌对的排斥值，找出满足上述后代规则的细菌序列（排列）的最小长度。

inputFormat:
输入的第一行包含一个正整数 $K$，意义见题目描述。

接下来的 $2^K$ 行，每行包含在 $[0,10^6]$ 范围内的 $2^K$ 个整数。这 $2^K \times 2^K$ 个整数表示细菌对之间的排斥值：第 $m$ 行第 $n$ 列中的整数是细菌 $m$ 和细菌 $n$ 之间的排斥值。当然这个整数等于第 $n$ 行第 $m$ 列的整数。如果 $m=n$，这个整数将会是 $0$。

outputFormat: 输出一行一个整数，表示满足条件的细菌序列的最小长度。

hint:
#### 【数据范围】

对于 $100\%$ 的数据，保证 $1 \le K \le 9$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $160$。

题目译自 **[COCI2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST #1](https://hsin.hr/coci/archive/2012_2013/contest1_tasks.pdf)** ___T6 MARS___。


title: [JDWOI-2] 红黑树

background: 小 M 迷上了画画，所以她用红色和黑色的画笔画出了一棵红黑树。

description:
这棵树有 $n$ 个点，从 $1$ 开始标号，其中 $1$ 号点为树根。一开始，小 M 给这 $n$ 个点分别涂上了红色或黑色，第 $i$ 号点的颜色是 $a_i$（'R' 代表红色，'B' 代表黑色）。

但可惜的是，小 M 对这棵树并不是非常满意，她希望第 $i$ 号点的颜色为 $b_i$。

好在她的好朋友小 K 懂得一点点膜法。小 K 可以先选定一个点，然后把这个点的颜色反转（红变黑，黑变红）。但这个膜法太强大了，所以会把膜法传递下去，即在反转的一秒之后使当前点的父节点颜色也进行反转，如此传递，直到根节点为止。特殊的，如果在同一时刻有多个膜法作用在同一个点上，这些膜法会两两抵消，如果恰好抵消完了（即膜法的个数为偶数），则当前点不会变色，并且不会有膜法继续传递下去。注意此处抵消膜法不需要耗时间。

但毕竟小 K 还是个新手，所以他在一秒之内只能最多对一个节点施展上述膜法。

为了尽快让小 M 开心，小 K 想知道，至少经过多少秒才能让这棵红黑树初次出现小 M 的理想颜色状态？可以证明，总可以按题目要求变成理想颜色状态。

inputFormat:
**本题多测**。

第一行一个整数 $Q$，表示数据组数。

**对于每组数据：**

第一行一个整数 $n$，表示红黑树的节点数。

第二行一个长度为 $n$ 的字符串 $a$，表示红黑树的初始颜色状态，其中仅含有 'R' 或 'B'。

接下来 $n-1$ 行，每行两个整数 $x,y$，描述一条树边。

最后一行一个长度为 $n$ 的字符串 $b$，表示红黑树的理想颜色状态，其中仅含有 'R' 或 'B'。

outputFormat: 共 $Q$ 行每行一个整数，一组数据一行，表示答案，即最小耗时。

samples:
2
5
RRBBR
1 2
1 3
2 4
2 5
BRBRB
5
RRRRR
1 2
2 3
3 4
4 5
BBBBB

hint:
**【样例解释】**

第一组数据中，小 K 可以在第 $1$ 秒给 $4$ 号点膜法，整个树变为 RRBRR，在第 $2$ 秒给 $5$ 号点膜法，整个树变成 RBBRB，在第 $3$ 秒给 $1$ 号点膜法，整个树变成 BRBRB。

第二组数据中，小 K 可以在第 $1$ 秒给 $5$ 号点膜法，在第二秒给 $2$ 号点膜法；或者在第 $1$ 秒给 $3$ 号点膜法，在第 $2$ 秒给 $5$ 号点膜法。

**【数据范围】**

对于 $10\%$ 的数据，$1\leq n\leq 5$；

对于 $30\%$ 的数据，$1\leq n\leq 10$；

对于另外 $20\%$ 的数据，$\forall a_i\neq b_i$；

对于 $100\%$ 的数据，$1\leq n\leq 20$，$1\leq Q\leq 20$，树随机生成。


title: [BalticOI 2021 Day2] The short shank

description:
你入狱了，你现在正在洛谷第一监狱里。

监狱共有 $N$ 个牢房，从左到右编号为 $1 \sim N$。你和你的狱友们准备策划一场造反，第 $i$ 个牢房里的罪犯准备在第 $t_i$ 个时刻点造反，如果第 $i$ 个牢房的罪犯造反后，第 $i+1$ 个牢房的罪犯会无视他在第 $t_{i+1}$ 个时间点造反的规矩，在第 $t_i+1$ 个时间点就会造反。

狱警提前预知了一切，所以他们会放置 $D$ 个床垫，如果在第 $i$ 个牢房和第 $i+1$ 个牢房中间放置一个床垫，那么当第 $i$ 个牢房的罪犯造反时，第 $i+1$ 个牢房的罪犯不会立即造反，而会等到第 $t_{i+1}$ 个时间点。

你想知道，狱警合理安排床垫后，在第 $T$ 个时间点及以前最少会有多少个罪犯造反。

inputFormat:
第一行三个整数 $N,D,T$ 代表罪犯个数，床垫个数和希望的时间点。

第二行 $N$ 个整数 $t_i$ 代表第 $i$ 个罪犯造反的时间点。

outputFormat: 一行一个整数代表答案。

hint:
#### 样例 1 解释

最优解是在第 $2$ 个牢房和第 $3$ 个牢房之间放入床垫，造反的是第 $1,2,4,5$ 个牢房里的罪犯。

#### 数据规模与约定

**本题采用捆绑测试。**

- Subtask 1（15 pts）：$N \le 500$。
- Subtask 2（10 pts）：$N \le 5 \times 10^5$，$D=1$。
- Subtask 3（20 pts）：$N \le 4000$。
- Subtask 4（10 pts）：$N \le 7.5 \times 10^4$，$D \le 15$。
- Subtask 5（25 pts）：$N \le 7.5 \times 10^4$。
- Subtask 6（20 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le D<N \le 2 \times 10^6$，$1 \le T,t_i \le 10^9$。

另有 Subtask 0 为样例。

#### 说明

翻译自 [BalticOI 2021 Day2 A The short shank](https://boi.cses.fi/files/boi2021_day2.pdf)。


title: [BalticOI 2021 Day2] The Collection Game

background:
**本题是交互题。**

你的代码不需要也不应该包含 `swaps.h` 头文件，但应包含以下声明：

```cpp
extern "C" void schedule(int i, int j);
extern "C" std::vector<int> visit();
extern "C" void answer(std::vector<int> r);
extern "C" void solve(int N, int Q) {
  // Code Here
}
```

description:
您要参观博物馆的 $N$ 个展馆，因为您之前有入狱史（BalticOI 2021 Day2 A），所以博物馆官方仅允许您参观小于等于 $V$ 次。每一次参观您可以浏览多次，每一次浏览您可以浏览 **一对** 展馆 $(i,j)$，然后您就可以得知这两个展馆哪个展馆的艺术价值最高。为了不浪费您的时间，每一次参观每个展馆只能浏览最多一次。

不幸的是，因为您的入狱史，博物馆 **可能** 会交换您要浏览的一对展馆里的展品，这样您得到的艺术价值关系就是反过来的，您最后对这 $N$ 个展馆中的其中一个的排名也应基于 **最后一次** 对这个展馆的浏览。

现在请通过浏览来确定这 $N$ 个展馆的艺术价值的排列。

### 交互格式

您需要实现函数 `void solve (int N, int V)`，其中 $N $ 和 $V$ 为展馆数量和最多参观次数。

`solve` 函数只被调用一次，并且可以在 `solve` 函数里面调用：

- `void schedule (int i, int j)` 浏览一对展馆 $(i,j)$，博物馆有可能交换展品。
- `vector <int> visit ()` 整理浏览结果，返回的序列按照浏览的展馆对数 $(i,j)$ 顺序返回若干个 $k$，如果第 $i$ 个展馆的艺术价值高于第 $j$ 个展馆，$k=1$，否则 $k=0$。
- `void answer (vector <int> r)` $r$ 是一个长度为 $N$ 的序列，并且是一个 $1 \sim N$ 的排列，$r_i=p$ 代表第 $i$ 个展馆在这 $N$ 个展馆的艺术价值排序中排第 $p$ 个。

如果您函数的调用不满足要求，一次参观一个展馆浏览了超过 $1$ 次，或者参观了超过 $V$ 次，您的程序都会立即停止然后判为 `Not correct`。请不要在标准输出中输出任何东西，否则会被判为 `Security violation!`。

如果您使用 C++ 编码，请调用 swaps.h 头文件，如果您想检验您的程序的正确性，可以在下方附件中下载 sample_grader.cpp 与 swaps_sample.cpp，分别为您提供检验正确性和示例说明的作用。

如果您使用 Python 编码，可以在下方附件中下载 swaps_sample.py 检验。

交互库希望标准输入里有一行：

- 一行两个整数 $N,V$。

随后，交互库会调用您的程序，最后，交互库会在标准输出中返回信息：

|信息|意义|
|:-:|:-:|
|**Invalid input.**|标准输入的格式错误|
|**Invalid schedule.**|`schedule` 函数调用无效|
|**Out of visits.**|`visit` 函数调用超过 $V$ 次|
|**Invalid answer.**|`answer` 函数调用无效|
|**Wrong answer.**|`answer` 函数调用的 $r$ 错误|
|**No answer.**|`solve` 函数没有调用 `answer` 函数|
|**Correct: v visit(s) used.**|上述事件都没有发生，调用了 $V$ 次 `visit` 函数|

针对上面若干个错误的情况，交互库仅会返回 **Not correct**，或者正确的时候返回 **Correct**。每当出现上面的若干个错误，或者您的程序调用了 `answer` 函数时，程序会被自动停止。

hint:
#### 样例 1 解释

$N=4$，$V=50$，下面是一种合法的调用：

|你的程序|返回值|博物馆是否交换
|:-:|:-:|:-:|
|`schedule(1,2)`|-|否|
|`schedule(3,4)`|-|是|
|`visit()`|`{1,0}`|-|
|`schedule(2,4)`|-|否|
|`visit()`|`{1}`|-|
|`answer({1,2,4,3})`|-|-|

对于上表，$r=\{2,1,4,3\}$ 也满足要求。如果第三次 `visit` 交换了，那么 $r=\{4,1,2,3\}$ 满足要求。

#### 数据规模与约定

**本题采用捆绑测试。**

- Subtask 1（5 pts）：$V=5000$，博物馆永远不会交换展品。
- Subtask 2（10 pts）：$V \ge 1000$，博物馆永远不会交换展品。
- Subtask 3（5 pts）：$N \le 100$，$V=5000$。
- Subtask 4（15 pts）：$V=5000$。
- Subtask 5（15 pts）：$V\ge 500$。
- Subtask 6（35 pts）：$V \ge 100$。
- Subtask 7（15 pts）：$V \ge 50$。

对于 $100\%$ 的数据，$1 \le N \le 500$，$50 \le V \le 5000$。

#### 说明

翻译自 [BalticOI 2021 Day2 B The Collection Game](https://boi.cses.fi/files/boi2021_day2.pdf)。


title: [BalticOI 2021 Day2] The Xana coup

description:
给定一棵点数为 $N$ 个树，第 $i$ 个点有点权 $a_i$，$a_i \in \{0,1\}$。

你可以进行切换操作：

- 对点 $i$ 进行切换操作会使得点 $i$ 及与其 **直接相连** 的点的点权取反。

其中直接相连指两点之间恰好只有一条边。

求至少需要多少次切换操作才能使得所有点的点权变为 $0$。

inputFormat:
第一行一个整数 $N$ 代表树的点数。

接下来 $N-1$ 行每行两个整数代表树的一条边。

第 $N+1$ 行 $N$ 个整数 $a_i$ 代表第 $i$ 个点的点权。

outputFormat:
如果有解，一行一个整数代表答案。

如果无解，输出 `impossible`。

hint:
#### 样例 1 解释

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

$a_i=0$ 为黑色，$a_i=1$ 为白色。

可以对点 $4,5,3,1$ 进行切换操作使得所有点的点权为 $0$。

#### 数据规模与约定

**本题采用捆绑测试。**

- Subtask 1（5 pts）：$N \le 20$。
- Subtask 2（15 pts）：$N \le 40$。
- Subtask 3（10 pts）：如果点 $u$ 和点 $v$ 满足 $|u-v|=1$，那么他们有边相连。
- Subtask 4（40 pts）：一个点最多与 $3$ 个点相连。
- Subtask 5（30 pts）：无特殊限制。

对于 $100\%$ 的数据，$3 \le N \le 10^5$。

#### 说明

翻译自 [BalticOI 2021 Day2 C The Xana coup](https://boi.cses.fi/files/boi2021_day2.pdf)。


title: 「PMOI-4」排列变换

description:
给定常数 $k$。对于一个长度为 $n$ 的**排列** $a$，定义

$$f(a)=\{\max_{1 \le i \le k} \{a_i\},\max_{2 \le i \le k+1} \{a_i\},\cdots,\max_{n-k+1 \le i \le n} \{a_i\}\}$$

对于一个长度为 $n$ 的**序列** $a$，定义其权值 $w(a)$ 为 $a$ 中不同的数的个数。

现在，$\text{ducati}$ 想知道，对于所有长度为 $n$ 的排列 $p$，它们的 $w(f(p))$ 之和。

inputFormat: 一行两个正整数 $n,k$。

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

由于答案可能很大，你需要将它对 $998244353$ 取模。


title: [AHOI2021初中组] 坑

background:
AHOI2021 初中组 T2

**你可以选择跳过背景部分。**

买东西的路上小雪吸了好几口雾霾，最后打了个喷嚏。恶劣的天气、压抑的氛围让小雪心情越来越差，之后倒起了苦水：

“唉！今天又被一个不靠谱的同学坑了，浪费了我好多时间。”

“期中考试还早，有什么好焦虑的呢？别卷了，正好来看看最近在蛐蛐国流行的一个游戏吧。”

小雪看了游戏来了精神：看起来好像很解压。

description:
游戏在一个左右无限延伸的数轴上进行，上面有 $n$ 只跳蚤和 $m$ 个坑，它们都可以被抽象成数轴上的一个点。

玩家每回合需要选择让所有跳蚤一起向左/向右跳一个单位长度。如果一个代表跳蚤的点与一个代表坑的点重合了，跳蚤就会掉进坑中，发出惨叫后死去。

郁闷的小雪想用最快的时间杀死所有跳蚤，请你帮小雪计算一下这个最少的回合数。

inputFormat:
第一行两个空格隔开的正整数 $n,m$。

第二行 $n$ 个空格隔开的整数 $x_1,x_2,\ldots,x_n$，其中 $x_i$ 表示第 $i$ 只跳蚤初始时的坐标。

第三行 $m$ 个空格隔开的整数 $y_1,y_2,\ldots,y_m$，其中 $y_i$ 表示第 $i$ 个坑的坐标。

输入数据保证以上 $n+m$ 个坐标两两互不相等。

outputFormat: 仅一行一个整数，表示杀死所有跳蚤的最少回合数。

samples:
见附加文件的 hole2.in。
见附加文件的 hole2.ans。

hint:
【样例 1 解释】

第一回合让所有跳蚤向右跳一步，第 2 个跳蚤进第一个坑，剩下两个跳蚤分别位于 4, 3。

下面四回合让所有跳蚤向左跳，两个跳蚤都进入第一个坑，游戏结束。

【数据范围与提示】

**提示：本题输入规模较大，请避免使用过慢的输入方式。**

- 对于 $20\%$ 的数据，保证 $1 \le n \le 20$，$1 \le m \le 300$；
- 对于另外 $20\%$ 的数据，保证 $1 \le n,m \le 300$；
- 对于另外 $20\%$ 的数据，保证 $1 \le x_i,y_i \le 2000$；
- 对于另外 $10\%$ 的数据，保证 $1 \le n,m \le 2000$；
- 对于另外 $10\%$ 的数据，保证 $m=2$；
- 对于 $100\%$ 的数据，保证 $1 \le n,m \le 2 \times 10^5$，$-10^9 \le x_i,y_i \le 10^9$。


title: [AHOI2021初中组] 收衣服

background:
AHOI2021 初中组 T3

**你可以选择跳过背景部分。**

沉迷于虐待跳蚤游戏的小雪没有发觉时间过了多久，一抬头发现竟然天色大变！天空一片昏黄，一股怪味扑鼻而来。没想到在如此发达的 2077 年，城市中还能碰到沙尘暴，这超现实的场景让小雪怀疑是跳蚤国王显灵。

“别愣着了，快去收衣服呀！”小可可突然想到。

description:
看着这么多蒙灰的衣服，他们俩欲哭无泪；而且，有的衣服是没法一起洗的，为了分门别类，小可可给了每件衣服一个 $1 \sim n$ 的两两不同的标号，其中 $n$ 是衣服的件数，把衣服排成 $1,2,\ldots,n$ 的顺序再洗会比较方便。

小可可还想到，我们可以把一段连续的晾衣架拿出来，在手上翻转顺序，再放回去。作为 OI 选手的你，马上抽象出了小可可排序衣服的算法：我们设初始时从左往右第 $i$ 件衣服的标号为 $p_i$，按 $1,2,\ldots,n-1$ 的顺序枚举 $i$，设 $p_i,p_{i+1},\ldots,p_n$ 中标号最小的是 $p_j$，那么将 $p_i,p_{i+1},\ldots,p_{j-1},p_j$ 左右翻转变成 $p_j,p_{j-1},\ldots,p_{i+1},p_i$。

小雪很快发现，小可可的算法看似厉害，实际上很傻——在天色的影响下，大家都分不出衣服的标号了。于是他们只能回到房间进行理性愉悦：我们假设左右翻转区间 $[i,j]$ 的操作代价是 $w_{i,j}$，一次排序的代价是每次翻转的操作代价之和。现在小可可想知道，当 $p$ 取遍 $n!$ 种排列时，所有情况的排序代价之和。

只用输出答案对 $998244353$（$=7 \times 17 \times 2^{23} + 1$，一个质数）取模后的值。

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

下面 $n-1$ 行，第 $i(1 \le i \le n)$ 行 $n - i + 1$ 个空格隔开的整数，第 $j$ 个表示 $w_{i,j}$。

outputFormat: 一行一个整数，表示答案对 $998244353$ 取模的结果。

samples:
见附加文件的 sort2.in。
见附加文件的 sort2.ans。


title: [AHOI2021初中组] 地铁

background:
AHOI2021 初中组 T4

**你可以选择跳过背景部分。**

小可可发现自己所学算法在生活中其实无大用，感觉十分沮丧。小雪见状还是嘀咕了几句“应该还是有用的吧”。

“不过没用又怎么样呢？算法只不过是一块名牌大学的敲门砖罢了。”

“你这话我就不同意了。跳蚤国王曾经和我说过，以后科研或者工作中我们还会和信息学竞赛中的某些东西重逢，虽然可能不会再有信息学竞赛这么难。

“除开功利的因素之外，搞信息学竞赛还是能享受到很多思考的乐趣的。”

“你说的也对。每次我在考场上不会做质疑这题是不是有问题的时候，考后看题解总是懊恼又快乐——这么自然的思路我怎么想不到呢！”

一颗理论计算机科学家的种子悄悄萌芽。

沙尘暴突然神奇般的散去了。实在坐不下去的两人决定出门坐地铁瞎逛，随性下车。即使没有刻意为之，小雪在地铁上却想出了一个有意思的问题，你能解决吗？

description:
B 市的地铁历史悠久，小雪和小可可乘坐的 X 号线是环形路线，上面分布着 $n$ 个车站，**相邻两个车站之间的铁路长度为正整数**。现在小雪进行了一些观察，得到了 $m$ 条信息，第 $i$ 条信息是如下形式之一：

1. 环上顺时针由 $S_i$ 到 $T_i$ 的一段距离不小于一个给定的值 $L_i$（$S_i$ 和 $T_i$ 是两个车站）；
2. 环上顺时针由 $S_i$ 到 $T_i$ 的一段距离不大于一个给定的值 $L_i$。

小雪想要你计算最后 X 线地铁的总长度有多少种不同的合法取值。

inputFormat:
第一行两个空格隔开的正整数 $n$ 和 $m$。

下面 $m$ 行，第 $i$ 行四个空格隔开的正整数 $type_i,S_i,T_i,L_i$，其中 $type_i \in \{1,2\}$ 表示信息的类型。车站顺时针编号为从 1 开始的连续整数。保证 $1 \le S_i,T_i \le n$ 且 $S_i \ne T_i$。

outputFormat:
仅一行一个整数，表示所求答案。如果有无穷种取值，请输出 `-1`。

**保证答案不为 0，即至少有一种可能的方案。**

samples:
见附加文件的 subway3.in。
见附加文件的 subway3.ans。

hint:
【样例 1 解释】

定义数组 $d[1..4]$，其中 $d[i]$ 表示 $i$ 号车站顺时针到 $i+1$ 号车站的铁路长度。

1. $d=[1,2,2,2]$，总长度为 $7$；
2. $d=[1,2,2,3]$，总长度为 $8$；
3. $d=[1,2,2,4]$，总长度为 $9$；
4. $d=[1,2,3,4]$，总长度为 $10$。

可以证明，不存在其他的可能长度，于是答案为 $4$。

【样例 2 解释】

$3$ 号车站顺时针到 $1$ 号车站的铁路长度可以为任意正整数。

【数据范围与提示】

- 对于 $30\%$ 的数据，保证 $n,m \le 9$，$L_i \le 5$；
- 对于另外 $15\%$ 的数据，保证 $T_i$ 是 $S_i$ 顺时针方向后第一个车站；
- 对于另外 $20\%$ 的数据，保证 $T_i$ 是 $S_i$ 顺时针方向后第二个车站；
- 对于另外 $25\%$ 的数据，保证 $n,m \le 50$；
- 对于 $100\%$ 的数据，保证 $3 \le n \le 500$，$1 \le m \le 500$，$1 \le L_i \le 10^9$。


title: 「GLR-R3」立春

background:
  「从此雪消风自软，梅花合让柳条新」

---

  “明天就要返校了呢。”

  灰色的长发被身后的人儿慢慢地顺着，顺着，于假期最后一个慵懒的清晨醒来，与春日的第一抹阳光迷迷糊糊地耳语，她的目光随着点过窗外的鸟雀，停留在那丛褐色的光秃枝丫。

  “天依？”

  赤红色的眸子随之望去，片刻，静默。

  “如果我能告诉它，今天是立春，是春天的……”

  “那么它会抽芽，繁盛，会成为我们窗外或红或绿的美妙。”

  “——因为它本该如此，希望如此吧。”

---

  **立春** 「雏鸟站在悬崖上　展开了翅膀　地平线上的梦想　照进一缕光」

description:
由于天依刚睡醒，害怕第一题的题面就迷糊了大家，所以本题只有简要题意。~~（其实是实在编不下去了。）~~

设 $\sigma$ 为任意一个长度为 $n$ 的排列，$\tau(\sigma)$ 表示其中的逆序对个数，请求出

$$
\sum_\sigma 2^{\tau(\sigma)}
$$

对 $(10^9+7)$ 取模的结果。

inputFormat: 输入一行一个整数 $n$，表示排列的长度。

outputFormat: 输出一行一个整数，表示所求得的答案。


title: [COCI2011-2012#2] NAJBOLJIH 5

description: 给定 $8$ 个数字 $X_1,X_2,...,X_8$，从中选出 $5$ 个数字，使得这 $5$ 个数字的总和最大。输出这 $5$ 个数字的和以及它们的编号。$X_i$ 的编号为 $i$。

inputFormat: 输入共 $8$ 行，第 $i$ 行包含一个正整数 $X_i$。**保证所有 $X_i$ 互不相同**。

outputFormat:
输出共两行。

第一行包含一个整数，表示最大的总和。

第二行包含 $5$ 个整数，表示 $5$ 个数的编号，**按升序排序**。

hint:
#### 【数据范围】

对于 $100\%$ 的数据，$1 \le X_i \le 150$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $50$。

题目译自 **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #2](https://hsin.hr/coci/archive/2011_2012/contest2_tasks.pdf)** ___T1 NAJBOLJIH 5___。


title: [COCI2011-2012#2] OKRET

description:
给定一幅 $R \times C$ 的地图，其中 `.` 表示该格子能走，`X` 表示该格子不能走。判断该地图是否有死胡同。

如果一个格子满足上下左右四个格子中**只有一个格子能走**，那么这个格子就是死胡同。当然，不能走到地图外。

inputFormat:
输入的第一行包含两个正整数 $R,C$。

接下来 $R$ 行，每行包含 $C$ 个字符，描述这幅地图。

outputFormat: 如果地图中有死胡同，输出 $1$，否则输出 $0$。

hint:
#### 【数据范围】

对于 $100\%$ 的数据，$3 \le R,C \le 10$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $80$。

题目译自 **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #2](https://hsin.hr/coci/archive/2011_2012/contest2_tasks.pdf)** ___T2 OKRET___。


title: [COCI2011-2012#2] ZADAĆA

description:
给定 $N$ 个正整数 $A_1,A_2,...,A_N$ 和 $M$ 个正整数 $B_1,B_2,...,B_M$，求：

$$\gcd(\prod\limits_{i=1}^NA_i,\prod\limits_{i=1}^MB_i)$$

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

第二行包含 $N$ 个正整数 $A_i$。

第三行包含一个正整数 $M$。

第四行包含 $M$ 个正整数 $B_i$。

outputFormat: 输出一行，表示答案。**如果答案超过九位数，你只需输出它的最后九位即可**。

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

$\gcd(30,20) = 10$，因此答案为 $10$。

#### 【数据范围】

对于 $100\%$ 的数据，$1 \le N,M \le 1000$，$1 \le A_i,B_i \le 10^9$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $100$。

题目译自 **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #2](https://hsin.hr/coci/archive/2011_2012/contest2_tasks.pdf)** ___T3 ZADAĆA___。


title: [COCI2011-2012#2] KOMPIĆI

description:
给定 $N$ 个正整数 $A_1,A_2,...,A_N$，求有多少整数对 $(i,j)$，满足以下条件：

- $1 \le i < j \le N$
- **$A_i$ 和 $A_j$ 至少有一位数字是相同的（不一定要在相同的数位）**。

inputFormat:
输入的第一行包含一个正整数 $N$。

接下来 $N$ 行，每行包含一个正整数 $A_i$。

outputFormat: 输出一行一个整数，表示满足条件的整数对。

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

样例 1 中，满足要求的整数对为 $(1,3)$。

样例 2 中，满足要求的整数对为 $(1,3)$，$(1,4)$，$(2,3)$，$(3,4)$。

#### 【数据范围】

对于 $100\%$ 的数据，$1 \le N \le 10^6$，$1 \le A_i \le 10^{18}$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $120$。

题目译自 **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #2](https://hsin.hr/coci/archive/2011_2012/contest2_tasks.pdf)** ___T4 KOMPIĆI___。


title: [COCI2012-2013#5] LJESTVICA

background: Veronica 在音乐学院上学，她拿到了一张只有音符的乐谱，并且需要识别其所使用的音阶。

description:
在这个问题中，我们只考虑 A 小调和 C 大调。其中 A 小调音阶为 $\{ A,B,C,D,E,F,G \}$，C 大调音阶为 $\{ C,D,E,F,G,A,B \}$。

称每个音阶的第一个、第四个和第五个音为主调，你需要判断给定的乐谱是 A 小调或是 C 大调。

判断方法：

判断此乐谱中每个小节的第一个音符，是 A 小调的主调或是 C 大调的主调，最后判断哪个音阶的主音个数更多。

如果两者个数一样多，取整个乐谱的最后一个音符。如果最后一个音符为 A 则属于 A 小调，否则属于 C 大调。

inputFormat: 输入共一行，一个字符串，表示给出的乐谱，保证给出的乐谱中只包含 $\{ $`A`,`B`,`C`,`D`,`E`,`F`,`G`,`|` $\}$，其中 `|` 用来分割小节。

outputFormat: 输出共一行，一个字符串 `C-dur` 表示 C 大调，或 `A-mol` 表示 A 小调。

samples: AEB|C C-dur

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

两个小节的第一个音符分别为 `A` 和 `C`，由于两个音阶的主调个数相同，取后出现的 `C`，即 C 大调。

------------

**【数据范围】**

对于 $100\%$ 的数据，保证 $5\le$ 乐谱长度 $\le100$，且给出的乐谱合法。

------------

**【说明】**

本题分值按 COCI 原题设置，满分 $50$。

题目译自 [COCI2012~2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST #5](https://hsin.hr/coci/archive/2012_2013/contest5_tasks.pdf) _**T1 LJESTVICA**_ 。


title: [COCI2012-2013#5] ARHIPELAG

background: 一个受欢迎的旅游目的地国家坐落在一个惊人美丽的群岛上沐浴在阳光下。这个国家的居民以其众多的岛屿为傲。然而,全球气候变暖让他们非常担心:海平面上升导致干燥土地的流失迅速增加，这削弱了群岛的美丽。

description:
这个群岛的地图是一个 $R$ 行 $C$ 列的方阵。`X` 表示陆地，`.` 表示海。据估计，在 $50$ 年里，海水将淹没目前所有三面或四面环海的土地。

假设地图外全被海覆盖。你的任务是计算出 $50$ 年后的群岛地图(在所描述的海平面上升之后)。

因为那时的土地可能会比今天更少，你不需要打印出整个地图，而只是包含所有的土地的最小的矩形部分。

inputFormat:
第一行包含两个整数 $R$ 和 $C$，表示地图有 $R$ 行 $C$ 列；

第 $2$ 至 $R+1$ 行，目前群岛的地图，`X` 表示陆地，`.` 表示海。

outputFormat: 一个矩阵，表示 $50$ 年后群岛的地图。

hint:
**【数据范围】**

对于 $100\%$ 的数据，$1\le R,C \le 10$。

------------

**【说明】**

本题分值按 COCI 原题设置，满分 $80$。

题目译自 [COCI2012~2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST #5](https://hsin.hr/coci/archive/2012_2013/contest5_tasks.pdf) _**T2 ARHIPELAG**_。


title: [COCI2012-2013#5] HIPERCIJEVI

description: 在遥远的星系中，最快的运输方式是超级管道，它们将 $K$ 个站台连接在一起。从站台 $1$ 到达站台 $N$ 最少需要经过多少个站台?

inputFormat:
第一行，三个整数 $N,K,M$，分别表示站台数，每根超级管道连接的站台数和超级管道数。

接下来 $M$ 行，每行 $K$ 个正整数，表示这跟超级管道连接的站台编号。

outputFormat: 一行，一个正整数，表示最少需要经过的站台数，如果到达不了站台 $N$ ，则输出 `-1`。

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

有两种方法从站台 $1$ 走到站台 $9$：

$1\Rightarrow 3\Rightarrow 6\Rightarrow 9$ 或 $1\Rightarrow 5\Rightarrow 6\Rightarrow 9$

共经过了 $4$ 个站台，可以证明这是经过站台最少的情况。

------------

**【数据范围】**

对于 $100\%$ 的数据，$1\le N\le 10^5$，$1\le K,M\le 1000$。

------------

**【说明】**

本题分值按 COCI 原题设置，满分 $120$。

题目译自 [COCI2012~2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST#5](https://hsin.hr/coci/archive/2012_2013/contest5_tasks.pdf) _**T4 HIPERCIJEVI**_。


title: [COCI2012-2013#5] ROTIRAJ

description:
给定一个长度为 $N$ 的序列，将其划分，使每个子序列正好有 $K$ 个数（保证 $K$ 能被 $N$ 整除），有两种操作：

- 一、将每个序列中的数字向左/向右移动 $X$ 个位置

- 二、将整个序列向左/向右移动 $X$ 个位置

注意只有操作二才能改变子序列中的数字。

现给出所有操作后得到的序列和所有操作，请你求出原始序列。

inputFormat:
第一行三个正整数 $N,K,Q$，分别表示操作后序列的长度，每个子序列的长度和操作数。

接下来 $Q$ 行，每行两个正整数 $A_i$ 和 $X_i$，分别表示操作类型和移动的长度。$X>0$ 时表示向右移动，$X<0$ 时表示向左移动。

最后一行包含 $N$ 个整数 $Z_i$，表示操作后的序列。

outputFormat: 共一行，$N$ 个整数，表示原始序列。


title: [COCI2012-2013#5] MNOGOMET

description:
人们正在踢足球，分成两个队。每个球员都穿着队服，上面印着一个在队中独一无二的 $1$ 到 $N$ 间正整数，包括 $1$ 和 $N$。

对于每个玩家，我们知道他的精准度，知道他能把球传给的队友（集合 $F$ ），也知道能抢断他的对手（集合 $E$ ）。

当一名球员恰好接得一球之后的一秒后有以下情况中的一种会发生:

- 球员将球传给随机一名队友

- 随机一位对手将球夺过

- 球员试图向球门射门

如果球员试图射门，得分的概率等于他的精准度。无论射门成功与否，将球判给对方的 $1$ 号球员。

不同事件的可能性为比例 $|F|:|E|:1$，仅依赖于当前持球的玩家（ $|S|$ 代表集合 $S$ 的大小）。

“随机”一词指的是集合 $F$（或 $E$ ）中的所有玩家均有相同的概率从目前持球的球员那里拿到传的球。

不需计算传球的时间。

比赛以队伍一的球员 $1$ 控球开始，当一个球队进了 $R$ 个球，或者 $T$ 秒过去了，比赛结束（以两者中先发生的时间为准）。对于每一个可能的进球，计算出比赛以它结束的概率。

inputFormat:
第一行包含三个正整数 $N,R,T$，分别表示每个队伍中球员的人数，赢得比赛需要的进球数和比赛的时长。

接下来的 $N$ 行，描述队伍一的球员的信息；再下来的 $N$ 行，描述队伍二的球员的信息。

对于每一个球员的信息，一个实数 $p$，表示此球员的精准度；两个正整数 $N_f,N_e$，分别表示此球员的队友数和敌人数；接下来 $N_f$ 个数，为此球员的队友的编号；接下来 $N_e$ 个数，为此球员的敌人的编号。

注意：此球员的队友编号中不会包含此球员的编号。

outputFormat:
共 $R\times (N+2)$ 行，每行一个实数，表示比赛以此进球结束的概率。

先按照时间顺序输出队伍一的进球，再按照时间顺序输出第二队的。

输出的答案与标准答案相差 $\le 0.000001$ 即视为正确。


title: 「Wdoi-1.5」幻想乡游览计划

background:
（此为背景，可以跳过）

自从姬虫百百世开挖了妖怪之山山顶的虹龙洞后，一成不变的幻想乡又多了可以探索的地方。充满心机的、监视着幻想乡一切动静的八云紫自然需要对其内部了如指掌，以此来掌握对幻想乡的绝对控制权。作为八云紫的式神的八云蓝，则奉命探索这块区域。随行的还有八云蓝的式神，橙。

虹龙洞开采的目的是为了获取其中的龙珠，而龙珠分布在虹龙洞内的各个角落。为了能够滴水不漏地得到更多的龙珠，百百世挖出了纵横交错的矿道，连接着各处的龙珠采集点。矿道之间相互交错，构成了一张层层叠叠的网。八云蓝和橙的任务则是分别到达过虹龙洞内所有的龙珠采集点，采集足够多的信息，以完成八云紫对虹龙洞彻底的监控目标。

然而，身处于黑暗的洞穴内，诺大的虹龙洞的环境十分险恶。极度缺氧的环境使得探索虹龙洞并不是一件容易的事情，因此八云蓝与橙不可能在虹龙洞内探索过长的时间。所幸的是，八云蓝可以联系到八云紫；而拥有操控境界能力的紫，则可以利用隙间交换蓝和橙的位置。

八云紫已经私通菅牧典从大天狗那里得到了虹龙洞的内部结构图。为了尽量减少在虹龙洞内滞留的时间，八云一家需要设计出一套可行的方案。

description:
虹龙洞内可以抽象成一张有 $n$ 个点和 $m$ 条的无向连通图，图可能有自环和重边。

紫会用隙间的能力，将蓝和橙传送到虹龙洞的某一结点上。此处使用隙间所花费的时间忽略不计。输出格式中的 $S$ 即代表初始传送到的结点。

接下来橙和蓝将会分别进行移动。每单位时间，蓝或者橙可以移动到与她们所在结点**直接相连**的结点上，或者紫使用隙间能力交换蓝和橙的位置。请注意：在这一单位时间内**只有一个人（蓝或者橙或者紫）可以行动**，并且此处的交换操作也是花费时间的。

现在，八云蓝请你构造出一个方案，使得橙和蓝**各自都**能经过虹龙洞的每个结点至少 $1$ 次，并且最后**都**回到一开始所在的结点 $S$ 以结束此次游览。在「输出格式」中蓝说明了构造方案的格式，你只要按格式输出构造方案告诉蓝就行了。

inputFormat:
第一行两个整数 $n,m$，表示该图有 $n$ 个节点，$m$ 条边。

接下来 $m$ 行，每行两个整数 $u,v$，表示有一条连接 $u,v$ 的无向边。

outputFormat:
第一行输出两个整数 $S$ 和 $k$。其中 $S$ 的含义见题目描述，$k$ 表示你的方案的操作次数。

接下来 $k$ 行，你可以输出三种操作中的一种指导八云一家行动：
- 输出 `Ran u`，表示让蓝移动到结点 $u$；
- 输出 `Chen u`，表示让橙移动到结点 $u$；
- 输出 `Swap` 表示让紫交换橙和蓝的位置。

你需要保证你的构造方案合法。

容易发现，你的操作次数 $k$ 等于进行所有操作所花费的单位时间数。

hint:
### 样例解释

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{操作次数} & \textbf{蓝的位置} &\textbf{橙的位置} \cr\hline
0 & 1 & 1 \cr\hline
1 & 2 & 1 \cr\hline
2 & 2 & 3 \cr\hline
3 & 3 & 2 \cr\hline
4 & 1 & 2 \cr\hline
5 & 1 & 1 \cr\hline
\end{array}
$$

### 判分方式

**本题使用 Special Judge。**

对于每组数据，若你输出的方案不合法（含不合法的移动操作，或者蓝或橙没有经过每个结点至少 $1$ 次，或者最后蓝和橙没有在 $S$ 点），你的分数为零分。否则你的分数将这样计算：

- 当 $k \leq 4\cdot n$ 时，你将获得该测试点 $20\%$ 的分数；
- 当 $k \leq 3\cdot n$ 时，你将获得该测试点 $40\%$ 的分数；
- 当 $k \le \lfloor\frac{11}{4} \cdot n\rfloor$ 时，你将获得该测试点 $70\%$ 的分数；
- 当 $k \le \lfloor\frac{8}{3} \cdot n\rfloor$ 时，你将获得该测试点所有的分数。

### 数据范围

**本题采用捆绑测试，且仅有一个 subtask，总成绩取各测试点最低分。**

对于 $100\%$ 的数据，$3\leq n,m \leq 5\times 10^5$。

### 校验器

为了方便选手测试，在附件中我们下发了 `checker.cpp` 文件，选手可以编译该程序，并使用它校验自己的输出文件。但请注意它与最终评测时所使用的校验器并不完全一致。你也不需要关心其代码的具体内容。

编译命令为：`g++ checker.cpp −o checker -std=c++14`。

checker 的使用方式为：`./checker <inputfile> <outputfile>`，参数依次表示输入文件与你的输出文件。

若你输出的数字大小范围不合法，则校验器会给出相应提示。若你的输出数字大小范围正确，但方案错误，则校验器会给出简要的错误信息：

1. `A x`，表示进行到第 $x$ 个操作时不合法。
2. `B x`，表示操作执行完毕后蓝/橙没有经过每个节点至少一次，其中 $x=0$ 表示蓝，$x=1$ 表示橙。
3. `C x`，表示操作执行完毕后蓝/橙没有回到 $S$ 点。其中 $x=0$ 表示蓝，$x=1$ 表示橙。
4. `Illeagl Output`，表示你输出了错误的操作。

若你的方案正确，校验器会给出 `OK`。

保证在输入正确、方案合法的情况下 checker 的运行时间小于 1s。


title: 「Stoi2033」听见下雨的声音

background:
> 而我听见下雨的声音
> 想起你用唇语说爱情
> 幸福也可以很安静
> 我付出一直很小心
> 终于听见下雨的声音
> 于是我的世界被吵醒
> 就怕情绪红了眼睛
> 不舍的泪在彼此的脸上透明
> ——《听见下雨的声音》

description:
SNS 现在要举办一次比赛，总共有 $n$ 个项目，比赛分 $n$ 场举行，每个项目恰比赛一场。

校长希望比赛结果更多样，于是他决定从同学们之中找到 $2^n$ 位实力适当的选手，满足每个项目中每人的实力各不相同。

选定所有选手后，校长再进行适当的场次安排，且在进行每场比赛时对应比赛项目实力较强的一半选手晋级，其余人淘汰，不再参与之后的比赛，直到最后只剩下一位选手成为最终的冠军。

校长希望对于所有不同的比赛场次安排，最终可能夺冠的不同人数尽量多。现在他想要求出这个最大值，并且对于每个可能夺冠的选手找到一种安排每场比赛项目的方式使得 ta 最终夺冠。

因为校长公务繁忙，所以他要求作为学校首位 AKIOIer 的你来帮他完成这个任务。具体地，你需要先对 $i=1,2,\dots,n$ 给出第 $i$ 项的选手实力从强到弱排名（用选手编号的排列表示），再对每位可能夺冠的选手给出一个 $1,2,\dots,n$ 的排列表示安排的场次顺序让他最终夺冠。可见 **输出格式**。

inputFormat: 一行一个正整数 $n$。

outputFormat:
第一行输出一个数 $m$ 表示最多有多少人可能夺冠。

接下来 $n$ 行，第 $i$ 行输出 $2^n$ 个数依次表示第 $i$ 个项目实力从高到低的选手编号。

接下来 $m$ 行，每行先输出一个数 $x$ 表示一个可以夺冠的选手的编号，然后输出一个 $1,2,\dots,n$ 的排列表示一种场次安排的方式使得 $x$ 最终夺冠。

**请务必保证输出格式正确，否则 Special Judge 可能会出现错误。**

hint:
#### 样例解释

首先由于至多只有 $2$ 种场次安排方式，所以显然至多只有 $2$ 人可能夺冠。

对于选手 $1$，首先项目 $2$ 会淘汰 $4,2$，剩下选手 $1,3$，然后项目 $1$ 会淘汰 $3$，最终 $1$ 夺冠。

对于选手 $3$，首先项目 $1$ 会淘汰 $2,4$，剩下选手 $1,3$，然后项目 $2$ 会淘汰 $1$，最终 $3$ 夺冠。

#### 数据范围

本题共有 $11$ 个测试点，第 $i$ 个测试点满足 $n=i+2$。

每个测试点分值分别为 $6,7,8,8,8,8,8,11,11,12,13$。

本题提供 [Special Judge 源码](https://www.luogu.com.cn/paste/6q40493c) 和 checker.exe（见 **附件下载**）。以下是 checker.exe 可能的返回结果及其含义：

 + `Wrong answer.`：可能夺冠的人数 $m$ 有误。

 + `Invalid contestant number.`：出现不合法的选手编号，包括选手编号不为 $[1,2^n]$ 中的整数，或排名不为 $1,2,\dots,2^n$ 的排列。

 + `Invalid item number.`：出现不合法的项目编号，包括项目编号不为 $[1,n]$ 中的整数，或排名不为 $1,2,\dots,n$ 的排列。

 + `Contestant didn't won the first prize.`：某名选手并不能通过你给出的比赛场次安排夺冠。

 + `Accepted`：答案正确。


title: [AHOI2021初中组] 超市购物

background:
AHOI2021 初中组 T1

**你可以选择跳过背景部分。**

春的一天，正是乍暖还寒时候，狂风乍起。小可可裹紧了单薄的外衣，往小雪家中赶去。

“今天真不是个出门的时候啊！”小可可感叹道。

“但是我还有东西要买……你就陪我去下超市吧？”

在超市里，小雪一共买了 23.70 元的东西，最后却只付了 20.1 元，小可可见状很疑惑。

“超市对学生有优惠呗，最后会打八五折。”

“那也不可能是这个价啊？我想想……应该是 20.145 元才对。”

“超市结算的时候最后会去分化整，也就是说，以角作为付钱的最小单位，多的零头就不要了。”

description: 现在，假如小可可一共买了 $n$ 种类型的商品，第 $i$ 种商品的单价为 $a_i$ 元，买了 $b_i$ 件，最后打八五折，并且舍去多出的小于一角的零头，你能不能帮他算算实际要付的钱数？

inputFormat:
第一行一个正整数 $n$，表示商品的种类数。

下面 $n$ 行，每行一个**两位小数 $a_i$** 和一个整数 $b_i$，用空格隔开，分别表示第 $i$ 种商品的单价和购买量。**注意，输入中不会省略小数点后的零。**

outputFormat: 仅一行，一个**一位小数**，表示小可可在打折并去分后要付的实际元数。**注意，即使小数点后一位是 0，也要输出。**

samples:
见附加文件的 shopping3.in。
见附加文件的 shopping3.ans。

hint:
【样例 1 解释】

这就是【题目背景】中的例子。

【样例 2 解释】

小可可的原购买金额为 $3.00 \times 2 + 17.95 \times 1 + 0.10 \times 1 = 24.05$ 元，打八五折后为 $24.05 \times 85\% = 20.4425$ 元，去掉零头后为 $20.4$ 元。

【数据范围与提示】

**提示：如果你对浮点数不熟悉的话，请尽量利用整数完成。**

- 对于 $30\%$ 的测试点，保证 $n=1$；
- 对于另外 $30\%$ 的测试点，保证答案是整角；
- 对于 $100\%$ 的测试点，保证 $1 \le n \le 10$，$0.01 \le a_i \le 99.99$，$1 \le b_i \le 10$。


title: [COCI2011-2012#2] FUNKCIJA

description:
Mirko 写了如下的函数：

（C++）

```cpp
int fun() {
    int ret = 0;
    for (int a = X1; a <= Y1; ++a)
         for (int b = X2; b <= Y2; ++b)
             ...
                 for (int <N-th> = XN; <N-th> <= YN; ++<N-th>)
                     ret = (ret + 1) % 1000000007;
    return ret;
}

```

（Pascal）

```pascal
function fun: longint;
var
  ret: longint;
  a, b, ... , y, z: longint;
begin
  ret := 0;
  for a := X1 to Y1 do
    for b := X2 to Y2 do
      ...
        for <N-th> := XN to YN do
          ret := (ret + 1) mod 1000000007;
  fun := ret;
end;
```

_<N-th>_ 表示第 $N$ 个小写字母。每个 $X_i$ 和 $Y_i$ 可能表示外层循环的变量名，也可能表示一个 $\le 10^5$ 的正整数。例如 $X_3$ 可以是 $a$，$b$，也可以是一个整数常量。$X_i$ 和 $Y_i$ 中至少有一个会是整数常量。

计算这个函数的返回值。

inputFormat:
输入的第一行包含一个正整数 $N$。

接下来 $N$ 行的第 $i$ 行每行包含用空格分隔的 $X_i,Y_i$。如果 $X_i$ 和 $Y_i$ 都是整数常量，那么 $X_i \le Y_i$。

outputFormat: 输出一行一个整数，表示函数的返回值。

hint:
#### 【数据范围】

对于 $100\%$ 的数据，$1 \le N \le 26$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $150$。

题目译自 **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #2](https://hsin.hr/coci/archive/2011_2012/contest2_tasks.pdf)** ___T5 FUNKCIJA___。


title: [COCI2011-2012#2] RASPORED

description:
Mirko 的比萨店是城里最好的，镇上所有的居民每天午餐都吃比萨饼。而且 Mirko 的送货服务很快，送货时间可以忽略不计。但是 Mirko 只有一个小烤箱，一次只能烤一个比萨饼。

我们将城里的 $N$ 个居民从 $1$ 到 $N$ 编号，他们计划吃午餐的时间为 $L_i$，Mirko 需要为他们烘焙比萨的所需时间为 $T_i$。

如果一个居民在他计划吃午餐时间的前 $K$ 个时间单位收到了他的比萨饼，那么 Mirko 会得到 $K$ 元小费。相应地，如果一个居民在他计划吃午餐时间的后 $K$ 个时间单位才收到了他的比萨饼，那么 Mirko 必须向居民付款 $K$ 元。如果比萨饼准时送到，Mirko 不会得到小费，但是也不用付任何费用。

请你帮助 Mirko 安排一天的比萨烘焙顺序，使得他一天赚取的**总小费最大**。

**注意：**

1. 一天从时间单位 $0$ 开始，你可以认为这一天是无限长的。

2. 居民们有时会改变他们的 $T_i,L_i$。

inputFormat:
输入的第一行包含两个正整数 $N,C$，分别表示居民人数和比萨需求改变的数量。

接下来 $N$ 行，每行包含两个整数 $L_i,T_i$。

接下来 $C$ 行，每行包含三个正整数 $R_j,L_j,T_j$，分别表示要改变的居民编号、改变后的 $L_i$ 和改变后的 $T_i$。

outputFormat:
输出的第一行包含一个整数，表示未修改前 Mirko 能得到的最大总小费。

接下来对于每一个修改操作输出一行一个整数，表示这次修改后 Mirko 能得到的最大总小费。

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

最优的比萨烘焙顺序为 $(1,3,2)$。这样的话，第 $1$ 个比萨在第 $2$ 个时间单位送达，第 $3$ 个比萨在第 $5$ 个时间单位送达，第 $2$ 个比萨在第 $10$ 个时间单位送达。

第 $1$ 个比萨由于早送了 $8$ 个时间单位，所以 Mirko 得到了 $8$ 元小费；第 $2$ 个比萨由于迟送了 $1$ 个时间单位，所以 Mirko 需要付 $1$ 元；第 $3$ 个比萨由于迟送了 $4$ 个时间单位，所以 Mirko 需要付 $1$ 元。因此最大的总小费为 $3$。

经过第 $1$ 次修改后，比萨烘焙顺序没有变，小费变成了 $5,0,-3$。

经过第 $2$ 次修改后，比萨烘焙顺序变为 $(1,2,3)$，小费变成了 $5,0,-11$。

#### 【数据范围】

对于 $50\%$ 的数据，$1 \le T_i,T_j \le 10^3$。

对于 $100\%$ 的数据，$1 \le N,C \le 2 \times 10^5$，$0 \le L_i,L_j \le 10^5$，$1 \le T_i,T_j \le 10^5$，$1 \le R_j \le N$。

#### 【说明】

本题分值按 COCI 原题设置，满分 $150$。

题目译自 **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #2](https://hsin.hr/coci/archive/2011_2012/contest2_tasks.pdf)** ___T6 RASPORED___。


title: [COCI2016-2017#5] TUNA

description:
渔夫在昨晚捕到 $N$ 条金枪鱼。他准备将这些鱼卖给一个平台。

对于每一条鱼，平台会给出两个估测值 $P_1,P_2$。如果这两个值之差不超过 $X$，则取较大的值作为该条鱼的价值；否则如果差超过 $X$，则取另一个值 $P_3$。

现在给定 $N$ 条鱼的值（可能会有 $2$ 个或 $3$ 个），求所有鱼的总价值。

inputFormat:
第一行，一个整数 $N$，表示金枪鱼的数量。

第二行，一个整数 $X$。

接下来的若干行分为 $N$ 个部分用来表示每条鱼的信息。每部分的格式为下列二者之一：

- 该部分仅有唯一一行，该行包含两个整数 $P_1,P_2$。
- 该部分共有两行，第一行包含两个整数 $P_1,P_2$，第二行包含一个整数 $P_3$。

outputFormat: 输出所有鱼的总价值。


title: 「RdOI R3」毒水

description:
**这是一道 IO 交互题。**

现在你面前有 $n$ 瓶水，从 $1\sim n$ 编号，其中有 $1$ 瓶水有毒，你可以用一些小白鼠来进行判断。

但是你找的小白鼠中**有且仅有**一只**变异鼠**，**如果它喝的水中有毒水，那么它不会死亡。否则它会在 $59$ 秒内死亡。其它小白鼠如果喝了毒水将在 $59$ 秒内死亡，否则不会死亡**。

你需要在一分钟内找出这瓶毒水，因为测试已经花了 $59$ 秒，所以你的代码只能运行 $1$ 秒。

### 交互方式

首先你需要从标准输入读取两个整数 $n$，$maxk$，表示水的数量，以及你最多能找到的小白鼠个数。

若你需要 $k$ 只小白鼠，你需要向标准输出打印 $k+1$ 行，除了最后一行，每一行的格式为：`1 m B1 B2 ... Bm`，表示你找到一只小白鼠并让它喝 $B_1$ 号，$B_2$ 号，$\cdots$，$B_m$ 号这 $m$ 瓶中的水。你需要在最后写上一行：`2`，随后清空缓冲区，表示你不需要更多的小白鼠了。

下面是一些语言的刷新缓冲区操作：

- C++：`fflush(stdout)` 或 `cout.flush()`。
- C: `fflush(stdout)`。
- Java: `System.out.flush()`。
- Python: `stdout.flush()`。
- Pascal: `flush(output)`。
- 其他语言：请参考对应语言的帮助文档。

当然，如果 $k>maxk$，交互库会返回 `WA`、`RE`、`UKE` 或 `TLE`，同时该测试点不得分。

然后你需要从标准输入读取 $k$ 个整数 $R_1,R_2,\cdots,R_k;R_i\in\{0,1\}$。若 $R_i=0$ 代表第 $i$ 号小白鼠已死亡，否则代表第 $i$ 号小白鼠仍存活。

最后你需要从标准输出打印一个整数，表示毒水的编号。

**注意，请避免你的程序让小白鼠喝相同编号的水，交互库将返回 `Repeated poison.`**

inputFormat: 见**交互方式**。

outputFormat: 见**交互方式**。

hint:
### 样例说明

毒水的编号为 $2$，且第 $2$ 次和第 $10$ 次均为让小白鼠喝下 $2$ 号毒水，故这两次操作返回的结果为 $0$。其他操作由于让小白鼠喝的不是毒水，返回的结果为 $1$。

**样例仅为理解交互方式使用，可能不符合逻辑。**

---

### 数据范围

**本题采用捆绑测试。**

**注意：本题不存在一个 subtask 包含其他所有 subtask**。

| subtask | 分值 | $n$             | $maxk\ge$ |
| ------- | ---- | --------------- | ------- |
| $1$     | $1$  | $=1$            | $0$     |
| $2$     | $9$  | $\le 1000$      | $3000$  |
| $3$     | $20$ | $\le 1000$      | $30$    |
| $4$     | $30$ | $8\le n \le 16$ | $7$     |
| $5$     | $40$ | $\le 1000$      | $15$    |

---

### 注意

只有你向交互器发送 $2$ 操作时，交互器才会将你先前的 $1$ 操作的答案告诉你。也就是说，你不能在执行一次 $1$ 操作后立刻得到这次操作的返回结果。


title: [COCI2016-2017#5] Pareto

background:
二八定律提出：在任何一组东西中，最重要的只占其中一小部分，而其余尽管是多数，却是次要的。

例如，微软发现只需要修复 $20\%$ 的漏洞就能够减少 $80\%$ 的故障时间。再者，研究表明，$80\%$ 的财富都掌握在 $20\%$ 的人的手中。

description: 给定 $N$ 个银行客户的存款。求两个实数 $A,B$，使得 $A\%$ 的客户恰好拥有存款总额的 $B\%$，且 $B-A$ 最大。

inputFormat:
第一行，一个整数 $N$，表示银行客户的数量。

接下来的一行，共 $N$ 个整数，依次表示每个客户的存款。

outputFormat:
第一行，输出所求的 $A$ 值。

第二行，输出所求的 $B$ 值。

保证对于最大的 $B-A$，最终答案唯一。

若输出与答案相差不超过 $0.01$，则算作答案正确。

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

不难发现，存款金额为 $200$ 的客户拥有存款总额的约 $66.666667\%$。

**【数据规模与约定】**

对于 $100\%$ 的数据，$1 \le N \le 3 \times 10^5$，所有客户的存款金额都是不超过 $10^8$ 的非负整数。

**【提示与说明】**

**题目译自 [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #5](https://hsin.hr/coci/archive/2016_2017/contest5_tasks.pdf) _T2 Pareto_。**

**本题分值按 COCI 原题设置，满分 $80$。**


title: [COCI2016-2017#5] Unija

description: 给定 $N$ 个几何中心位于平面直角坐标系原点的矩形。将这 $N$ 个矩形进行涂色，求被涂色的总面积。

inputFormat:
第一行，一个整数 $N$。

接下来的 $N$ 行，每行两个偶数 $X,Y$，分别表示矩形的宽和长（分别对应横向长度和纵向长度）。

outputFormat: 输出被涂色的总面积。

hint:
**【样例 1 图解】**

![](https://cdn.luogu.com.cn/upload/image_hosting/g1w4hrf7.png?x-oss-process=image/resize,m_lfit,h_389,w_485)

**【数据规模与约定】**

对于 $40\%$ 的数据，输入的整数均小于 $3333$。

对于 $50\%$ 的数据，没有具有包含关系的矩形。

对于 $100\%$ 的数据，$1 \le N \le 10^6$，$2 \le X,Y \le 10^7$。

**【提示与说明】**

**题目译自 [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #5](https://hsin.hr/coci/archive/2016_2017/contest5_tasks.pdf) _T3 Unija_。**

**本题分值按 COCI 原题设置，满分 $100$。**


title: [COCI2016-2017#5] Ronald

description:
一个国家的 $N$ 个城市通过双向航线相连。

规定一次操作为：

- 选定其中一个城市
- 开设该城市到其它所有城市的航线，同时取消该城市的原有航线

请问是否存在一种操作方式，使得每两个城市之间都存在直达航线（操作次数不限）。

inputFormat:
第一行，一个整数 $N$，表示城市的数量。

第二行，一个整数 $M$，表示初始的航线数量。

接下来的 $M$ 行，每行两个不相等的整数，表示该航线连接的两个城市。

outputFormat: 若存在符合题意的操作方式，则输出 `DA`。否则输出 `NE`。

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

选定城市 $1$（即开通 $1-2$ 的航线）即可。

**【样例 3 解释】**

原有航线为 $1-3$ 和 $2-4$。

第一次选定城市 $1$。此时航线 $1-3$ 被取消，同时新开设航线 $1-1,1-2,1-4$。

第二次选定城市 $3$。此时新开设航线 $3-1,3-2,3-4$。

**【数据规模与约定】**

对于 $100\%$ 的数据，$2 \le N \le 1000$，$0 \le M \lt \dfrac{N(N-1)}{2}$。

**【提示与说明】**

**题目译自 [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #5](https://hsin.hr/coci/archive/2016_2017/contest5_tasks.pdf) _T4 Ronald_。**

**本题分值按 COCI 原题设置，满分 $120$。**