title: [BalticOI 2014 Day1] Sequence

description: 现在有 $K$ 个连续正整数，每个整数你只能看见其中一位数字，求最开始的数 $N$ 的最小值。

inputFormat:
第一行一个整数 $K$ 代表数列长度。
第二行 $K$ 的整数代表你能看见的数字。

outputFormat: 一行一个整数代表 $N$ 的最小值。

hint:
#### 样例说明

对于样例 $1$，使得 $N$ 最小的数列为 $47,48,49,50,51,52$，$N$ 的最小值为 $47$。

#### 数据规模与约定

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

- Subtask 1（9 pts）：$N,K \le 1000$。
- Subtask 2（33 pts）：$K \le 1000$。
- Subtask 3（25 pts）：给定的数位都相等。
- Subtask 4（33 pts）：无特殊限制。

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

**本题强制 O2 优化。**

#### 说明

翻译自 [BalticOI 2014 Day1 C Sequence](http://www.boi2014.lmio.lt/tasks/sequence-en.pdf)。


title: [COCI2015-2016#5] ZAMKA

type: P

description:
给定三个整数 $L,D,X$，你需要找到两个整数 $N,M$，使得：

- $N$ 为满足条件的最小整数，$L\le N\le D$ 且 $N$ 的各位数字之和为 $X$；
- $M$ 为满足条件的最大整数，$L\le M\le D$ 且 $M$ 的各位数字之和为 $X$。

保证 $N,M$ 一定存在。

inputFormat:
输入共三行。

第一行一个整数 $L$，第二行一个整数 $D$，第三行一个整数 $X$。

outputFormat:
输出共两行。

第一行为一个整数 $N$，第二行为一个整数 $M$。

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

对于 $100\%$ 的数据，$1\le L\le D\le 10^4$，$1\le X\le 36$。

#### 说明

**题目译自 [COCI2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #5](https://hsin.hr/coci/archive/2015_2016/contest5_tasks.pdf) *T1 ZAMKA***。


title: [COCI2015-2016#5] MULTIGRAM

description:
定义由多个相同的单词首尾相连组成的字符串为复词，定义组成这个字符串的单词为词根。你需要判断它是否为复词。如果是，你需要找到其中第一个出现的词根。如果有多种可能的词根，请输出长度最短的。不是复词则输出 `-1`。

**注意：如果两个字符串经过字母顺序的改变后能够完全相同，则认作同一个单词。**

inputFormat: 输入一行一个由小写字母组成的字符串。

outputFormat:
如果给定的字符串不是复词，则输出 `-1`。

否则输出第一个出现的长度最短的词根。

samples: aaaa a

samples: bbabab bba

hint:
#### 样例解释

##### 样例 $1$

注意到 `aa` 也是第一个出现的词根，但 `a` 是最短的。

##### 样例 $2$

这个字符串仅由单词 `ab` 构成，不是复词。

##### 样例 $3$

字符串由两个相同的单词 `bba` 和`bab` 组成，第一个出现的为 `bba`。

#### 数据规模与约定

对于 $100\%$ 的数据，字符串的长度不超过 $10^5$。

#### 说明

**题目译自 [COCI2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #5](https://hsin.hr/coci/archive/2015_2016/contest5_tasks.pdf) *T2 MULTIGRAM***。


title: [COCI2015-2016#5] PERICA

description:
给定一个长度为 $N$ 的序列 $a_1,a_2,\dots,a_N$。

请你求出所有 $K$ 个数的组合中最大数之和 $\bmod\ 10^9+7$ 的结果。

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

第二行一个长度为 $N$ 的序列 $a_1,a_2,\dots, a_N$。

outputFormat: 输出一行一个整数，为所有 $K$ 个数的组合中最大数之和 $\bmod\ 10^9+7$ 的结果。


title: [COCI2015-2016#5] POPLAVA

description:
有一个由 $N$ 列组成的柱状图，从左至右的柱子高度分别为 $h_1,h_2,\dots,h_N$。

现在你需要向其中储水，柱状图的容量定义为使得水的结构“稳定”时最多所能储水的量。即水在重力作用下不会流动。下图为一个稳定的例子。

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

具体来说，我们设从左至右每一列上水的高度为 $v_1,v_2,\dots,v_N$。记 $s_i=h_i+v_i$ ，当满足下列条件时为稳定状态：

- 对于任意的 $i\geq2$，当$v_i>0$ 时，有$s_i\le s_{i-1}$；

- 对于任意的 $i\le N-1$，当$v_i>0$ 时，有$s_i\le s_{i+1}$；

- $v_1=v_N=0$。

现在你需要选择一个 $1\sim N$ 的排列作为柱子 $h_1,h_2,\dots,h_N$ 的高度，使得柱状图的容量为 $X$。如果不存在，则输出 `-1`。如果有多种方案，输出任意一种即可。

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

outputFormat:
如果方案不存在，输出 `-1`；

否则输出一行 $N$个整数，为 $h_1,h_2,\dots,h_N$。**输出任意一种方案即可，本题使用 SPJ。**


title: [COCI2015-2016#5] OOP

description: 给定 $N$ 个单词和 $Q$ 个模板，一个模板由一个 `*` 和一些小写字母组成。一个模板覆盖了一个单词当且仅当将 `*` 替换为任意字母后，模板和单词能够完全重合。对于每个模板，求出它能够覆盖多少个单词。

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

接下来的 $N$ 行，每行一个小写字母组成的单词。

接下来的 $Q$ 行，每行一个模板。

以上读入的字符总数少于 $3\times 10^6$。

outputFormat: 输出共 $Q$ 行。表示每个模板能够覆盖的单词的个数。

samples:
5 3
eedecc
ebdecb
eaba
ebcddc
eb
e*
*dca
e*c

hint:
#### 数据规模与约定
对于 $40\%$ 的数据，$1\le N,Q\le 10^3$；
对于 $100\%$ 的数据，$1\le N,Q\le 10^5$。

#### 说明

**题目译自 [COCI2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #5](https://hsin.hr/coci/archive/2015_2016/contest5_tasks.pdf) *T5 OOP***。


title: [BalticOI 2014 Day2] Portals

description:
给定一个 $R\times C$ 的迷宫，每个格子都有一种方块：

- `#` 墙，不可以走，不可以穿过
- `.` 路，可以走
- `S` 出生点，玩家从这里开始走，只有一个
- `C` 终点，玩家要到达这里，只有一个

现在要对迷宫进行扩容，周围要增加一个方块 `#`，变成 $(R+2)\times (C+2)$ 的迷宫。

并且在任何时候，它都可以向上、左、下、右四个方向中的一个发射传送门。当一个传送门被发射，它会一直向发射的方向飞行，直到碰触到墙壁。这时，传送门会被放置在这堵墙上。

走一格需要 $1$ 的时间，穿梭传送门也需要 $1$ 的时间。

求从出生点到终点最少需要多少时间。

如果很难理解题意，请配合样例进行理解。

inputFormat:
第一行两个整数 $R,C$ 代表迷宫大小。
接下来 $R$ 行每行 $C$ 个字符代表迷宫。

outputFormat: 一行一个整数代表到达终点的最小时间。

hint:
#### 样例说明

对于样例 $1$，我们把迷宫模拟出来并且在周围加上 `#` 之后，如下图所示：

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

人形物体为 `S`，蛋糕形物体为 `C`。

如图所示，至少需要 $4$ 的时间。

#### 数据规模与约定

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

- Subtask 1（11 pts）：$R,C \le 10$。
- Subtask 2（20 pts）：$R,C \le 50$。
- Subtask 3（20 pts）：$R,C \le 200$，每个 `.` 周围都至少有一个 `#`。
- Subtask 4（19 pts）：$R,C  \le 200$。
- Subtask 5（30 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le R,C \le 1000$。

**本题强制 $O2$ 优化。**

#### 说明

翻译自 [BalticOI 2014 Day2 B Portals](https://boi.cses.fi/files/boi2014_day2.pdf)。


title: [BalticOI 2014 Day2] Senior Postmen

background: # 滥用本题评测将被封号

description:
给定一张 $N$ 点 $M$ 边的无向图，求从中找出若干个环，使得：

- 这些环没有重复的边。
- 这些环覆盖了所有的点和边。

inputFormat:
第一行两个整数 $N,M$ 代表点数和边数。
接下来 $M$ 行每行两个整数 $u,v$ 代表一条边。

outputFormat: 若干行每行若干个整数代表一个环。

hint:
#### 样例说明

对于样例 $1$：

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

#### 数据规模与约定

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

- Subtask 1（38 pts）：$N \le 2000$，$M \le 10^5$。
- Subtask 2（17 pts）：$N,M \le 10^5$。
- Subtask 3（45 pts）：无特殊限制。

对于 $100\%$ 的数据，$3 \le N,M \le 5 \times 10^5$。

**本题使用 Special Judge。**

感谢 spj 提供者 @[tiger2005](https://www.luogu.com.cn/user/60864)。

#### 说明

翻译自 [BalticOI 2014 Day2 C Senior Postmen](https://boi.cses.fi/files/boi2014_day2.pdf)。


title: [COCI2015-2016#5] PODNIZOVI

description:
给定一个长度为 $N$ 的数组 $a_1,a_2,\dots,a_N$。令 $s_1,s_2,\dots,s_q$ 为这个数组所有的非空子序列，且 $q=2^n-1$。

关于字典序：如果两个数组 $A$ 和 $B$ 的第一个不相同的位置为 $i$，且 $A_i<B_i$；或 $A$ 是 $B$ 的严格前缀（即不能相等），则 $A$ 的字典序小于 $B$。

我们将由 $v_1,v_2,\dots,v_p$ 组成的数组的 hash 值定义为：

$$h(s)=(v_1\times B^{p-1}+v_2\times B^{p-2}+\dots +v_{p-1}\times B+v_p) \bmod M$$

其中 $B,M$ 是给定的整数。

对于给定的整数 $K$，求 $h(s_1),h(s_2),\dots,h(s_K)$ 的值。

inputFormat:
第一行四个整数 $N,K,B,M$。

第二行 $N$ 个整数 $a_1,a_2,\dots,a_N$。

outputFormat: 输出共 $K$ 行，第 $i$ 行为 $h(s_i)$ 的值。


title: [BOI2004] REPEATS

description:
如果字符串 $s$ 满足：

- 对于一个数对 $(k,l)~(k\ge 1,l\ge 1)$。
- $s$ 是由 $k$ 个长度为 $l$ 的字符串 $t$ 拼接成的。

那么 $s$ 就被称作是一个 $(k,l)\text{ - repeat}$ 串。

如 $s=\tt abaabaabaaba$ 就是一个 $t=\tt aba$ 的 $(4,3)\text{ - repeat}$ 串。

对于一个字符串 $u$（仅含字符 $\texttt a$ 和 $\texttt b$），你需要找出其中的一段是 $(k,l)\text{ - repeat}$ 串的**连续的**字符串，使 $k$ 尽可能大。

例如 $u=\tt babb\underline{abaabaabaaba}b$，其中划线部分就是一个 $(4,3)\text{ - repeat}$ 串，这时 $k$ 的值最大。

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

接下来 $n$ 行，每行一个字符（$\texttt a$ 或 $\texttt b$），表示这个字符串。

outputFormat:
第一行一个数 $k$。

第二行一个数 $l$。

第三行一个数 $p$，表示这个 $(k,l)\text{ - repeat}$ 串的开始位置（位置从 $1$ 开始）。

**如果有多种情况，输出任意一种。**

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

对于 $100\%$ 的数据，有 $1\le n\le 5\times 10^{4}$，$u_i\in\{\tt a,b\}$。

#### 说明

译自 [BalticOI 2004 Day2 A REPEATS](https://boi.cses.fi/files/boi2004_day2.pdf)

特别感谢 @[Sprague_Garundy](https://www.luogu.com.cn/user/764746) 提供的 SPJ！


title: [BOI2004] RECTANGLES

description:
平面上有 $n$ 个矩形。矩形边平行于坐标轴。这些长方形可以重叠、重合或相互分离。它们的顶点坐标 $(x,y)$ 中，$x,y$ 都是非负整数，横坐标不超过 $x_{\max}$，纵坐标不超过 $y_{\max}$。

$A$ 点位于 $(0,0)$，若 $C(x_{\max},0),D(0,y_{\max}),E(x_{\max},y_{\max})$，则 $B$ 点位于线段 $CE$ 或 $DE$ 上。

线段 $AB$ 可能与矩形相交（即使只与一个矩形**顶点**相交，也视为相交）。

你需要找到一个 $B$，使与线段 $AB$ 相交的矩形尽可能**多**。

inputFormat:
第一行三个整数 $x_{\max},y_{\max},n$。

接下来 $n$ 行，每行四个整数，分别表示第 $i$ 个矩形的左下角坐标与右上角坐标。

outputFormat:
一行三个整数，分别为：

- 最多的相交矩形数。
- 此时 $B$ 点坐标。

如果有多种方案，输出**任意一种**。

hint:
#### 样例 1 说明

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

输出也可以为 `5 22 11`。

#### 数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le 10^4$，$0\le x_{\max},y_{\max}\le 10^9$。

#### 说明

译自 [BalticOI 2004 Day2 B RECTANGLES](https://boi.cses.fi/files/boi2004_day2.pdf)

#### 特别感谢

感谢 @[tiger2005](https://www.luogu.com.cn/user/60864) 提供的 SPJ！


title: [BOI2004] CAR PARK

description:
举办 BOI2004 的青年旅社有一个停车场，由 $6\times 6$ 的方格组成。行从 $1$ 到 $6$ 从上到下连续编号；列从左到右，编号方法相同。

只有停车场第三排第六列有一个出口。

在那个停车场上，有 $n$ 辆停着的车。你的车在这些车中，但不幸的是，由于你的车被另一辆车挡住了，你的汽车不能直接出去。你与你的朋友可以移动汽车。但是无论是你自己的车还是其他车都不能转向或转弯。

你需要确定使你的 $2\times 1$ 方格车（编号为 $1$）离开停车场所需的最小步数。一步意味着把一辆车移到一个正方形。其他车辆不得驶离停车场。

只有两种车：

- $2\times 1$
- $3\times 1$

汽车只能沿它长的一条边所在的轴移动。

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

接下来 $n$ 行，每行四个数 $l,opt,x,y$，分别表示汽车长度、停放的方向、汽车左上角坐标。

outputFormat:
仅一行一个数，即使车离开停车场所需的最小步数。

如果不能，输出 `-1`。

hint:
#### 样例 1 说明

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

步骤（编号 $+$ 移动步骤）：

- $4\gets\gets\gets$
- $2\to$
- $6\uparrow$
- $3\uparrow$
- $8\gets\gets$
- $5\downarrow\downarrow\downarrow$
- $7\downarrow\downarrow$
- $1\to\to\to\to\to$

#### 数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le 16$，$opt\in\{0,1\}$，$l\in\{2,3\}$，$1\le x,y\le 6$。

#### 说明

译自 [BalticOI 2004 Day2 C CAR PARK](https://boi.cses.fi/files/boi2004_day2.pdf)


title: [BalticOI 2014 Day1] Cop and Robber

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

### 请使用 C++14/C++17 提交以避免不必要的 CE。

### 你需要将你的函数包裹在 `extern "C" { }` 中，具体的，一种包裹方式如下：

```cpp
extern "C" {
	const int N = 500;
	int start(int n, bool a[N][N]) {
		// ...
	}
	int nextMove(int x) {
		// ...
	}
}
```

description:
警察抓小偷，每名警察会选择一个街角进行把守，每次警察可以选择不动或者挪动到相邻的角落，小偷初始也在一个街角，因为他知道地图，所以他会选择最好的策略进行移动，但是小偷不能原地不动。

每一轮先是警察进行移动，然后是小偷进行移动，有下面两种结局：

1. 小偷能够一直躲避警察
2. 在一个街角上，小偷和警察相遇了，小偷被逮捕了

求警察能不能抓到小偷，能的话输出最小轮数。

您的代码必须以小偷一方为优胜策略方。

#### 交互策略

你需要写两个函数与交互器进行交互，函数原型分别为：

```cpp
int start(int N, bool A[MAX_N][MAX_N]);
int nextMove(int R);
```

 - 其中 `start(N, A)`传入以下参数：

   - $N$——街角的数量（街角以 $0$ 到 $N - 1$ 编号）；

   - $A$——一个二维数组描述小巷：对于所有的 $0 \le i,\,j \le N-1$，若 $i$ 与 $j$ 不连通，则 $A[i,j]=\texttt{false}$，否则 $A[i,j]=\texttt{true}$

    所有小巷都是双向的（即对于所有 $i$ 和 $j$，$A[i,j]=A[j,i]$），并且不会出现自环（即对于所有 $i$，$A[i,i]=\texttt{false}$）。此外，你可以假设警察总能从其他街角通过小巷到达一个街角。

 如果警察可能在由参数描述的地图上抓到强盗，函数`start`应该返回警察与强盗相遇的街角编号。否则返回 $-1$。

 - 而 `nextMove(R)` 传入参数 $R$，表示当前强盗的所在的街角编号。该函数应返回这次移动之后警察所在的街角编号。

函数 `start` 必定会在第一次调用函数 `nextMove` 调用一次。如果 `start` 返回了 $-1$，那么 `nextMove` 将不会被调用。否则，`nextMove` 会被反复调用直到追捕行动结束。更确切地说，只要满足以下情况之一，程序必须终止：

 - `nextMove` 返回了一个不合法的移动；

 - 强盗能够一直躲避警察；

 - 强盗被抓住了。

hint:
#### 样例说明

对于样例 $1$，图如下图所示：

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

函数调用过程如下：

|函数调用|函数返回|
|:-:|:-:|
|`start(4, [[0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]])`|`3`|
|`nextMove(1)`|`3`|
|`nextMove(0)`|`0`|

#### 数据规模与约定

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

- Subtask 1（16 pts）：无重边。
- Subtask 2（14 pts）：地图为网格形，如下：

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

- Subtask 3（30 pts）：$2 \le N \le 100$。
- Subtask 4（40 pts）：$2 \le N$。

对于 $100\%$ 的数据，$1 \le N \le 500$。

感谢交互库和 spj 作者 @[tiger2005](https://www.luogu.com.cn/user/60864)。

**本题强制 $O2$ 优化。**

#### 说明

翻译自 [BalticOI 2014 Day1 A Cop and Robber](https://boi.cses.fi/files/boi2014_day1.pdf)。


title: [COCI2007-2008#6] CESTARINE

description:
Luka 的 $n$ 辆卡车行驶在一辆高速路上。高速路上有许多出入口。我们认为相同编号的出入口在同一位置。

开进高速路后，司机会收到一张写着他入口号的单子。驶出时，驾驶员支付的通行费等于出入口号的绝对差。

Luka 是一个爱贪小便宜的人。他发现，即使他们的路线不重叠，司机们可以在高速路上交换他们的单子。

但是，不能再同一位置的出入口进行上高速与下高速。

请你编程求出最少的通行费。

inputFormat:
第一行，一个正整数 $n$，表示卡车的个数。

接下来，$n$ 行，每行两个正整数，$x_i, y_i$， 表示入口和出口的编号。

outputFormat: 第一行，一个正整数 $ans$，表示最少的通行费。

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

最少的通行费为 $ |65−60| + |10−3| + |25−45| = 32$。

#### 数据规模及约定

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le x, y \le 10^6$，$x \not= y$。

#### 提示
请使用 $64$ 位整数类型（在 C / C++ 语言中为 `long long`，在 Pascal 语言中为 `int64`），否则可能会导致答案错误（即 Wrong Answer）。

#### 说明
- 本题满分 $80$ 分。
- 本题默认开启 O2 优化开关。
- 题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #6](https://hsin.hr/coci/archive/2007_2008/contest6_tasks.pdf) T6 CESTARINE，译者 @[tearing](https://www.luogu.com.cn/user/219791)。


title: 「EZEC-3」造房子

background: pigstd 要去造房子了。

description:
pigstd 有 $a$ 个 A 材料和 $b$ 个 B 材料，造**第** $i$ 层楼需要 $i$ 个 A 材料与 $i$ 个 B 材料。

但是 pigstd 觉得房子不够高，于是他拿出了 $c$ 块钱，每块钱都可以用来买 $1$ 个 A 材料或者 $1$ 个 B 材料。

现在 pigstd 想知道，他最多能建多少层楼的房子。

inputFormat: 第一行三个整数 $a,b,c$。

outputFormat: 一行一个整数，表示 pigstd 最多能建多少层楼的房子。


title: [BalticOI 2013 Day1] Palindrome-Free Numbers

description:
我们定义回文串为正着读反着读都一样的数字串，如果一个数字串的一个长度大于 $1$ 的子串也为回文串的话，那么我们也定义这个数字串为回文串。

顾名思义，不是回文串的数字串为非回文串。

给定 $a,b$，求区间 $[a,b]$ 中有多少个数字串为非回文串。

inputFormat: 一行两个整数 $a,b$ 代表这个区间。

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

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

对于 $100\%$ 的数据，$0 \le a \le b \le 10^{18}$。
对于其中的 $25\%$ 的数据，$b-a \le 10^5$。

#### 说明

翻译自 [BalticOI 2013 Day1 B Palindrome-Free Numbers](https://boi.cses.fi/files/boi2013_day1.pdf)。


title: [BalkanOI2011] trapezoid

description:
考虑两条水平的直线，这两条线之间会有 $N$ 个梯形。

如果两个梯形不相交，则称他们在一个独立集内。

您需要求出最大的独立集大小和这种独立集的个数。

由于独立集的个数可能很多，请输出其 $\bmod\ 30013$ 的值。

inputFormat:
第一行为一个整数 $N$。

接下来 $N$ 行，每行四个整数 $a_i,b_i,c_i,d_i$，分别表示第 $i$ 个梯形的左上，右上，左下和右下顶点。

outputFormat:
仅一行两个整数，表示最大的独立集大小和这种独立集的个数。

由于独立集的个数可能很多，请输出其 $\bmod\ 30013$ 的值。

hint:
#### 样例解释
下面这个图不怎么准确，但是应该够用：

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

#### 数据范围及限制
- 对于 $50\%$ 的数据，保证 $N\le 5\times 10^3$。
- 对于 $100\%$ 的数据，保证 $1\le N\le 10^5$，$1\le a_i,b_i,c_i,d_i\le 10^9$，没有两个梯形具有相同的顶点。

#### SPJ 计分标准
如果您只回答对了第一个问题，得该测试点 $40\%$ 的分数。

所以，如果您只会第一个问题，也请在第二个问题瞎输出一点。

#### 说明
本题译自 [Balkan Olympiad in Informatics 2011](http://www.boi2011.ro/boi2011/) [Day 2](http://www.boi2011.ro/boi2011/?pagina=probleme) [T3 trapezoid](http://www.boi2011.ro/resurse/tasks/trapezoid.pdf)。


title: [BalticOI 2013 Day1] Ball Machine

description:
给定一棵树，在根节点放一些球，如果下方有空位，那么它就会往下滚到下面的节点，如果有多个节点选择，它会选择 **以其（即后文中提到的儿子节点）为根节点的子树中标号最小值最小** 的儿子节点。

从一个位置上拿走球，上面的球也会滚下来。

每次给定一些操作，分别为在根节点放若干个球，和把某个节点的球拿走，求最后的结果。

inputFormat:
第一行两个整数 $N,Q$ 代表树的节点数和操作数。
这 $N$ 个节点编号为 $1$ 到 $N$。
接下来 $N$ 行每行一个整数第 $i$ 行代表第 $i$ 个节点的父节点。
接下来 $Q$ 行每行两个整数 $opt,num$：

- 如果 $opt=1$，代表在根节点放 $num$ 个球。
- 如果 $opt=2$，代表撤掉 $num$ 节点的球。

outputFormat:
每次操作后都需要输出一个结果：

- 如果 $opt=1$，输出最后一个球落到了哪里。
- 如果 $opt=2$，输出撤掉那个球会有多少个球滚下来。

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

对于 $100\%$ 的数据，$1 \le N,Q \le 10^5$。
对于其中 $25\%$ 的数据，每个节点的儿子节点数只可能为 $0$ 个或 $2$ 个，且所有叶子节点到根节点的距离相同。
对于另外 $30\%$ 的数据，$opt=2$ 的操作输出的总为 $0$。
对于另外 $40\%$ 的数据，只能一个 $opt=1$ 的操作。

#### 说明

翻译自 [BalticOI 2013 Day1 A Ball Machine](https://boi.cses.fi/files/boi2013_day1.pdf)。


title: 「EZEC-4」括号

background: > 离景似是昨日，转眼却已经年$\newline$ 往事依旧，物是全非

description:
给一个由小括号组成的序列和 $n$ 个括号串，要你在序列中匹配允许不连续的子串。

母序列的每个括号最多被匹配一次。

一种可能的不连续子串匹配方式为 ```)()(``` 中匹配 ``` ))(``` 。

每个括号串有一个值 $v$，代表对这个串每匹配一个括号得到的价值。

每个括号串均可以多次匹配，可以随时停止匹配，但是不能在未匹配完一个括号串的情况下开始匹配其他括号串。

注意如果你跳过了母序列的某几个括号去匹配后面的，那么你将不能返回前面继续进行匹配。

求匹配能得到的最大值。

inputFormat:
第一行一个整数 $n$，表示括号串的个数。

第二行一个字符串 $k$，表示给出的母序列。

接下来 $n$ 行，每行一个括号串 $a$ 和一个数字 $v$。在这 $n$ 行中，第 $i$ 行的字符 $a_i,v_i$ 表示一个存在的括号串以及匹配这个括号串内一个括号所能得到的价值。

outputFormat: 一个数 $r$，表示能取得的最大值。


title: [BalticOI2013] Brunhilda’s Birthday

description:
有一个整数 $n$ 以及一个长度为 $m$ 的素数表 $p$。

您可以进行任意多次操作，每一次操作时，您选择一个素数 $p_i$，这会使得 $n\to \lfloor \frac{n}{p_i}\rfloor\times p_i$。

您的目标是求出使得 $n$ 变为 $0$ 的最小操作数，如果不可能变为 $0$，请输出 `oo`。

为了增加难度，您需要回答 $Q$ 组 $n$。

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

接下来一行 $m$ 个整数 $p$。

接下来 $Q$ 行，一行一个整数 $n$，表示每一次询问给出的 $n$。

outputFormat: 对于每一个询问，求出使得 $n$ 变为 $0$ 的最小操作数，如果不可能变为 $0$，请输出 `oo`。

hint:
#### 数据范围及限制
- 对于 $20$ 分的数据，保证 $m,n,Q\le 10^4$。
- 对于另外 $20$ 分的数据，保证 $Q=1$。
- 对于 $100\%$ 的数据，保证 $1\le m,Q\le 10^5$，$2\le p_i\le 10^7$ 且 $p_i$ 为素数，$1\le n\le 10^7$。

#### 说明
本题译自 [Baltic Olympiad in Informatics 2013](https://boi.cses.fi/tasks.php) [Day 2](https://boi.cses.fi/files/boi2013_day2.pdf) T1 Brunhilda’s Birthday。

因为译题人找不到合适的设置，所以本题满分 $110$ 分。


title: [BalticOI 2013 Day1] Pipes

description:
给定一个 $N$ 点 $M$ 边的无向图，**保证图连通**。现在每个点都有一定量的水，现在可以在一条边上进行操作：

- 让水流出：给定 $d$，假设长度为 $m$，流的时间为 $s$，那么总共失水速度为 $\dfrac{2dm^3}{s}$，这条边两边的每个点的失水速度为 $\dfrac{dm^3}{s}$。
- 让水流进：给定 $p$，假设长度为 $m$，流的时间为 $s$，那么总共得水速度为 $\dfrac{2pm^3}{s}$，这条边两边的每个点的得水速度为 $\dfrac{pm^3}{s}$。

现在给定这个图，和每个点的水量的变化速度，求每条边的水量的变化速度的构造方案。

inputFormat:
第一行两个整数 $N,M$ 代表点数和边数。
这 $N$ 个点编号为 $1$ 到 $N$。
接下来 $N$ 行每行一个整数 $c_i$ 代表这个点的水量变化速度，正数为得水，负数为失水。
接下来 $M$ 行每行两个整数代表一条边。

outputFormat:
如果不存在这样的构造方案或者有多解，只输出一个整数 `0`。
如果存在这样的方案，输出 $M$ 行，每行一个整数代表每条边的水量变化速度。
得水为正数，失水为负数。

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

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le M \le 5 \times 10^5$，$-10^9 \le c_i \le 10^9$，如果有解且唯一解，每个答案在 $[-10^9,10^9]$ 的范围内。
对于其中 $30\%$ 的数据，该图为一棵树。

#### 说明

翻译自 [BalticOI 2013 Day1 C Pipes](https://boi.cses.fi/files/boi2013_day1.pdf)。


title: [BalticOI2013] Tracks in the Snow

description:
有一个含 $H$ 行，$W$ 列的字符矩阵，初始全为 `.`。

有两种动物，狐狸和兔子，将会从左上角走到右下角，狐狸会留下 `F` 的痕迹，兔子会留下 `R` 的痕迹。

痕迹会相互覆盖。

走路规则如下：
- 可以往返走；
- 不可以走对角线；
- 不可以跳格子；
- 不可能有两只动物一起走。

现在您得到了这个被动物们走过的矩阵，请求出至少有几个动物走过了该矩阵。

inputFormat:
第一行为两个整数 $H,W$。

接下来 $H$ 行，一行 $W$ 个字符，表示整个字符矩阵。

outputFormat: 仅一行一个整数，表示至少有几个动物走过了该矩阵。

samples:
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF

hint:
#### 数据范围及限制
- 对于 $30$ 分的数据，保证答案 $\le 200$，$H,W\le 500$。
- 对于 $100\%$ 的数据，保证 $1\le H,W\le 4\times 10^3$，答案 $\ge 1$，读入的字符只会是 `.` 或 `R` 或 `F`。

#### 说明
本题译自 [Baltic Olympiad in Informatics 2013](https://boi.cses.fi/tasks.php) [Day 2](https://boi.cses.fi/files/boi2013_day2.pdf) T2 Tracks in the Snow。


title: 『JROI-2』Dancing Line

background:
> 若唤音乐随直线走动，那么你的双眸就是无穷。

k 舔喜欢玩 Dancing Line。

k 舔决定自己做一个 Dancing Line 关卡。

description:
注：本题不考虑「迷宫」等线转向方式特殊，「足球」等传送线，「钢琴」等飞跃落地的情况。

众所周知，Dancing Line 的路线是一条折线，每次点击会使线的前进方向**顺时针或逆时针旋转 $90^\circ$**，且**任意相邻两次旋转方向不同**。

比如下面是合法的路径（路径**不一定要随着平面直角坐标系的网格行走**）：

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

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

而下面是不合法的路径：

旋转角度不为 $90^\circ$：

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

连续两次向左转弯：

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

显然不符合要求的路径：

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

k 舔将路线放进了二维坐标系内，并记下了路线的**起点**、**终点**和**拐弯点**的坐标（横纵坐标**均为整数**），放进文件里就离开了。

等到 k 舔回来打开电脑时，发现他文件里的数据全部乱掉了，各点的坐标不再像之前那样按顺序存储好，而是按一种奇怪的顺序排列好了。

k 舔想要根据这些数据来重新复原这条路线，他还想要估计这个关卡的难度，用 $s$ 来表示：

$$s=\sum\limits_{i=1}^{n}{t_i^2},t_i=\dfrac{d(P_{i-1},P_i)}{v}$$

其中：

- $P_i(0\leq i\leq n)$ 表示路线**复原后**从起点开始的第 $i$ 个点（起点为 $P_0$，终点为 $P_n$）。
- $v$ 为线的速度，是一个给定的**正整数**。
- $d(A,B)$ 表示点 $A$ 和点 $B$ 在坐标轴内的距离。

你能帮助他吗？

inputFormat:
第一行两个正整数 $n,v$，意义如上。

接下来 $n+1$ 行，每行两个整数，表示**复原前**文件内各点的坐标。

outputFormat:
一个数 $s$，意义如上，输出其对 $998244353$ 取模的结果。

具体来讲，设其用最简分数的方式表示为 $\dfrac{x}{y}$，你需要输出满足 $ys\equiv x\pmod{998244353}$ 的最小非负整数，在本题中你需要输出 $x\times y^{998244351}\bmod 998244353$。

hint:
**样例解释**

对于样例一，路线如下：

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

各段长度分别为 $2\sqrt{5},2\sqrt{5},\sqrt{5},3\sqrt{5},2\sqrt{5},\sqrt{5},4\sqrt{5},2\sqrt{5}$，$s$ 值为 $53\dfrac{3}{4}$，取模后结果为 $249561142$。

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

**数据范围与约定**

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

- Subtask 1（5 pts）：$n\leq 6$。
- Subtask 2（15 pts）：$n\leq 80$。
- Subtask 3（30 pts）：$n\leq 800$。
- Subtask 4（50 pts）：无特殊限制。

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

- $2\leq n \leq 10^6$。
- $-10^9\leq x_i,y_i\leq 10^9$。
- $1\leq v\leq 10^7$。
- **保证所有点坐标各不相同**。
- **保证给出的点一定能且只能复原出唯一的路径。**

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

$d(A,B)=\sqrt{(x_A-x_B)^2+(y_A-y_B)^2}$，其中 $A(x_A,y_A),B(x_B,y_B)$。

-----
Source：[JROI-2 Summer Fun Round](https://www.luogu.com.cn/contest/30241) - T3

Idea&Sol&Data：[kkk的小舔狗](/user/104581)

Std&Retest：[Tony2](/user/171288)


title: [BalticOI2013] Vim

description:
给定一个长度为 $N$ 的字符串 $S$，Victor 的目标是将其中的 `e` 全部删除，而不删除其他字符。最开始光标在第一个字符处。

Victor 使用 `Vim` 来解决这个问题。

然而，Victor 并不熟悉 `Vim`，他只知道这里面的三个指令：
- `x`：删除光标处的字符，光标位置不变，不可以在最后的字符处使用这个命令。
- `h`：将光标向左移动一格，如果光标位于第一个位置，则光标不动。
- `f`：其后接一个字符 $c$，其将会将光标移至其右边的第一个字符 $c$，$c\not =$ `e`。

请计算将其中的 `e` 全部删除，而不删除其他字符的最小**按键**数。

inputFormat:
第一行为一个整数 $N$。

接下来一行一个字符串 $S$。

outputFormat: 仅一行一个整数，表示将其中的 `e` 全部删除，而不删除其他字符的最小**按键**数。

hint:
#### 样例解释
`fdhxhhxffhxfahxhhhxhhhxfdhxfghxfahhx` 为最优解。
#### 数据范围及限制
- 对于 $50$ 分的数据，保证 $N\le 500$。
- 对于另外 $10$ 分的数据，保证 $N\le 5\times 10^3$。
- 对于 $100\%$ 的数据，保证 $1\le N\le 7\times 10^4$，$S_i\in\{$ `a` $\sim$ `j` $\}$，$S_1,S_N\not=$ `e`。

**译者提醒：实在是搞不懂怎样设置了，所以按洛谷默认的来。**
#### 说明
本题译自 [Baltic Olympiad in Informatics 2013](https://boi.cses.fi/tasks.php) [Day 2](https://boi.cses.fi/files/boi2013_day2.pdf) T3 Vim。


title: [WC2020] 有根树

description:
给定一棵包含 $n$ 个结点的有根树，结点从 $1\sim n$ 编号，1 号点为根结点。小明有一个结点集合 $S$，对于 $S$ 中的结点 $u$，他定义 $w_u$ 的值为 $u$ 的子树中（包括 $u$ 本身）被包含在集合 $S$ 内的结点数，为了方便叙述，对于不在 $S$ 中的结点，我们认为其 $w_u=0$。

接下来，小明需要你选择一个包含根结点的连通块 $C$。记 $a$ 表示连通块 $C$ 中被包含在集合 $S$ 内的结点数，$b$ 表示不在连通块 $C$ 中的结点的 $w$ 值最大值，若不存在不在 $C$ 中的结点，则 $b = 0$，小明希望你能最小化 $\max(a,b)$。

小明觉得这个问题还比较简单，所以还给出了 $q$ 次操作，每次会令集合 $S$ 加入或删除一个结点，请你对每次操作后的集合 $S$ 给出 $\max(a,b)$ 的最小值。

inputFormat:
第一行一个正整数 $n$ 表示结点数。

接下来 $n-1$ 行，每行两个整数 $x,y$，表示树上的一条边 $(x,y)$。

接下来一行一个正整数 $q$ 表示操作数。

接下来 $q$ 行，每行两个数 $t,v$ 表示一次操作。若 $t=1$ 则该操作为将结点 $v$ 加入 $S$，保证操作前 $v \notin S$。若 $t=2$ 则该操作为将结点 $v$ 从 $S$ 中删去，保证操作前 $v\in S$。
初始时 $S$ 为空集。

outputFormat: 每次操作后，输出一行一个整数表示答案。


title: [WC2020] 猜数游戏

description:
黑板上写有 $n$ 个互不相等且都小于 $p$ 的正整数 $a_1, a_2, \cdots, a_n$。小 J 想用这些数字和小 M 玩一个猜数游戏。

游戏规则十分简单：游戏开始时，小 J 会从这些数字中随机选择若干个让小 M 来猜，而小 M 则可以通过若干次**询问**来确定小 J 选择了哪些数字。

每一次**询问**的模式如下：小 M 可以任意指定一个数字 $a_k$，若它是小 J 所选择的数字之一，则小 J 会告诉小 M 他所选择的数字中所有能表示成 $(a_k)^m \bmod p$ 的数，其中 $m$ 是任意正整数，$\bmod$ 表示求二者做带余除法后的余数。反之，若 $a_k$ 没有被小 J 选中，则小 J 只会告诉小 M $a_k$ 没有被选中。

游戏会在小 M 确定小 J 所选中的所有数字后立刻结束。

例如，若 $n=4$，$p=7$，数字 $\{a_n\}$ 按下标顺序依次为 $\{1, 3, 4, 6\}$，小 J 选定的数字为 $\{1, 4, 6\}$，一种可能的游戏进行的过程（并非是最优过程）如下：

| 小 M 的询问 | 小 J 的反馈                           |
| ----------- | ------------------------------------- |
| $a_2 = 3$   | $a_2$ 没有被选中                      |
| $a_4 = 6$   | $6(= 6^1 \bmod 7)$，$1(=6^2 \bmod 7)$ |
| $a_3 = 4$   | $4(= 4^1 \bmod 7)$，$1(=4^3 \bmod 7)$ |

$3$ 次询问后小 J 所选出的所有数都已被小 M 确定，游戏结束。

小 M 还有作业没有写完，因此他需要对游戏进行的时间进行评估。他想知道为了使游戏结束，他所需要做出询问的最小次数的期望 $S$ 是多少。

为了避免精度误差，你需要输出答案乘 $(2^n - 1)$ 后模 $998244353$ 的余数。在本题中，你可以认为小 J 每次在选数时会在集合 $\{a_1, a_2, \cdots, a_n\}$ 的全部**非空子集**中等概率地选择一个，在这个前提下可以证明 $(2^n - 1) \times S$ 一定是一个整数。

inputFormat:
第一行两个正整数 $n$ 和 $p$。

第二行 $n$ 个正整数，依次表示 $a_1, a_2, \cdots, a_n$。

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


title: [WC2020] 选课

background:
### 提醒：

本题目前的官方数据有部分与数据范围不符。

**令 $P$ 为限制涉及到的课程数目，保证 $P\leq12$。**

**有一个测试点不满足 $T \geq \sum s_i$。**

description:
随着期末考试的结束，一年一度的选课环节又拉开了帷幕。

小 C 是一个热爱学习的好学生，他给自己定了一个小目标：在新的学期至少修够 $T$ 学分。从教务处给出的公告上看，本次可供选择的课程一共有 $m$ 种分类，第 $i$ 种分类中有 $n_i$ 门课程。小 C 根据公告的内容，提高了自己的学习目标：在所有课程至少修满 $T$ 学分的基础上，第 $i$ 种分类（$i=1,2,\cdots,m$）至少修够 $s_i$ 的学分。同时，聪明的小 C 凭借自己的经验，计算出了学习每门课程所能得到的学分和所需要消耗的脑力值。不仅如此，他还发现，有些课程之间存在特殊的关系：同时学习某两门内容相似的课程，可能会减少脑力值的消耗；同时学习某两门十分硬核的课，可能会增加脑力值的消耗；某两门课程时间冲突，则无法同时学习。

小 C 希望能够花费最少的脑力值来达到他的目标。你能帮小 C 计算出达到目标所需要的最小脑力值吗？

inputFormat:
第一行两个正整数 $m,T$，表示分类种数和总共需要修够的学分数。

接下来 $m$ 段输入，对于第 $i$ 段输入：

第一行有两个非负整数 $n_i,s_i$，表示第 $i$ 种分类的所有课程数和需要修够的学分。

第 $j+1$（$1\le j\le n_i$）行有两个正整数 $w_{i,j},c_{i,j}$，表示选修第 $i$ 种分类中的第 $j$ 门课能获得的学分和需要消耗的脑力。

$m$ 段输入之后，有一个非负整数 $p$，表示关系的条数。

接下来 $p$ 行每行一条关系，每一条关系可表示为以下 3 种形式之一（以下所有输入数据均为正整数）：

$1\ x_1\ y_1\ x_2\ y_2\ c$，表示同时修第 $x_1$ 种分类中的第 $y_1$ 门课和第 $x_2$ 种分类中的第 $y_2$ 门课，可以减少 $c$ 的消耗。

$2\ x_1\ y_1\ x_2\ y_2\ c$，表示同时修第 $x_1$ 种分类中的第 $y_1$ 门课和第 $x_2$ 种分类中的第 $y_2$ 门课，需要增加 $c$ 的消耗。

$3\ x_1\ y_1\ x_2\ y_2$，表示第 $x_1$ 种分类中的第 $y_1$ 门课和第 $x_2$ 种分类中的第 $y_2$ 门课不能同时修。

outputFormat: 输出文件只有一行，包含一个整数，表示达到目标所需要的最小脑力值。如果无法达到小 C 的目标，请输出 `-1`。

hint:
#### 样例1解释

即使学习所有课程，总学分仍无法达到小 C 的要求，故输出 `-1`。

#### 样例2解释

一种可能的选法为：第一种分类中选择第 4、5 门课，第二种分类选择第 1、3、6 门课，第3种分类不选课程（选法不唯一）。

#### 数据范围

设 $N=\sum_{i=1}^{m} n_i$，$M$ 为消耗脑力值的最大值（包括有关系的课程中增加或减少的消耗）。

对于 $5\%$ 的数据：$N\le 5$。

对于 $10\%$ 的数据：$N\le 15$。

有另外 $10\%$ 的数据：$N\le 1000$，$p=0$。

有另外 $10\%$ 的数据：$w_i=1$，$p=0$。

有另外 $10\%$ 的数据：$T=\sum_{i=1}^{m} s_i$，$p=0$。

有另外 $10\%$ 的数据：$N\le 10^4$，$M\le 50$，且有关系的课程在同一分类中。

有另外 $10\%$ 的数据：$N\le 5\times 10^4$，$M\le 50$。

对于 $100\%$ 的数据：$N\le 5\times 10^5$，$M\le 200$，$0\le T-\sum_{i=1}^{m} s_i\le 40$，$m\le 5\times 10^4$，$p\le 12$，$w_{i,j}\in\{1,2,3\}$。

**官方数据有误，经测试，$p$ 最大为 $66$**

数据保证任意两种课程至多只有一种关系。


title: 「EZEC-3」排列

description:
pigstd 有一堆数，他想在这么多数中选出若干个数排成一列，记为 $x_{1},x_{2},\cdots,x_{p}$（$p$ 为数的个数）。

这一列数合法**当且仅当**满足以下条件：

- $p \ge 2$。
- 令 $y_{i} = x_{i + 1} - x_{i}$（特别的，$y_{p}=x_{1}-x_{p}$），如果把 $y_{1}$ 到 $y_{p}$ 按 $y_1,y_2,\cdots,y_p$ 的顺序排成**一圈**，那么每两个相邻的数互为相反数且绝对值都为 $k$。

pigstd 想知道，在所有合法的数列中，所有在这个数列中的数之和**最大**是多少。

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

接下来 $n$ 行，每行两个整数 $a_{i},b_{i}$，表示 pigstd 有 $b_{i}$ 个 $a_{i}$。

**不保证 $a_{i}$ 互不相同，若有 $a_{i}$ 相同则累加其个数计算。**

outputFormat:
一行一个整数，表示在每一种排列中，所有在这个排列中的数的**最大**的和。

**若没有合法的排列，则只输出 $\texttt{NO}$。**

hint:
**【样例 1 说明】**

当 pigstd 的排列为：$0,3,0,3$ 或 $3,0,3,0$ 时，总和最大，为 $6$。

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

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$0 \le k,a_{i} \le 10^6$，$1 \le b_{i} \le 10^6$。

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

- Subtask 1（5 points）：保证无合法的数列；
- Subtask 2（15 points）：$k = 0$；
- Subtask 3（5 points）：$n = 1$；
- Subtask 4（5 points）：$n = 2$；
- Subtask 5（30 points）：$n,k,a_i,b_i \le 10^3$；
- Subtask 6（40 points）：无特殊限制。


title: 「SWTR-6」GCDs & LCMs

description:
小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。

他想从这些数中选出一些数 $b_1,b_2,\cdots,b_k$ 满足：对于所有 $i\ (1\leq i\leq k)$，$b_i$ 要么是序列 $b$ 中的最大值，要么存在一个位置 $j$ 使得 $b_j>b_i$ 且 $b_i+b_j+\gcd(b_i,b_j)=\mathrm{lcm}(b_i,b_j)$。

- 如果你不知道 $\gcd$ 和 $\mathrm{lcm}$ 是什么，可以点击最底部的「帮助/提示」部分的链接。

小 A 想让选出的数之和尽量大。请求出这个最大值。

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

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

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

hint:
**「样例 1 说明」**

可以选择 $b=\{2,3\}$，因为 $2+3+\gcd(2,3)=\mathrm{lcm}(2,3)$。

**「数据范围与约定」**

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

- Subtask 1（5 points）：$n\leq2$；
- Subtask 2（20 points）：$n\leq 17$；
- Subtask 3（15 points）：$a_i\leq 2\times 10^3$；
- Subtask 4（15 points）：$n\leq 2\times 10^3$；
- Subtask 5（10 points）：$n\leq 5\times 10^4$；
- Subtask 6（10 points）：$a_i\leq 10^7$；
- Subtask 7（25 points）：无特殊限制。

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^5$，$1\leq a_i\leq 10^9$。

**「帮助/提示」**

$\gcd$ 表示[最大公约数](https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0/869308?fr=aladdin)，$\mathrm{lcm}$ 表示[最小公倍数](https://baike.baidu.com/item/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0/6192375?fr=aladdin)。

**「来源」**

[【LGR-075】洛谷 8 月月赛 II Div.2 & SWTR-06 & EZEC Round 3](https://www.luogu.com.cn/contest/33190)。

idea & solution & data by [Alex_Wei](https://www.luogu.com.cn/user/123294)。


title: 「SWTR-6」Snow Mountain

background:
**题目背景与解题无关。**

**题目描述最下方有简化版题意。**

天空中飘着雪，放眼望去白茫茫一片。小 A 拿着地图，四处探寻着。

突然，只见前方有一个洞穴。出于好奇心，小 A 走了进去。

洞穴里黑漆漆一片，一眼望不到尽头。道路的两旁尽是白骨，显然，这是曾经来这里探险的人们的残骸。小 A 打了一个冷颤。

这时，小 A 留意到了地上的一张纸片。打开来一看，上面竟写着：

$$\texttt{Please contact lydsy2012@163.com!}$$

description:
> 洞穴里有一些水晶，每个水晶有一个能量值 $a_i$。**能量值有大有小，但不会相同。** 这些神秘的水晶上附着邪恶势力的灵魂。现在你的任务是摧毁这些水晶，并让它们释放出的邪恶能量能量尽可能小。
>
> 你可以选择两个未被摧毁的水晶 $i,j$，将它们摧毁并释放出 $\min(a_i,a_j)\times k$ 的邪恶能量。其中 $k$ 表示这是第 $k$ 次摧毁。
>
> 不过有一些**无序**水晶对 $(x,y)$，如果你将它们一并摧毁，就会发生强大的共振导致山洞倒塌，使你葬身其中！

带着这张纸片，小 A 来到了山洞的尽头，果然发现了 $n$ 个水晶（$n$ 为偶数）。正如纸片上所说，每个水晶都有一个能量值 $a_i$。

对这些水晶进行一番观察，小 A 发现了一个规律：每个水晶 $i$ 在**所有能量值比它大**的水晶中，只会和**最多一个**发生共振，记其编号为 $x_i$。

现在小 A 知道了 $a_i,x_i$，你能帮助他求出摧毁这些水晶释放出邪恶能量之和的最小值吗？无法摧毁输出 $\texttt{-1}$。否则先输出最小值，再输出摧毁方案。

若摧毁方案有多种，输出任意一种即可。

- 需要注意的是，摧毁后水晶编号不会发生改变。

---

简化版题意：

给定两个长为 $n\ (2|n)$ 的序列 $a,x$，满足 $a_i$ 互不相同且如果 $x_i \neq -1$，那么 $a_{x_i}>a_i$。

现在需要进行 $\frac{n}{2}$ 次删除操作：选择两个未被删除的数 $a_i,a_j$ 满足 $x_i\neq j$ 且 $x_j\neq i$，并用 $\min(a_i,a_j)\times k$ 的代价将这两个数从序列 $a$ 中删去（删除后剩余元素下标不变），其中 $k$ 表示这是第 $k$ 次删除。

求删除所有数的最小代价与方案。无解输出 $\texttt{-1}$。若方案有多种，输出任意一种即可。

inputFormat:
第一行一个整数 $n$，保证 $n$ 是偶数。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，保证 $a_i$ 互不相同。

接下来一行 $n$ 个整数 $x_i$，如果 $x_i=-1$ 则表示第 $i$ 个水晶不与能量值比它大的水晶发生共振；否则保证 $a_{x_i}>a_i$。

**题目输入量较大，建议使用 `scanf`。**

outputFormat:
若题目无解，输出一行 $\texttt{-1}$。

否则首先输出一行一个整数，表示释放出邪恶能量之和的最小值。

接下来 $\dfrac{n}{2}$ 行每行两个由空格隔开的整数，表示被摧毁的水晶对。

**题目输出量较大，建议使用 `printf`。**

hint:
**「样例 3 说明」**

无法摧毁所有水晶，因为水晶 $4$ 无法被摧毁。

**「数据范围与约定」**

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

- Subtask 1（5 points）：$n=2$；
- Subtask 2（20 points）：$n \leq 10$；
- Subtask 3（15 points）：$x_i=-1$；
- Subtask 4（20 points）：$n\leq 3\times 10^3$；
- Subtask 5（15 points）：$a_i$ 升序排列，即 $a_i<a_{i+1}\ (1\leq i<n)$；
- Subtask 6（24 points）：无特殊限制。
- Subtask 7（1 point）：hack 数据。

对于 $100\%$ 的数据，$2 \leq n \leq 5 \times 10^5$，$1 \leq a_i \leq 10^9$。
保证 $n$ 为偶数且 $a_i$ 互不相同。
保证答案不超过 $2^{63}-1$。

**「帮助/提示」**

请注意 IO 优化。

**「Special Judge」**

**本题使用 SPJ。**

**请认真阅读输出格式。** 输出格式有误可能导致 UKE。

若你的输出的第一行与答案的第一行不同，你将获得本测试点的 $0\%$ 分数。

若无解且第一行相同，你将获得本测试点的 $100\%$ 分数。

若有解且第一行相同，但方案有误，你将获得本测试点的 $60\%$ 分数。

若有解且第一行相同，方案正确，你将获得本测试点的 $100\%$ 分数。

另附 `checker` 与 `testlib.h`。

百度网盘链接：[link](https://pan.baidu.com/s/1Tk-8-UiLzCpOuPVuoCcbbQ)，提取码：b7eg。


title: [USACO2006 OPEN] 县集市 The County Fair

description:
每年，FJ 都喜欢去参加县集市，集市上有 $n$ 个展位，每个摊位 $i$ 都会在当天的特定时间 $p_i$ 发放精美的礼品。FJ 已经听说了这一点，他希望能收集尽可能多的礼品和他的奶牛们一起分享。要想获得摊位 $i$ 发放的礼品，FJ 必须确保时间点 $p_i$ 时位于摊位 $i$。

为了获得尽可能多的礼品，FJ 进行了一番详细的调查，通过调查FJ确定了从摊位 $i$ 到摊位 $j$ 所花费的时间 $t_{i,j}$。集市的布局很不寻常，这会导致，FJ如果在从 $i$ 到 $j$ 的过程中选择从其他摊位绕行，可能会比直接从 $i$ 到 $j$ 所花费的时间更少，然而我们耿直的 FJ 从来不这么做，如果他想从摊位 $i$ 到摊位 $j$，他一定会花 $t_{i,j}$ 的时间从 $i$ 走到 $j$。另外由于集市所在地崎岖不平，所以 $t_{i,j}$ 可能与 $t_{j,i}$ 不相同。

FJ 在时间 $0$ 时，位于 $1$ 号摊位，请计算他最多可以收集多少奖品。

inputFormat:
第 $1$ 行：一个整数 $n$，表示摊位的数量。

第 $2$ 行：共 $n$ 个整数，其中第 $i+1$ 的正数 $p_i$ 表示摊位 $i$ 发放礼品的时间。

第 $n+2$ 到第 $n^2+n+1$ 行：共 $n^2$ 行，第一个 $n$ 行描述了 FJ 从摊位 $1$ 走到到摊位 $1$...$n$ 所需时间（$t_{1,1},t_{1,2}, ...t_{1,n}$），接下来的 $n$ 行描述了 FJ 从摊位 $2$ 走到摊位 $1$...$n$ 所需时间（$t_{2,1},t_{2,2}, ...t_{2,n}$），以此类推，最后的 $n$ 行描述了 FJ 从摊位 $n$ 走到摊位 $1$...$n$ 所需要的时间 $t_{n,1},t_{n,2}, ...t_{n,n}$。对于任意摊位 $i$，$t_{i,i}=0$。

outputFormat: 一行：一个整数，表示 FJ 最多可以领取到的奖品数量。

hint:
#### 样例说明

样例中集市上共有 $4$ 个摊位。$1$ 号摊位在时间 $13$ 发放礼品，$2$ 号摊位在时间 $9$ 发放礼品，$3$ 号摊位在时间 $19$ 发放礼品，$4$ 号摊位在时间 $3$ 发放礼品。

FJ 首先从 $1$ 号摊位走到 $4$ 号摊位，用时 $3$，并在时间 $3$ 到达，正好可以领取到奖品，接着他从摊位 $4$ 走到摊位 $2$ ，用时 $5$，并在时间 $8$ 到达，在等待 $1$ 个时间点后可以领取 $2$ 号摊位的礼品，接着他从 $2$ 号摊位走到 $1$ 号摊位，用时 $4$，并在时间 $13$ 到达，从而可以收集到第 $3$ 个礼品。

#### 数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 400$，$0\le p_i\le 10^9$，$1\le t_{i,j}\le 10^6$。

数据来自 darkbzoj。


title: [W1] 团

description:
我有一张 $n$ 个节点的无向边带权图。它的边很多，用这个方法表示：

 - 有 $k$ 个集合；第 $i$ 个集合可以表示为 $S_i=\{(T_1,W_1),(T_2,W_2),\dots,(T_{|S_i|},W_{|S_i|})\}$。
 - 对于任何两对 $(T_i,W_i),(T_j,W_j)$ 在同一个集合里面，图中会形成一条连 $T_i$ 和 $T_j$ 的边，边权为 $W_i+W_j$。

请对于所有节点 $i$ 找到 $1$ 到 $i$ 的最短路，即从 $1$ 到 $i$ 的边权和最小的简单路径。

inputFormat:
第一行两个正整数 $n,k$。
接下来描述 $k$ 个集合。
第 $i$ 集合的描述的第一行一个正整数 $|S_i|$，表示 $|S_i|$ 的大小。
接下来 $S_i$ 行，每行两个正整数 $t,w$，表示 $(t,w)\in S_i$。

outputFormat: 一行 $n$ 个正整数；第 $i$ 个正整数表示 $1$ 到 $i$ 的最短路长度。如果不存在一条路径，输出 $\textsf{0x3f3f3f3f3f3f3f3f}=4557430888798830399$。


title: [W1] 推

background:
一个”点集“为一个二维平面上的整点组成的**多重**集合。
可以从一个点集构造一个三角形当且仅当这个三角形的所有顶点在该点集里面。
从一个点集 $S$ 里可以构造恰好 $|S|^3$ 个三角形。（可能一些三角形会退化为一条面积为 0 的线段）

description:
有一个点集，初始为空集。
有 $N$ 个操作，在每一个操作，会从这个点集插入或删除一个点。每一步完成后，询问这个点集可构造的所有三角形面积 *__八次方__* 之和。

所有询问答案都可以表示为 $a/b$，其中 $a$ 和 $b$ 互质。输出 $a\cdot b^{-1}\pmod{998244353}$。

inputFormat:
第一行一个正整数 $N$，表示接下来的步骤个数。
接下来 $N$ 行，每一行三个正整数 $t,x,y$。
如果 $t=1$，则插入 $(x,y)$ 这个点；如果 $t=2$ 则删除 $(x,y)$ 这个点。

outputFormat: 一共 $N$ 行，第 $i$ 行一个正整数，表示第 $i$ 个步骤完成之后的询问答案。

hint:
对于 $10\%$ 的数据，$N\le10$；
对于 $30\%$ 的数据，$N\le10^3$；
对于另外 $10\%$ 的数据，没有删除步骤；
对于 $100\%$ 的数据，$1\le N\le10^5,0\le x,y<998244353$，任何删除的点都保证原来存在。


title: 「MCOI-04」Dream and Strings

description:
Tommy 的加密系统用了如下的字符串哈希算法：

```cpp
int Hash(std::string s, int base, int mod) {
  int result = 0;
  for(int i=0; i<s.length(); i++)
    result = (1ll * result * base + s[i]) % mod;
  return result;
}
```

其中 $\texttt{base}$ 和 $\texttt{mod}$ 是给定参数，满足 $257\le\texttt{base}\le\texttt{mod}\le10^9+9$，并且 $\texttt{mod}$ 是一个质数。

现在 Dream 要破解 Tommy 的密文，先需要找到一个适合的哈希碰撞。给定 $\texttt{base}$，$\texttt{mod}$，和一个字符串 $S$，请找一个一样长度的字符串 $T$ 使得 $|S|=|T|$，$\texttt{hash(S)=hash(T)}$，但是 $S$ 和 $T$ 有至少一个位置不同。

如果有多个合法的 $T$，输出任意一个即可。

inputFormat:
第一行，两个正整数 $\texttt{base}$ 和 $\texttt{mod}$。
第二行，一个由小写字母组成的字符串 $S$。

outputFormat: 一行，一个由小写字母组成的字符串 $T$，表示答案。

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

如果 $S$ 是一个字符串，$|S|$ 是它的长度。

对于前 $10\%$ 的数据，$\texttt{mod}=997$。
对于前 $40\%$ 的数据，$|S|=2\times10^5$ 并且 $S$ 随机。
对于 $100\%$ 的数据，$50\le|S|\le2\times10^5$，$257\le\texttt{base}<\texttt{mod}\le10^9+9$，$\texttt{mod}$ 是一个质数。

#### 说明

[Minecraft OI Round 4](https://www.luogu.com.cn/contest/33344) D
idea & solution：w33z8kqrqk8zzzx33 check：MatKave


title: [W1] 算

description:
有一个 $m$ 项多项式 $p(x)$ 以及两个参数 $c$ 和 $t$，其中 $p(x)=a_0+a_1x+\dots+a_{m-1}x^{m-1}$。
定义一个新函数 $s(n)$:
$$s(n)=\sum_{i=1}^np(i)[\gcd(i,n)=1]\bmod 998244353$$
请计算 $s(c),s(c^2),\dots,s(c^t)$。

inputFormat:
第一行三个正整数，分别表示 $m,c,t$。
第二行 $m$ 个正整数，表示 $a_0,a_1,\dots,a_{m-1}$。

outputFormat: 输出 $t$ 行，第 $i$ 行一个正整数 $s(c^i)$。


title: [BalticOI 2010 Day1] BEARs

background: 本题中的 $(a,b) \to (c,d)$ 代表一条从 $(a,b)$ 连向 $(c,d)$ 的线段。

description:
给定 $N$ 条长度为 $1$ 的线段，定义他们为「标记线」。

现在在点 $(A,B)$ 处有一个强盗，他要前往 $(0,0)$，警察们可以任意选择一个点，关闭他四周的任意一条线段。比如选择点 $(0,0)$，线段 $(-1,1) \to (1,1)$，$(-1,1)\to (-1,-1)$，$(-1,-1) \to (1,-1)$，$(1,-1) \to (1,1)$ 其中之一将会被关闭，但是关闭的线段中不能有与标记线 **直接相连** 的线段。比如 $(0,0) \to (0,2)$ 与 $(0,1) \to (0,3)$ 是直接相连的，但是 $(-1,1) \to (1,1)$ 与 $(0,0) \to (0,3)$ 不是。

强盗可以到达关闭的线段上的点，但是不能通过关闭的线段离开。

求强盗离 $(0,0)$ 的最近的距离的最大值 $D$。

inputFormat:
第一行两个整数 $A,B$ 代表强盗初始在 $(A,B)$。
第二行一个整数 $N$ 代表标记线数。
接下来 $N$ 行每行两个整数 $X_1,Y_1,X_2,Y_2$ 代表一条标记线 $(X_1,Y_1) \to (X_2,Y_2)$。

outputFormat: 一行一个整数代表强盗离 $(0,0)$ 的最近的距离的最大值 $D$。

hint:
#### 样例说明

对于样例 $1$，如下图所示：

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

选择的点为 $(0,0)$，关闭的线段为 $(1,1) \to (1,-1)$。

#### 数据规模与约定

对于 $100\%$ 的数据，$|A|,|B|,|X_1|,|Y_1|,|X_2|,|Y_2| \le 10^6$，$0 \le N \le 500$，保证每条标记线 $X_1=X_2$ 或者 $Y_1=Y_2$。

#### 说明

翻译自 [BalticOI 2010 Day1 A BEARs](https://boi.cses.fi/files/boi2010_day1.pdf)。


title: 「SWTR-8」扫雷计数

background:
2020 年 6 月的某一天，小 A 在等待网络加载的过程中打开了扫雷，从此便一发不可收拾。

小 A 是一个任何事都喜欢做到极致的人，玩游戏也不例外：他不惜花费大量时间不断尝试打破记录。一个个夜晚就在熟练的 `Alt + G + N` 中过去了。

> “这把有戏，前五十个雷只用了不到四十五秒”。他心里想着，紧握鼠标的手微微颤抖。
>
> “快，快，快 …… 还有最后二十个雷 ……”。
>
> 游戏的关键时刻，他难以按捺激动的心情。直到他遇到了二选一。
>
> 他愣了一下，随后迅速按下最后两块空地当中的一个。
>
> 一束横贯屏幕的白色激光缓缓扫过，他知道自己打破了记录 …… [整整十二秒](https://cdn.luogu.com.cn/upload/image_hosting/1seixkiz.png)！巨大的惊喜让他跳了起来。
>
> 2020.6.19

description:
以下是简化后的扫雷游戏规则：

- 定义连通为 **八连通**。
- 如果打开雷，所有雷 **全部同时爆炸**，游戏结束。
- 如果打开空地，若其周围没有雷，则递归打开周围八个方块。
- [如图](https://cdn.luogu.com.cn/upload/image_hosting/kjjqs2v1.png)，点开任意红色框内方块均形成当前局面。

给定一张 $n\times m$ 的初始地图。小 A 决定搜出所有可能的局面，并找到最优鼠标点击顺序，从而速通这张地图。

为设置合适的数组大小，小 A 需要知道有多少种不同局面。对 $998244353$ 取模。

- 如果方块是雷，它有爆炸和未爆炸两种状态；如果方块是空地，它有打开和未打开两种状态。
- 两个局面不同，当且仅当存在方块状态不同。
- 保证周围无雷的空地形成不超过 $37$ 个连通块。

inputFormat:
第一行一个整数 $S$，表示该测试点的 Subtask 编号。

第二行两个整数 $n, m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串描述地图，其中 $\texttt{.}$ 表示方块无雷，$\texttt{*}$ 表示方块有雷。

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

hint:
**「样例解释」**

用 `.` 表示未打开的方块，`+` 表示打开的方块，`*` 表示未爆炸的雷，`!` 表示爆炸的雷。

样例 1 的所有 4 种局面为 `.*   +*   .!   +!`。

样例 2 的所有 20 种局面为
```plain
0
..*
...

1
++*  .+*  ..!  ..*  ..*
++.  ...  ...  .+.  ..+

2
++!  ++*  .+!  .+*  .+*  ..!  ..!  ..*
++.  +++  ...  .+.  ..+  .+.  ..+  .++

3
++!  .+!  .+!  .+*  ..!
+++  .+.  ..+  .++  .++

4
.+!
.++
```

数字描述了最少点击次数。

**「数据范围与约定」**

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

设周围无雷的空地形成 $d$ 个连通块。

- Subtask #1（15 points）：$nm\leq 21$。
- Subtask #2（4 points）：地图中只有一个雷。
- Subtask #3（5 points）：$d = 0$。
- Subtask #4（6 points）：$d = 1$。
- Subtask #5（7 points）：$d = 2$。
- Subtask #6（8 points）：$d \leq 17$。依赖 Subtask #1，#2，#3，#4，#5。
- Subtask #7（9 points）：$d \leq 23$。依赖 Subtask #6。
- Subtask #8（16 points）：$d\leq 27$。依赖 Subtask #7。
- Subtask #9（17 points）：$d\leq 33$。依赖 Subtask #8。
- Subtask #10（13 points）：无特殊限制。依赖 Subtask #9。

对于 $100\%$ 的数据：

- $1\leq n, m\leq 500$。
- $0\leq d\leq 37$。
- **不保证** 地图中有雷或空地。

**「题目来源」**

- [Sweet Round 8](https://www.luogu.com.cn/contest/73382) D
- Idea & Solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。
- Tester：[chenxia25](https://www.luogu.com.cn/user/138400) & [asmend](https://www.luogu.com.cn/user/21658)。

感谢 [Elegia](https://www.luogu.com.cn/user/21423) 对本题做出的贡献。


title: [IOI2019] 视觉程序

background:
[评测方式](https://www.luogu.com.cn/paste/5z13bn4l)

[一些说明~~和扯淡~~](https://www.luogu.com.cn/paste/l6kcccs4)

description:
你在给机器人编写一个视觉程序。每次机器人的摄像头拍下一张照片时，图像将以黑白图像的形式存储在机器人的内存中。每张图像是由像素构成的 $H\times W$ 网格。图像的行从 $0$ 到 $H-1$ 编号，列从 $0$ 到 $W-1$ 编号。每张图像含有**恰好两个**黑色像素，其他像素均为白色。

机器人可以用简单指令构成的程序来处理图像。给出 $H$，$W$ 和一个正整数 $K$ 的值，你的目标是要编写一个函数，用来为机器人生成程序。该程序需要判定图像中两个黑色像素的距离是否正好为 $K$。这里，在第 $r_1$ 行及第 $c_1$ 列上的像素与第 $r_2$ 行及第 $c_2$ 列上的像素之间的距离定义为 $|r_1-r_2|+|c_1-c_2|$。 在这个式子中，$|x|$ 表示 $x$ 的绝对值，即当 $x\ge0$ 时，其值为 $x$，而当 $x<0$ 时，其值为 $-x$。

下面描述机器人是如何运作的。

机器人的内存有足够多的存储单元，从 $0$ 开始编号。每个存储单元可以保存 $0$ 或 $1$，且它的内容一旦设置后就不可更改。图像一行接一行地保存在存储单元里，这些存储单元的编号从 $0$ 到 $H\cdot W-1$。第一行保存在存储单元 $0$ 到 $W-1$ 里，最后一行保存在存储单元 $(H-1)W$ 到 $H\cdot W-1$ 里。特别地，如果位于第 $i$ 行第 $j$ 列上的那个像素是黑色的，则保存在存储单元 $i\cdot W+j$ 里的值为 $1$，否则为 $0$。

机器人的程序是一个**指令**的序列，这些指令用从 $0$ 开始的连续整数进行编号。在程序运行时，指令将一条一条地被执行。每条指令读取一个或多个存储单元的值（我们将这些值称为指令的**输入**），同时产生一个 $0$ 或 $1$ 的值（我们称之为指令的**输出**）。指令 $i$ 的输出将会保存在存储单元 $H\cdot W+i$ 中。指令 $i$ 的输入只能是保存图像的存储单元，或者是保存之前指令输出的存储单元，也就是编号为从 $0$ 到 $H\cdot W+i-1$ 的存储单元。

机器人共有四种指令：
- `NOT`：有唯一一个输入。若输入为 $0$ 时，其输出为 $1$，否则为 $0$。
- `AND`：有一个或多个输入。其输出为 $1$ 当且仅当输入**全部**为 $1$。
- `OR`：有一个或多个输入。其输出为 $1$ 当且仅当输入中**至少有一个** $1$。
- `XOR`：有一个或多个输入。其输出为 $1$ 当且仅当输入中 $1$ 的个数是**奇数**。

如果两个黑色像素之间的距离正好为 $K$，则最后一条指令的输出应为 $1$，否则输出应为 $0$。
#### 实现细节
你需要实现以下函数：
```plain
void construct_network(int H, int W, int K)
```
- $H$，$W$：机器人摄像头所拍到的图像的尺寸
- $K$：一个正整数
- 这个函数需要生成一个机器人的程序。对于机器人摄像头所拍到的每幅图像，该程序应判定图像中两个黑色像素之间的距离是否正好为 $K$。

该程序应当通过调用以下函数将指令追加到机器人的程序中（最初机器人的程序是空的）：
```plain
int add_not(int N)
int add_and(int[] Ns)
int add_or(int[] Ns)
int add_xor(int[] Ns)
```
- 分别追加一条 `NOT`，`AND`，`OR` 或 `XOR` 指令。
- $N$（对于 `add_not` 而言）：要追加的 `NOT` 指令的输入存储单元编号
- $Ns$（对于 `add_and`，`add_or`，`add_xor` 而言）：要追加的 `AND`，`OR` 或 `XOR` 指令的输入存储单元的编号的数组
- 每次函数调用都会返回追加指令的输出存储单位的编号。对这些函数的连续调用将会返回从 $H\cdot W$ 开始的连续整数。

机器人的程序最多可以包含 $10^4$ 条指令。这些指令一共最多只能读入 $10^6$ 个值。换句话说，所有 `add_and`，`add_or` 及 `add_xor` 调用中的 $Ns$ 数组的长度总和再加上 `add_not` 调用的次数不得超过 $10^6$。

当追加完最后一条指令后，函数 `construct_network` 必须返回。所产生的机器人程序会在一些图像上进行评测。对于一幅图像，程序最后一条指令的输出是 $1$ 当且仅当两个黑色像素之间的距离正好为 $K$。如果对测试点中的每幅图像，你的解答所产生的程序都可以正确地输出结果，那就通过了该测试点。

评测程序在评测你的程序时可能会出现以下错误信息：
- `Instruction with no inputs`：一个空数组被作为 `add_and`，`add_or` 或 `add_xor` 的输入。
- `Invalid index`：给 `add_not`，`add_or` 或 `add_xor` 提供了不正确（可能是负数）的存储单元编号作为输入。
- `Too many instructions`：你的函数尝试添加多于 $10^4$ 条的指令。
- `Too many inputs`：程序中的指令一共读取了多于 $10^6$ 个值。
#### 评测程序示例
评测程序示例读取下述格式的输入：
- 第 $1$ 行：$H$，$W$，$K$
- 第 $2+i$ 行（$i\ge0$）：$r1_i$，$c1_i$，$r2_i$，$c2_i$
- 最后一行：$-1$

除第一行和最后一行外，每一行都表示了一幅含有两个黑色像素的图像。记第 $2+i$ 行上的图像为图像 $i$。该图像中，一个黑色像素位于第 $r_1[i]$ 行及第 $c_1[i]$ 列上，令一个黑色像素位于第 $r_2[i]$ 行及第 $c_2[i]$ 列上。

评测程序首先调用 `construct_network(H, W, K)`。若 `construct_network` 违反了题目描述中的限制条件，评测程序示例将会输出在实现细节一节末尾所列举的某条错误信息并退出。

否则，评测程序示例将输出两部分内容。

首先，评测程序示例会以下列格式输出机器人程序所产生的输出：
- 第 $1+i$ 行（$0\le i$）：对于图像 $i$，机器人程序最后一条指令的输出（$1$ 或 $0$）。

其次，评测程序示例会以下列格式输出到当前目录下一个名为 `log.txt` 的文件中：
- 第 $1+i$ 行（$0\le i$）：$m_{i,0}$，$m_{i,1}$，$\dots$，$m_{i,c-1}$

在第 $1+i$ 行上的序列描述以图像 $i$ 作为输入时，在机器人程序运行结束后放在内存中的数据。具体来说，$m_{i,j}$ 是保存在存储单元 $j$ 里面的值。注意，$c$ 的值（序列长度）等于 $H\cdot W$ 再加上机器人程序的指令数。

hint:
#### 样例
假设 $H=2$，$W=3$，$K=3$。在此情况下，两个黑色像素之间的距离为 $3$ 的图像只有两种。

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

- 情况一：黑色像素是 $0$ 和 $5$。
- 情况二：黑色像素是 $2$ 和 $3$。

一种可行的方案是通过以下调用来构造机器人程序：
1. `add_and([0, 5])`，将加入一条指令，当且仅当图像符合情况一时其输出为 $1$。输出结果将保存在存储单元 $6$ 里。
1. `add_and([2, 3])`，将加入一条指令，当且仅当图像符合情况二时其输出为 $1$。输出结果将保存在存储单元 $7$ 里。
1. `add_or([6, 7])`，将加入一条指令，当且仅当上述两种情况之一成立时其输出为 $1$。
#### 数据范围
对于所有数据：
- $1\le H,W\le200$；
- $2\le H\cdot W$；
- $1\le K\le H+W-2$。

详细子任务附加限制与分值如下表：
| 子任务编号 |                           附加限制                           | 分值 |
| :--------: | :----------------------------------------------------------: | :--: |
|    $1$     |                     $\max(H,W) \le 3$                        | $10$ |
|    $2$     |                     $\max(H,W) \le 10$                       | $11$ |
|    $3$     |                     $\max(H,W) \le 30$                       | $11$ |
|    $4$     |                     $\max(H,W) \le 100$                      | $15$ |
|    $5$     |                       $\min(H,W) = 1$                        | $12$ |
|    $6$     |     每幅图像上位于第 $0$ 行且位于第 $0$ 列的那个像素是黑色的         | $8$ |
|    $7$     |                           $K = 1$                            | $14$ |
|    $8$     |                      没有任何附加限制                           | $19$ |


title: [THUWC2017] 大葱的神力

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

大葱是我国自古以来的美食，像我国传统美食北京烤鸭，用鸭子点缀出大葱的香味，令人赞不绝口。民间也流传着有「每天一棵葱，不当单身狗」的说法。

然而，大葱要发挥出独属于自己的神力，也是有条件的。

description:
现在小葱同学有 $N$ 棵大葱和 $M$ 个抽屉，将第 $i$ 棵大葱放到第 $j$ 个抽屉里面会产生 $w_{i,j}$ 的神力。自然小葱同学希望获得尽量多的神力，但是抽屉有着容积的限制，大葱也有着自己的体积。第 $i$ 棵大葱的体积为 $a_i$，第 $j$ 个抽屉的容积为 $b_j$。一个抽屉里面装着的大葱的体积之和不能超过这个抽屉的容积，一棵大葱不能拆分放到两个抽屉中。

小葱同学现在想知道，在这样的条件下，这些大葱最多会产生多少的神力？

inputFormat:
**本题为提交答案题**，输入文件为 `drawer1.in ~ drawer10.in`，详见附加文件。

第一行两个整数 $N,M$，代表大葱的个数和抽屉的个数。

接下来一行 $N$ 个整数，代表每棵大葱的体积。

接下来一行 $M$ 个整数，代表每个抽屉的容积。

接下来 $N$ 行每行 $M$ 个整数，第 $i$ 行第 $j$ 个数代表第 $i$ 棵大葱放到第 $j$ 个抽屉中会产生的神力。

outputFormat:
输出文件为 `drawer1.out ~ drawer10.out`，分别对应相应的输入文件。

对于每组输入数据，输出 $N$ 行每行一个整数，第 $i$ 个数代表第 $i$ 棵大葱被放到了哪个抽屉里面。如果第 $i$ 棵大葱没有被放到任何一个抽屉里面，则输出 $0$。

hint:
#### 样例说明

样例只是一种合法情况，获得的总神力值为 $2+3=5$。

#### 评分方式

**本题使用 Special Judge**，对于每个测试点，我们都有 $10$ 个参数 $a_1,a_2,\cdots,a_{10}$，如果你的输出所产生的的神力 $v$ 满足 $v \ge a_i$，则我们保证该测试点你至少会得到 $i$ 分。

#### 如何测试你的输出

在附加文件中，我们提供了 `scorer.cpp`，请自行编译来测试输出，这个程序将用于评判你的输出能够产生多少的神力。

若编译后文件名称为 `scorer`，在终端（Linux）中，输入以下命令：

```plain
./scorer <input_name> <output_name>
```

或在命令提示符（Windows）中，输入以下命令：
```plain
scorer <input_name> <output_name>
```
来对你的输出进行评判。其中 `<input_name>` 为输入文件名称，`<output_name>` 为输出文件名称。


title: [THUPC2019] 大碗宽面

description:
Yazid 喜欢吃大碗宽面。现有 $m$ 碗宽面，其中第 $i$ 碗宽面（$1 \le i \le m$）共包含 $n_i$ 根面条，它们的宽度分别为 $A_{i,1},A_{i,2},\cdots,A_{i,n}$。

记 $f(u,v)$ 表示若混合第 $u$ 碗宽面和第 $v$ 碗宽面，将得到的超大碗宽面的第 $\left\lfloor\dfrac{n_u +n_v +1}{2}\right\rfloor$ 小的面条宽度（$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数）。

Yazid 想求出所有 $f(u,v)$，但为了节省你的输出时间，你只需要对所有 $1 \le u \le m$ 求出：

- $R(u)=\mathop{\rm xor}\limits_{v=1}^{m} {(f(u,v)+u+v)}$（$\rm xor$ 指异或运算，在 C++ 语言中对应 `^` 运算符）。

inputFormat:
第一行一个正整数 $m$，表示宽面碗数。

接下来 $m$ 行，每行若干个用单个空格隔开的整数描述一碗宽面：这部分的第 $i$ 行的第一个正整数为 $n_i$，表示第 $i$ 碗宽面包含的面条数；接下来 $n_i$ 个非负整数 $A_{i,j}$ 描述各面条的宽度。

outputFormat: 输出 $n$ 行，每行一个整数，其中第 $i$ 行的整数为 $R(i)$。


title: [CRCI2008-2009] NOP

description:
Mirko 购买了新的微处理器。

不幸的是，他发现为旧处理器编写的许多程序在新处理器上无法运行。

在深入了解这两种处理器说明书后，他发现了原因。

为了更快地工作，新处理器对程序的机器代码施加了某些约束，而这些约束在以前的模型中是不存在的。

处理器的机器代码由顺序执行的指令组成。 每个指令使用一个字节的存储器。

同样，指令可以具有 $0$ 个或多个参数，每个参数都使用一个额外的内存字节。在机器代码中，参数紧随指令之后。

当设置为文本格式时，机器代码指令为大写字母，而参数为小写字母。 例如：

![a5mSaQ.png](https://s1.ax1x.com/2020/08/08/a5mSaQ.png)

该程序由四个指令组成：第 $1$ 个使用三个参数，第 $2$ 个使用两个参数，第 $3$ 个不使用，第四个使用四个参数。 该程序使用 $13$ 个字节的内存。

新的处理器模型以四字节的块为单位获取内存，因此每条指令必须从可被四整除的内存地址开始（内存中的第一个字节为地址 $0$）。

我们可以将 `NOP`（No Operation，即无操作）指令插入旧程序中，这些指令不执行任何操作。

![a5ezVg.png](https://s1.ax1x.com/2020/08/08/a5ezVg.png)

指令 $A$，$B$，$C$ 和 $D$ 现在位于内存位置 $0$、$4$、$8$ 和 $12$，这满足了处理器的约束。

请你编程求出最少需要插入的 `NOP` 数量。

inputFormat:
一行一个字符串 $s$，表示旧处理器模型编写的程序的机器代码。

该程序将始终以 $1$ 条指令开始，即机器码中的第一个大写字母。 如果一条指令在机器代码中多次出现，则它将始终使用相同数量的参数。

outputFormat: 一行一个正整数 $ans$，表示最少需要插入的 `NOP` 数量。

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

令 $|s|$ 为字符串 $s$ 的字符数，对于 $100\%$ 的数据，$1\le |s| \le 200$。

#### 说明
- 本题满分 $30$ 分。
- 本题译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CRCI2008-2009](https://hsin.hr/coci/archive/2008_2009/regional_tasks.pdf) NOP，译者 @[tearing](https://www.luogu.com.cn/user/219791)。


title: [CRCI2008-2009] MAJSTOR

background: 剪刀石头布是一种流行的两人游戏。

description:
在游戏中，两人都用自己的手出示三个手势之一：石头，布或剪刀。

如果两个玩家出示相同的手势，则该游戏为平局。否则，剪刀胜布，布胜石头，而石头胜剪刀。

Sven 多年来一直在研究游戏的心理错综复杂性，并已成为游戏的真正大师，他的朋友们在一对一的游戏中没有与他抗衡的机会。

随着世界锦标赛的临近，Sven 正在与 $n$ 个朋友同时玩游戏，以练习他的技能。

游戏有 $r$ 轮，在每一轮中，Sven 和他的每个朋友出三种手势之一。

计分规则：

- Sven 获胜，得 $2$ 分。
- 平局，得 $1$ 分。
- 对手获胜，得 $0$ 分。

编写一个程序来计算 Sven 的总得分，如果他事先知道他的朋友会出的所有手势，那么他最大得分也是可能的。

inputFormat:
第一行，一个正整数 $r$，表示比赛轮数。

第二行，$r$ 个字符，第 $i$ 个字符表示 Sven 在第 $i$ 局出的手势，只可能是 `S`（剪刀），`P`（布），`R`（石头）。

第三行，一个正整数 $n$，表示他的朋友数。

接下来 $n$ 行，每行都有 $r$ 个字符，第 $j$ 个字符表示 Sven 的第 $i$ 个朋友在第 $j$ 局出的手势，只可能是 `S`（剪刀），`P`（布），`R`（石头）。

outputFormat:
第一行，输出 Sven 的实际分数。

假设他的朋友没有改变他们的手势，则在第二行输出他最大的得分。

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

对于 $100\%$ 的数据，$1 \le n, r \le 50$。
#### 说明
- 本题满分 $50$ 分。
- 本题译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CRCI2008-2009](https://hsin.hr/coci/archive/2008_2009/regional_tasks.pdf) MAJSTOR，译者 @[tearing](https://www.luogu.com.cn/user/219791)。


title: [CRCI2008-2009] CIJEVI

description:
为了帮助设计天然气管道，克罗地亚和莫斯科正在使用电脑游戏「管道狂热」。

在游戏中，欧洲分为 $R$ 行和 $C$ 列。每个单元格可以为空，也可以包含七个基本管道构建块之一：

![a5eXKf.png](https://s1.ax1x.com/2020/08/08/a5eXKf.png)

气体可以通过构建块沿任一方向流动。 构建块 `+` 的特殊之处在于气体必须沿两个方向（一个垂直方向，一个水平方向）流动，如以下示例所示：

![a5eLxP.png](https://s1.ax1x.com/2020/08/08/a5eLxP.png)

当黑客从计划中删除了一个构建块时，但新管道已经开始投入使用。

编写一个程序，确定被删除构建块的位置和它的类型。

inputFormat:
第一行，两个整数 $R$ 和 $C$，表示欧洲的面积。

接下来，$R$ 行，表示该计划，字符有：

- `.`， 表示空单元格
- `|`，`-`，`+`，`1`，`2`，`3`，`4`，表示构件类型（见图 $1$）；
- `M`，表示莫斯科。
- `Z`，表示克罗地亚。

**数据保证 `M` 和 `Z` 仅出现一次。**

莫斯科和克罗地亚的每一个都将恰好有一个构建块。 此外，该计划将没有冗余构建块，即在添加丢失的块之后必须使用计划中的所有块。

输入将保证解决方案存在并且是唯一的。

outputFormat: 输出被擦除块的行和列，以及块的类型（输入中的 $7$ 个字符 `|`，`-`，`+`，`1`，`2`，`3`，`4` 之一）。

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

对于 $100\%$ 的数据，$1 \le R, C \le 25$。
#### 说明
- 本题满分 $70$ 分。
- Subtask 1 为 hack 数据，不计分。
- 本题译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CRCI2008-2009](https://hsin.hr/coci/archive/2008_2009/regional_tasks.pdf) CIJEVI，译者 @[tearing](https://www.luogu.com.cn/user/219791)。
- 2023.11.17 添加一组 hack 数据。
- 2024.02.16 再添加一组 hack 数据。


title: [CRCI2008-2009] TABLICA

description:
小 Q 有一张 $N \times N$ 的表格。若 $N = 4$，那么他将 $1$ 填入第一列第一行，$2$ 填入第二列第一行，$\cdots$，$5$ 填入第一列第二行，$\cdots$，$15$ 填入第三列第四行，$16$ 填入第四列第四行。

现在，小 Q 对该表格作如下操作：
1. 移动行：向右移动一行中的所有单元格，以使最后一列中的数字移到第一列。

2. 移动列：向下移动一列中的所有单元格，以使最后一行中的数字移到第一行。

小 Q 想把一个数字 $X$ 移到单元格 $(R,C)$，于是进行如下操作：

- 当 $X$ 不在第 $C$ 列时，移动它所在的行。
- 当 $X$ 不在第 $R$ 行时，移动它所在的列。

下面是一个如何将数字 $6$ 移动到单元格 $(3, 4)$ 的例子。

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

小 Q 想移动 $K$ 个数字，问至少要进行多少次操作。

inputFormat:
第一行，两个正整数 $N$ 和 $K$，分别表示表格大小和移动次数。

接下来，$K$ 行，对于每一行：

- 三个整数 $X, R, C$，含义见题目描述。

outputFormat:
共 $K$ 行，对于每一行：

- 对每个询问，输出至少移动的次数。

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

对于 $100\%$ 的数据：$2 \le N \le 10^4$，$1 \le K \le 10^3$，$1 \le X \le N^2$，$1\le R,C \le N$。

#### 说明
- 本题满分 $100$ 分。
- 本题译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CRCI2008-2009](https://hsin.hr/coci/archive/2008_2009/regional_tasks.pdf) TABLICA，译者 @[tearing](https://www.luogu.com.cn/user/219791)。


title: 「MCOI-02」Build Battle 建筑大师

background:
WAPER 爱玩 hypixel（世界上最大的 Minecraft 小游戏服务器） 建筑大师！

提示：在本题中，羊毛属于一种方块。

description:
现在 WAPER 准备玩 $q$ 局建筑大师。在第 $i$ 局游戏的开始，WAPER 会选定一个参数 $m_i$，并 **按顺序** 放置 $n$ 个有颜色的羊毛，羊毛颜色的排列如下：

$$1,\ 2,\ ...\ ,\ m_i-1,\ m_i,\ 1,\ 2,\ ...\ ,m_i-1\ ,m_i\ ,\ ...\ (n-1) \ \bmod \  m_i+1$$

例如 $n=7,m=3$ 时，颜色排列如下：

$$1\ ,2,\ 3,\ 1,\ 2,\ 3,\ 1$$

现在 WAPER 准备打破一些方块（可以一个也不打破，也可以全部打破），WAPER 想知道这样可以产生多少种不同的颜色序列。（两个颜色序列不同当且仅当其长度不同或某一位置的羊毛颜色不同）

因为答案太大，所以输出答案对 $10^9+7$ 取模的结果。

（其实就是询问这个序列本质不同的子序列对 $10^9+7$ 取模的结果）

inputFormat:
第一行两个整数 $n$ 和 $q$ 代表羊毛数和局数。
第二行 $q$ 个整数 $m_i$ 代表参数。

outputFormat:
$q$ 行，每行一个整数代表答案。
答案对 $10^9+7$ 取模。

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

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

- Subtask 1（5 pts）$\ \ $：$n \le 20$，$q=1$。
- Subtask 2（15 pts）：$n \le 10^3$，$q=1$。
- Subtask 3（15 pts）：$\max\{m_i\} \le 20$，$q=1$。
- Subtask 4（25 pts）：$q=1$。
- Subtask 5（40 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,q \le 10^6$，$1 \le m_i \le n$。

#### 说明

Minecraft OI Round 2 B

- Maker：WAPER420
- Tester：灵空

$样例不是出题人写的！！！！！！！！$


title: 「EZEC-3」四月樱花

background:
$$又到樱花曼舞的春日，$$

$$花蕾，像无数星星闪烁在枝头含春嬉戏，$$

$$心有灵犀；$$

$$又是为花吹雪的季节，$$

$$花蕊，引万千蜂蝶赶树梢抱春絮语，$$

$$心有念想。$$

$$开了，一夜乍起，$$

$$火树樱花汇聚开遍山野好似茫茫沧海；$$

$$大地樱花，$$

$$赏心悦目怒放层林尽染好似朵朵云霞；$$

$$纵有三千烦恼，$$

$$不过灿烂阳光下释然地娓娓一笑；$$

$$纵有万般郁闷，$$

$$不如和煦暖风里淡淡地悠悠一了；$$

[——《四月樱花》](http://music.163.com/song?id=1355079681&userid=587823498)

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

description:
在樱花盛开的四月，```Muxii``` 望着满天飘落的樱花，向身旁的 ```ZZH``` 问道：

“究竟有多少朵樱花在这个四月飘落？”

```ZZH``` 答道：“樱花飘落的朵数 $s$ 与时间 $t$ 有如下关系：

$$s=\prod_{x=1}^t\prod_{y|x}\frac{y^{d(y)}}{\prod_{z|y}(z+1)^2}$$

其中 $d(y)$ 表示 $y$ 的约数个数。”

但作为一个~~文科生~~萌新，```Muxii``` 显然无法清楚地知道具体的数目，因此他只好继续向 ```ZZH``` 询问这个问题的答案。

由于数量可能很大，所以你只需要替 ```ZZH``` 告诉 ```Muxii``` 他所需要的答案对 $p$ 取模的结果就好了。

inputFormat: 两个正整数 $t$ 和 $p$，分别表示 ```Muxii``` 询问的时间、模数。

outputFormat: 输出一个正整数 $s$，表示樱花飘落的朵数。答案对 $p$ 取模。


title: [CRCI2008-2009] RELJEF

description:
两组穴居人发生了土地纠纷，决定用老办法解决——互相扔棍子。争斗是在一个山洞里发生的，这个山洞很高，所以不用担心棍子飞得太高，但是地面上的矿藏却会妨碍棍子的飞行。

洞可以划分为 $r$ 行和 $c$ 列，所以整个洞口由 $r \times c$ 个单元格组成（可当作一个竖直的平面）。

洞穴中的每一个单元格要么是空的，要么含有一块矿物块。如果两块矿物块在四个主要方向（上、下、左、右）中的一个方向上相邻，则判定它们属于同一矿群。

争斗开始时，一组穴居人在山洞的左侧，另一组穴居人则在右侧。这两组人轮流向另一组人投掷棍子，先由一组人选择棍子飞行的高度，然后（必要时爬到别人的肩膀上）投掷，棍子将在选定的高度上水平飞过洞穴。

如果棍子在路上撞到了一块矿物块，该单元格处的矿物块将被击碎（即不复存在），棍子也将同时掉落至地面而停止飞行。

当一个矿物块被击碎后，与其相连的矿物块群可能因不再有矿物块与其相连作为支撑物而因重力向地面坠落。在下落的过程中，矿物块群不会改变形状，即其中所有的矿物块将会一起下落。如果下落时某个矿物块落在地面上，整个矿物块群就会停止下落并成为一个新产生的矿物块。特别地，如果一个矿物块落在另一个矿物块上，它们就会合并成为一个矿物块。

现在已知洞穴中矿物块的布局和扔棍子的高度，请确定这场争斗结束后，洞内的矿物布局。

inputFormat:
第一行，两个整数 $r$, $c$，含义见题目描述。

接下来是一个字符表，共有 $r$ 行 $c$ 列。其中，`.` 代表一个空单元格，`x` 代表一个含有矿物块的单元格。

接下来一行，一个正整数 $n$，表示木棍数。

最后一行，$n$ 个整数，表示棍棒的投掷高度。高度 $1$ 为矩阵的底部，高度 $r$ 为顶部。 第一根棍将从左向右飞行，第二根则从右向左飞行，以此类推。

outputFormat: 共 $r$ 行，每行 $c$ 个字符，表示洞穴的最终布局。

hint:
#### 样例 #2 解释
第一根木棍将第 $4$ 列高度为 $6$ 的矿物块击碎，未使任何矿物块失去支撑而下落；

第二根木棍将第 $7$ 列高度为 $6$ 的矿物块击碎，未使任何矿物块失去支撑而下落；

第三根木棍将第 $3$ 列高度为 $4$ 的矿物块击碎，使第 $4$ 列高度为 $4$ 和 $5$ 的两个矿物块下落直至与该列高度为 $1$ 的矿物块合并；

第四根木棍将第 $7$ 列高度为 $3$ 的矿物块击碎，使第 $6$ 列高度为 $3$ 的矿物块连带着第 $5$ 列高度为 $3$，$4$，$5$ 的矿物块以及第 $6$ 列高度为 $6$ 的矿物块一起下落直至落至地面；

第五根木棍将第 $2$ 列高度为 $1$ 的矿物块击碎，未使任何矿物块失去支撑而下落。

#### 数据规模及约定
- 对于 $100\%$ 的数据，$1\le r,c,n \le 100$。
- 对于 $100\%$ 的数据，保证初始状态下不会有任何一个碎块群漂浮在空中，且在任何时间点都不会有两个或两个以上的碎块群同时落下。
#### 说明
- 本题满分 $120$ 分。
- 本题译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CRCI2008-2009](https://hsin.hr/coci/archive/2008_2009/regional_tasks.pdf) RELJEF，@[tearing](https://www.luogu.com.cn/user/219791) 作了主要的翻译工作，@[mnesia](https://www.luogu.com.cn/user/115711) 进行了润色以及对样例 #2 的解释进行了翻译。


title: [CRCI2008-2009] CVJETICI

description:
在一个遥远的星球上，发现了一种有两根茎的奇怪植物。

行星上的每个植物都可以用 $3$ 个数进行描述：茎 $L$， $R$ 的 $x$ 坐标，以及茎连接的高度 $H$。 以下给出的图像描绘了 $L = 2$， $R = 5$， $H = 4$ 时的植物：

![a5evqS.png](https://s1.ax1x.com/2020/08/08/a5evqS.png)

每天，这个星球上都有新植物生长起来。在第 $1$ 天生长的植物，其高度为 $1$，之后每一天长出来的每株植物高度都比前一天长出来的植物高。

当一株植物的茎与另一株植物连接两根茎的的水平线相交时，交点处就会长出一朵小花（该处有小花时除外）。**有一种情况例外**：如果交点处成 ``T`` 字构形，即一株植物的茎与另一株植物的茎重合时，交点处将不会长出小花。下面是一些示例：

![a5mp5j.png](https://s1.ax1x.com/2020/08/08/a5mp5j.png)

在给出所有植物坐标的情况下，请求出每天长出的小花的数量。

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

接下来，$n$ 行中，每行两个整数 $L_i$ 和 $R_i$，表示某一天长出的植物的两根茎的坐标。

outputFormat: 共 $n$ 行，每行一个正整数，依次表示第 $n$ 天时长出的小花数量。

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

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le L_i < R_i \le 10^5$。
#### 说明
- 本题满分 $130$ 分。
- 本题译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CRCI2008-2009](https://hsin.hr/coci/archive/2008_2009/regional_tasks.pdf) CVJETICI，@[tearing](https://www.luogu.com.cn/user/219791) 作了主要的翻译工作，@[mnesia](https://www.luogu.com.cn/user/115711) 进行了润色。


title: [BalticOI 2010 Day1] Lego

description:
给定一些 $2 \times 2$ 的乐高方块，分别有白色（W），灰色（G）和黑色（B）。现在您要往 $6 \times 6$ 的底板上放置方块，需要保证不能有完全浮空的方块（即四个方格均无放置的地方）也不能超出 $6 \times 6$ 的底板。

现在给定一个放置完方块的底板的一面的示意图，和这一面逆时针旋转 $90^\circ$ 后的一面的示意图，求有多少种放置方块的方法数。

inputFormat:
第一行一个整数 $H$ 代表这种放置方块的高度。
接下来 $H$ 行每行六个字符，代表从这一面看到的示意图。
接下来 $H$ 行每行六个字符，代表从上一面逆时针旋转 $90^\circ$ 后的示意图。
只能从前面，后面，左面，右面看，不能从上面，下面看。

outputFormat:
一行一个整数代表答案。
答案保证在 64 位有符号整数内。

hint:
#### 样例 1 解释

如下图：

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

第一个是从 $A$ 面观察到的示意图。
第二个是从 $B$ 面（$A$ 面逆时针旋转 $90^\circ$）观察到的示意图。

下面是这 $6$ 种情况（感谢 Vonov 提供的图片！）：

![](https://cdn.luogu.com.cn/upload/image_hosting/wymozlif.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/1vw0fu3t.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/umn2hync.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/pykojvay.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/9z9wvzxp.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/hkp3tjfp.png)

#### 数据规模与约定

对于 $100\%$ 的数据，$1 \le H \le 6$。

#### 说明

翻译自 [BalticOI 2010 Day1 B Lego](https://boi.cses.fi/files/boi2010_day1.pdf)。


title: [BalticOI 2010 Day1] Printed Circuit Board

description:
你现在有无数个平面直角坐标系，给定 $N$ 条线段，每条线段连接 $(X_{i,1},0)$ 和 $(X_{i,2},H)$（$H$ 是一个正数，不过并不给定，解题也并不需要），要求将这些线段放置在平面直角坐标系上，不能有任意两条线段相交。

求最小需要多少平面直角坐标系才能容纳这些线段。

inputFormat:
第一行一个整数 $N$ 代表线段数。
接下来 $N$ 行每行两个整数 $X_{i,1},X_{i,2}$ 代表一条线段。

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

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

对于 $100\%$ 的数据，$1 \le N\le 10^5$，$0 \le X_{i,1},X_{i,2} \le 10^6$。所有的 $X_{i, 1}$ 互不相同，所有的 $X_{i,2}$ 互不相同。也即，没有两个端点在同一位置。

#### 说明

翻译自 [BalticOI 2010 Day1 C Printed Circuit Board](https://boi.cses.fi/files/boi2010_day1.pdf)。


title: [BalticOI 2010 Day2] Matching Bins

description:
给定一行 $N$ 个整数 $A_1,A_2,\dots,A_N$。 $M=\max\{A_1,A_2,\dots A_N\}$。

你需要找到一个最大的整数 $K$，使得从左至右共 $K$ 个数都小于接下来的 $K$ 个数。

inputFormat:
输入第一行两个整数 $M,N$，表示数列中的最大数和数的个数。

第二行 $N$ 个整数 $A_1,A_2,\dots,A_N$。

outputFormat: 输出一行一个整数，为最大的 $K$。

hint:
对于 $100\%$ 的数据，保证 $1\le M\le 2\times 10^3$，$1\le N\le 2\times 10^4$，$1\le A_i\le M$。

----

**题目译自 [BalticOI 2010](https://www.luogu.com.cn/problem/U125995) [Day2](https://boi.cses.fi/files/boi2010_day2.pdf) *T1 Matching Bins***。


title: [BalticOI 2010 Day2] Candies

description:
给定一个长度为 $N$ 的序列 $B_1,B_2,\dots,B_N$。

一个整数 $M$ 能够被表示出来当且仅当从序列中任取 $K$ 个数 $A_1,A_2,\dots,A_K$，使得 $\sum_{i=1}^{k}A_i=M$。

你需要修改序列中的一个数 $P$，使得尽可能多的整数能够被表示出来。

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

第二行 $N$ 个整数 $B_1,B_2,\dots,B_N$。

outputFormat:
输出一行两个整数 $P,Q$，以一个空格隔开。

表示序列中的一个数字 $P$ 修改成 $Q$。

如果有多种方案，则输出的 $P$ 尽可能小。 $P$ 最小时如有多种方案，则输出的 $Q$ 尽可能小。

hint:
对于 $100\%$ 的数据，保证 $2\le N\le 100$，$1\le B_i\le 7000$。

**题目译自 [BalticOI 2010](https://www.luogu.com.cn/problem/U126003) [Day2](https://boi.cses.fi/files/boi2010_day2.pdf) *T2 Candies***。


title: [BalticOI 2010 Day2] Mines

background: **本题为提交答案题，输入公开，请见题目附件。**

description:
给定一个 $H\times W$ 的矩阵 A，矩阵 A 中的每个数都等于矩阵 B 中相同位置四周八个方向的 `X` 加上该位置的 `X` 的个数。

请构造任意一种由 `.` 和 `X` 组成的满足题意的 $H\times W$ 的矩阵 B.

inputFormat:
输入第一行一个整数 $H,W$，表示矩阵的规格。

接下来的 $H$ 行，每行 $W$ 个整数，表示矩阵 A。

outputFormat: 输出共 $H$ 行，每行 $W$ 个字符 `.` 或 `X`，表示一种满足条件的矩阵 B。**本题使用 SPJ。**

hint:
对于 $100\%$ 的数据，保证 $1\le H,W\le 600$，始终有方案存在。

**题目译自 [BalticOI 2010](https://www.luogu.com.cn/problem/U126003) [Day2](https://boi.cses.fi/files/boi2010_day2.pdf) *T3 Mines***。


title: 「MCOI-02」Ancestor 先辈

background:
这题跟 MC 有关的就是题目背景出现了三次 MC，提示说明出现了一次 MC。

```
           ▃▆█▇▄▖
       ▟◤▖　　　  ◥█
   ◢◤ 　  ◢▐　　     ▐▉
 ▗◤　  　   ▂ ▗▖　 ▕ █▎
 ◤　▗▅▖ ◥▄　 ▀▀▀◣　█▊
▐　▕▎  ◥▖◣◤　 　　◢██
█◣　◥▅█▀　     　▐███◤
▐█▙▂　　　      ◢███◤
　◥██◣　　　　 ◢▄◤
　　　▀██▅▇▀▎▇
```

description:
对于两个序列 $a,b$，如果满足：

$$ \forall i \leq \min(n,m),s.t.\ a_i \leq b_i $$

那么我们称 $a$ 比 $b$ 屑（$n$ 为 $a$ 的长度，$m$ 为 $b$ 的长度）。

如果对于一个序列 $a$，它比它的所有后缀都屑，那么我们称这个序列为先辈。

给定一个长为 $n$ 的序列 $a_i$，共有 $k$ 次操作，包括以下两种：

- `1 l r x` 区间 $[l,r]$ 加上 $x$。
- `2 l r` 查询区间 $[l,r]$ 是不是先辈。

inputFormat:
第一行两个整数 $n,k$ 代表序列长度与操作数。
第二行 $n$ 个整数 $a_i$ 代表数列每一项的值。
接下来 $k$ 行每行首先三个整数 $opt,l,r$：

- 如果 $opt=1$，接下来一个整数 $x$ 代表操作 $1$。
- 如果 $opt=2$，代表操作 $2$。

**由于数据故障，$r$ 可能取到 $n+1$，请在这类情况下自行令 $r=n$，谢谢。**

outputFormat: 对于每个操作 $2$，输出询问结果。

hint:
#### 样例说明

对于样例 $1$：

1. 询问区间 $[1,3]$ 是否为先辈，不是，输出 `No`。
2. 区间 $[3,4]$ 加上 $9$，现在序列为 $\{1,9,10,18,8,1,0\}$。
3. 询问区间 $[1,4]$ 是否为先辈，是，输出 `Yes`。
4. 区间 $[5,6]$ 加上 $11$，现在序列为 $\{1,9,10,18,19,12,0\}$。
5. 询问区间 $[2,6]$ 是否为先辈，不是，输出 `No`。

#### 数据规模与约定

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

- Subtask 1（1 pts）$\ \ $：询问操作的区间长度均为 $1$。
- Subtask 2（9 pts）$\ \ $：$n,k \le 10^3$。
- Subtask 3（10 pts）：$n,k\le 5\times 10^3$。
- Subtask 4（10 pts）：只有查询操作。
- Subtask 5（10 pts）：修改操作的数量不超过 $100$。
- Subtask 6（20 pts）：$n,k \le 10^5$。
- Subtask 7（40 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,k \le 10^6$，$|a_i|,|x| \le 10^9$。

**本题强制 $O2$ 优化。**

#### 说明

Minecraft OI Round 2 C

- Maker：happydef
- Tester：tarjin


title: [COCI2009-2010#3] FILIP

description:
给你两个十进制正整数 $a, b$，输出将这两个数翻转后的较大数。

**「翻转」在本题中的定义详见「说明 / 提示」部分。**

inputFormat: 第一行，两个十进制正整数 $a, b$。

outputFormat: 第一行，$a$ 和 $b$ 翻转后的较大数。

hint:
#### 「翻转」在本题中的定义

设原数有 $f$ 位，最高位为 $a_1$，第二位为 $a_2$，……，第 $f$ 位为 $a_f$。

那么该数的翻转同样有 $f$ 位，最高位为为 $a_f$，第二位为 $a_{f - 1}$，……，第 $f$ 位为 $a_1$。

#### 数据规模及约定

对于 $100\%$ 的数据，$100 \le a, b \le 999$，$a, b$ 不含 $0$ 或不为 $0$。

#### 说明
翻译自 [COCI 2009-2010 #3 T1 FILIP](https://hsin.hr/coci/archive/2009_2010/contest3_tasks.pdf)，满分 30，每个测试点 3 分，共 10 个测试点。


title: [COCI2009-2010#3] SLATKISI

background: 可爱的 Mirko 在糖果店买了很多糖果。

description:
他不能总是支付准确的金额，所以店主和他达成了协议。

他告诉店主他有的最小的钞票，店主就把他的金额四舍五入到他能支付的最接近的数字。

例如，如果 Mirko 最小的钞票是 $100$ 元，他想买 $150$ 元的糖果，店主就把他的金额四舍五入到 $200$ 元。如果他想买 $149$ 元的糖果，店主就会把他的金额四舍五入到 $100$ 元。

最近，Mirko 怀疑店主想骗他。请你判断店主有没有骗他。

Mirko 的妈妈只会给他 $1, 10, 100, 10^3, 10^4, 10^5, \cdots, 10^9$ 元钞票，他有无限张这些钞票。

inputFormat: 第一行，两个整数，$c, k$，表示 Mirko 要买的糖果的价格和 Mirko 最小的钞票上的零数，这里的「零数」指的是一个数 $0$ 的个数，在本题中，即 $10^t$ 中的 $t$。

outputFormat: 第一行，一个整数，$c$ 四舍五入到最接近的 Mirko 可以的支付金额。

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

对于 $100\%$ 的数据，$1 \le c \le 10^9$，$0 \le k \le 9$。

#### 说明
翻译自 [COCI 2009-2010 #3 T2 SLATKISI](https://hsin.hr/coci/archive/2009_2010/contest3_tasks.pdf)，满分 50，每个测试点 5 分，共 10 个测试点。


title: [COCI2009-2010#3] SORT

description:
Mirko 是一个伟大的密码破解者。他知道世界上任何密码都可以通过频率分析来破解。

但他完全弄错了什么是频率分析。

他截获了一个敌人的信息。这个信息由 $N$ 个小于等于 $C$ 的数字组成。

Mirko 相信频率分析包括对这个序列进行排序，使频率较高的数字出现在频率较低的数字之前。

给定任何两个数字 $x$ 和 $y$，如果 $x$ 在原始序列中出现的次数大于 $y$ 出现的次数，则 $x$ 出现在 $y$ 之前。如果出现的次数相等，则输入中谁的值出现的早，谁就应该在排序后的序列中出现靠前。

请帮助 Mirko 制作一个「频率排序器」。

inputFormat:
第一行，两个正整数 $N, C$，含义见题目描述。

第二行，$N$ 个正整数 $a_i$，表示消息。

outputFormat: 第一行，$N$ 个正整数，表示排序后的序列。

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

对于 $100\%$ 的数据，$1 \le N \le 10^3$，$1 \le C \le 10^9$，$1\le a_i \le C$。

#### 说明
翻译自 [COCI 2009-2010 #3 T3 SORT](https://hsin.hr/coci/archive/2009_2010/contest3_tasks.pdf)，满分 70，每个测试点 7 分，共 10 个测试点。


title: [COCI2009-2010#3] RAZGOVOR

description:
可爱村只有一条长长的街道，从东向西延伸，有 $m$ 户人家。每栋房子都有一个单独的房号，从 $1$ 开始到 $m$ 结束。

最近的暴风雪摧毁了大部分电话线，所以市长出资建造了一个新的电话线。Mirko 对这个新的电话网络的普及程度很感兴趣，所以他在一些点上安装了特殊的探测器。

探测器可以检测到两栋房子之间的任何电话，一栋房子在探测器的 **东边**，一栋房子在探测器的 **西边**。

在第一个月结束时，Mirko 撤掉了所有的探测器，现在想知道在这一个月里，可能打过的电话中，**最小** 的电话数量是多少。

inputFormat:
第一行，两个正整数，$n, m$，分别表示探测器和房屋的数量。

接下来，$n$ 行，每行两个正整数 $P_i$，和 $C_i$，编号为 $i$ 的探测器检测到的位置和电话总数。 我们说，如果且仅当一个探测器在编号为 $P_i$ 和 $P_i+1$ 的房屋之间时，他就在位置 $P_i$ 上。

**同一位置上最多有一个探测器。**

outputFormat: 输出一个正整数，表示最小的通话次数。

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

- 对于 $50\%$ 的数据，$1 \le n \le 10^3$，$1 \le C_i \le 10^3$，$n < m \le 10^9$，$1 \le P_i < M$。
- 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le C_i \le 10^9$，$n < m \le 10^9$，$1 \le P_i < M$。

#### 说明
翻译自 [COCI 2009-2010 #3 T4 RAZGOVOR](https://hsin.hr/coci/archive/2009_2010/contest3_tasks.pdf)，满分 100，每个测试点 10 分，共 10 个测试点。


title: 3D Cube

background:
**此题数据纯手造，并有手玩验证。**

idea & data：[zrmpaul](/user/226760)
tester：[Hilarious_Reality](/user/80049)

--------

小 Z 喜欢三维模型，并从不同角度进行细致的观察。

description:
小 Z 拿到了一个二维矩阵。底面可以看作一个 $n \times m$ 的方格纸。

在每一个格子上，可以放任意个方块。由于有地心引力，方块不会悬空，且不会用胶水粘住。

他给出了这个三维矩阵的三视图，请你构造一个方块组，满足以下条件：

对于每一行、每一列，最多只有一个“**峰**”出现。特别地，底层矩阵的周围的高度被视为 $0$。如 `12321` 是一个“峰”，而 `13231` 有两个“峰”。

再举一些例子：

|方块排列|“峰”的数量|
|:----:|:----:|
|$\texttt{123}$|$1$|
|$\texttt{212}$|$2$|
|$\texttt{122221}$|$1$|
|$\texttt{00011000}$|$1$|
|$\texttt{10010101}$|$4$|

求出需要**最少**方块的矩阵。如果无解，请输出 `-1`。

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

第二行 $n$ 个整数：左视图，第 $i$ 个整数表示左视图中第 $i$ 列的方块个数。

第三行 $m$ 个整数：主视图，第 $j$ 个整数表示主视图中第 $j$ 列的方块个数。

接下来 $n$ 行，每行 $m$ 个整数：俯视图，其中 `0` 表示没有方块，`1` 表示有方块。

outputFormat:
如果无解，则输出 `-1`。

否则输出共 $n$ 行，每行 $m$ 个非负整数，为构造的三维矩阵的俯视图，其中第 $i$ 行第 $j$ 个整数表示该位置上的方块个数。

**请确保按照输出格式输出，否则可能导致 SPJ 返回 UKE 等结果。**

hint:
### 数据范围

**本题各部分测试点采用捆绑测试。**

对于 $20\%$ 的数据：给出输入文件，程序打表输出答案，见附件 `easy.zip`。

对于 $100\%$ 的数据：$n\times m\leq25$。在俯视图中每个格子上最多有 $7\times10^8$ 个方块，且在俯视图中 `1` 的个数 $\leq20$。


title: 小 H 的序列

background: 小 H 有一个序列。

description:
**提交时自动开启 O2 优化。**

小 H 想让你维护一个长为 $n$ 序列 $a_1,a_2,\ldots,a_n$，要求支持

- 修改操作：将所有满足$i\in[l,r]$且$u\le a_i\le v$的$a_i$的值修改为$w$；
- 查询操作：求出$\sum_{i=l}^ra_i^t\bmod k$。

inputFormat:
总共包括 $m+2$ 行。

第一行包含两个正整数 $n,m$，分别表示序列长度和操作次数。

第二行包含 $n$ 个正整数 $a_1,a_2\ldots,a_n$，表示最初的序列。

接下来的 $m$ 行，每行由一个数 $o$ 开头，表示操作类型。

- 如果 $o=0$，表示修改操作，紧接着给出五个正整数 $l,r,u,v,w$；
- 如果 $o=1$，表示查询操作，紧接着给出四个正整数 $l,r,t,k$，意义如【题目描述】中所述。

每行的两个数字间由单个空格隔开，数据在 Windows 下生成。**行末不保证没有多余空格**。

outputFormat: 一行一个整数，表示所有查询操作的答案的异或和（如果没有查询操作输出一个数 $0$）。

hint:
输入的所有数字均为正整数。
设存在数据范围 $\mathrm{randmax}$，满足 $n,m,a_i,w\le\mathrm{randmax},1\le l\le r\le n,1\le u\le v\le \mathrm{randmax},1\le t,k\le10^9$。

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

保证数据除 $n,m$ 以及测试点 $4,5$ 的 $t$ 外随机，各变量意义如【题目描述】中所述。

由于本题输入量较大及为了省下不必要的评测耗时，请注意输入优化。在此给出以下模板（`c++`语言）：

```cpp
/* ---- read() & rlong() - begin ---- */
#define gc() (p0==p1&&(p1=(p0=buf)+fread(buf,1,1048576,stdin),p0==p1)?EOF:*p0++)
char buf[1048576],*p0,*p1;
inline int read() {
	int r=0; char c=gc(); while (c<48||c>57) c=gc();
	while (c>47&&c<58) {r=(r<<3)+(r<<1)+(c^48); c=gc();} return r;
}
#undef gc
/* ---- read() & rlong() -- end ----- */
```

调用`read()`函数会从输入中读入一个`int`型整数，注意该模板不能处理负数，调试时请使用文件输入。


title: 「MCOI-02」Convex Hull 凸包

background: 一场比赛需要一道签到题。

description:
Leasier 玩 MC 被逮到了，所以他只好算出下面这个式子的值。

$$\displaystyle\sum_{i = 1}^n \sum_{j = 1}^m \tau(i) \tau(j) \tau(\gcd(i, j))$$

由于结果可能很大，所以你只需要求出结果对 $p$ 取模的值。

如果您对本题的数学符号有疑问，请到「提示」区查看提示。

inputFormat: 一行，三个整数 $n, m, p$。

outputFormat: 一行，一个整数，表示所求的值。

hint:
#### 数据规模和约定
**本题开启捆绑测试。**

| Subtask | $n, m$ | 分值 |
| :------: | :------: | :------: |
| $1$ | $1 \leq n, m \leq 10^3$ | $15 \operatorname{pts}$ |
| $2$ | $1 \leq n, m \leq 10^5$ | $25 \operatorname{pts}$ |
| $3$ | $1 \leq n, m \leq 10^6$ | $30 \operatorname{pts}$ |
| $4$ | 无特殊限制 | $30 \operatorname{pts}$ |

对于 $100\%$ 的数据，$1 \leq n, m \leq 2 \times 10^6$，$1 \leq p \leq 10^9$。
#### 提示
作为对萌新友好的签到题，肯定是要给提示的。

- $\sum$ 为求和符号，比如 $\displaystyle\sum_{i = 1}^n i$ 代表 $1 + 2 + \cdots + n$。
- $\tau$ 表示约数个数，比如 $\tau(6) = 4$。
- $\gcd$ 是最大公约数，比如 $\gcd(12, 15) = 3$。
#### 说明
Minecraft OI Round 2 A

- Maker：Leasier
- Tester：happydef


title: [USACO05MAR] Space Elevator 太空电梯

description:
奶牛们要去太空了！它们打算用方块建造一座太空电梯。现在它们有 $N$ 种方块，第 $i$ 种方块有一个特定的高度 $h_i$，一定的数量 $c_i$。为了防止宇宙射线破坏方块，第 $i$ 种方块的任何部分不能超过高度 $a_i$。\
请用这些方块堆出最高的太空电梯。

inputFormat:
第一行，一个整数 $N$；\
第二行到 $N+1$ 行，第 $i+1$ 行三个整数 $h_i,a_i,c_i$，数字之间用空格分隔。

outputFormat: 共一行，一个整数，为太空电梯的高度。


title: [COCI2009-2010#3] PATULJCI

description:
白雪公主和 $n$ 个小矮人在森林里，当 $n$ 个小矮人在挖矿时，白雪公主在玩电脑。

每天早上，小矮人排成长长的队伍，去矿山挖矿。白雪公主在他们身边跑来跑去，拍下照片上传到她最喜欢的 App 上。

小矮人进入矿区后，白雪公主回到自己的房子里，翻看图片，挑选漂亮的图片。每个小矮人都有一顶彩色的帽子，有 $c$ 种不同的颜色。如果一张照片上有一半以上的帽子是同一种颜色，那就是漂亮的。换句话说，如果图片上有 $k$ 个小矮人，如果大于 $\dfrac{k}{2}$ 个小矮人有相同颜色的帽子，那就是漂亮的图片。

请求出第 $m$ 张图是否漂亮，如果漂亮，以什么颜色为主。

inputFormat:
第一行，两个正整数 $n, c$，分别表示小矮人的数量和颜色的数量。

第二行，$1$ 到 $c$ 之间的 $n$ 个整数，表示小矮人帽子的颜色，按照当天早上排队的方式排序。

第三行，一个正整数 $m$，表示图片数量。

接下来，$m$ 行，每行两个正整数 $a$ 和 $b$。每一行都描述了一幅画，上面有从 $a$ 开始一直到 $b$ 的所有小矮人。

outputFormat: $m$ 行。对于每张图片，如果白雪公主认为图片不漂亮，则输出 `no`，如果认为漂亮，则输出 `yes` 和 $x$，$x$ 是图片上的主要颜色。

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

- 对于 $30\%$ 的数据，$1 \le m < 10$，$3 \le n \le 3 \cdot 10^5$，$1 \le c \le 10^4$，$1 \le a \le b \le n$。
- 对于另外 $30\%$ 的数据，$1 \le m \le 10^4$，$3 \le n \le 3 \cdot 10^5$，$1 \le c < 10$，$1 \le a \le b \le n$。
- 对于 $100\%$ 的数据，$1 \le m \le 10^4$，$3 \le n \le 3 \cdot 10^5$，$1 \le c \le 10^4$，$1 \le a \le b \le n$。

#### 说明
翻译自 [COCI 2009-2010 #3 T5 PATULJCI](https://hsin.hr/coci/archive/2009_2010/contest3_tasks.pdf)，满分 120，每个测试点 12 分，共 10 个测试点。


title: 小 L 的零食

background: 小 L 很喜欢吃零食。

description:
**提交时自动开启 O2 优化**。

小 L 现在想把一些零食放在一个盒子里。但是零食没放稳就会摔坏，所以小 L 希望求出**有多少种稳定的堆放零食的方法**。

零食都可以抽象成一个 $1\times1$ 的正方形，而盒子的底部可以看成长度为 $n$ 的一维线段。准确地说，零食被分为 $n$ 堆，从左到右地放在盒子里面，依次记为第 $1,2,\ldots,n$ 堆。我们认为每一堆的高度 $h_i$ 是这一堆零食的数量，且任意一堆都可以不包含任何零食。

我们定义第 $i$ 堆零食是稳定的，当且仅当：

- $h_i\le m$，即这一堆零食高度不超过 $m$。
- 在满足上一条的同时，满足以下两条之一或同时满足：
  - $i=1$ 或 $i=n$，此时有一侧是盒子内壁所以这一堆不会倒下；
  - $\color{red}\max\{h_{i-1},h_{i+1}\}\ge h_i-d_i$，此时它两侧的两堆零食有一堆足够高可以支撑这一堆不倒下。

我们定义一种稳定的堆放零食的方法，是一个长度为 $n$ 的 $h_i$ 的序列，满足按这个序列堆放出来的零食每一堆都是稳定的。

显然盒子里最多放下 $n\times m$ 个零食，我们认为小 L 的零食数量不少于 $n\times m$，并且不必将所有零食全部放进盒子。额外地，我们认为**每一个零食都是完全一样的**。

inputFormat:
总共包括 $2$ 行。

第一行包含两个正整数 $n,m$。

第二行包含 $n$ 个整数 $d_1,d_2\ldots,d_n$，意义如【题目描述】中红色部分所示。

每行的两个数字间由单个空格隔开，数据在 Windows 下生成。**行末不保证没有多余空格**。

outputFormat: 一行一个整数，表示有多少种稳定的堆放零食的方法，**结果对 $998244353$ 取模**。

hint:
本题采用如下计分策略：
**subtask $1$**（#$1$~#$8$）：$10\%$，$n,m\le5$；
**subtask $2$**（#$9$~#$12$）：$30\%$，$n,m\le5\times10^2$；
**subtask $3$**（#$13$~#$16$）：$20\%$，$n,m\le3\times10^3$；
**subtask $4$**（#$17$~#$24$）：$40\%$，$n,m\le7\times10^3$。
对于 $100\%$ 的数据：$1\le n,m\le7\times10^3$，$0\le d_i\le m$。**你必须通过一个 subtask 内所有测试点，才被认为通过该 subtask。**

**本题开启子任务依赖。**


title: [BalkanOI2009] year2012 - A New Beginning

background:
[英文题面](/problem/U126972) | [题目来源](http://www.cs.org.mk/boi2009/tasks.html)

本题官方题解最大点时间 1.56s，故本题时间限制 2s。

description:
一次极端的太阳爆发使地球升温，造成了一场巨大的灾难。地壳板块在地幔中自由浮动；震级未知的地震正在导致大都市倒塌；山峦被巨大的海啸淹没；各国正转向熔岩和火山灰的海洋。

现在是 $2012$ 年 $12$ 月 $21$ 日，你唯一能让你和你的家人免于世界末日的机会就是登上喜马拉雅山的政府船，这是拯救人类的现代方舟。你有一架匀速飞行的飞机和一张有所有固定机场的地图。不幸的是，并不是所有的机场都连接在一起——巨大的火山灰云阻塞了一些航线，而其他机场却相距太远。此外，并不是所有的机场都有燃料供应——有些机场除了光秃秃的道路什么都没有留下——而且在那里你无法给飞机加油。由于所有的导航手段都被摧毁了，两个机场之间唯一可能的路径就是最短的一条。最重要的是，由于大气不稳定和空气密度的急剧变化，发动机的燃油效率在飞行中会有所不同。因此油耗也不同。好的新情况是你知道在哪一个机场可以飞行，所需的燃料量，以及你可以在哪里加油。你所要做的就是想办法尽快从机场到喜马拉雅山的机场。编写一个 `year2012` 程序，根据每个机场的坐标、是否有燃油、飞机的油箱容量、飞机的速度、一个潜在的航班连接的几对机场以及每一次飞行需要多少燃料，计算完成这项任务所需的最短时间。

inputFormat:
从标准输入读入。

第一行四个整数（译者注：可以看到样例并没有严格遵守此规则，具体的数据范围建议以【提示说明】中的为准，下同）$N,M,V,C$，分别表示机场数量、可用航线数量、飞机恒定速度和油箱容量。

接下来 $N$ 行，每行由三个实数 $X_i,Y_i,Z_i$ 和一个布尔值 $R_i$ 组成。三个实数表示 $i$ 号机场的空间坐标， $R_i=0$ 表示不能在这个机场加油，$R_i=1$ 表示可以加油。

接下来 $M$ 行，每行三个整数 $A_k,B_k,F_k$，表示这条航线的两端和花费的燃油量。每条航线都是双向的。

最后一行两个整数 $S,T$，表示路线上第一个和最后一个机场。

outputFormat:
输出到标准输出。

一行，一个实数，表示从 $S$ 到 $T$ 的最短时间。如果你的答案与标准答案的绝对误差不超过 $10^{-4}$，你的答案将被认为是正确的。

如果你无法到达目的地，输出 $0$。

hint:
**数据范围**

- 机场数量 $N\in\left[2,10^3\right]\cap\Z$。
- 可用航线数量 $M\in\left[1,10^4\right]\cap\Z$。
- 飞机恒定速度 $V\in\left[1,10^3\right]$ 为小数点后最多 $3$ 位的实数。
- 油箱容量 $C\in\left[1,10^3\right]\cap\Z$。
- 机场空间坐标 $X_i, Y_i, Z_i\in\left[-100,100\right]$，为小数点后最多 $18$ 位的实数。另外，保证 $X_i^2+Y_i^2+Z_i^2$ 对于所有 $i$ 均相同。换句话说，对于一个测试数据，所有的机场距离地心的距离均相同。
- 可以加油的机场数量 $\in\left[1,20\right]\cap\Z$。
- 地球半径为不小于 $1$ 的整数。
- 航线的两端 $A_k, B_k\in\left[1,N\right]\cap\Z$ 且 $A_k\ne B_k$。满足同一条航线只会出现一次。
- 航线花费的油量 $F_k\in\left[1,C\right]\cap\Z$。

**备注**

- 一条航线的距离为球体上最短的弧。这种弧可能有很多个，但是我们只关心距离。
- 所有航线距离均不小于 $10^{-6}$。
- 由于实数运算可能的精度误差，每个机场到地心的距离可能略有不同。但是数据保证所有距离的绝对误差不超过 $10^{-10}$，因此算法的正确性不受影响。
- $R_s = 1$，这意味着飞机的油箱初始是满的。每次路过一个可以加油的机场，油箱将会再次加满。
- 飞机降落、加油、起飞、加速的过程可以被忽略，即认为是 $0$。
- 所有可用的航线都是彼此独立的。这意味着如果有航线从 $A$ 到 $B$，路过 $C$，这不代表有从 $A$ 到 $C$、或从 $B$ 到 $C$ 的可用航线。

**部分分**

对于 $40\%$ 的数据，$N\le 8$.

---

**样例解释**

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

地球的半径为 $5$。飞机速度为 $2.5$，油箱容量为 $9$。我们想要从 $1$ 到 $3$。如图，黑实线代表可用的航线，机场编号在矩形的内部，油量花费在黑实线边上备注。我们可以加油的机场的点是空心的。显然，我们不能直接通过 $1\rightarrow 2\rightarrow 3$ 或者 $1\rightarrow 4\rightarrow 3$——它们的油量花费分别为 $13$ 和 $10$，超过了油箱的最大容量。事实上，所有路线都花费了大于 $9$ 的燃油，因此我们必须经过 $6$ 号机场。我们有三条可能的路线：$1\rightarrow 2\rightarrow 6$、$1\rightarrow 4\rightarrow 6$ 和 $1\rightarrow 5\rightarrow 2\rightarrow 6$。前两种显然是最短的两个（航线 $1\rightarrow 2$、$5\rightarrow 2$、$2\rightarrow 6$、$1\rightarrow 4$ 和 $4\rightarrow 6$ 花费同样长的时间）。在我们在 $6$ 号机场加满油后，如果我们前往 $2$ 号机场，我们依然不能到达目的地——我们缺少一个单位的燃油。为一可行的路线是通过 $4$，然后花光所有燃油到达 $3$。最后，我们可选的路线有 $1\rightarrow 2\rightarrow 6\rightarrow 4\rightarrow 3$ 和 $1\rightarrow 4\rightarrow 6\rightarrow 4\rightarrow 3$。他们都有四个直角弯，因此它们的总长度相等，都等于地球的赤道周长，或 $2\pi R$。因此，花费的时间为 $\dfrac{2\pi R}{V}\approx 12.566370614359172953850573533118$。


title: [BalkanOI2009] Reading

background: [英文题面](/problem/U126973) | [题目来源](http://www.cs.org.mk/boi2009/tasks.html)

description:
有一个关于人脑有趣的事实：在阅读时，它主要分析每个单词的第一个和最后一个字母，而不一定要按照正确的顺序来构造单词。因此，即使一句话基本上没有正确的单词，也可能会被正确的理解。（原文中这段文字的部分单词的字母顺序被打乱，但是译者认为这样会影响阅读，因此没有改变翻译中文字的顺序）

Elly 已经注意到，打乱某些字母会得到更好的结果！例如，字母 `l` 和 `i`、`a` 和 `o`、`x` 和 `m` 非常相似。于是她定义了一个字母的值，从 $1$ 到 $5$ 。其中，相似的字母的值较低，而非常不同的字母值较高。等号字母的值是 $1$。通过这种方式，每个单词可以被赋予一个值——相邻字母之间所有值的总和。

想象一下，她把 `e` 和 `l` 的值定义为 $3$，`l` 和 `y` 的值定义为 $2$，`i` 和 `l` 的值定义为 $1$。那么单词 `elly` 的值是 $3+1+2=6$（记住，等号字母的距离是 $1$）。单词 `lily` 的值为 $4$，而 `i` 的值为 $0$ =）。长单词的价值不一定比短单词大——比如 `lilii`（保加利亚语中`lily` 的复数形式）——它的值只有 $4$，但 `elle`（法语中的意思是 `she`）的价值是 $7$。但是，每增加一个字母，至少会增加一个单词的值。

Ellenora 希望构建一种即使有大量混乱的字母也很容易阅读的语言。她决定将值不大于 $N$ 的所有非空单词都包括在内。

你能帮她找出他们有多少吗？

inputFormat:
从标准输入读入。

第一行两个整数 $N$ 和 $M$，表示单词的值的最大值（$1\le N\le 10^9$）和字符对的数量。Elly 已经定义了一个值。所有未提及的字母对的距离都等于 $1$。接下来的 $M$ 行中的每一行都包含一个三元组 $L_1\,L_2\,F$，这意味着字母 $a\le L_1,L_2\le z$ 之间的距离为 $1\le F\le 5$。从 $L_1$ 到 $L_2$ 的距离与从 $L_2$ 到 $L_1$ 的距离相同，即距离是无序的。

outputFormat:
输出到标准输出。

一行，一个整数，表示由小写英文字母组成的单词数，满足它的值不大于 $N$。因为这个数量可能非常大，所以你只需要输出它对 $10^9+7$ 取模后的结果。

samples:
20 10
e l 3
e o 1
o n 2
o r 4
r a 4
i n 5
e n 2
n t 3
t w 3
w i 5

hint:
**数据范围**

对于 $50\%$ 的数据，$N\le 10^6$。

对于全部数据，$1\le N\le 10^9$，每一对字母最多只会出现一次。

---

**样例解释**

一些可行的单词有：`elleonora`、`entwine`、`aaaaaaaaaaaaaaaaaaaaa`。


title: [BalkanOI2009] Strip

background: [英文题面](/problem/U126974) | [题目来源](http://www.cs.org.mk/boi2009/tasks.html)

description:
让我们考虑一条宽度为 $1$、长度为 $n$、厚度为可忽略的条带，由单位正方形组成。如图所示（其中 $n=7$），从它的左边开始，我们使用从 $0$ 到 $n$ 的非负整数命名每个垂直的线。我们只能沿着这些垂直线折叠长方形条带，并且在这之后两个部分被粘在一起，不再会被拉直。

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

自然地，在折叠之后，一些编号会重叠在一起，形成一个有更多编号的垂直线。图中显示了沿垂直线 $3$ 折叠后的情况。在此操作之后，有一些线会有两个编号。例如，我们同样可以说 $1$ 或 $5$，他们代表的是同一条垂直线。再沿着 $2$ 折叠（我们也可以说 $4$，都是一样的），就会有一条垂直线有甚至三个名称，正如我们所看到的：$(1;3;5)$。举个例子，如果我们沿着段 $3$ 对长方形条带进行折叠，我们只需旋转条带，而不改变其名称或长度。我们把这样的折叠称为“空的”：它**不是**非法的，只是没有做任何重大的改变。

按照这种方式，一组长度为 $k$ 的整数数列（每个整数从 $0$ 到 $n$）唯一地定义了条带的折叠方法。编写一个程序，找出折叠完成后该条带的长度。

inputFormat:
从标准输入读入。
- 第一行两个正整数 $n,k$，表示条带长度和折叠次数。
- 第二行 $k$ 个非负整数，表示折叠的顺序，每个数都在 $\left[0,n\right]$ 的范围内。

outputFormat:
输出到标准输出。

一行，一个整数，表示折叠后的长度。


title: [JOISC2020] ビルの飾り付け 4

background:
JOISC2020 Day 1 T1

由于数据点较多，本题只评测其中的部分数据。

description:
给定两个长度为 $2n$ 的序列 $A,B$，构造一个长度为 $2n$ 的序列 $C$ 满足以下条件：

- 对于 $1\leq i\leq 2n$，$C_i$ 只能从 $A_i$ 和 $B_i$ 中选取

- $C_i$ 从 $A_i$ 中选取的次数和从 $B_i$ 中选取的次数都恰好为 $n$。

- $C$ 为单调不降的序列。

如果满足条件的 $C$ 有多个，只需要输出一个。

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

第二行 $2n$ 个数字，第 $i$ 个为 $A_i$。

第三行 $2n$ 个数字，第 $i$ 个为 $B_i$。

outputFormat:
如果无解则输出 $-1$，否则按照以下方式输出一个字符串 $s$：

对于 $1\leq i\leq 2n$，如果 $C_i$ 是从 $A_i$ 选取的则 $s_i=\texttt{A}$，否则 $s_i=\texttt{B}$。


title: [USACO05MAR] Checking an Alibi 不在场的证明

description:
农场有 $F$ 个点，已知 $P$ 条边以及每条边的起点终点和通过时间，给出 $C$ 个有牛的点，求在规定时间 $M$ 内能从起点到达牛当前位置的牛的数量，并按升序输出牛的编号。

谷仓里发现谷物被盗！FJ 正试图从 $C$ 只奶牛里找出那个偷谷物的罪犯。幸运的是，一个恰好路过的卫星拍下谷物被盗前 $M$ 秒的农场的图片。这样约翰就能通过牛们的位置来判断谁有足够的时间来盗窃谷物。

约翰农场有 $F$ 草地，标号 $1$ 到 $F$，还有 $P$ 条双向路连接着它们。通过这些路需要的时间在 $1$ 到 $70000$ 秒的范围内。田地 $1$ 上建有那个被盗的谷仓。给出农场地图，以及卫星照片里每只牛所在的位置，请判断哪些牛有可能犯罪。

请注意：数据里可能存在重边（起点和终点相同的边）。

inputFormat:
第 $1$ 行：四个以空格分隔的整数：$F,P,C$ 和 $M$。\
第 $2$ 行至 $P+1$ 行：三个空间分隔的整数，描述一个路径。连接 $F1$ 和 $F2$ 的路径需要 $T$ 秒。\
第 $P+2$ 行至 $P+C+1$ 行：每行一个整数，是一头牛的位置。

outputFormat: 第 $1$ 行输出嫌疑犯的数目，接下来每一行输出一只嫌疑犯的编号。

hint:
#### 样例解释

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

#### 数据约定

对于 $100\%$ 的数据：$1 \le M \le 70000$，$1 \le C \le 100$，$1 \le P \le 1000$，$1 \le F \le 500$。


title: 「Wdoi-2」来自地上的支援

background:
波光粼粼的山顶湖与庄严神圣的神社之下，是一座复合型活火山。
沿幻想风穴而下，便能到达火山之下，废弃已久的地狱原址。
>在旧地狱中，有一座大都市。那里是旧地狱还是地狱的时候在那工作的众鬼们居住的地方，只有那里亡者们是无法踏入去的。后来地狱体制改革，机构搬离了这个地方。
因为这个缘故这块地狱变成了废墟，但却有一部分看上了那里的妖怪擅作主张占领了那里，于是就成了如今的旧地狱了。
这里比地上更没有秩序可言。悍匪恶霸，特别是惹人类讨厌的家伙都喜欢搬到这边定居下来。

自旧地狱喷泻而出的间歇泉，给妖怪之山带来了优良的温泉，也喷出了大量的怨灵。

为了解决这次异变，乐园的巫女和普通的魔法使结伴而行，在来自地上的支援下，自幻想风穴直冲地底。

先后结（bao）识（da）了黑暗洞窟中的明亮之网、地壳下的嫉妒心、人们所谈论的怪力乱神后，二人来到了遗址中心的洋馆，地灵殿。

受这里主人的指引，二人来到了位于深处的间歇泉地下中心。

description:
### 简要题意
给定正整数 $n$、$v$ 和长度为 $n$ 的数组 $\{A_i\}$。

有一个长度为 $n$ 的数组 $B$，初始值与 $A$ 相同。
执行 $n$ 次操作，第 $i$ 次操作在 $[1,i]$ 中按如下规则选取一个正整数 $j$，然后把 $B_j$ 变成 $B_j+v$：
- 选取 $B_j$ 最大的 $j$。
- $B_j$ 相同时选择 $A_j$ 最大的 $j$。
- $A_j,B_j$ 均相同，选择较小的 $j$。

我们称这是选中了一次 $j$。

有 $m$ 次询问，每次询问给定 $x_i,k_i$。表示求最小的 $s$，使得**若**将 $A_{x_i}$ 的初始值改为 $s$（注意此时 $B_{x_i}$ 的初始值也会跟着改变），$x_i$ 至少被选中 $k_i$ 次，或报告不存在（**结果为** $0$）。请注意，$s$ 不存在最小值时也是报告不存在（**结果为** $0$）。

询问之间互相独立，也就是每次询问不会对 $A_{x_i}$ 和 $B_{x_i}$ 产生实质性更改。

### 原始题意

到达控制中心之后，主角组和灵乌路空进行了激烈的狗斗大赛。负责技术维护的河童需要接受荷取来自地上指挥部的指令，保障生产安全。

具体地，有 $n$ 个核反应机组依次排开，第 $i$ 个机组的活动强度为 $A_i$。为了维护平衡，控制系统依次操作 $n$ 次，第 $i$ 次操作会在前 $i$ 个机组中找到一个**当前活动度最高的**机组，进行一次调节平衡操作，并将其活动度增加 $v$。倘若有多个机组活动度最高，就应当选择初始活动度**最大**的，若还是无法比较，则取编号最小。

为了在自动控制系统的基础上调节平衡，荷取会发出 $m$ 条指令，形如她每次会给出两个整数 $x_i,k_i$，表示她会修改第 $x_i$ 个机组的初始活动度。她希望通过修改（必须改成一个**非负整数** $s$）后，$x_i$ 号机组至少被平衡 $k_i$ 次。如果无论如何都无法达到要求，那么结果就是 $0$；否则请求出满足条件的**最小的** $s$。

inputFormat:
- 第一行有三个整数 $n, m, v$。
- 接下来一行，有 $n$ 个整数，描述 $a_i$。
- 接下来 $m$ 行，每行有两个整数 $x_i,k_i$，描述一次询问。

outputFormat: - 一行，输出两个整数，表示所有结果的**异或和**与**加法和**。

hint:
### 样例 1 解释

对于第一次询问，我们将 $A_3$ 修改为 $7$。

- 第一次操作选择了位置 $1$，于是 $B_1$ 变为 $4$。
- 第二次操作选择了位置 $2$，于是 $B_2$ 变为 $7$。虽然操作前 $B_1=B_2$，但是 $A_2>A_1$，因此选择位置 $2$。
- 第三次操作选择了位置 $3$，于是 $B_3$ 变为 $10$。
- 第四次操作选择了位置 $3$，于是 $B_3$ 变为 $13$。
- 第五次操作选择了位置 $3$，于是 $B_3$ 变为 $16$。
- 第六次操作选择了位置 $3$，于是 $B_3$ 变为 $19$。
- 第七次操作选择了位置 $3$，于是 $B_3$ 变为 $22$。

于是位置 $3$ 一共被选择了 $5$ 次，满足题意。可以证明，如果把 $A_3$ 的初始值设为 $6$，无法达成要求。于是该询问结果为 $7$。

对于第二个询问，容易发现不可能有 $4$ 次以上操作选择位置 $6$。因此该询问结果为 $0$。

$7\oplus 0=7$，$7+0=7$，因此输出 $7,7$。

### 数据范围

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n,m\le} & \bm {a_i\le } & \bm{v\le} & \textbf{分值} \cr\hline
1 & 10 & 100 & 10 & 10 \cr\hline
2 & 100 & 5\times 10^3 & 50 & 20 \cr\hline
3 & 10^3 & 10^9 & 100 & 10 \cr\hline
4 & 10^5 & 10^9 & 100 & 25 \cr\hline
5 & 2\times 10^6 & 10^9 & 100 & 35 \cr\hline
\end{array}$$

对于全部数据，满足 $1 \le n,m \le 2\times 10^6$，$1 \le v \le 100$，$1 \le a_i \le 10 ^ 9$，$1 \le x,k \le n$。

**本题 IO 量较大，请选择合适的输入方式。**


title: 寒妖王

background: 寒冷的保加利亚小屋里，你发现了寒妖王给你提出的一个问题。

description:
给定一张 $n$ 个点 $m$ 条边的图，保证无重边与自环。第 $i$ 条边有权值 $w _i$。

定义一个边集是好的，当且仅当将这些边和与这些边相连的点取出来形成的图没有两个或以上处在同一个连通块的不同的环（两个环不同指的是构成环的边集不能完全相同）。同时定义一个边集的权值为边集中所有边的边权之和。

现在，每条边均有 $50\%$ 的概率消失。求在消失过程完成后，图中权值最大的好边集的权值的期望。

输出该期望值对一个大质数 $998244353$ 取模的结果。

可以知道这里的期望值是一个有理数。其对 $998244353$ 取模的结果相当于是将其写为最简分数形式 $\frac x y$（其中 $x$ 与 $y$ 互质）后 $x \times y ^{998244351}$ 对 $998244353$ 取模的结果。

inputFormat:
第一行两个正整数 $n, m$，表示该图的点数和边数。

接下来 $m$ 行，每行三个整数 $u _i, v _i, w_i$，分别描述了图中第 $i$ 条边的两个端点与这条边的权值。

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

hint:
**「数据范围与约定」**

- 对于前 $20\%$ 的数据，保证 $n \le 10$，$m \le 20$；
- 对于前 $40\%$ 的数据，保证 $n \le 10$，$m \le 30$；
- 对于另外 $30\%$ 的数据，保证所有边的权值均相等；
- 对于所有数据，保证 $1 \le n \le 15$，$1 \le m \le 60$，$1 \le u _i, v _i \le n$，$0 \le w _i < 998244353$。


title: [APIO2020] 粉刷墙壁

background:
由于官方数据包过大，本题仅评测部分数据。

本题仅支持 C++ 系列语言，提交时**不需要**包含 `paint.h` 头文件。

如果交互库存在其他问题，请私信 mrsrz。

description:
距离上一次 Pak Dengklek 在他的家中粉刷墙壁已经过了一段时间，所以他想重新粉刷一次。他家的墙壁由 $N$ 段组成，它们从 $0$ 到 $N - 1$ 编号。本题中我们假设存在 $K$ 种不同的颜色，颜色用从 $0$ 到 $K - 1$ 的整数表示（例如，红色用 $0$ 表示, 蓝色用 $1$ 表示，以此类推）。Pak Dengklek 希望用第 $C[i]$ 种颜色来粉刷第 $i$ 段的墙壁。

为了粉刷墙壁，Pak Dengklek 雇用了一家有 $M$ 个承包商的承包商公司，承包商从 $0$ 到 $M - 1$ 编号。对 Pak Dengklek 来说不幸的是，承包商只愿意粉刷他们自己喜欢的
颜色。具体来说，第 $j$ 个承包商喜欢 $A[j]$ 种颜色，并且只想用下列颜色来粉刷墙壁：第 $B[j][0]$ 种颜色，第 $B[j][1]$ 种颜色，$\dots$，或第 $B[j][A[j] − 1]$ 种颜色。

Pak Dengklek 可以给承包商公司提出一些要求。在单个要求中，Pak Dengklek 将给出两个参数 $x$ 和 $y$， 其中 $0 \leq x < M$，$0 \leq y \leq N - M$。承包商公司将会指派第 $((x + l) \mod M)$ 个承包商粉刷第 $(y + l)$ 段墙壁，其中 $0 \leq l < M$。如果存在一个 $l$ 使
得第 $((x + l) \mod M)$ 个承包商不喜欢第 $C[y + l]$ 种颜色，那么该要求将无效。

Pak Dengklek 需要为每个要求付费，因此他想知道为了使墙壁中每个段都能用自己预期的颜色粉刷，他至少要提出多少个要求，或是确认他的预期无法达到。每一段墙壁可以被粉刷多次，但必须保证每次粉刷的颜色都是 Pak Dengklek 所预期的。

你必须实现 `minimumInstructions` 函数：

- `minimumInstructions(N, M, K, C, A, B)` - 该函数将被评测库恰好调用一次。
	- $N$：一个整数表示墙壁的段数。
	- $M$：一个整数表示承包商的数量。
	- $K$：一个整数表示颜色的种数。
	- $C$：一个长度为 $N$ 的整数序列，表示每段墙壁预期的颜色。
	- $A$：一个长度为 $M$ 的整数序列，表示承包商喜欢的颜色数。
	- $B$：一个长度为 $M$ 的每个元素为序列的序列，表示承包商喜欢的具体颜色。
	- 该函数必须返回一个整数，表示 Pak Dengklek 为了让墙壁按预期粉刷所需要提出的最小要求数；若预期无法达到则返回 $-1$。

outputFormat: 样例评测库将输出函数 `minimumInstructions` 的返回值

hint:
在第一个样例中， $N = 8$，$M = 3$，$K = 5$，$C = [3, 3, 1, 3, 4, 4, 2, 2]$，$A = [3, 2, 2]$，$B = [[0, 1, 2], [2, 3], [3, 4]]$。Pak Dengklek 可以提出下列的要求。

1. $x = 1$，$y = 0$。这是一个有效的要求，第一个承包商可以粉刷第零段墙壁，第二个承包商可以粉刷第一段墙壁，第零个承包商可以粉刷第二段墙壁。
2. $x = 0$，$y = 2$。 这是一个有效的要求，第零个承包商可以粉刷第二段墙壁，第一个承包商可以粉刷第三段墙壁，第二个承包商可以粉刷第四段墙壁。
3. $x = 2$，$y = 5$。 这是一个有效的要求，第二个承包商可以粉刷第五段墙壁，第零个承包商可以粉刷第六段墙壁，第一个承包商可以粉刷第七段墙壁。

容易看出 Pak Dengklek 不能用少于 $3$ 个的要求来达到预期，因此 `minimumInstructions(8, 3, 5, [3, 3, 1, 3, 4, 4, 2, 2], [3, 2, 2], [[0, 1, 2], [2, 3], [3,
4]])` 应该返回 $3$。

在第二个样例中，$N = 5$，$M = 4$，$K = 4$，$C = [1, 0, 1, 2, 2]$，$A = [2, 1, 1, 1]$，$B =
[[0, 1], [1], [2], [3]]$。由于第三个承包商只喜欢第 $3$ 种颜色但没有任何一段墙壁能被该颜色粉刷，Pak Dengklek 无法给出任何有效指令。因此`minimumInstructions(5, 4, 4,[1, 0, 1, 2, 2], [2, 1, 1, 1], [[0, 1], [1], [2], [3]])` 应该返回 $-1$。

对于 $0 \leq k < K$, 令 $f(k)$ 表示喜欢第 $k$ 种颜色的承包商数量。

【条件限制】

- $1 \leq N \leq 100 000$。
- $1 \leq M \leq \min(N, 50 000)$。
- $1 \leq K \leq 100 000$。
- $0 \leq C[i] < K$。
- $1 \leq A[j] \leq K$。
- $0 \leq B[j][0] < B[j][1] < \dots < B[j][A[j] − 1] < K$。
- $\sum f(k)^2 \leq 400 000$。

【子任务 $1$（$12$ 分）】

- $f(k) \leq 1$。

【子任务 $2$（$15$ 分）】

- $N \leq 500$。
- $M \leq \min(N, 200)$。
- $\sum f(k)^2 \leq 1 000$。

【子任务 $3$（$13$ 分）】

- $N \leq 500$。
- $M \leq \min(N, 200)$。

【子任务 $4$（$23$ 分）】

- $N \leq 20 000$。
- $M \leq \min(N, 2 000)$。

【子任务 $5$（$37$ 分）】

- 无附加限制。


title: [APIO2020] 交换城市

background:
由于官方数据包过大，本题仅评测部分数据。

本题仅支持 C++ 系列语言，提交时**不需要**包含 `swap.h` 头文件。

由于交互库本身的性能问题，本题的时间限制上调为 $3$ 秒。如果交互库存在其他问题，请私信 mrsrz。

description:
印度尼西亚有 $N$ 个城市以及 $M$ 条双向道路，城市从 $0$ 到 $N - 1$ 编号，道路从 $0$ 到 $M - 1$ 编号。每条道路连接着两个不同的城市，第 $i$ 条道路连接第 $U[i]$ 个城市与第 $V[i]$ 个城市，汽车行驶这条道路将耗费 $W[i]$ 个单位汽油。通过这些道路，任意两个城市间能够互相到达。

接下来的 $Q$ 天中, 每天会有一对城市希望建立政治关系。具体来说，第 $j$ 天，第 $X[j]$ 个城市想要和第 $Y[j]$ 个城市建立政治关系。为此，第 $X[j]$ 个城市将会派一名代表坐汽车前往第 $Y[j]$ 个城市。同样地，第 $Y[j]$ 个城市也会派一名代表坐汽车前往第 $X[j]$ 个城市。

为了避免拥塞，两辆车不应在任何时间点碰面。更具体地，两辆车不能在同一个时间点出现在同一个城市。同样地，两辆车也不应该沿相反的方向同时行驶过同一条道路。另外，汽车行驶过一条道路时必须完整经过道路并到达道路另一端的城市（换句话说，汽车不允许在道路中间掉转方向）。但是，汽车可以多次到达一个城市或是多次经过一条道路。此外，汽车可以在任何时间在任何城市等候。

由于高燃料容量汽车的价格昂贵，两个城市都分别希望选择一条路线，使得两辆汽车所需的最大单位汽油容量最小。每个城市中都有加油站并且供油量是无限的，因此汽车所需的单位汽油容量实际上就是行驶过的道路中最大的单位汽油消耗量。

你必须实现 `init` 和 `getMinimumFuelCapacity` 函数。

- `init(N, M, U, V, W)` - 该函数将在所有 `getMinimumFuelCapacity` 的调用前被评测库恰好调用一次。
	- $N$： 一个整数表示城市数。
	- $M$： 一个整数表示道路数。
	- $U$： 一个长为 $M$ 的整数序列表示道路的第一个端点城市。
	- $V$： 一个长为 $M$ 的整数序列表示道路的第二个端点城市。
	- $W$： 一个长为 $M$ 的整数序列表示道路的汽油消耗。

- `getMinimumFuelCapacity(X, Y)` - 该函数将被评测库调用恰好 $Q$ 次。
	- $X$： 一个整数表示第一个城市。
	- $Y$： 一个整数表示第二个城市。
	- 该函数必须返回一个整数，表示根据题目描述中的规则，两辆分别从第 $X$ 个城市与第 $Y$ 个城市出发要到达彼此城市的车，它们的单位汽油容量最大值的最小值。若无法满足题目规则则返回 $−1$。

outputFormat: 对每个 `getMinimumFuelCapacity` 的调用，样例评测库会输出该函数的返回值

hint:
第一个样例中, $N = 5$，$M = 6$，$U = [0, 0, 1, 1, 1, 2]$，$V = [1, 2, 2, 3, 4, 3]$，$W =
[4, 4, 1, 2, 10, 3]$，$Q = 3$，$X = [1, 2, 0]$，$Y = [2, 4, 1]$。如下图：

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

评测库初始时将调用 `init(5, 6, [0, 0, 1, 1, 1, 2], [1, 2, 2, 3, 4, 3],[4, 4, 1, 2, 10, 3])`。之后，评测库将进行如下函数调用：

- `getMinimumFuelCapacity(1, 2)`。首先，从第一个城市出发的汽车可以行驶到第三个城市。接着，从第二个城市出发的汽车可以行驶到第一个城市，并且在第三个城市的汽车可以行驶到第二个城市。因此，最大的单位汽油容量为 $3$ （从第三个城市到第二个城市需要花费 $3$ 个单位汽油）。没有其他更优的路线方案，因此该函数应该返回 $3$。

- `getMinimumFuelCapacity(2, 4)`。任何从第四个城市出发或要到达第四个城市的汽车都需要耗费 $10$ 个单位汽油，因此该函数应该返回 $10$。

- `getMinimumFuelCapacity(0, 1)`。该函数应该返回 $4$。

第二个样例中，$N = 3$，$M = 2$，$U = [0, 0]$，$V = [1, 2]$，$W = [5, 5]$，$Q = 1$，$X = [1]$，$Y = [2]$。 如下图：

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

评测库初始时将调用 `init(3, 2, [0, 0], [1, 2], [5, 5])`，之后，评测库将进行如下函数调用：

- `getMinimumFuelCapacity(1, 2)`。两辆车无法满足不在同一时间点碰面的要求，所以该函数应该返回 $-1$。

【条件限制】

- $2 \leq N \leq 100 000$。
- $N - 1 \leq M \leq 200 000$。
- $0 \leq U[i] < V [i] < N$。
- 任意两个城市间至多存在一条道路直接相连。
- 任意两个城市经过道路可以互相到达。
- $1 \leq W[i] \leq 10^9$。
- $1 \leq Q \leq 200 000$。
- $0 \leq X[j] < Y [j] < N$。

【子任务 $1$（$6$ 分）】

- 每个城市至多是两条道路的一个端点。

【子任务 $2$（$7$ 分）】

- $M = N - 1$。
- $U[i] = 0$。

【子任务 $3$（$17$ 分）】

- $Q \leq 5$。
- $N \leq 1 000$。
- $M \leq 2 000$。

【子任务 $4$（$20$ 分）】

- $Q \leq 5$。

【子任务 $5$（$23$ 分）】

- $M = N - 1$。

【子任务 $6$（$27$ 分）】

- 无附加限制。


title: [APIO2020] 有趣的旅途

background:
由于官方数据包过大，本题仅评测部分数据。

本题仅支持 C++ 系列语言，提交时**不需要**包含 `fun.h` 头文件，但需要在程序开头声明 `int hoursRequired(int,int)` 以及 `int attractionsBehind(int,int)`。如果您不明白这是什么意思，也可以直接将 `fun.h` 中的内容粘贴到程序的开头。

交互库在程序非正常结束时可能会返回一些奇怪的信息。

如果交互库存在其他问题，请私信 mrsrz。

description:
雅加达最大的主题公园中有 $N$ 个景点，它们从 $0$ 到 $N -1$ 编号。这些景点由 $N-1$ 条双向道路连接，任意两个景点间经由这些道路将存在唯一一条简单路径。道路从 $0$ 到 $N - 2$ 编号。第 $i$ 条道路连接第 $A[i]$ 个景点与第 $B[i]$ 个景点，经过这条道路需要花费一个小时。为了避免拥塞，每个景点将至多与三条道路相连。

你想寻找一条游玩路线并使得每个景点都被参观一次。你认为从一个景点走到下一个景点时经过太多道路是十分无聊的。为了寻找一条有趣的路线，你打算安排景点的参观顺序，使得参观下一个景点所花费的时间不超过参观之前景点所花费的时间。换句话说，你想找到一个序列 $P[0], P[1],\dots, P[N - 1]$ 使其包含 $0$ 到 $N - 1$ 中的所有整数恰好一次，并且从第 $P[i]$ 个景点到达第 $P[i + 1]$ 个景点所需的时间不超过从第 $P[i - 1]$ 个景点到达第 $P[i]$ 个景点所需的时间，其中 $0 < i < N - 1$。

你手上没有景点的完整地图，因此你必须向信息中心进行若干次询问才能找到一条有趣路线。你最多能进行 $Q$ 次询问，每次询问需要提供两个参数 $X$ 和 $Y$ ，其中 $0 \leq X, Y < N$。每次询问是以下任意一种：

- 从第 $X$ 个景点到第 $Y$ 个景点需要花费多少个小时。特别地，若 $X = Y$ 则回答将是 $0$。

- 有多少个景点 $Z$ 满足，当你想从第 $X$ 个景点到达第 $Z$ 个景点时一定会经过第 $Y$ 个景点。第 $Y$ 个景点将会被计算在内，特别地，若 $X = Y$ 则回答将是 $N$。

你必须实现 `createFunTour` 函数：

- `createFunTour(N, Q)` - 该函数将被评测库恰好调用一次。
	- $N$：一个整数表示景点的数量。
	- $Q$：一个整数表示询问次数的最大值。
	- 该函数可以调用以下两个交互函数：
    	- `hoursRequired(X, Y)`
        	- $X$：一个整数表示第一个景点的编号。
			- $Y$：一个整数表示第二个景点的编号。
			- 该函数将返回一个整数表示从第 $X$ 个景点到第 $Y$ 个景点需要花费的小时数。
			- 如果 $X$ 或 $Y$ 的值不在 $0$ 到 $N - 1$ 的范围内，该测试点将视为答案错误。
		- `attractionsBehind(X, Y)`
			- $X$：一个整数表示第一个景点的编号。
            - $Y$：一个整数表示第二个景点的编号。
			- 该函数将返回一个整数表示有多少个景点 $Z$ 满足，当你想从第 $X$ 个景点到达第 $Z$ 个景点时一定会经过第 $Y$ 个景点。
			- 如果 $X$ 或 $Y$ 的值不在 $0$ 到 $N - 1$ 的范围内，该测试点将视为答案错误。
	- 该函数必须返回一个长为 $N$ 的整数序列，表示你找到的景点参观顺序。

outputFormat: 如果 `createFunTour` 正确返回了一个满足题意的序列，并且 `hoursRequired` 和 `attractionsBehind` 的调用次数总和不超过 $Q$，那么样例评测库将会输出 `createFunTour` 得到的序列。其他情况下样例评测库将会输出错误信息

hint:
在下图的例子中 $N = 7$，$Q = 400 000$，$A = [0, 0, 0, 1, 1, 2]$，$B = [1, 5, 6, 2, 4, 3]$。

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

评测库将调用 `createFunTour(7, 400000)`。
- 如果你询问 `hoursRequired(3, 5)`，函数将返回 $4$。
- 如果你询问 `hoursRequired(5, 4)`，函数将返回 $3$。
- 如果你询问 `attractionsBehind(5, 1)`，函数将返回 $4$。从第五个景点到第一、二、三、四个景点将一定会经过第一个景点。
- 如果你询问 `attractionsBehind(1, 5)`，函数将返回 $1$。
- 一个符合要求的返回序列为 $[3, 6, 4, 5, 2, 0, 1]$，到达下一个参观景点所需的时间按顺序分别为 $[4, 3, 3, 3, 2, 1]$。

【条件限制】

- $2 \leq N \leq 100 000$。
- $Q = 400 000$。
- 任意两个景点间可以通过双向道路互相到达。
- 每个景点至多连接着三条道路。

【子任务 $1$（$10$ 分）】

- $N \leq 17$。

【子任务 $2$（$16$ 分）】

- $N \leq 500$。

【子任务 $3$（$21$ 分）】

- 对所有的 $1 \leq i < N$，有一条连接着第 $i$ 个景点与第 $\lfloor \dfrac{i-1}{2} \rfloor$
个景点的双向道路。

【子任务 $4$（$19$ 分）】

存在至少一个景点 $T$ 使得对于所有 $0 \leq i < N$，`hoursRequired(T, i)` $<30$ 并且存在一个整数区间 $[L[i], R[i]](0 \leq L[i] \leq i \leq R[i] < N)$ 满足下列条件：

- 从第 $T$ 个景点到达第 $j$ 个景点必须经过第 $i$ 个景点当且仅当 $L[i] \leq j \leq R[i]$。

- 若 $L[i] < i$，则恰有一个景点 $X$ 满足：
	- $L[i] \leq X < i$。
	- 有一条连接第 $i$ 个景点与第 $X$ 个景点的道路。
- 若 $i < R[i]$，则恰有一个景点 $Y$ 满足：
	- $i < Y \leq R[i]$。
	- 有一条连接第 $i$ 个景点与第 $Y$ 个景点的道路。

【子任务 $5$（$34$ 分）】
- 无附加限制。


title: 「GLR-R4」小满

background:
  「树阴满地日当午，梦觉流莺时一声」

---

  乐队训练之余，锻炼时间可是必不可少的，可是就算几个女孩子撒开蹄子跑，也不可能在高三打球狂人的统治下抢到一块羽毛球场的。经过了数周从训练室冲到球场，再从球场灰心地踱回训练室的循环后，阿绫绝望地向大家宣布了一个坏消息：“只能打野球了。”

  “还有几个月了哟……”

  “老 V 你又来了！”才回训练室的阿绫扶着门抱怨着。

  “所以你们打球得抓紧时间啦！”

---

  **小满** 「生活一圈圈日子一年年　总是这样重复一遍又一遍」

description:
  野场羽毛球，在生态环境良好的校园里，可是经常遭遇不测的——

  “天依！怎么球又被挂树上啦！”

  如阿绫所见，她们仅剩的一颗可怜的羽毛球被天依用吃包子的劲儿抡到树上去了。为了避免找别人的排球或者篮球来砸树的尴尬，阿绫这次特意准备了一根折叠杆。

  折叠杆初始时处于完全收缩状态，我们认为它的长度 $\ell=0$。完全展开折叠杆需要 $n$ 步，每步为以下两种情况之一：

1.  将杆末端的折叠处展开。此操作没有额外参数，操作完成后 $\ell\gets 2\ell$，即杆的长度变为原来的两倍。

2.  将杆末端的伸缩处展开。此操作将给出额外可变参数 $d$，操作完成后 $\ell\gets \ell+d$，即杆的长度增加 $d$。

  树上球的高度、杆最终的高度和天依吃包子的劲儿可能都是庞大的，所以阿绫需要你来计算一下杆最终的长度 $\ell$。你需要回答阿绫 $n$ 次操作依次完成后，**$\ell$ 的二进制表示**。

inputFormat:
第一行一个整数 $T$ ，表示你需要分别处理的数据组数。

对于每组数据：

- 第一行一个整数 $n$，表示将进行的操作次数；

- 接下来 $n$ 行，每行格式形如 `1` 或 `2 d`，分别描述两类操作。其中整数 $d$ 用十进制表示。

outputFormat: 对于每组测试数据，输出最终的 $\ell$ 的二进制表示。**你的答案不应包含多余的前导零**。


title: [BalticOI 2020/2012 Day0] Roses

background:
因为特殊原因，本题目另外 $24$ 组数据请在 [这里](https://www.luogu.com.cn/problem/U127462) 提交。

Valentine 是人赢。

description:
现在 Valentine 要给他的 $N$ 个妹子买玫瑰花，现在 Valentine 面前有两家店，每一家店有无数朵玫瑰花，但是他们按束卖。第一家店一束花里有 $A$ 朵，每一束花要用 $B$ 块钱。第二家店一束花里有 $C$ 朵，每一束花要用 $D$ 块钱。

求 Valentine 至少买 $N$ 朵花最少需要花多少钱。

至少可以这么理解，假如 $M>N$，但是买 $M$ 朵花的钱比买 $N$ 朵花的少，Valentine 就会买 $M$ 朵花，并把多出来的花给其他妹子，没错，Valentine 很花心。

inputFormat: 一行五个整数 $N,A,B,C,D$，意义见题目所述。

outputFormat: 一行一个整数代表最小花费。

hint:
#### 样例说明

对于样例 $1$，Valentine 可以选择在第二家店买 $2$ 束花。

对于样例 $2$，Valentine 可以选择在第一家店买 $1$ 束花，在第二家店买 $2$ 束花。

#### 数据规模与约定

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

- Subtask 1（20 pts）：$N,A,B,C,D \le 1000$。
- Subtask 2（80 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N \le 10^{15}$，$1 \le A,B,C,D \le 10^5$，保证答案不超过 $10^{18}$。

#### 说明

翻译自 [BalticOI 2020 Day0 B Roses](http://www.boi2020.lv/data/tasks/en/day0/roses.pdf)。

与 BalticOI 2012 Day0 A 内容一致。


title: [USACO05MAR] Ombrophobic Bovines 发抖的牛

description:
FJ 的牛们非常害怕淋雨，那会使他们瑟瑟发抖。他们打算安装一个下雨报警器，并且安排了一个撤退计划。他们需要计算最少的让所有牛进入雨棚的时间。
牛们在农场的 $F$ 个田地上吃草。有 $P$ 条双向路连接着这些田地。路很宽，无限量的牛可以通过。田地上有雨棚，雨棚有一定的容量，牛们可以瞬间从这块田地进入这块田地上的雨棚。
请计算最少的时间，让每只牛都进入雨棚。

inputFormat:
第 $1$ 行：两个整数 $F$ 和 $P$；
第 $2$ 到 $F+1$ 行：第 $i+1$ 行有两个整数描述第 $i$ 个田地，第一个表示田地上的牛数，第二个表示田地上的雨棚容量。两个整数都在 $0$ 和 $1000$ 之间。
第 $F+2$ 到 $F+P+1$ 行：每行三个整数描述一条路，分别是起点终点，及通过这条路所需的时间（在 $1$ 和 $10^9$ 之间）。

outputFormat: 一个整数，表示最少的时间。如果无法使牛们全部进入雨棚，输出 $-1$。


title: 『JROI-4』分数

background: 万人血书 [KHIN](https://www.luogu.com.cn/user/236807) 完成[女装 flag](https://www.luogu.com.cn/paste/pdsav61j)(1/10000) $\to$ 万人血书 [KHIN](https://www.luogu.com.cn/user/236807) 完成[女装 flag](https://www.luogu.com.cn/paste/pdsav61j)(2/10000)(1/5000) $\to$ 万人血书 [KHIN](https://www.luogu.com.cn/user/236807) 完成[女装 flag](https://www.luogu.com.cn/paste/pdsav61j)(2/5000)(1/2500) $\to$ 万人血书 [KHIN](https://www.luogu.com.cn/user/236807) 完成[女装 flag](https://www.luogu.com.cn/paste/pdsav61j)(2/2500)(1/1250) $\to$ 万人血书 [KHIN](https://www.luogu.com.cn/user/236807) 完成[女装 flag](https://www.luogu.com.cn/paste/pdsav61j)(2/1250)(1/625) $\cdots$ 以此类推，在可以约分的情况下，“万人血书”很快就能完成。[](KH粉丝群群号：808706015)

description:
“$x$ 人血书”的过程可以看成一个函数 $f(x)$：

有一个 $\frac{0}{x}$ 的分数。重复以下步骤直到这个分数为 $1$：

1. 分子 $+1$。
2. 如果这个分数可以约分，约分到最简形式。

现在小 D 给了你 $T$ 组数据，每组数据都是给定 $n$，求在 $1\le x\le n$ 的情况下 $f(x)$ 的最大操作次数。

但是他太菜了，不会，你能帮帮他吗？

inputFormat:
第一行一个正整数 $T$。

接下来 $T$ 行，每行一个正整数 $n$。

outputFormat: 共 $T$ 行，每行一个整数 $s$ 表示在 $1\le x\le n$ 的情况下 $f(x)$ 的最大操作次数。


title: [JOISC2020] 美味しい美味しいハンバーグ

background:
JOISC2020 Day 1 T2

由于数据点较多，本题只评测其中的部分数据。

下面的题意是简要题意。

description:
有一个 $10^9\times 10^9$ 的金属网格，其中 $(x,y)$ 表示从左往右第 $x$ 列，从上往下第 $y$ 行的格子。（$1\leq x,y\leq 10^9$）。在这些网格上放了 $N$ 块汉堡肉，依次编号为 $1,\cdots,N$，其中第 $i$ 块汉堡肉放在以 $(L_i,D_i)$ 为左下角，$(R_i,U_i)$ 为右上角的矩形区域内，并且汉堡肉可以重叠。

你需要检查所有的汉堡肉是否煮熟。你可以选择金属网上的 $K$ 个格子，并且垂直地在这个格子中间插一根竹签。对于每一块汉堡肉来说，你可以通过在它所处的格子中插一根竹签来确认这块汉堡肉是否煮熟。当然，你也可以在一个格子里面插多根竹签或者是在没有汉堡肉的格子插竹签，尽管这很不必要。

形式上说，你需要找到 $K$ 组 $(x_1,y_1),\cdots,(x_k,y_k)$，满足以下条件：

- 对于所有 $i$，存在一个 $j$ 满足 $L_i\leq x_j\leq R_i,D_i\leq y_j\leq U_i$。

- 对于所有 $j$，$1\leq x_j,y_j\leq 10^9$。

你需要写一个程序来找出这 $K$ 组 $(x_j,y_j)$，数据保证有解。

inputFormat:
第一行两个的整数 $N,K$，含义见题面描述。

接下来 $n$ 行，每行四个整数 $L_i,D_i,R_i,U_i$，描述一块汉堡肉。

outputFormat:
$K$ 行，每行两个整数 $x_j$ 和 $y_j$。

如果有多解，输出任意一个均可。


title: [JOISC2020] 掃除

background:
JOISC2020 Day 1 T3

由于数据点较多，本题只评测其中的部分数据。

希望获得完整数据的可以到[这里](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day1/sweeping-data.zip)自行下载。

description:
由于 Bitaro AK 了 IOI，所以 IOI 主办方送了他一套房子，为一个边长为 $N$ 的等腰直角三角形。房间内一点用坐标 $(x,y)$ 表示，其中 $0\leq x+y\leq N$。直角顶点为原点，三角形两腰分别为 $x$ 轴与 $y$ 轴。

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

一天，Bitaro 发现自己已经 AK 了 1919810 届 IOI 闲的没事做准备打扫房间里的灰尘。这些灰尘一开始一共有 $M$ 堆，其中第 $i$ 堆位于 $(X_i,Y_i)$。同时，可能存在多堆灰尘位于同一个位置上的情况。

现在 Bitaro 准备用扫帚打扫房间。我们认为扫帚是放置在房间里的一条线段，并且将这条线段的长度称为扫帚的宽度。由于 Bitaro 很有条理，所以他只会用以下的两种方式打扫房间：

- Bitaro 将扫帚平行于 $y$ 轴放置，一端位于原点。然后他会垂直向右移动扫帚，直到不能移动为止。如果扫帚的宽度为 $l$，那么原来一堆满足 $x<N-l,y\leq l$ 的灰尘 $(x,y)$ 将会被移动到 $(N-l,y)$。（这个位置可能会存在多堆灰尘）我们称这个过程为过程 H。

- Bitaro 将扫帚平行于 $x$ 轴放置，一端位于原点。然后他会水平向上移动扫帚，直到不能移动为止。如果扫帚的宽度为 $l$，那么原来一堆满足 $x\leq l,y<N-l$ 的灰尘 $(x,y)$ 将会被移动到 $(x,N-l)$。（这个位置可能会存在多堆灰尘）我们称这个过程为过程 V。

在 Bitaro 的房间里，依次会发生 $Q$ 个事件。第 $i$ 个事件形如以下 $4$ 种：

- Bitaro 想要计算第 $P_i$ 堆灰尘的位置坐标；

- Bitaro 使用宽度为 $L_i$ 的扫帚，进行了过程 H；

- Bitaro 使用宽度为 $L_i$ 的扫帚，进行了过程 V；

- 有一堆新的灰尘出现在点 $(A_i,B_i)$ 处。如果在这个事件之前一共有 $c$ 堆灰尘，那么这堆灰尘就是房间中的第 $c+1$ 堆灰尘。

由于 Bitaro 已经 AK 了 IOI，啥都不想干，所以你需要写一个程序，给出房间的腰长，每一堆灰尘的位置坐标和每个事件的细节，求出要求的某堆灰尘的位置坐标。

inputFormat:
第一行三个整数，分别为 $N,M,Q$。

接下来 $m$ 行，每行两个整数 $X_i,Y_i$，表示第 $i$ 堆灰尘一开始的位置。

接下来 $Q$ 行，每行两到三个整数，表示一个事件。设 $T_i$ 为第一个整数，每行含义如下：

- 如果 $T_i=1$，则这行有两个整数 $T_i,P_i$，表示 Bitaro 要计算第 $P_i$ 堆灰尘的坐标；

- 如果 $T_i=2$，则这行有两个整数 $T_i,L_i$，表示 Bitaro 用宽度为 $L_i$ 的扫帚进行了过程 H；

- 如果 $T_i=3$，则这行有两个整数 $T_i,L_i$，表示 Bitaro 用宽度为 $L_i$ 的扫帚进行了过程 V；

- 如果 $T_i=4$，则这行有三个整数 $T_i,A_i,B_i$，表示一堆新的灰尘出现在 $(A_i,B_i)$ 位置。

outputFormat: 对于每个 $T_i=1$ 的事件，输出一行两个整数，表示事件 $i$ 发生时第 $P_i$ 堆灰尘的位置坐标。

hint:
### 样例 1 解释

一开始第一堆灰尘位于 $(1,1)$，第二堆灰尘位于 $(4,0)$。图一描述了房间现在的情况。

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

在第一个事件中，添加了 $(2,3)$ 位置上的第三堆灰尘。图二描述了房间现在的情况。

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

在第二个事件中，Bitaro 用宽度为 $3$ 的扫帚进行了过程 V。之后，第一堆灰尘移动到了 $(1,3)$，图三描述了房间现在的情况。

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

在第三个事件中，Bitaro 计算了第一堆灰尘的坐标 $(1,3)$。

在第四个事件中，添加 $(1,2)$ 位置上的第四堆灰尘。图四描述了房间现在的情况。

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

在第五个事件中，Bitaro 用宽度为 $3$ 的扫帚进行了过程 H，第一堆灰尘移到了 $(3,3)$，第三堆灰尘移到了 $(3,3)$，第四堆灰尘移到了 $(3,2)$。图五描述了房间现在的情况。

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

在第六个事件中，Bitaro 用宽度为 $0$ 的扫帚进行了过程 H，第二堆灰尘移到了 $(6,0)$。图六描述了房间现在的情况。

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

在第七个事件中，Bitaro 计算了第四堆灰尘的坐标 $(3,2)$。

在第八个事件中，Bitaro 用宽度为 $2$ 的扫帚进行了过程 V，然而什么都没有发生。图七描述了房间现在的情况。

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

在第九个事件中，Bitaro 计算了第三堆灰尘的坐标 $(3,3)$。

在第十个事件中，Bitaro 计算了第二堆灰尘的坐标 $(6,0)$。

这组样例满足子任务 1 和子任务 5 的限制。

#### 样例 2~5 解释

第二组样例满足子任务 1,2,4,5 的限制。

第三组样例满足子任务 1,2,5 的限制。

第四组样例满足子任务 1,3,4,5 的限制。

第五组样例满足子任务 1,5 的限制。

#### 子任务

| 子任务编号 | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: |
| Subtask 1 | $m\leq 2\times 10^3,Q\leq 5\times 10^3$ | $1$ |
| Subtask 2 | $T\in\{1,2,4\}$ | $10$ |
| Subtask 3 | $T\in\{1,2,3\},X_i\leq X_{i+1},Y_i\geq Y_{i+1}(1\leq i\leq m-1)$ | $11$ |
| Subtask 4 | $T\in\{1,2,3\}$ | $53$ |
| Subtask 5 | 无 | $25$ |

对于 $100\%$ 的数据，$1\leq n\leq 10^9,1\leq m\leq 5\times 10^5,1\leq Q\leq 10^6$。保证：

- $0\leq X_i,Y_i\leq N,X_i+Y_i\leq N(1\leq i\leq m)$；

- $1\leq P_i\leq M^\prime(1\leq i\leq Q)$，其中 $M^\prime$ 表示事件 $i$ 发生时灰尘的堆数；

- $0\leq L_i\leq n-1(1\leq i\leq Q)$；

- $0\leq A_i,B_i\leq n,A_i+B_i\leq n(1\leq i\leq Q)$；

- 至少存在一个 $T_i=1$ 的事件。


title: [NOI2020] 美食家

description:
坐落在 Bzeroth 大陆上的精灵王国击退地灾军团的入侵后，经过十余年的休养生息，重新成为了一片欣欣向荣的乐土，吸引着八方游客。小 W 是一位游历过世界各地的著名美食家，现在也慕名来到了精灵王国。

精灵王国共有 $n$ 座城市，城市从 $1$ 到 $n$ 编号，其中城市 $i$ 的美食能为小 W 提供 $c_i$ 的愉悦值。精灵王国的城市通过 $m$ 条**单向道路**连接，道路从 $1$ 到 $m$ 编号，其中道路 $i$ 的起点为城市 $u_i$ ，终点为城市 $v_i$，沿它通行需要花费 $w_i$ 天。也就是说，若小 W 在第 $d$ 天从城市 $u_i$ 沿道路 $i$ 通行，那么他会在第 $d + w_i$ 天到达城市 $v_i$。

小 W 计划在精灵王国进行一场为期 $T$ 天的旅行，更具体地：他会在第 $0$ 天从城市 $1$ 出发，经过 $T$ 天的旅行，最终在**恰好第 $T$ 天**回到城市 $1$ 结束旅行。由于小 W 是一位美食家，每当他到达一座城市时（包括第 $0$ 天和第 $T$ 天的城市 $1$），他都会品尝该城市的美食并获得其所提供的愉悦值，若小 W 多次到达同一座城市，他将**获得多次愉悦值**。注意旅行途中小 W **不能在任何城市停留**，即当他到达一座城市且还未结束旅行时，他当天必须立即从该城市出发前往其他城市。

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

对于上图，小 W 一种为期 $11$ 天的可行旅游方案为 $1 \to 2 \to 1 \to 2 \to 3 \to 1$：
- 第 $0$ 天，小 W 从城市 $1$ 开始旅行，获得愉悦值 $1$ 并向城市 $2$ 出发。
- 第 $1$ 天，小 W 到达城市 $2$，获得愉悦值 $3$ 并向城市 $1$ 出发。
- 第 $4$ 天，小 W 到达城市 $1$，获得愉悦值 $1$ 并向城市 $2$ 出发。
- 第 $5$ 天，小 W 到达城市 $2$，获得愉悦值 $3$ 并向城市 $3$ 出发。
- 第 $7$ 天，小 W 到达城市 $3$，获得愉悦值 $4$ 并向城市 $1$ 出发。
- 第 $11$ 天，小 W 到达城市 $1$，获得愉悦值 $1$ 并结束旅行。
- 小 W 在该旅行中获得的愉悦值之和为 $13$。

此外，精灵王国会在**不同**的时间举办 $k$ 次美食节。具体来说，第 $i$ 次美食节将于第 $t_i$ 天在城市 $x_i$ 举办，若小 W 第 $t_i$ 天时恰好在城市 $x_i$，那么他在品尝城市 $x_i$ 的美食时会**额外得到** $y_i$ 的愉悦值。现在小 W 想请作为精灵王国接待使者的你帮他算出，他在旅行中能获得的愉悦值之和的**最大值**。

inputFormat:
从标准输入中读入数据。

第一行四个整数 $n, m, T, k$，依次表示城市数、道路条数、旅行天数与美食节次数。

第二行 $n$ 个整数 $c_i$，表示每座城市的美食所能提供的愉悦值。接下来 $m$ 行每行三个整数 $u_i, v_i, w_i$，依次表示每条道路的起点、终点与通行天数。

最后 $k$ 行每行三个整数 $t_i, x_i, y_i$，依次表示每次美食节的举办时间、举办城市与提供的额外愉悦值。

本题中数据保证：
- 对所有 $1 \leq i \leq m$，有 $u_i\neq v_i$。但数据中可能存在路线重复的单向道路，即可能存在 $1 \leq i < j \leq m，使得 u_i = u_j, v_i = v_j$。
- 对每座城市都满足：至少存在一条以该该城市为起点的单向道路。
- 每次美食节的举办时间 $t_i$ 互不相同。

outputFormat:
输出到标准输出中。

仅一行一个整数，表示小 W 通过旅行能获得的愉悦值之和的最大值。

**若小 W 无法在第 $T$ 天回到城市 $1$，则输出 $-1$**。

hint:
#### 样例 1 解释

该样例为题目描述中的例子，最优旅行方案见题目描述。

#### 样例 2 解释

最优方案为 $1 \to 3 \to 4 \to 2 \to 3 \to 4 \to 1$。
- 第 $0$ 天，小 W 从城市 $1$ 开始旅行，获得愉悦值 $3$ 并沿道路 $3$ 通行。
- 第 $2$ 天，小 W 到达城市 $3$，获得愉悦值 $2$ 并沿道路 $4$ 通行。
- 第 $5$ 天，小 W 到达城市 $4$，由于美食节获得愉悦值 $20 + 4$ 并沿道路 $7$ 通行。
- 第 $6$ 天，小 W 到达城市 $2$，获得愉悦值 $1$ 并沿道路 $5$ 通行。
- 第 $8$ 天，小 W 到达城市 $3$，获得愉悦值 $2$ 并沿道路 $4$ 通行。
- 第 $11$ 天，小 W 到达城市 $4$，获得愉悦值 $4$ 并沿道路 $8$ 通行。
- 第 $16$ 天，小 W 到达城市 $1$，获得愉悦值 $3$ 并结束旅行。
- 小 W 获得的愉悦值之和为 $39$。

#### 样例 3

见选手目录下的 delicacy/delicacy3.in 与 delicacy/delicacy3.ans。

该样例满足 $k=0$

---

### 测试点约束

对于所有测试点：

$1 \leq n \leq 50$，$n \leq m \leq 501$，$0 \leq k \leq 200$，$1 \leq t_i \leq T \leq 10^9$。

$1 \leq w_i \leq 5$，$1 \leq c_i \leq 52501$，$1 \leq u_i, v_i, x_i \leq n$，$1 \leq y_i \leq 10^9$。

每个测试点的具体限制见下表：

| 测试点编号 |  $n$ |  $m$ |  $T$ | 特殊限制 |
| :-: | :-:| :-: |:-:| :-:|
|  $1\sim 4$ |  $\le 5$ |  $\le 50$ |  $\le 5$ | 无 |
|  $5\sim 8$ |  $\le 50$ |  $\le 50$ |  $\le 52501$ | 无 |
|  $9\sim 10$ |  $\le 50$ |  $\le 50$ |  $\le 10^9$ | A |
|  $11\sim 13$ |  $\le 50$ |  $\le 50$ |  $\le 10^9$ |  $k=0$ |
|  $14\sim 15$ |  $\le 50$ |  $\le 50$ |  $\le 10^9$ |  $k\le 10$ |
|  $16\sim 17$ |  $\le 50$ |  $\le 50$ |  $\le 10^9$ | 无 |
|  $18\sim 20$ |  $\le 50$ |  $\le 501$ |  $\le 10^9$ | 无 |

特殊限制 A：$n = m$ 且 $u_i = i,v_i = (i \bmod n) + 1$。


title: [NOI2020] 命运

description:
**提示**：我们在题目描述的最后一段提供了一份简要的、形式化描述的题面。

在遥远的未来，物理学家终于发现了时间和因果的自然规律。即使在一个人出生前，我们也可以通过理论分析知晓他或她人生的一些信息，换言之，物理学允许我们从一定程度上“预言”一个人的“命运”。

简单来说，一个人的命运是一棵由时间点构成的有根树 $T$：树的根结点代表着出生，而叶结点代表着死亡。每个非叶结点 $u$ 都有一个或多个孩子 $v_1, v_2,\dots , v_{c_u}$，表示这个人在 $u$ 所代表的时间点做出的 $c_u$ 个不同的选择可以导向的不同的可能性。形式化的，一个选择就是树上的一条边 $(u, v_i)$，其中 $u$ 是 $v_i$ 的父结点。

一个人的一生是从出生（即根结点）到死亡（即某一个叶子结点）的一条不经过重复结点的路径，这条路径上任何一个包含至少一条边的子路径都是这个人的一段**人生经历**，而他或她以所有可能的方式度过一生，从而拥有的所有人生经历，都被称为**潜在的人生经历**。换言之，所有潜在的人生经历就是所有 $u$ 到 $v$ 的路径，满足 $u, v \in T$，$u \neq v$，并且 $u$ 是 $v$ 的祖先。在数学上，这样一个潜在的人生经历被记作有序对 $(u, v)$，树 $T$ 所有潜在的人生经历的集合记作 $\mathcal P_T$。

物理理论不仅允许我们观测代表命运的树，还能让我们分析一些潜在的人生经历是否是“重要”的。一个人所作出的每一个选择——即树上的每一条边——都可能是**重要**或**不重要**的。一段潜在的人生经历被称为重要的，当且仅当其对应的路径上存在一条边是重要的。我们可以观测到一些潜在的人生经历是重要的：换言之，我们可以观测得到一个集合 $\mathcal Q \subseteq \mathcal P_T$，满足其中的所有潜在的人生经历 $(u, v) \in \mathcal Q$ 都是重要的。

树 $T$ 的形态早已被计算确定，集合 $\mathcal Q$ 也早已被观测得到，一个人命运的不确定性已经大大降低了。但不确定性仍然是巨大的——来计算一下吧，对于给定的树 $T$ 和集合 $\mathcal Q$，存在多少种不同的方案确定每条边是否是重要的，使之满足所观测到的 $\mathcal Q$ 所对应的限制：即对于任意 $(u, v) \in \mathcal Q$，都存在一条 $u$ 到 $v$ 路径上的边被确定为重要的。

**形式化的**：给定一棵树 $T = (V, E)$ 和点对集合 $\mathcal Q \subseteq V \times V$ ，满足对于所有 $(u, v) \in \mathcal Q$，都有 $u \neq v$，并且 $u$ 是 $v$ 在树 $T$ 上的祖先。其中 $V$ 和 $E$ 分别代表树 $T$ 的结点集和边集。求有多少个不同的函数 $f$ : $E \to \{0, 1\}$（将每条边 $e \in E$ 的 $f(e)$ 值置为 $0$ 或 $1$），满足对于任何 $(u, v) \in \mathcal Q$，都存在 $u$ 到 $v$ 路径上的一条边 $e$ 使得 $f(e) = 1$。由于答案可能非常大，你只需要输出结果对 $998,244,353$（一个素数）取模的结果。

inputFormat:
从标准输入读入数据。

第一行包含一个正整数 $n$，表示树 $T$ 的大小，树上结点从 $1$ 到 $n$ 编号，$1$ 号结点为根结点；

接下来 $n - 1$ 行每行包含空格隔开的两个数 $x_i, y_i$，满足 $1 \leq x_i, y_i \leq n$，表示树上的结点 $x_i$ 和 $y_i$ 之间存在一条边，但并不保证这条边的方向；

接下来一行包含一个非负整数 $m$，表示所观测得到信息的条数。

接下来 $m$ 行每行包含空格隔开的两个数 $u_i, v_i$，表示 $(u_i, v_i) \in \mathcal Q$。**请注意**：输入数据可能包含重复的信息，换言之可能存在 $i \neq j$，满足 $u_i = u_j$ 且 $v_i = v_j$。

输入数据规模和限制参见本题末尾的表格。

outputFormat:
输出到标准输出中。

输出仅一行一个整数，表示方案数对 $998, 244, 353$ 取模的结果。


title: [NOI2020] 时代的眼泪

description:
小 L 喜欢与智者交流讨论，而智者也经常为小 L 出些思考题。

这天智者又为小 L 构思了一个问题。智者首先将时空抽象为了一个二维平面，进而将一个事件抽象为该平面上的一个点，将一个时代抽象为该平面上的一个矩形。

为了方便，下面记 $(a, b) \leq (c, d)$ 表示平面上两个点 $(a, b),(c, d)$ 满足 $a \leq c$，$b \leq d$。

更具体地，智者给定了 $n$ 个**事件**，他们用平面上 $n$ 个不同的点 $\{(x_i, y_i)\}^n_{i=1}$ 来表示；智者还给定了 $m$ 个**时代**，每个时代用平面上一个矩形 $(r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2})$ 来表示，其中 $(r_{i,1}, c_{i,1})$ 是矩形的左下角，$(r_{i,2}, c_{i,2})$ 是矩形的右上角，保证 $(r_{i,1}, c_{i,1}) \leq (r_{i,2}, c_{i,2})$。我们称时代 $i$ 包含了事件 $j$ 当且仅当 $(r_{i,1}, c_{i,1}) \leq (x_j, y_j ) \leq (r_{i,2}, c_{i,2})$。

智者认为若两个事件 $i, j$ 满足 $(x_i, y_i) \leq (x_j, y_j)$，则这两个事件形成了一次**遗憾**。而对一个时代内包含的所有事件，它们所形成的遗憾被称为这个**时代的眼泪**，而形成的遗憾次数则称为该时代的眼泪的大小。现在智者想要小 L 计算**每个时代的眼泪的大小**。

小 L 明白，如果他回答不了这个问题，他也将成为时代的眼泪，请你帮帮他。

inputFormat:
从标准输入中读入数据。

第一行两个整数 $n, m$，分别表示事件数与时代数。

第二行 $n$ 个整数 $p_i$，其中第 $i$ 个数表示事件 $i$ 在平面上的坐标为 $(i, p_i)$。保证 $p_i$ 为一个 $1$ 到 $n$ 的排列。

之后 $m$ 行，每行四个整数 $r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2}$，表示每个时代对应的矩形。

outputFormat:
输出到文件标准输出中。

输出 $m$ 行，每行包含一个整数，第 $i$ 行输出第 $i$ 个时代的眼泪的大小。


title: [JOISC2020] 首都

background: JOI 国是一个庞大的国度。

description:
JOI 国拥有 $N$ 个城镇，编号为 $1$ 到 $N$，这些城镇由 $N-1$ 条双向道路连接。

JOI 国还拥有 $K$ 个城市，编号为 $1$ 到 $K$，第 $i$ 个城镇属于第 $C_i$ 个城市。

现在 JOI 国的总理 JOI 君 114514 世要挑选一个城市作为首都，从首都中的任一个城镇到达另一个首都中的城镇可以只经过首都中的城镇，但这明显是不合理的。

所以 JOI 君 114514 世要进行合并城市，合并城市 $x$ 和城市 $y$ 就会把城市 $y$ 里的所有小镇归为城市 $x$。

求能找到首都的最小合并次数。

inputFormat:
第一行两个整数 $N,K$ 代表城镇数和城市数。
接下来 $N-1$ 行每行两个整数 $u,v$ 代表一条双向边。
接下来 $N$ 行第 $i$ 行一个整数 $C_i$ 代表第 $i$ 个城镇属于第 $C_i$ 个城市。

outputFormat: 一行一个整数代表最小的合并次数。

hint:
#### 样例 1 解释

可以将城市 $1$ 和 $3$ 合并，然后选择城市 $1$ 作为首都。

#### 子任务

|子任务|特殊性质|分数|
|:-:|:-:|:-:|
|$1$|$N \le 20$|$1$|
|$2$|$N \le 2000$|$10$|
|$3$|每个城镇最多与两个城镇相连|$30$|
|$4$|无|$59$|

对于 $100\%$ 的数据，$1 \le K,u,v \le N \le 2 \times 10^5$，保证从任何一个城镇出发都能到达其他城镇，$1 \le C_i \le K$。

#### 说明

翻译自 [第１９回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) [Day4 A 首都](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day4/capital_city.pdf)。


title: [JOISC2020] 伝説の団子職人

background: 您是做团子带师，您太强了。

description:
您面前有一个 $R \times C$ 的网格，每一个格子里有一个团子，您可以横向，竖向，斜向地将三个连续的团子按顺序串起来，按顺序指可以串上中下，下中上之类的，但是不能串中下上，上下中之类的。

如果一串团子的颜色为绿，白，粉或者粉，白，绿，那么称这串团子叫 AK IOI 串。

求串最多 AK IOI 串的方法（我坚信做了几个 AK IOI 串就会 AK 几次 IOI）。

inputFormat:
第一行两个整数 $R,C$ 代表网格大小。
接下来 $R$ 行每行 $C$ 个字符代表网格：

- `P` 代表粉色团子
- `W` 代表白色团子
- `G` 代表绿色团子

outputFormat:
$R$ 行每行 $C$ 个字符代表串好的网格：

- 可以为 `-`，`|`，`/`，`\`，代表一个团子串
- 如果不是以上四种线，那么原样输出

输出文件应为 `01.ans` ~ `06.ans`。


title: [JOISC2020] 治療計画

background:
因为本题数据点过多，另外 $3$ 组数据请在 [这里](https://www.luogu.com.cn/problem/U127700) 测试。

JOI 村庄的村民们最近发生了 COVILLAGE-19 疫情！

description:
JOI 村庄有 $N$ 个房屋，编号为 $1$ 到 $N$，每个房屋住有一个村民，第 $i$ 个房屋居住编号为村民 $i$。

现在，这 $N$ 个房屋里的村民全部感染 COVILLAGE-19 病毒，有 $M$ 个治疗方案被提出，第 $i$ 个治疗方案描述为，在第 $T_i$ 天的晚上，编号在 $[L_i,R_i]$ 区间内的村民被治愈。

COVILLAGE-19 病毒还会继续传播，在某天早上，如果村民 $i$ 被感染，那么村民 $i+1$ 和村民 $i-1$ 也会被感染，因为病毒威力巨大，所以被治愈的村民有可能再次被感染。

您是 JOI 国的总理，您要选择一些方案使得 JOI 村庄所有村民全部被治愈，一天可以进行很多方案。

第 $i$ 个方案要花费 $C_i$，求最小花费。

inputFormat:
第一行两个整数 $N,M$ 代表村民数和方案数。
接下来 $M$ 行每行四个整数 $T_i,L_i,R_i,C_i$ 代表一个治疗方案。

outputFormat:
一行一个整数代表最小花费。
如果无法全部治愈，输出 $-1$。

hint:
#### 样例 1 解释

执行过程如下（红色为被病毒感染，绿色为治愈）：

1. 在第二天晚上，执行第 $1$ 个方案，情况如下：

$$\color{Red}1\ 2\ 3\ 4\color{Green}\ 5\ 6\ 7\ 8\ 9\ 10$$

2. 在第三天早上，村民 $5$ 被感染，情况如下：

$$\color{Red}1\ 2\ 3\ 4\ 5\color{Green}\ 6\ 7\ 8\ 9\ 10$$

3. 在第四天早上，村民 $6$ 被感染，情况如下：

$$\color{Red}1\ 2\ 3\ 4\ 5\ 6\color{Green}\ 7\ 8\ 9\ 10$$

4. 在第四天晚上，执行第 $5$ 个方案，情况如下：

$$\color{Green}1\ 2\ 3\color{Red}\ 4\ 5\ 6\color{Green}\ 7\ 8\ 9\ 10$$

5. 第五天早上，村民 $3,7$ 被感染，情况如下：

$$\color{Green}1\ 2\color{Red}\ 3\ 4\ 5\ 6\ 7\color{Green}\ 8\ 9\ 10$$

6. 在第五天晚上，执行第 $3$ 个方案，情况如下：

$$\color{Green}1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10$$

全部治愈，这三个方案花费为 $7$，为最小花费。

#### 样例 2 解释

无法使得所有村民全部治愈。

#### 子任务

|子任务|特殊性质|分数|
|:-:|:-:|:-:|
|$1$|$T_i=1$|$4$|
|$2$|$M \le 16$|$5$|
|$3$|$M \le 5000$|$30$|
|$4$|无|$61$|

对于 $100\%$ 的数据，$1 \le N,T_i,C_i \le 10^9$，$1 \le M \le 10^5$，$1 \le L_i \le R_i \le N$。

#### 说明

翻译自 [第１９回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) [Day4 C 治療計画](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day4/capital_city.pdf)。


title: 【模板】有负圈的费用流

description:
给定一张 $n$ 个点 $m$ 条边的费用网络，源为 $s$ 且汇为 $t$ ，求其最小费用最大流。

注意存在费用为负的边和总费用为负的环。

注意，本题中允许一个不经过 $s,t$ 的环整体加上一个流量。事实上，若不允许这种情况的出现，则哈密顿路可以归约为这个问题。

inputFormat:
输入第一行包括四个正整数 $n,m,s,t$。

第 $2$ 到 $m+1$ 行，每行四个整数 $x_i,y_i,f_i,v_i$，表示存在一条 $x_i$ 到 $y_i$ 的边，流量为 $f_i$，费用为 $v_i$。

outputFormat: 输出包括一行两个整数，分别表示最大流与最小费用。

hint:
对于 $100\%$ 的数据：$1\leq n\leq 200$，$1\leq m\leq {10}^{4}$，$0\leq f_i,|v_i|\leq 100$。

注：不知道消圈算法能不能过，由于数据分档，即使不能过应该也能拿到一定的分数。


title: [JOISC2020] 星座 3

background:
> 蓝蓝的天空银河里
有只小白船
船上有棵桂花树
白兔在游玩
桨儿桨儿看不见
船上也没帆
飘呀飘呀飘向西天
渡过那条银河水
走向云彩国
走过那个云彩国
再向哪儿去
在那遥远的地方
闪着金光
晨星是灯塔
照呀照得亮
晨星是灯塔
照呀照得亮

**本题被卡空间的可以尝试使用 C++14 通过**

description:
JOI 君去拍照，拍了一张大小为 $N \times N$ 的图片，第 $i$ 列第 $j$ 行的格子称为格子 $(i,j)$。

图里有白色的小白船，黄色的星星（天知道为啥星星是黄色的），黑色的空格（天知道这空格是啥），第 $i$ 列自下往上数到第 $A_i$ 行的格子里都是小白船，另外有 $M$ 颗星星，第 $i$ 颗星星在格子 $(X_i,Y_i)$，除了小白船和星星，其他格子都是空格。

现在 JOI 君定义满足下面的一个矩阵为星座：

1. 不包含小白船
2. 至少包含 $2$ 颗星星

JOI 君已经看星座看了 114514 年了，他厌烦了，所以他要把图片中的一些星星涂黑变成黑色空格，涂黑第 $i$ 颗星星会让图片增加 $C_i$ 的不自然度。求不存在星座的最小不自然度。

inputFormat:
第一行一个整数 $N$ 代表图片的大小。
第二行 $N$ 个整数第 $i$ 个整数 $A_i$ 代表小白船的位置。
第三行一个整数 $M$ 代表星星的个数。
接下来 $M$ 行每行三个整数 $X_i,Y_i,C_i$ 代表一颗星星。

outputFormat: 一行一个整数代表不存在星座的最小不自然度。

hint:
#### 样例 1 解释

把第三颗星星涂黑即可。

#### 样例 2 解释

把第三颗和第四颗星星涂黑即可。

#### 子任务

|子任务|特殊性质|分数|
|:-:|:-:|:-:|
|$1$|$N,M \le 300$|$14$|
|$2$|$N,M \le 2000$|$21$|
|$3$|无|$65$|

对于 $100\%$ 的数据，$1 \le N,M \le 2 \times 10^5$，$1 \le A_i,X_i,Y_i \le N$，$1 \le C_i \le 10^9$，$A_{X_i}<Y_i$，没有相同位置的星星。

#### 说明

翻译自 [第１９回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) [Day3 A 星座3](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day3/constellation3.pdf)。