title: 「CROI · R1」浣熊的小溪

background:
> “从太阳里奔来，又迎着阳光走去；张开熊爪，与风相拥，离别之际，却低首自吟。”\
那梦枫畔嬉戏的成长，那阳光下不羁的信仰，历久弥坚，在无数浣熊的心畔回响。 \
> 可叹，灵溪上畔，一人意志，大小工事，割裂了纯真的年华，刀刻了落寞的隔阂。\
那明澈的小溪，那快乐的往日，还会，在感怀中驻足吗……

description:
浣熊岭的森林可以看作一张 $n \times m$ 的网格图。工厂排放的废水污染了纵贯森林的梦枫溪（一条直线），导致所经区域对浣熊是有害的。小浣熊 CleverRaccoon 为了研究废水对浣熊的危害，要寻求你的帮助。

设 $f(n,m)$ 表示一条直线最多能穿过 $n\times m$ 的网格图的格子数。

小浣熊有两种问题想要问你：

1.  给定 $n,m$，求 $f(n,m)$；
2.  给定 $n,m,Q$，你需要找到 $n'\ge n,m'\ge m$，满足 $f(n',m')\ge Q$，且 $n'\times m'$ 尽可能小。求 $n'm'-nm$ 的最小值**对 $998244353$ 取模**的结果。数据保证 $f(n,m)<Q$。

inputFormat:
**本题包含多组测试数据。**

第一行，输入一个正整数 $T$，表示有 $T$ 次询问。

对于每次询问：

第一行，输入一个正整数 $op$，表示问题类型。

第二行，若 $op=1$，输入 $2$ 个正整数 $n$ 和 $m$；若 $op=2$，输入 $3$ 个正整数 $n$、$m$ 和 $Q$。

outputFormat: 共 $T$ 行，对于每次询问：一行输出 $1$ 个正整数，表示对应问题的答案。

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

对于第一次询问：

下图所示的情况是一种最佳构造方案，梦枫溪穿过 $2 \times 3$ 的网格森林时，最多穿过 $4$ 个小网格（黄色部分为穿过的网格，灰色部分为未穿过的网格）。

![](https://cdn.luogu.com.cn/upload/image_hosting/7dknua6w.png?x-oss-process=image/resize,m_lfit,h_360)

下示方案不是一种最佳方案，梦枫溪是从两个绿色网格中间的一个顶点上穿过的，所以两个绿色区域都没有被穿过。因此梦枫溪只穿过了 $3$ 个小网格。

![](https://cdn.luogu.com.cn/upload/image_hosting/cgjzaf2i.png?x-oss-process=image/resize,m_lfit,h_360)

对于第二次询问：

如下图所示，当 $n'=2$, $m'=9$ 时，才能使梦枫溪穿过 $10$ 个网格的情况下，在原基础添加的 $n'm'-nm$ 个网格是最少的（红色虚线左边是原来的森林，右边是添加的部分）。

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

#### 数据范围

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

| Subtask | $n$ | $m$ | $Q$ | 特殊性质 | Score |
| :-: | :-: | :-: | :-: | :-: | :-: |
| $0$ | $\le10^{18}$ | $=1$ | $\le2 \times 10^{18}$  | $op=1$ | $5$ |
| $1$ | $\le10^{18}$ | $=1$ | $\le2 \times 10^{18}$  | $op=2$ | $5$ |
| $2$ | $\le10^{18}$ | $\le10^{18}$ | $\le2 \times 10^{18}$ | $op=1$ | $25$ |
| $3$ | $\le10^{18}$ | $\le10^{18}$ |$\le2 \times 10^{18}$ | $op=2$ | $25$ |
| $4$ | $\le10^9$ | $\le10^9$ | $\le2 \times 10^9$ | 无特殊性质 | $30$ |
| $5$ | $\le10^{18}$ | $\le10^{18}$ | $\le2 \times 10^{18}$ | 无特殊性质 | $10$ |

对于 $100\%$ 的数据，保证 $1 \le T \le 10$，$op \in \{1,2\}$，$1 \le n,m \le 10^{18}$，$2 \le n+m \le Q \le 2 \times 10^{18}$。


title: 地铁

type: P

background:
> 两年级生 孤单一人
>
> 仰望上空 陋市苍穹
>
> 在宇宙这个约会室中
>
> Maybe 我们只是刚好没能邂逅呢

description:
著名工程学专家 625OutContradiction 设计了一张地铁交通网 $G$．$G$ 拥有 $n$ 个站点和 $m$ 条地铁线路．

第 $i$ 条地铁线路 $P_i$ 会经过交通网上的若干站点，形如 $P_i=(u_1,u_2,u_3,...,u_{k_i})(k_i>0)$：每两个相邻站点 $u_j,u_{j+1}(j<k_i)$ 之间存在一段属于线路 $i$ 的从 $u_j$ 通向 $u_{j+1}$ 的单向地铁轨道．保证一条地铁线路不重复经过同一站点．但一个站点可能被若干条地铁线路经过．

丹羽和艾莉欧准备从 $1$ 号站点前往 $n$ 号站点．然而他们的自行车坏掉了，只好准备乘坐地铁．现在他们需要决定出行的方案．

一种出行方案具体是这样的：从 $1$ 号站点出发，选定一条经过 $1$ 号站点的地铁线路并开始乘坐地铁．沿当前地铁线路乘坐地铁的过程中，可以选择换乘其他任意一条经过当前站点的地铁线路．要求最终到达 $n$ 号站点．乘坐地铁过程中重复经过某一站点或某段地铁轨道是被允许的．

**请注意：从 $1$ 号站点出发，第一次乘坐地铁不被算作换乘．**

艾莉欧提出了 $q$ 个问题．对于每个问题，艾莉欧会提供三个参数 $a, b, c$．在这次问题中，一个出行方案如果经过了 $x$ 段地铁轨道并进行了 $y$ 次换乘，那么它的疲惫值为 $ax+by$．您需要回答换乘次数不超过 $c$ 的出行方案中最小的疲惫值是多少．

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

接下来 $m$ 行，第 $i$ 行形如：$k_i,u_1,u_2,u_3,...,u_{k_i}$．
表示一条地铁线路．

接下来 $q$ 行，每行三个整数，表示 $a,b,c$．

outputFormat: $q$ 行，对应每个问题的回答．

hint:
### 样例 #1 说明
$1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$ 是给出的第一条地铁线路，$1\rightarrow 3$，$2\rightarrow 4\rightarrow 5$ 是第二三条地铁线路．

对于第一二组询问，均存在一种最优的出行方案为，在 $1$ 站点搭乘第二条地铁线路到达 $3$ 站点，在 $3$ 站点换乘第一条地铁线路到达终点；共经过 $3$ 段地铁轨道，并进行了 $1$ 次换乘，故第一二组询问的答案分别为 $3\times 1+1\times 1=4$，$3\times 3+1\times 0=9$．对于第三组询问，由于换乘的代价较大，最优的方案为顺着第一条地铁线路一直通向终点，途径 $4$ 段地铁轨道，答案为 $4$．

### 数据点约束
对于所有数据满足：

$1\le n \le 10^5$，$1\le m \le 10^4$，$1\le q \le 10^5$，$\sum k_i \le 3\times 10^5$．

$0 \le a,b \le 10^6$，$0 \le c \le 20$．

---
对于 $10\%$ 的数据满足：$n \le 20$，$\sum k_i \le 40$，$q \le 30$．

---

对于另外 $20\%$ 的数据满足：$c=0$．

---

对于另外 $30\%$ 的数据满足：$q=1$．

---

题目中可能存在只经过一个地铁站的地铁线路．这种线路可以直接忽视．数据保证：对于任意一组询问，存在一条合法的路线可以到达终点．


title: 健将青蛙……

background:
小青蛙在打破监狱后，注重身体的锻炼。

他成为了一只运动**健将**。

他的故事还在继续……

description:
**这是一道提交答案题。**

你的大脑需要被锻炼。

你是一个 bot。你有一个大小为 $300$ 的内存条（下标为 $1\sim 300$），初始时全为 $0$。每个内存条中存储着一个 $32$ 位整数（即 C++ 中的 `int`）。

你需要构造一个网格图，某些网格上的节点有一个指令，机器人根据指令进行操作和移动。

下文把有指令的节点称作特殊节点。

节点上的指令有如下几种：

- 增减：将内存条某个位置上的整数增、减 $1$，并向指定的方向移动一步；
- 比较：比较内存条中下标为 $i,j$ 的数的大小，并根据大小向指定方向移动一步；
- 输入：机器人将从这里出发，并向指定方向移动一步，**该节点不应被重复经过**；
- 输出：机器人到达该节点时结束行动并输出指定位置的值。

**其中输入、输出节点必须存在且唯一。**

任务：

1. 在初始内存条下标 $1,2$ 位置中读入 $a,b$，输出 $a+b$。保证 $0\leq a,b\leq 100$。
2. 在初始内存条下标 $1$ 位置中读入 $a$，输出 $2^a$。保证 $0\leq a\leq 20$。
3. 在初始内存条下标 $1$ 位置中读入 $a$，输出 $a^2$。保证 $1\leq a\leq 1000$。
4. 在初始内存条下标 $1,2$ 位置中读入 $a,b$，输出 $a\oplus b$。保证 $0\leq a,b<2^{19}$。
5. 在初始内存条下标 $1\sim 51$ 位置中读入 $n=50,a_1,a_2\dotsc,a_n$，输出升序排序后的 $a_1\sim a_n$。保证 $0\leq a_i\leq100$。
6. 在初始内存条下标 $1\sim 59$ 位置中读入 $n=30,u_1,v_1\dotsc,u_{n-1},v_{n-1}$，表示由 $n$ 个节点，$n-1$ 条边 $u_i,v_i$ 组成的树，要求输出给定树的直径长度（定义为树上最长的简单路径所包含的边数），保证 $1\leq u_i,v_i\leq n$。

你需要保证机器人从输入节点出发能到达输出节点，并且中途不会访问到非特殊节点，且移动次数 $\leq 5\times 10^7$。

outputFormat:
**本题使用 `Special Judge` 判定答案正误。**

针对题目给定的 $6$ 个任务，你需要分别提交你的输出文件 `robot1.out~robot6.out`。

对于每个文件，你的输出应为以下格式：

第一行输出两个正整数 $n,m$ 表示网格大小为 $n$ 行 $m$ 列。你需要保证 $n\times m\leq 10^7$。

第二行输出一个正整数 $k$ 表示特殊节点数量。其中 $1\leq k \leq n \times m$。

接下来 $k$ 行每行格式如下：

前两个输出的整数 $x,y$ 表示特殊节点所在位置为第 $x$ 行第 $y$ 列，其中 $1\leq x\leq n,1\leq y\leq m$，且所有 $(x,y)$ 互不相同，接下来按照节点类型输出不同内容：

- 若为自增节点，则输出 `+`，自减节点输出 `-`，并输出一个整数表示自增/自减的内存下标 $i$，其中 $1\leq i\leq 300$，最后输出一个 `LRUD` 中的字符表示移动方向（分别对应左右上下，下同）。
- 若为比较节点，则输出 `c`，接下来两个整数 $i,j$ 表示比较的下标，你需要保证 $1\leq i,j\leq 300$。最后输出两个 `LRUD` 中的字符分别表示 $i$ 下标中的数大于 $j$ 下标中的数时的移动方向和 $i$ 下标中的数小于等于 $j$ 下标中的数时的移动方向。
- 若为输入节点则输出 `i`，并输出一个 `LRUD` 中的字符表示移动方向。
- 若为输出节点则输出 `o`，并输出一个整数 $p$ 表示输出大小，接下来 $p$ 个 **互不相同的整数** $a_1\sim a_p$ 表示你要输出的内存条中的下标，你需要保证 $1\leq p,a_i\leq 300$。

**你需要保证给出的特殊节点中输入、输出节点必须存在且唯一。**

hint:
上述样例给出了一个读入 $a,b$，输出 $\max(a,b)$ 的程序。

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

评分方式：若你的输出格式错误或给出结果错误，则获得 $0$ 分。否则对于每个测试点，你的得分与 $n\times m$ 的大小有关。每个测试点有 $2$ 个评分参数 $c_1,c_2$，若你的 $n\times m\leq c_1$ 则获得该测试点满分，否则若 $c_1< n\times m\leq c_2$ 则获得该测试点 $60\%$ 分数，否则获得 $40\%$ 的分数。

| Task Id | $c_1 =$ | $c_2 =$ | pts |
| :----------: | :----------: | :----------: | :----------: |
| 1 | $6$ | $9$ | $10$ |
| 2 | $9$ | $12$ | $15$ |
| 3 | $9$ | $10$ | $15$ |
| 4 | $35$ | $48$ | $20$ |
| 5 | $499$ | $999$ | $20$ |
| 6 | $3\times 10^3$ | $3\times 10^5$ | $20$ |

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

本题下发 `附件.zip` 中含有对解题有帮助的文件。

- `./checker/checker.cpp`，其实现与评测时使用的 `Special Judge` 大致相同，
- `./toy/index.html` 可在浏览器中使用。其为本题的网页版可视化工具，使用方法参见内部的 `instruction`。


title: [yLOI2022] 西施江南

background:
> 我晤江南面 如逢西施颜
> 清芬宜送岸 菡萏新雨前
> 皓腕分珠帘 珠露扬波珠玉敛
> 天然一段聚散 嫣然曾与言
> 平芜辙尚浅 无韵化湖田
> 林园虽工典 芳姿不可嵌
> 何人冠诗篇 重街杳杳重门掩
> 似有柔荑遮目 空谷足尖

银临《西施江南》

description: 给定 $n$ 个正整数 $a_1, a_2, a_3, \dots a_n$，记 $g$ 是这些数的**最大公约数**，$l$ 是这些数的**最小公倍数**。请你判断 $l \times g$ 是否等于 $a_1 \times a_2 \times \dots \times a_n$。

inputFormat:
**本题单测试点内有多组测试数据**。

输入的第一行是一个整数 $T$，表示测试数据组数。对每组数据按如下格式输入：

每组数据的第一行是一个整数，表示整数个数 $n$。
每组数据的第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

outputFormat:
对每组数据依次输出一行一个字符串表示答案。

- 若 $l \times g = a_1 \times a_2 \times \dots \times a_n$，请输出 $\texttt{Yes}$。
- 否则，请输出 $\texttt{No}$。

samples:
见附加文件中的 C2.in
见附加文件中的 C2.ans

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

以下用 $N$ 表示单个测试点内 $n$ 的和，即 $N = \sum n$。

- 对 $12\%$ 的数据，保证 $n = 2$。
- 对 $36\%$ 的数据，保证 $n \leq 5$。
- 对 $52\%$ 的数据，保证 $N \leq 1000$。
- 对 $76\%$ 的数据，保证 $N,a_i \leq 10^5$。
- 对 $100\%$ 的数据，保证 $2 \leq n,N \leq 5 \times 10^5$，$2 \leq a_i \leq 10^8$，$1 \leq T \leq 20$。

### 提示

**数据千万条，清空第一条**。
**多测不清空，爆零两行泪**。
**清空不规范，超时总相伴**。


title: [NERC2018] Alice the Fan

background: 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) A 题。

description:
Alice 喜欢看排球比赛，她尤其喜欢看 A 队打球，排球比赛的规则如下：

- 一场比赛最多有 $5$ 局。

- 前面 $4$ 均需获得至少 $25$ 分方可获胜，第 $5$ 局仅需获得 $15$ 分。

- 如果单局内其中一方满足获胜条件**但是**双方比分之差不满 $2$，不算获胜。

- 有一方比分达到 $3$ 即为获胜，此时立刻结束比赛。

现在分别给你 A 队和 B 队赢球的个数，请你帮忙确定 A 队最好的比分是多少，或者确定这场球赛还没有结束。

（注：本题定义最好的比分为，如果 A 队可以赢，要使得它们两队的比分差尽可能大，反之尽可能小。）

inputFormat:
第一行一个整数 $m(1 \leq m \leq 50000)$，表示 A 队打过 $m$ 场不同的比赛。

接下来 $m$ 行，每行两个整数 $a(1 \leq a \leq 200)$ 和 $b(1 \leq b \leq 200)$，分别表示该场比赛 A 队和 B 队的得分。

outputFormat: 对于每场比赛，输出 A 队最好的比分情况和一种符合条件的**每场**的比分，或者确定这是不可能的，输出 `Impossible`。

hint:
测试数据保证 $1 \leq m \leq 50000$，$1 \leq a,b \leq 200$。

注：由于技术原因，SPJ 在评测时出现 UKE 是因为您的代码存在谬误，造成了 SPJ 读取字符时多/少读取到了，后面便无法正常评测。


title: [yLOI2022] 签到题

description: 给定一个长度为 $8$ 的字符串 $s$，请你分别统计 $s$ 中大小写字母和数字字符的个数。

inputFormat: 输入只有一行一个长度为 $8$ 的字符串 $s$。

outputFormat:
输出一行三个整数，依次表示：

- $s$ 中数字字符的个数。
- $s$ 中小写字母的个数。
- $s$ 中大写字母的个数。

samples:
IAKIOIOI
0 0 8


title: 「CROI · R1」浣熊的阴阳鱼

background:
> 往昔，阴阳由天地所创，孕大含深；今昔，时光为记忆所刻，随行如影。\
流水落花间，嬉闹于阴阳树的意境；沧海桑田间，铭心于阴阳忆的缤斓。\
阴鱼，阳鱼……挥翰着日月的闲情，留存着浣熊的惬意，却不复存在……\
小浣熊 CleverRaccoon 与最后一瞬阴阳，含泪而笑……

description:
一棵树的各结点都悬挂着 $1$ 条阴鱼或阳鱼（分别用 $0,1$ 表示），它们可能在某刻由于基因突变互相转化。

小浣熊 CleverRaccoon 带着一只能装 $2$ 条鱼的篮筐在此树的某条链上行走。当他所在点上的鱼与某条筐内鱼的属性相反时，他会将这 $2$ 条鱼合成 $1$ 条阴阳鱼并吃下；在筐中没有满的条件下，他会将所在点上的鱼放入筐中。

现有两种操作：

1. 一个结点上的阴阳鱼发生基因突变，变为另一种类型的阴阳鱼。
2. 帮助聪明的小浣熊 CleverRaccoon 求出：当他沿着这棵树上的某条链行走时，能吃下的阴阳鱼的条数。

inputFormat:
第一行，两个正整数 $n$ 和 $q$，表示结点个数、修改和询问总次数。

第二行 $n$ 个整数，表示每个结点上悬挂的鱼的属性。

接下来 $n−1$ 行，每行两个正整数 $u,v$，表示 $u$ 和 $v$ 两个点之间有一条边。

接下来 $q$ 行，格式为 `1 u` 或 `2 u v`。

若格式为 `1 u`，则表示结点 $u$ 上的鱼基因突变。

若格式为 `2 u v`，则表示询问小浣熊  CleverRaccoon 在从 $u$ 到 $v$ 的简单路径中能吃下的阴阳鱼的条数。

outputFormat: 对于每次询问，单行输出一个整数，表示小浣熊  CleverRaccoon 能吃下的阴阳鱼的条数。

hint:
**数据范围**

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

- Subtask 0（10 points）：$n,q \leq 10$。
- Subtask 1（15 points）：$n,q \leq 2\times10^3$。
- Subtask 2（15 points）：保证树的深度小于 $10^3$。
- Subtask 3（60 points）：无特殊限制。

对于所有测试数据： $1 \leq n,q\leq 10^5$。


title: [NERC2018]  Bimatching

background: 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) B 题。

description:
你与一些好友一起举办了一个舞会！

在这个舞会上，有 $n$ 位男性和 $m$ 位女性，本来舞蹈的形式是一男一女跳的，但是由于男性紧缺，你并不能让所有女性都有一个男性舞伴，于是你发明了一种新的舞蹈形式：一个男性，搭配两个女舞伴。

当然，每个女性在挑选舞伴时，都会对那些男性舞伴做出评价，如果评价是 $1$，说明这位女性愿意和这位男性一起跳舞，只有当两位女性都愿意和那位男性跳舞时，才能成为一对舞伴。

你作为一个组织者，自然要为大家着想，你需要求出能凑出的最多的舞伴对数，**每个舞伴不能重叠**。

inputFormat:
第一行一个数 $t (1 \leq t \leq 20)$，表示数据组数。

接下来 $t$ 组数据，每组第一行两个整数 $n$ 和 $m$，此处我们保证 $1 \leq n,m$ 且 $n + m \leq 150$。

然后一个 $n \times m$ 的矩阵，$a_{i,j}$ 表示 $j$ 号女士是否愿意和 $i$ 号男士一起跳舞。

outputFormat: 对于每组测试数据，输出一行，表示最多能凑出的舞伴对数。

hint:
数据保证 $1 \leq t \leq 20$，$1 \leq n, m$ 且 $n + m \leq 150$。

下图是对样例一和样例二的解释，其中加粗部分表示其中的一种可行方案。

样例一：

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

样例二：

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


title: [NERC2018] Cactus Search

background:
翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) C 题。

如果你想让数组问题更难解决，可以在树上解决；如果你想让树的问题更难解决，可以在仙人掌上解决。

description:
在前几年，就有过人提出了许多关于仙人掌——连通无向图的问题，其中每条边最多属于一个简单的循环。更加直观地说，仙人掌是一棵树的概括，在这棵树上允许有一些环。下面的图片给出了仙人掌的一个例子。

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

你和 Chloe 在一个仙人掌上玩游戏，你有一株仙人掌，但是淘气的 Chloe 偷偷拿走了一个顶点 $v$，你需要在 $10$ 次以内猜出 $v$，如果你猜到了 $v$，那你就赢了，如果你猜测的是另一个点 $u$，Chloe 会告诉你一个点 $w$，其中 $w$ 到 $v$ 经过的边数严格小于 $u$ 到 $v$。

inputFormat:
首先，第一行给你两个整数 $n$ 和 $m$，其中 $n$ 表示一共有 $n$ 个顶点，图的边由一组边不同的路径表示，$m$ 表示它们的数量。

接下来一行，$m$ 个整数 $k_i$，表示该条路径经过了 $k_i$ 个顶点，然后接下来 $k_i$ 个整数，表示一次经过的路径（不会重复经过点）。输入中的图形是一个仙人掌。每次猜测，程序会返回你一些返回值，如果是 `FOUND`，说明你猜对了，否则是 `GO w`，表示 $w$ 到 $v$ 经过的边数严格小于你猜测的点到 $v$ 的边数。你的程序每次询问要猜测不超过 $10$ 次，如果你猜测的次数 $> 10$ 次，那么你就不通过该测试点。

此外为了避免你是蒙对的，需要进行 $n$ 次询问，每次猜测成功后，你直接进行下一轮询问，询问 $n$ 次完直接退出。

outputFormat:
每次询问，你需要向**标准输出**输出一个整数 $u$，代表你猜测的结果，**然后清空缓冲区**。

你可以使用如下语句来清空缓冲区：

- 对于 C/C++：`fflush(stdout)`；
- 对于 C++：`std::cout << std::flush`；
- 对于 Java：`System.out.flush()`；
- 对于 Python：`stdout.flush()`；
- 对于 Pascal：`flush(output)`；
- 对于其他语言，请自行查阅对应语言的帮助文档。

samples:
5 2
5 1 2 3 4 5
2 1 3

FOUND
GO 4
FOUND
GO 2
FOUND
GO 1
FOUND
GO 4
GO 5
FOUND

hint:
数据保证 $1 \leq n \leq 500$，$0 \leq m \leq 500$，$1 \leq k_i \leq 500$。

注：为了方便比对，在样例输入输出上加入了一些空行进行对齐，实际输入输出中没有这些空行。


title: [NERC2018]  Distance Sum

background: 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) D 题。

description:
给你一个 $n$ 个顶点 $m$ 条边的连通无向图，定义 $u$ 与 $v$ 的距离 $d(u, v)$ 为从 $u$ 到 $v$ 最短路径上经过的边数。

现在请你求出 $\sum_{u=1}^n \sum_{v=u+1}^n d(u,v)$。

inputFormat:
第一行给定两个整数 $n(1 \leq n \leq 10^5)$，$m(n - 1 \leq m \leq n + 42)$，分别表示点数和边数。

接下来 $m$ 行，每行 $2$ 个整数 $x_i$ 和 $y_i(1 \leq x_i,y_i \leq n, x_i \neq y_i)$，表示 $x_i$ 和 $y_i$ 之间有一条边。

保证没有重边和自环。

hint:
对于所有数据保证 $1 \leq n \leq 10^5$，$n-1 \leq m \leq n + 42$，$1 \leq x_i, y_i \leq n$ 且 $x_i \neq y_i$。

样例一的图是：

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

其中 $d(1,2) = 1$，$d(1,3) = 1$，$d(1,4) = 2$，$d(2,3) = 1$，$d(2,3) = 2$，$d(3,4) = 1$，总和为 $1 + 1 + 2 + 1 + 2 + 1 = 8$。

样例二为：

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


title: [NERC2018] Easy Chess

background: 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) E 题。

description:
Elma 正在学习象棋。

Elma 是个新手，她还不特别了解象棋是如何下的，所以，为了更好地让她了解象棋，她的奶奶让她从一个棋盘（如下图）中进行 $n$ 次移动，每次移动只能是水平或垂直地移动若干个格子的，且每个点只能到达一次，使得从 a1 到 h8 处。

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

inputFormat: 输入一个数 $n(2 \leq n \leq 63)$，表示你一共需要走的步数。

outputFormat: 给出一种可行方案且保证停留过的点不重复。

hint: 对于所有数据保证 $2 \leq n \leq 63$ 且保证存在至少一种合法方案。


title: [NERC2018] Fractions

background: 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) F 题。

description: 给你一个整数 $n$，你需要构造出若干个形如 $\dfrac{a_i}{b_i}$ 的真分数，使得 $\sum^k_{i=1} \frac{a_i}{b_i} = 1 - \frac{1}{n}$，且 $b_i$ 可以整除 $n$。

inputFormat: 一个正整数 $n (2 \leq n \leq 10^9)$。

outputFormat:
如果不能构造，输出一行 `NO`。

否则的话就构造出其中一种的合法方案，输出 `YES`，然后让 $\sum^k_{i=1} \frac{a_i}{b_i} = 1 - \frac{1}{n}$，按第二行第一个整数 $k$，接下来 $k$ 行一行两个整数 $a_i$ 和 $b_i(b_i \neq n)$。

注意你输出的 $k$ 的范围是 $2 \leq k \leq 10^5$。

hint:
对于所有的数据，保证 $1 \leq n \leq 10^9$。

对于第一个样例，不存在一种方案使得答案总和为 $\frac{1}{2}$。

对于第二个样例，$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}$。


title: [NERC2018]  Guest Student

background: 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) G 题。

description:
你作为某知名大学的客座学生，你想要在那里学习 $k$ 节课，但同时很遗憾，对于每周，你只有特定的时间才能有空去听课，如果 $a_i = 1$，说明周 $i$ 你有空，反之则没空。

你需要安排一个合理的日程，使得你去听第一节课到最后一节课中间经过的时间最短，当然第一节课听什么的顺序由你决定。

inputFormat:
第一行一个整数 $t (1 \leq t \leq 10000)$，表示数据组数。

接下来每组数据第一行一个整数 $k (1 \leq k \leq 10^8)$。

然后 $7$ 个整数 $a_1 \sim a_7$，$a_i = 1$ 表示有空，$a_i = 0$ 表示没空。

outputFormat: 对于每组数据，输出一个整数，表示最短的从第一节课到最后一节课所经过的时间。

hint:
对于所有数据，保证 $1 \leq t \leq 10000$，$1 \leq k \leq 10^8$ 且 $a_i \in \{0,1\}$。

对于样例一，从周二开始听课听到下周二，经过 $8$ 天。


title: [NERC2018] Harder Satisfiability

background: 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) H 题。

description:
我们定义一个“完全量化的布尔类型的 2-CNF 公式”（下简称 2-CNF）是以 $Q_1 x_1 \ldots Q_n x_n F(x_1,\ldots x_n)$ 构成的，$Q_i$ 只有两种，一种是“通用量词” $\forall$，另一种是“存在量词” $\exists$。然后 $F$ 是一个 $m$ 子句的 $s \lor t$（$\mathtt{OR}$ 运算） 的连词（$\mathtt{AND}$ 运算），其中 $s$ 和 $t$ 不一定不同且不一定是否定（为 $\texttt{false}$）。由于 2-CNF 公式是给定的，所以并没有自由变量（即答案固定为 $\texttt{true}$ 或 $\texttt{false}$）。

至于计算 2-CNF 公式的值，我们可以使用一个简单的递归算法来求：

- 如果没有量词（即 $\forall$ 或 $\exists$ ），则返回剩余表达式的返回值。

- 否则，我们使用递归计算公式：$F_z = Q_2x_2 \ldots Q_nx_n F(z,x_2,\ldots,x_n)$，此处 $z = 0,1$。

- 如果当前符号为 $\exists$，则返回 $F_0 \lor F_1$（$\mathtt{OR}$ 运算）。否则符号为 $\forall$ 返回 $F_0 \land F_1$。

inputFormat:
第一行是一个整数 $t (1 \leq t \leq 10^5)$，表示数据组数。

接下来 $t$ 组数据，每组数据第一行两个整数 $n(1 \leq n \leq 10^5)$ 和 $m (1 \leq m \leq 10^5)$，$n$ 表示量词的长度，$m$ 表示在 $F$ 中的元素个数。

然后一行，一串长度为 $n$ 的字符串 $s$，如果 $s_i = $ `A`，则 $Q_i = \forall$，否则若 $s_i = $ `E`，则 $Q_i = \exists$。

接下来 $m$ 行，一行两个整数 $u_i,v_i(-n \leq u_i,v_i \leq n)$，如果 $u_i \geq 1$ 则第 $i$ 个变量是 $x_{u_i}$，如果 $u_i \leq -1$ 则第 $i$ 个变量是 $-(x_{-u_i})$，$v_i$ 同理。

outputFormat: 对于每组数据，如果 2-CNF 公式为真输出 `TRUE`，否则输出 `FALSE`。

hint:
数据保证 $1 \leq t \leq 10^5$，$1 \leq n,m \leq 10^5$，$-n \leq u_i,v_i \leq n$。

第一个 2-CNF 公式可以化简为 $\forall x_1 \exists x_2(x_1 \lor \overline{x_2}) \land (\overline{x_1} \lor x_2) = \forall x_1 \exists x_2 x_1 \oplus x_2$，对于任意的 $x_1$ 都存在 $x_2 = \overline{x_1}$ 使得答案为真。

第二个 2-CNF 改变了公式的顺序，对于任意的 $x_1$，都可以选择 $x_2 = x_1$，使得表达式为 `FALSE`。

第三个表达式是 $\forall x_1 \exists x_2 \forall x_3 (x_1 \lor \overline{x_2}) \land (\overline{x_1} \lor \overline{x_3})$，如果令 $x_1 = 1$，$x_3 = 1$，则没有 $x_2$ 的值可以使得句子赋值为真，所以公式为假。


title: [NERC2018]  Interval-Free Permutations

background: 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) I 题。

description:
我们定义一个从 $1 \sim n$ 的排列是“间隔排列”的情况是，在这个排列中存在连续的一段长度为 $2 \sim n-1$ 的子区间使得这段子区间在排序后是一串连续的自然数。比如，$\{6,7,1,8,5,3,2,4\}$ 是一个“间隔排列”，因为 $\{6,7\}$，$\{5,3,2,4\}$，$\{3,2\}$ 经过排序后都是一段连续的自然数。

现在已知 $n$，请你输出**不是**“间隔排列”的排列总数，由于输出可能很大，请对 $p$ 取模。

inputFormat:
第一行两个整数 $t (1 \leq t \leq 400)$ 和 $p (10^8 \leq p \leq 10^9)$，分别表示数据组数和模数。

接下来 $t$ 行，一行一个整数 $n (1 \leq n \leq 400)$。

outputFormat: 对于每组数据输出 $1 \sim n$ 的所有排列中**不是**“间隔排列”的排列总数对 $p$ 取模的值。


title: [NERC2018] JS Minification

background: 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) J 题。

description:
你有一个程序，其中每行包含 $0$ 个或多个可以用空格分隔的标记，你需要将其按下列方法“压行”。

- 在每一行中，如果存在 `#` 开头的部分，说明这是一个注释，其与其同一行后面的东西一起不被执行。

- 通过重复跳过空格并从当前解析位置开始查找可能最长的标识符，将每一行从左到右解析为标识符序列，从而将源代码转换为标识符序列。下面列出了所有可能的标识符：

> - 保留标识符：缩小过程中应保留的任何类型的运算符、分隔符、文字、保留字或库函数的名称。保留标记是不包含 `#` 的非空格 ASCII 字符的固定字符串。
> - 数字标识符：有数字组成的一连串数字字符串。
> - 单词标识符：由以下集合中的一系列字符组成：小写字母、大写字母、数字、`_`、`$` 且不以数字开头。

请注意，在压缩过程中，满足数字或单词定义，但出现在保留标记列表中的**最长字符序列**被视为保留标识符。

在压缩过程中，使用以下算法以系统的方式重命名单词：

- 定义 $s$ 为若干个由小写字母组成的字符串按长度为第一关键词，字典序为第二关键词进行排序后的序列。

- 将标识符序列中遇到的第一个单词重命名为目标单词列表中的第一个词，并将标识符顺序中出现的所有相同单词重命名成第一个词。然后将标识符序列中遇到的第二个新词重命名为目标单词列表中的第二单词，依此类推。

此外，你可以删除原本某些不必要的空格与换行符。但是注意，你删除后并不可以使原本不是标识符的某些字符串变成了标识符，或是原本是标识符的变成了不是标识符的。

inputFormat:
输入的第一行包含一个整数 $n \ (1 \leq n \leq 40)$，代表标识符的数量。

输入的第二行包含由空格分隔的保留标识符的列表，该列表中没有重复，长度不小于 $1$，不大于 $20$。

输入的第三行包含单个整数 $m \ (1 \leq m \leq 40)$，代表输入代码中的行数。

接下来 $m$ 行一行一串代码（可能包含前导空格）。

outputFormat: 输出一行，是对输入代码进行压缩处理的结果。输出解析后的与具有相应重命名后的标识符序列，并且应包含尽可能少的空格。如果有多种方法，那请输出空格最少且长度最小的。

samples:
16
fun while return var { } ( ) , ; > = + ++ - --
9
fun fib(num) { # compute fibs
  var return_value = 1, prev = 0, temp;
  while (num > 0) {
    temp = return_value; return_value = return_value + prev;
    prev = temp;
    num--;
  }
  return return_value;
}

samples: fun a(b){var c=1,d=0,e;while(b>0){e=c;c=c+d;d=e;b--;}return c;}

hint: 保证数据范围 $1 \leq n \leq 40$，$1 \leq m \leq 40$。


title: [NERC2018] King Kog’s Reception

background: 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) K 题。

description:
有些骑士想要拜访国王，但是由于这里的骑士都很遵守礼节，他们都会提前预约好他要来拜访的时刻和拜访将持续的时间。骑士按照接待处记录的时刻顺序依次拜访国王，每个骑士必须等前面的骑士结束拜访。

很不幸，公主也准备要来拜访国王，但善良的公主并不会为此而打乱骑士们拜访的顺序，而她会等待骑士们拜访完了再来拜访，请你计算公主要等多长时间。

inputFormat:
共 $q+1$ 行。

第一行一个整数 $q (1 \leq q \leq 3 \times 10^5)$。

然后 $q$ 行，先是一个字符。

- 如果字符是 `+`，紧跟在后面两个数字，表示骑士 $i$ 要于 $t (1 \leq t \leq 10^6)$ 时刻到达，拜访时间 $d(1 \leq d \leq 10^6)$ 时间单位。

- 如果字符是 `-`，后面一个数字 $i(1 \leq i \leq q)$，表示骑士 $i$ 暂时取消了他的预约。

- 如果字符是 `?`，后面一个数字 $t (1 \leq t \leq 10^6)$，表示公主将于 $t$ 时刻拜访。

outputFormat: 对于每个 `?`，输出一行，表示公主要等待多长时间。注意此处公主拜访时骑士的预约记录只有前面的几个，并不包含后面加进来的。

hint: 对于所有数据，保证 $1 \leq q \leq 3 \times 10^5$，$1 \leq t \leq 10^6$，$1 \leq d \leq 10^6$。


title: [NERC2018] Lazyland

background: 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) L 题。

description:
一个城市里有 $n$ 个人，和 $k$ 种职业，其中，每个人都有一个现在正在从事的职业 $a_i$，但是很遗憾，由于某些职业的空缺，使得这个城市根本无法继续正常生存下去。

你作为一城之主，自然不希望看到自己的城市这样子下去，你决定说服其中的某些人，使得每种职业都有人在做，对于每个人 $i$，你需要耗费 $b_i$ 的时间去说服。

你需要求出你去说服的时间的最小值。

inputFormat:
第一行两个整数 $n$ 和 $k (1 \leq k \leq n \leq 10^5)$，分别表示 $n$ 个人和 $k$ 种职业。

第二行 $n$ 个整数 $a_i (1 \leq a_i \leq k)$，表示第 $i$ 个人正在从事的职业 。

第三行 $n$ 个整数 $b_i (1 \leq b_i \leq 10^9)$，表示第 $i$ 个人被说服去做别的职业的时间。

outputFormat: 输出去说服市民的最小时间。

hint:
对于所有的数据，保证 $1 \leq k \leq n \leq 10^5$，$1 \leq a_i \leq k$，$1 \leq b_i \leq 10^9$。

对于样例一，分别令 $1$，$6$，$8$ 号市民去从事 $2$，$4$，$6$ 号职业。


title: [NERC2018] Minegraphed

background: 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) M 题。

description:
Marika 正在制作一款名为 Minegraphed 的游戏，游戏内容是你在一个三维的矩形立方体上移动。平行六面体游戏场地的每个单元格都是空单元格或障碍单元格。你总是在一个空建筑里面，要么在最底层，要么在一个障碍的顶部。对于每次移动，你可以选择东南西北中的一项进行移动，移动的规则如下：

- 你不能移动至矩形立方体外面。

- 如果你面前的单元格是空的，那么你可以向前移动一格，然后向底部落下，直到你到达最底层或者一个障碍。

- 如果你在非最顶层，你前面的单元格是一个障碍物，你上面的单元格和上面的单元格都是空的，然后你可以爬到该障碍物的顶部。

- 其余情况，你不能进行移动。

Marika 还有一个 $n \times n$ 的二维数组 $a$，你需要满足当 $a_{i,j} = 1$ 时，$i$ 能到达 $j$。

请构造一种合法方案。

inputFormat:
第一行一个整数 $n \ (1 \leq n \leq 9)$。

然后 $n$ 行，每行 $n$ 个数分别为 $a_{i,1},a_{1,2},\ldots,a_{i,n}$，$a_{i,j}$ 的含义见题目描述。

outputFormat:
输出第一行 $x,y,z$ 表示你的矩形立方体的长宽高，你需要保证 $x \times y \times z \leq 10^6$。

然后 $z$ 层（自上向下），每层一个 $x \times y$ 的矩形，如果 $map_{i,j}$ 为 `#`，表示它是障碍，如果为 `.`，表示是通路。否则若为数字，表示对应到 $n$ 的 $map_{i,j}$ 的数字。

保证存在解法。

hint:
样例解释：

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

对于所有数据保证 $1 \leq n \leq 9$，$a_{i,j} \in \{0, 1\}$。


title: [语言月赛 202307] 枚举结构

type: B

description:
D-- 是 2077 年的一种新兴语言。在 D-- 语言中，引入了一种「枚举结构」。具体的，这一种结构可以使用以下表达式表示：

```plaintext
X Y Z W
```

其中，$X, Z$ 为单个小写字母，代表变量名；$Y, W$ 为整数，代表枚举的起始值和终止值。其代表，将变量 $X$ 从 $Y$ 枚举到 $W$。

由于 D-- 追求极致的安全性，因此为了进行确认，**如果想要成功对 $X$ 变量进行枚举，那么 $Z$ 必须与 $X$ 相同**。

例如，一个合法的枚举结构表达式如下：

```plaintext
i 1 i 100
```

其代表，将 $i$ 变量从 $1$ 枚举到 $100$。

---

现在你收到了一个 D-- 枚举结构表达式 `X Y Z W`，请你判断和计算以下内容：

1. 表达式的合法性
	一个枚举结构表达式，只有满足以下全部条件，方可算作合法：

    - $X$ 与 $Z$ 均为小写字母。
    - $X$ 与 $Z$ 相同。
    - $Y$ 与 $W$ 均为整数。在给定的表达式中，我们保证这一条总是成立。

2. 如果合法，表达式将枚举的次数
	对于一个合法的枚举表达式，如果 $Y \le W$，其将会枚举 $W - Y + 1$ 次；否则，其将会枚举 $Y - W + 1$ 次。

inputFormat: 输入共一行一个表达式 `X Y Z W`，其中 $X,Z$ 为单个大小写字母或一位数字，$Y, W$ 为整数。

outputFormat:
输出共两行。

第一行为一个字符串。如果给定的表达式合法，输出 `valid`；否则输出 `Invalid`。
第二行为一个整数，如果给定的表达式不合法，输出 $-1$；否则输出表达式的枚举次数。

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

对于一个表达式 `X Y Z W`，对于 $100\%$ 的数据，$-2 \times 10 ^ 9 \leq Y, W \leq 2 \times 10 ^ 9$，$X, Z$ 均为单个小写字母或单个大写字母或一位数字。


title: [语言月赛 202307] 塔台超频

description:
在一条笔直的马路上有 $n$ 个塔台，它们被依次标号为 $1, 2, \cdots, n$，分别处于距离马路起点 $a _ 1, a _ 2, \cdots, a _ n$（$a _ 1 < a _ 2 < \cdots < a _ n$）的位置。

每个塔台初始时有一个通讯半径 $b _ 1, b _ 2, \cdots, b _ n$，这代表，对于 $i$ 号塔台，其可以与 $[a _ i - b _ i, a _ i + b _ i]$ 范围内的塔台通讯。

需要特别注意，对于两个塔台 A、B，当且仅当 A 塔台的**位置**处在 B 塔台的通讯范围内，B 塔台才能向 A 塔台传递信号。请注意这里不是「二者的通讯范围重合，即可通讯」。

现在你可以对这些塔台进行超频。具体的，你可以指定一个电压 $k$，之后**所有**塔台都会被加上 $k$ 的电压，通讯半径都会增大 $k$。这里的 $k$ 仅可为非负整数。

现在要求你通过超频，使信号可以从 $1$ 号塔台**依次**通过 $2, 3, \cdots$ 号塔台传输到 $n$ 号塔台，但是由于不合理的超频会较严重地磨损塔台，因此你想要尽可能降低超频的电压。

请你计算出，为了达到以上目的，塔台超频需要的最小电压是多少。

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

第一行为一个整数 $n$，代表塔台的数量。
接下来 $n$ 行，每行两个整数 $a _ i, b _ i$，分别代表各个塔台的位置和初始通讯半径。

outputFormat: 输出共一行一个整数，代表为了达到目的，塔台超频需要的最小电压。


title: [语言月赛 202307] 团伙首领

description:
某 E 正在机房值班，小朋友吵得她头晕脑胀，她将 $N$ 名吵闹的小朋友带出了机房，依次编号为 $1,2,\cdots,N$。

某 E 发现，这些小朋友形成了若干个小团伙，每个小朋友属于且只属于一个小团伙。她要求每一名小朋友指出自己所在小团伙的首领编号，第 $i$ 名小朋友指认的首领编号为 $S_i$。

假定所有小朋友都没有说谎，请问这 $N$ 名小朋友中一共形成了多少个小团伙？

inputFormat:
输入共两行。

输入的第一行为一个正整数 $N$。

输入的第二行为 $N$ 个正整数，第 $i$ 个为 $S_i$。

outputFormat: 输出一行一个整数，代表机房里小团体的数目。

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

- 对于 $30\%$ 的测试数据，每个小团体有且只有一个人。
 - 对于 $100\%$ 的测试数据，$N \le10^6$，$1 \leq S_i \leq N$。数据保证有解且合法，即每个小朋友都真实地指认了 ta 所在团伙的首领。


title: 「Cfz Round 1」Elevator

background: 电梯是一个可以让人充分思考的空间。

description:
给定两个长度为 $n$ 的数组 $a,b$。我们称序列 $p$ 是满足条件的，设 $p$ 的长度为 $m$，当且仅当：

- $p_1=1$；
- 对于所有的 $1\le i<m$，都有 $|p_i-p_{i+1}|=1$；
- 对于所有的 $1\le k\le n$，都存在一个有序数对 $(i,j)$，满足 $1 \le i < j \le m$ 且 $p_i=a_k$，$p_j=b_k$。

你需要输出所有满足条件的序列 $p$ 中，$p$ 的长度的最小值。

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

接下来 $n$ 行，第 $i$ 行两个整数 $a_i,b_i$。

outputFormat: 一个整数，表示所有满足条件的序列 $p$ 中，$p$ 的长度的最小值。


title: [入门赛 #14] 塔台超频 (Hard Version)

description:
在一条笔直的马路上有 $n$ 个塔台，它们被依次标号为 $1, 2, \cdots, n$，分别处于距离马路起点 $a _ 1, a _ 2, \cdots, a _ n$（$a _ 1 < a _ 2 < \cdots < a _ n$）的位置。

每个塔台初始时有一个通讯半径 $b _ 1, b _ 2, \cdots, b _ n$，这代表，对于 $i$ 号塔台，其可以与 $[a _ i - b _ i, a _ i + b _ i]$ 范围内的塔台通讯。

需要特别注意，对于两个塔台 A、B，当且仅当 A 塔台的**位置**处在 B 塔台的通讯范围内，B 塔台才能向 A 塔台传递信号。请注意这里不是「二者的通讯范围重合，即可通讯」。

现在你可以对这些塔台进行超频。具体的，你可以指定一个电压 $k$，之后**所有**塔台都会被加上 $k$ 的电压，通讯半径都会增大 $k$。这里的 $k$ 仅可为非负整数。

现在要求你通过超频，使信号可以从 $1$ 号塔台传输到 $n$ 号塔台，路径不限（即，无论如何，只需要让信号从 $1$ 号塔台到达 $n$ 号塔台即可）。但是由于不合理的超频会较严重地磨损塔台，因此你想要尽可能降低超频的电压。

请你计算出，为了达到以上目的，塔台超频需要的最小电压是多少。

outputFormat: 输出共一行一个整数，代表为了达到目的，塔台超频需要的最小电压。

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

对于 $100\%$ 的数据，保证 $2 \leq n \leq 5 \times 10 ^ 5$，$0 \leq a _ i, b _ i \leq 10 ^ 9$。


title: [语言月赛 202307] 扶苏和串

background: 众所周知，每个月入门赛的字符串题都是扶苏来枚举 idea 出出来的。

description:
给定一个 01 字符串 $s$，你可以任选 $s$ 的一个非空子串，把这个子串在 $s$ 中**翻转**一次。

问你能得到字典序最小的字符串是什么？

形式化的，你可以选择一个区间 $[l, r]$ 满足 $1 \leq l \leq r \leq |s|$，构造一个串 $t$ 满足：

$$t_i = \begin{cases}s_i, &i < l \text{ 或 } i > r \\ s_{r - (i - l)}, & l \leq i \leq r\end{cases}$$

这里字符串的下标从 $1$ 开始。

最小化字符串 $t$ 的字典序。

inputFormat: 输入只有一行一个字符串，表示 $s$。

outputFormat: 输出一行一个字符串，表示得到的字典序最小的字符串。

hint:
### 样例 1 解释

$s = \texttt{\underline{10}1}$，翻转下划线标出的子串，得到 $t = \texttt{011}$

### 样例 2 解释

$s = \texttt{00\underline{10100}}$，翻转下划线标出的子串，得到 $\texttt{0000101}$。

### 数据规模与约定

下面用 $|s|$ 表示输入字符串的长度。

- 对 $20\%$ 的数据，$|s| \leq 2$。
- 对 $40\%$ 的数据，$|s| \leq 8$。
- 另有 $10\%$ 的数据，$s$ 只含字符 $\texttt 1$。
- 另有 $10\%$ 的数据，$s$ 只含字符 $\texttt 0$。
- 对 $100\%$ 的数据，$1 \leq |s| \leq 100$。$s$ 只含字符 $\texttt{0,1}$。


title: [入门赛 #14] 魔法少女扶苏 (Hard Version)

description:
给定一个 $n$ 行 $m$ 列的数字矩阵，第 $i$ 行第 $j$ 列的数称为 $a_{i,j}$。

扶苏可以释放任意多次魔法，每次施放魔法，矩阵里的**每个**数字都会被减去 $1$。

现在扶苏想知道，她至少需要释放几次魔法，才能让矩阵中存在至少 $k$ 个位置 $(x, y)$，满足 $a_{x, y}$ 大于或等于它所在行和列的元素之和。

形式化地，你需要计算最小的魔法释放次数使得施放魔法后存在至少 $k$ 个位置 $(x, y)$，满足 $a_{x, y} \geq \sum \limits _{i = 1}^n a_{i,y} + \sum \limits _{i = 1}^m a_{x,i}$。

inputFormat:
第一行是三个整数，表示矩阵的行数 $n$，列数 $m$ 和要求符合条件的位置个数 $k$。

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行的第 $j$ 个整数表示初始的 $a_{i,j}$。

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

hint:
### 样例 1 解释

释放 $3$ 次魔法后，矩阵变为

$$\begin{matrix}-2 & -1 & 0\\1& 2&3\\\end{matrix}$$

于是 $a_{1,1} = -2 > (-1) + (-3) = \sum\limits_{i =1}^n a_{i,1} + \sum\limits_{i = 1}^m a_{1, i}$。

### 数据规模与约定

- 对 $100\%$ 的数据，保证 $1 \leq n, m \leq 3 \times 10^3$，$1 \leq k \leq n \times m$，$0 \leq a_i \leq 10^{11}$。

### 提示

**请使用合理的读入方式，避免超时。**


title: [入门赛 #14] Three-View Projection (Hard Version)

description:
> 全文与 $x, y, z$ 轴/方向有关的内容均基于以下的 $x, y, z$ 轴、位置及观测方向。观测者站在如图所示的位置，正在向着 $y$ 轴（绿线）正方向（箭头方向）观测。
> ![](https://cdn.luogu.com.cn/upload/image_hosting/05erek0j.png)

现在有一个长、宽、高（沿 $x, y, z$ 轴延展的长度）为 $n \text{ cm}, m \text{ cm}, k \text{ cm}$ 的长方体区域。我们将这片区域划分为 $n \times m \times k$ 个小格子。每个小格子中可以放置一个边长为 $1 \text{ cm}$ 的小正方体。

我们使用一个整数三元组 $(x, y, z)$ 来表示一个格子在空间中的位置，其代表从左往右数第 $x$ 个，从前往后数第 $y$ 个，从下往上第 $z$ 个格子。

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

例如，上图展示的 $3 \times 3 \times 3$ 区域中，按照观测者的位置，可以发现红蓝线（$x, z$ 轴）所在的面为前面，蓝绿线（$y, z$ 轴）所在的面为左面，红绿线（$x, y$ 轴）所在的面为下面，五个小正方体的位置分别为 $(1, 1, 1), (1, 1, 2), (2, 3, 2), (3, 3, 2), (2, 2, 3)$。

三视图是观测者从上面（从上往下）、左面（从左往右）、正面（从前往后）三个不同角度观察同一个空间几何体而画出的图形。

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

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

例如，以上是示例区域的三视图。

现在，给定一个区域及其中的正方体排布情况，请你帮助计算出这个区域的三视图。

inputFormat:
输入共 $n \times k + 1$ 行。

第一行为三个整数 $n, m, k$，代表长方形区域的长、宽、高。
接下来 $n \times k$ 行，每行 $m$ 个整数。其中，将其每 $n$ 行分为一组，第 $x$ 组第 $y$ 行（即第 $(x - 1) \times n + y$ 行）第 $z$ 列的整数 $a _ {x, y, z}$ 代表 $(y, z, x)$ 处格子的情况，若 $a _ {x, y, z} = 1$，代表该格子有小正方体；否则，代表该格子没有小正方体。

outputFormat:
输出共 $2k + m$ 行。

前 $k$ 行，每行 $n$ 个整数，代表**自上而下自左至右**正视图的情况。如果正视图中某个位置有填充，则输出 $1$，否则输出 $0$。同一行整数之间两两以一个空格隔开。
接下来 $k$ 行，每行 $m$ 个整数，代表**自上而下自后至前**左视图的情况。如果左视图中某个位置有填充，则输出 $1$，否则输出 $0$。同一行整数之间两两以一个空格隔开。
接下来 $m$ 行，每行 $n$ 个整数，代表**自后至前自左至右**俯视图的情况。如果俯视图中某个位置有填充，则输出 $1$，否则输出 $0$。同一行整数之间两两以一个空格隔开。

**以上方向均基于观测者初始站立位置及方向。如果对输出的顺序有疑惑，请参照样例辅助理解。**

hint:
### 样例 1 解释

样例 1 即为题目中的示例。

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

### 数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq n, m, k \leq 200$，$0 \leq a _ {x, y, z} \leq 1$。


title: 「CROI · R1」浣熊的溪石

background:
>回首往昔，碧空如洗，日暖风恬。\
溪石深浅有致地错落在明澈似玉的梦枫溪里。\
浣熊们水上跑酷的无限趣忆亦于此伊始……

description:
日升月落，春去秋来，梦枫溪石的高度千变万化。
爱思考的小浣熊 CleverRaccoon 想探寻这些溪石究竟能构成多少种不同的高度序列。

现有若干个长度为 $n$ 的非负整数列 $a$。

当 $n>1$ 时，$a_1,a_n$ 的取值为 $0\sim m$，其它数 $a_i$ 的取值为 $0\sim m-1$，其中 $2\leq i \leq n-1$。

当 $n=1$ 时，$a_1$ 的取值为 $0\sim m+1$。

**定义**：当且仅当 $\forall i\in\{1,2,\dots ,n\},a_i=b_i$ 或 $\forall i\in\{1,2,\dots ,n\},a_i=b_{n-i+1}$ 时，数列 $a,b$ 相同。

现给定 $n,m$，请求出最多有多少个**不同**的数列，答案对 $998244353$ 取模。

inputFormat:
**本题包含多组测试数据。**

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

接下来 $T$ 行，每行输入以空格间隔的 $2$ 个正整数 $n,m$，意义见题目描述。

outputFormat: 共 $T$ 行，对于每组数据，一行输出一个正整数，表示答案对 $998244353$ 取模的结果。


title: [入门赛 #14] 扶苏和串 (Hard Version)

background: 众所周知，每个月入门赛的字符串题都是扶苏来枚举 idea 出出来的。

description:
给定一个 01 字符串 $s$，你可以任选 $s$ 的一个非空子串，把这个子串在 $s$ 中**翻转**一次。

问你能得到字典序最小的字符串是什么？

形式化的，你可以选择一个区间 $[l, r]$ 满足 $1 \leq l \leq r \leq |s|$，构造一个串 $t$ 满足：

$$t_i = \begin{cases}s_i, &i < l \text{ 或 } i > r \\ s_{r - (i - l)}, & l \leq i \leq r\end{cases}$$

最小化字符串 $t$ 的字典序。

inputFormat: 输入只有一行一个字符串，表示 $s$。

outputFormat: 输出一行一个字符串，表示得到的字典序最小的字符串。

hint:
### 样例 1 解释

$s = \texttt{\underline{10}1}$，翻转下划线标出的子串，得到 $t = \texttt{011}$

### 样例 2 解释

$s = \texttt{00\underline{10100}}$，翻转下划线标出的子串，得到 $\texttt{0000101}$。

### 数据规模与约定

下面用 $|s|$ 表示输入字符串的长度。

- 对 $100\%$ 的数据，$1 \leq |s| \leq 3000$。$s$ 只含字符 $\texttt{0,1}$。


title: [语言月赛 202307] 魔法少女扶苏

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


title: [语言月赛 202307] std::string

background:
这是一道 **hack 题**。在本题目中，你将得到两个问题和两个解决对应问题的代码，但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括：

1. 输出错误的结果。
2. 运行超时。
3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。

对于这一问题，你需要提交一份符合要求的输入数据，使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能，也可以提交一份以任何语言写成的数据生成器。

---
**提示：如果你使用提交答案功能，请在提交其他题目时记得将语言改回你所使用的语言。**

description:
以下给出两个问题的题目描述：

#### 问题 1

输入 $n$，输出连续 $n$ 个 $\texttt{HelloLuogu}$ 组成的字符串。

#### 问题 2

给定一个数列 $a$，请你将这个数列划分成**尽可能多**的段，使得每段的按位与之和最小。

请你输出最多划分段的数量。

inputFormat:
#### 问题 1

输入只有一行一个整数 $n$。

#### 问题 2

第一行是一个整数 $n$。
第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

outputFormat:
#### 问题 1

输出一行一个字符串表示答案。

#### 问题 2

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

hint:
### 样例组与实际输入的说明

两个样例分别对应两个问题的样例输入输出。

如果你直接采用『提交答案』的方式，请分别将两个输入数据命名为 `1.in`、`2.in`，并打成 zip 压缩包进行提交；

如果你采用提交数据生成器的方式，你的生成器可以从标准输入读入一个整数 $x$，满足 $1 \leq x \leq 2$，表示该测试点对应的问题编号，然后**输出对应的输入数据**。

显然，你的程序不应该读入『输入格式』里提到的任何内容（而应该构造它们），也不应该输出『样例输出』里提到的任何内容（而是只输出你构造的输入数据）。你不应该使用样例测试你的程序，这只是对两个问题的样例说明。

### 样例 2 解释

划分成 $[2,3,1]$ 和 $[5,2]$ 两个段。两段的按位与都是 $0$，其和也是 $0$，可以证明这是和的最小值。

### 数据规模要求

你给出的数据必须满足如下要求：

1. 完全符合『输入格式』的规定，不能有多余的输入，但是可以有文末回车，问题 $1$ 可以有行末空格。
2. 对于问题 $1$，$1 \leq n \leq 10^5$。
3. 对于问题 $2$，$1 \leq n \leq 2 \times 10^5$，$0 \leq a_i \leq 10^9$。

### 目标代码

你需要 hack 如下的代码：

#### 问题 1

```cpp
#include <iostream>
using namespace std;

int main() {
  int n;
  string ans, base = "HelloLuogu";
  cin >> n;
  while (n--) ans = ans + base;
  cout << ans << endl;
}
```

#### 问题 2

```cpp
#include <vector>
#include <iostream>
#include <algorithm>

int T;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin >> n;
  std::vector<int> a(n + 1), pre(n + 2), post(n + 2);
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  pre[1] = a[1];
  for (int i = 2; i <= n; ++i) pre[i] = pre[i - 1] & a[i];
  post[n] = a[n];
  for (int i = n - 1; i; --i) post[i] = post[i + 1] & a[i];
  int ans = 1;
  for (int i = 1; i < n; ++i) if (pre[i] + post[i + 1] == pre[n]) {
    ++ans;
  }
  std::cout << ans << '\n';
}
```

目标代码的编译选项为 `-std=c++14 -fno-asm -O2`。编译器为洛谷提供的 g++。你可以在『在线 IDE』中选择 C++14 语言来获得完全相同的编译环境。

#### 数据判定

你给出的数据必须完全符合『数据规模要求』，否则将得到 Unaccepted 的结果。

#### 超时判定

程序每执行若干条指令，我们会检测一遍程序的运行时间。我们保证两次检测之间的指令条数是一个输入规模无关的量，也即每执行 $O(1)$ 条指令会进行一次检测。且两次检测之间的指令条数不会太多，一般不超过 $100$ 条 C++ 语句。

如果程序的运行时间超过 $500 \text{ms}$，则判定为程序运行超时，返回 accepted 结果。

#### 结果错误判定

如果程序在规定的时间内结束且给出了一个输出，我们会比较这个输出和**完全正确的输出**，如果二者不同，则判定为 hack 成功，返回 accepted 结果。

#### 未定义行为判定

我们会在每次**显式**的调用数组元素前判断数组下标是否超过数组范围，如果超过，则判定为 hack 成功，返回 accepted 结果。

这就是说，如果你希望通过未定义行为进行 hack，只能对显式的调用数组元素的行为进行 hack。

### 样例程序

这是一份可以帮你理解你需要输出的内容的样例程序，**但它不能给出正确的 hack 数据**。直接提交此程序不会得分。

```cpp
#include <iostream>

using namespace std;

int main() {
  int taskId;
  cin >> taskId;
  if (taskId == 1) {
    cout << "" <<endl;
  } else if (taskId == 2) {
    cout << "" << endl;
  } else { // 这个 else 不会被执行
    cout << "Stupid Fusu!" << endl;
  }
}
```

如果你使用『提交答案』功能，请务必保证打开压缩包后能且仅能**直接**看到两个 `.in` 文件。这就是说，文件结构必须是：

```plain
ans.zip
 |---1.in
 |---2.in
```

两个文件不应该被额外的文件夹包含，即文件结构不能是：

```plain
ans.zip
 |---ans(folder)
      |---1.in
      |---2.in
```

### 关于评测信息的说明

如果 hack 成功，对应测试点的信息为 accepted。如果返回其他信息，说明程序本身有误。

例如，如果返回 TLE，不代表成功的将对应程序 hack 至超时，而是表示数据生成器本身运行超时，测试点不得分。

特别的，返回 UKE 结果可能是数据不合法（有多余内容、缺少内容或数据范围不符合要求）。


title: [语言月赛 202307] 署前街少年

background:
> 时光无法缝补那块破碎的黑板
> 虚荣的少年与署前街越来越远
> ——赵雷，《署前街少年》

description:
某 E 得到了一个长度为 $2N$ 的数列 $a_1, a_2, a_3, \dots a_{2N}$，数列的第 $i$ 个数为 $a_i$。

奇变偶不变，符号看象限。这是三角函数诱导公式的重要口诀。某 E 同样想对数列实施这样的变换，具体来说：

 - 对于 $a_i$，若 $i \bmod 2=0$，则称 $a_i$ 为偶位数；若 $i \bmod 2 = 1$，则称 $a_i$ 为奇位数。
 - 对于 $a_i$，记 $i \bmod k = p$，则称 $a_i$ 为第 $p$ 象限数，其中 $k$ 为给定的参数。

奇变偶不变，符号看象限。某 E 将遵循以下的规则对数列进行变换：

- 若 $a_i$ 为偶位数，则 $a_i$ 不变。
- 若 $a_i$ 为奇位数，设 $a_i$ 为第 $p$ 象限数，则 $a_i$ 变为所有第 $p$ 象限数的和对 $i$ 取模的值。

请注意以上变换不会影响「所有第 $p$ 象限数的和」这一数值。

某 E 想知道，变换后的数列是什么样的。

inputFormat:
输入共两行。

输入的第一行为两个整数 $N,k$。

输入的第二行为 $2N$ 个整数，第 $i$ 个代表 $a_i$。

outputFormat: 输出一行 $2N$ 个整数，第 $i$ 个代表变换后的 $a_i$。


title: [语言月赛 202307] Three-View Projection

description:
> 全文与 $x, y, z$ 轴/方向有关的内容均基于以下的 $x, y, z$ 轴、位置及观测方向。观测者站在如图所示的位置，正在向着 $y$ 轴（绿线）正方向（箭头方向）观测。
> ![](https://cdn.luogu.com.cn/upload/image_hosting/05erek0j.png)

现在在地面上有一个长、宽（沿 $x, y$ 轴延展的长度）为 $n \text{ cm}, m \text{ cm}$ 的长方形区域。我们将这片区域划分为 $n \times m$ 个小格子。每个小格子中可以放置一个边长为 $1 \text{ cm}$ 的小正方体。

我们使用一个整数二元组 $(x, y)$ 来表示一个格子在空间中的位置，其代表从左往右数第 $x$ 个，从前往后数第 $y$ 个格子。

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

例如，上图展示的 $3 \times 4$ 区域中，按照观测者的位置，可以发现红蓝线（$x, z$ 轴）所在的面为前面，蓝绿线（$y, z$ 轴）所在的面为左面，红绿线（$x, y$ 轴）所在的面为下面。五个小正方体的位置分别为 $(1, 1), (1, 3), (3, 1), (3, 3), (3, 4)$。

三视图是观测者从上面（从上往下）、左面（从左往右）、正面（从前往后）三个不同角度观察同一个空间几何体而画出的图形。

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

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

例如，以上是示例区域的三视图。

现在，给定一个区域及其中的正方体排布情况，请你帮助计算出这个区域的三视图。

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

第一行为两个整数 $n, m$，代表长方形区域的长、宽。
接下来 $n$ 行，每行 $m$ 个整数。其中第 $x$ 行第 $y$ 列的整数 $a _ {x, y}$ 代表 $(x, y)$ 处格子的情况，若 $a _ {x, y} = 1$，代表该格子有小正方体；否则，代表该格子没有小正方体。

outputFormat:
输出共 $2 + m$ 行。

第一行为 $n$ 个整数，代表**自左至右**正视图的情况。如果正视图中某个位置有填充，则输出 $1$，否则输出 $0$。同一行整数之间两两以一个空格隔开。
第二行为 $m$ 个整数，代表**自后至前**左视图的情况。如果左视图中某个位置有填充，则输出 $1$，否则输出 $0$。同一行整数之间两两以一个空格隔开。
接下来 $m$ 行，每行 $n$ 个整数，代表**自后至前自左至右**俯视图的情况。如果俯视图中某个位置有填充，则输出 $1$，否则输出 $0$。同一行整数之间两两以一个空格隔开。

**以上方向均基于观测者初始站立位置及方向。如果对输出的顺序有疑惑，请参照样例辅助理解。**


title: Electro Master

background: I might be wrong.

description:
考虑一个由四种微观粒子构成的系统：正负 A 子 $\text{a}^+,\text{a}^-$，正负 B 子 $\text{b}^+,\text{b}^-$。

一开始，一条直线上放置了 $n$ 个 A 子；然后以某种方式给粒子以初速度，使得带正电荷的粒子向左，反之则向右运动。我们忽略粒子之间的相互作用，认为粒子在加速后速率一定，且均沿直线运动。

当两个粒子相撞时，粒子会反弹，沿着相反的方向继续运动。同时满足如下的变换规律：

- 若两种粒子的电荷相同，则无事发生；
- 若两种粒子的电荷不同，则改变成另一种同电荷的粒子。

例如：$\text{a}^-$ 和 $\text{b}^+$ 相撞后，$\text{a}^-$ 会变成 $\text{b}^-$，$\text{b}^+$ 会变成 $\text{a}^+$，并各自沿着相反的方向运动。

定义一种摆放方式的权值为，经过足够长的时间后，在左侧收集到的 B 子个数。

现在已经确定了一些 A 子的正负性，剩下的 A 子可能带正电，也有可能带负电。请求出对于所有可能方案的权值之和。

你需要将答案对 $998\,244\,353$ 取模。

inputFormat:
输入一行一个长为 $n$ 的字符串 $s$，代表从左到右的 A 子的正负性。具体而言：

- 若 $s_i$ 为 `+`，则第 $i$ 个 A 子带正电；
- 若 $s_i$ 为 `-`，则第 $i$ 个 A 子带负电；
- 若 $s_i$ 为 `?`，则第 $i$ 个 A 子可能带正电，也可能带负电。

outputFormat: 输出一行一个数，代表答案对 $998\,244\,353$ 取模后的结果。


title: 序列合并

description:
给定一个长度为 $n$ 的非负整数序列 $\{a_n\}$，你可以进行 $k$ 次操作，每次操作你选择两个相邻的数，把它们合并成它们的按位或。

形式化地，一次操作中，你选择一个下标 $i$（$1 \le i < n$），然后把原序列变成 $\{a_1,a_2,\cdots,a_i \operatorname{or} a_{i+1},a_{i+2},\cdots,a_n\}$。

求 $k$ 次操作后所有数按位与的最大值。

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

第二行包含 $n$ 个非负整数，其中第 $i$ 个非负整数为 $a_i$。

outputFormat: 输出一行，包含一个正整数，代表答案。

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

一种合法的方案：

- 第一次操作，选择第一个数和第二个数合并，序列变为 $\{3,2,3,1\}$。
- 第二次操作，选择第三个数和第四个数合并，序列变为 $\{3,2,3\}$。

最终所有数的按位与为 $2$。可以证明不存在更优的方案。

**【数据范围】**

- 对于 $25\%$ 的数据，$n \le 20$。
- 对于另外 $25\%$ 的数据，$k=n-2$。

对于所有数据，保证 $1 \le k<n \le 2 \times 10^5$，$0 \le a_i < 2^{30}$。


title: 『MGOI』Simple Round I | A. 魔法数字

background: > 目标越坚定的魔法士，越幸运。——殿堂魔法士 S

description:
初级魔法士小 M 的魔法数字是 $2$。

给定一个正整数 $n$，小 M 需要找到最大的 **偶数** $m$，使得 $2^m<n$。

请你帮帮他。

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

outputFormat: 一行一个 **偶数** $m$，表示答案。


title: 「TFOI R1」Tree Home

background:
阳光开朗大男孩天才 Z 今天要向蕉太狼表白力！

众所周知，蕉太狼是一个很可爱的女孩纸。
从前的天才 Z 总是担心因为自己表白失败而受到别人的嘲笑。但是今天，天才 Z 就要做出自己一生中最重要的一件事，那就是真诚地表白，无论后果如何。

出乎意料，蕉太狼其实也喜欢着天才 Z！

天才 Z 开心得像个 0#。

但是没过多久，天才 Z 就被甩力，原因蕉太狼发现天才 Z 对自己的闺蜜有非分之想。

天才 Z 拿出了自己的树状家谱，问候起了自己的祖宗们。

description:
有一个由 $n - 1$ 条**带权无向边**连接成的有 $n$ 个节点的树，每个节点都有它对应的**编号**以及**权值** $v_{i}$，整棵树的根节点为编号为 $1$ 的节点。

令 $f(a, b, c) = (a - b) \times \left[a^2 + b^2 + a \times b + 3 \times c \times (a + b + c)\right]$，其中 $a,b,c$ 可以为任意整数。同时用 $d_i$ 表示 $i$ 到根节点的每条边的**边权**之和。

现在天才 Z 要进行 $T$ 次询问，每次询问给定四个正整数 $l_{1},r_{1},l_{2},r_{2}$，你要从**编号**在区间 $[l_{1}, r_{1}]$ 和 $[l_{2}, r_{2}]$ 的点中各选择一个点 $p$ 和 $q$，当然你选择的两个点需要保证 $p \neq q$。用 $r$ 表示 $p$ 和 $q$ 的最近公共祖先，要使得 $|f(d_{p} - d_{r}, d_{q} - d_{r}, d_{r})| + |v_{p} - v_{q}|$ 的值最大，而你需要对每次询问输出这个最大值。

inputFormat:
第一行输入两个正整数 $n$ 和 $T$，表示这棵树的节点个数以及询问次数。

第二行输入 $n$ 个整数，第 $i$ 个数表示编号为 $i$ 的节点的权值。

接下来 $n - 1$ 行，每行输入三个整数 $u,v,w$，表示节点 $u$ 到节点 $v$ 之间有一条边权为 $w$ 的无向边。

接下来 $T$ 行，每行输入四个整数 $l_{1},r_{1},l_{2},r_{2}$，表示一次询问（意义如题面所述）。

outputFormat: 输出 $T$ 行，每行输出一个整数，表示每次询问的答案。

hint:
#### 样例解释

对于第一次询问，我们在两个区间分别取 $4$ 号点和 $6$ 号点即可得出答案 $19211$。

对于第二次询问，两个区间都只能取一个节点，所以答案为 $3$。

#### 数据范围

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

- Subtask 1（5 points）：$1 \leqslant n, T \leqslant 10$。
- Subtask 2（10 points）：$1 \leqslant n, T \leqslant 100$。
- Subtask 3（30 points）：$1 \leqslant n, T \leqslant 3000$。
- Subtask 4（55 points）：无特殊限制。

对于所有数据，$1 \leqslant n, T \leqslant 2 \times 10^5$，$0 \leqslant |w| \leqslant 25$，$1 \leqslant v_{x} \leqslant 10^9$，$1 \leqslant l_{1} \leqslant r_{1} \leqslant n$，$1 \leqslant l_{2} \leqslant r_{2} \leqslant n$，保证树中最大深度不超过 $100$。

**注意：两个区间 $[l_{1}, r_{1}]$ 和 $[l_{2}, r_{2}]$ 可能有重合部分。**


title: [语言月赛 202308] 小粉兔喜欢下象棋吗

description:
在中国象棋中，马走日字形。用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的格点，不考虑别马腿，考虑跳出棋盘外，在 $(i,j)$ 的马可以跳到 $(i-2,j+1)$，$(i-2,j-1)$，$(i-1,j+2)$，$(i-1,j-2)$，$(i+1,j+2)$，$(i+1,j-2)$，$(i+2,j+1)$，$(i+2,j-1)$ 八个位置。

将军抽车是中国象棋中常用的进攻策略。如下图所示，此时红帅在 $(1,5)$，红车在 $(2,8)$。若黑马跳到红框位置所指的 $(3,6)$，帅将由于被将军被迫移动，此时，马就可以吃掉红车。

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

本题将解决将军抽车的简化版问题。在本题中，将军抽车就是要通过一步跳马，在能够将军的同时将车置于马的攻击位置。

只考虑棋盘上有红帅、红车、黑马各一枚的情况，**不考虑帅是否可以通过移动实现对车的保护，不考虑别马腿**，在当前局面，轮到黑棋移动时，黑马是否可以通过一步移动，在不出界的情况下，实现将军抽车？

inputFormat:
输入共三行。

输入的第一行为两个整数 $S_x,S_y$，表示红帅的位置为 $(S_x,S_y)$。

输入的第二行为两个整数 $C_x,C_y$，表示红车的位置为 $(C_x,C_y)$。

输入的第三行为两个整数 $M_x,M_y$，表示黑马的位置为 $(M_x,M_y)$。

保证红帅在 $1 \sim 3$ 行的九宫格内。

outputFormat:
输出一行一个字符串：

- 若可以实现将军抽车，输出 `Yes`。
- 若不可以实现将军抽车，输出 `No`。

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

对于 $100\%$ 的测试数据，$1 \le S_x \le 3$，$4 \le S_y \le 6$，$1 \le C_x,M_x \le 10$，$1 \le C_y,M_y \le 9$。保证没有任意两枚棋子初始时处于同一位置。


title: 「MYOI-R3」签到

background:
Updated on 2024/5/12：新增两组 hack 数据，位于 Subtask #5 的 #31 和 #32。

Updated on 2024/5/13：由于争议过大，目前难度已降绿。暂时不考虑再次变动本题难度。

description:
这一场比赛为了选手顺利完成签到题，设置有 $n$ 个签到处，你和它们都在一条笔直的公路上，我们不妨把这条笔直的公路看作成一条数轴，你现在在数轴原点的位置上（即坐标为 $0$），第 $i$ 个签到处在坐标为 $x_i$ 的地方，你在每个时间单位内**最多**可以移动 $1$ 个单位长度。

你需要去**尽量多**的签到处签到，然后在 $m$ 个时间单位内回到数轴原点。签到的时间可以**忽略不计**，而且你可能在同一地点瞬间完成**位于同一位置的多个不同签到处**的签到。

出题人为了让各位选手们更方便、更顺利地签到，还在场上第 $p$ 个签到处放置了签到礼物。如果选手在这里**签过到**，那么回到原点的时间限制可以被**推迟到** $m+5$ 个单位时间。注：你可以在第 $m$ 个时刻后才获得礼物，但你必须在 $m+5$ 个单位时间前回到原点。

求选手**最多**可以在多少个不同的签到处签到，并在此前提下**最小化**签过到的签到处的编号的集合的字典序（如果有多解，输出任意一个方案即可）。

注：集合的字典序等价于把集合内的元素从小到大排序之后的序列的字典序。

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

第二行，一共 $n$ 个整数，第 $i$ 个整数表示 $x_i$。

outputFormat:
第一行，一个整数 $ans$，表示你最多能去签到的签到处的数量。

第二行，输出 $ans$ 个正整数，表示**依次要去签到**的签到处的编号。

**本题采用 Special Judge，如果有多解，输出任意一个即可。**


title: [EGOI2023] Inflation / 通货膨胀

background:
Day 1 Problem A.

题面译自 [EGOI2023 inflation](https://egoi23.se/assets/tasks/day1/inflation.pdf)。

description:
众所周知，瑞典南部的人们经常吃沙拉三明治。沙拉三明治的价格波动很大，分析经济情况的最好方法是每天去同一家沙拉三明治店，把菜单上所有价格都加起来。

一家沙拉三明治店的菜单上有 $N$ 个不同的菜品。第 $i$ 个菜品有价格 $p_i$。

每天，下列事件之一发生：

- `INFLATION x`：所有价格增加 $x$。
- `SET x y`：每个价格为 $x$ 的菜品的价格更改为 $y$。

你的任务是处理 $Q$ 天，在每天结束后输出所有菜品的总价格。

inputFormat:
第一行一个整数 $N$，表示菜品数量。

第二行 $N$ 个整数 $p_1,p_2,\cdots,p_N$。

第三行一个整数 $Q$，表示天数。

接下来 $Q$ 行，每行一个字符串 $s$ 和一至两个整数。

如果 $s$ 是 `INFLATION`，接下来一个整数 $x$。表示当天所有价格增加 $x$。

如果 $s$ 是 `SET`，接下来两个整数 $x,y$。表示每个价格为 $x$ 的菜品的价格更改为 $y$。

outputFormat: 输出 $Q$ 行，每天结束后所有菜品的总价格。

samples:
5
2 1 1 2 5
6
INFLATION 1
SET 3 2
SET 5 2
INFLATION 4
SET 6 1
SET 10 1

samples:
3
1 4 1
5
SET 1 1
SET 3 4
INFLATION 2
SET 3 1
SET 6 4

hint:
**样例 $1$ 解释**

下图为样例 $1$ 的前两天。注意到第一天结束后价格总和为 $16$，所以输出的第一个整数为 $16$。

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

---

**数据范围**

对于全部数据，$1\le N\le 3\times 10^5$，$1\le p_i\le 10^6$，$1\le Q\le 10^5$，$1\le x,y\le 10^6$。

- 子任务一（$14$ 分）：$N=1$。
- 子任务二（$28$ 分）：$N,Q,p_i,x,y\le 100$，依赖于子任务一。
- 子任务三（$19$ 分）：只有 `INFLATION` 事件。
- 子任务四（$23$ 分）：只有 `SET` 事件。
- 子任务五（$16$ 分）：无特殊限制，依赖于子任务二、三、四。

---

**提示**

答案可能不在 $32$ 位整型范围内，如果你使用 C++ 语言，请注意溢出的可能。


title: [EGOI2023] Padel Prize Pursuit / 追梦笼式网球

background:
Day 1 Problem B.

题面译自 [EGOI2023 ppp](https://egoi23.se/assets/tasks/day1/ppp.pdf)。

description:
有 $N$ 个编号为 $0$ 到 $N-1$ 的选手参加一场 $M$ 天的笼式网球锦标赛。每天恰好进行一次比赛。在锦标赛中共颁发 $M$ 块奖牌，每场比赛颁发一块新奖牌。在第 $i$ 天的比赛中（$0\le i\le M-1$），两名编号分别为 $x_i$ 和 $y_i$ 的选手参加。比赛中发生如下事件：

- 选手 $x_i$ 打败选手 $y_i$。
- 一个新的奖牌授予给获胜者 $x_i$。
- 失败者所有现有的奖牌都授予给获胜者。

在第 $M$ 天（最后一场比赛结束后一天）举行颁奖典礼。在颁奖典礼上，所有奖牌被收集起来，并授予给持有该奖牌时间最长的选手。具体地，在第 $M$ 天，奖牌 $i$ 授予给持有奖牌 $i$ 最多个晚上的选手（不必须连续持有）。如果两个或更多选手持有一个奖牌同样多晚上，奖牌授予给其中编号最小的选手。

你的任务是求出颁奖典礼中，每位选手被授予多少奖牌。

inputFormat:
第一行两个整数 $N,M$，表示选手数和比赛数。

接下来 $M$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 天的比赛中，选手 $x_i$ 打败选手 $y_i$。

outputFormat: 一行 $N$ 个整数，第 $k$ 个整数表示颁奖典礼中，第 $k$ 位选手被授予的奖牌数。

hint:
**样例 $1$ 解释**

下图展示了样例 $1$ 中锦标赛期间奖牌的归属。当选手 $1$ 在第三天被打败时，她的所有奖牌都被授予给选手 $2$。

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

---

**样例 $2$ 解释**

如下图。

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

在颁奖典礼中，选手 $0$ 被授予奖牌 $5$ 和 $6$，选手 $1$ 被授予奖牌 $3$ 和 $4$，选手 $2$ 被授予奖牌 $0,1,2$。

---

**数据范围**

对于全部数据，$2\le N\le 2\times 10^5$，$1\le M\le 2\times 10^5$，$0\le x_i,y_i\le N-1$ 且 $x_i\ne y_i$。

- 子任务一（$12$ 分）：$N=2$。
- 子任务二（$16$ 分）：$N,M\le 2\times 10^3$。
- 子任务三（$15$ 分）：第 $i$ 场比赛的获胜者参加了第 $i+1$ 场比赛，依赖子任务一。
- 子任务四（$20$ 分）：在第 $i$ 场比赛时，$x_i$ 有至少和 $y_i$ 一样多的奖牌。
- 子任务五（$22$ 分）：一旦一名选手被打败，她永远不会再次参赛。
- 子任务六（$15$ 分）：无特殊限制，依赖子任务二、三、四、五。


title: [EGOI2023] Find the Box / 找箱子

background:
Day 1 Problem C.

题面译自 [EGOI2023 findthebox](https://egoi23.se/assets/tasks/day1/findthebox.pdf)。

description:
**本题是一道 I/O 式交互题。**

玛伊是一名机器人研究员，在隆德大学工作。她了解到在大学的地下室里有一个价值连城的宝藏。宝藏就在地下深处一个空房间的箱子里。不幸的是，玛伊不能直接去找那个箱子。地下室里非常黑，且带着灯去会引起怀疑。她找到宝藏的唯一办法就是遥控住在地窖里的吸尘器机器人。

地下室是一个 $H\times W$ 的网格，其中行从 $0$ 到 $H-1$（从上到下）编号，列从 $0$ 到 $W-1$（从左到右）编号，也就是说左上角格子是 $(0,0)$，右下角格子是 $(H-1,W-1)$。装宝藏的箱子在与 $(0,0)$ 不同的某个未知的格子中。每天晚上，吸尘器机器人从左上角格子开始在地下室中移动。

每天晚上，玛伊给机器人一系列指令以指导机器人移动，指令是一个包含字符 `<`、`>`、`^` 和 `v` 的字符串。形式化地，如果机器人在格子 $(r,c)$ 且四周未被遮挡，`<` 使得机器人向左移动到 $(r,c-1)$，`>` 使得机器人向右移动到 $(r,c+1)$，`^` 使得机器人向上移动到 $(r-1,c)$，`v` 使得机器人向下移动到 $(r+1,c)$。

地下室的墙十分坚硬，因此如果机器人试图移动到格子外，什么都不会发生。箱子也十分坚硬，并且不能被推动。在每晚结束时，机器人会报告它的位置，并回到左上角格子。

时间就是金钱，因此玛伊需要用尽量少的晚上找到箱子。

outputFormat:
本题是一道 I/O 式交互题。

- 在开始时，你的程序应当输入一行两个整数 $H,W$，表示格子的高度和宽度。
- 之后，你的程序与交互库交互。在每一轮交互过程中，你应当输出一个问号 `?`，其后是一个非空字符串 $s$ 包含字符 `<`、`>`、`^` 和 `v`。字符串的长度必须至多为 $2\times10^4$。然后，你的程序输入两个整数 $r,c$（$0\le r\le H-1$，$0\le c\le W-1$），表示执行完指令后机器人的位置。注意每次询问后，机器人都会回到 $(0,0)$。
- 当你知道箱子的位置时，输出 `!` 和两个整数 $r_b,c_b$（$0\le r_b\le H-1$，$0\le c_b\le W-1$），表示箱子的坐标。在这之后，你的程序必须不再进行任何询问并退出。这个最终的输出在计算你的得分时不被计入询问次数。

请确保在每次询问后刷新输出流，否则你的程序可能被判定为 TLE。在 Python 中，`print()` 自动刷新输出流。在 C++ 中，`cout << endl;` 在输出换行后也会刷新输出流；如果使用 `printf`，请使用 `fflush(stdout)`。

交互库不自适应，意味着箱子的位置在交互开始前被确定。

hint:
**样例解释**

考虑样例。格子有高度 $H=4$ 和宽度 $W=5$，箱子在 $(r,c)=(2,3)$。下图展示了机器人在收到指令 `? vv>>>>>><^^^^^>` 后的路径，机器人最终停在 $(r,c)=(0,2)$。在第二次询问前，机器人回到左上角 $(0,0)$。程序询问 `? >>>>>>>>vvvvvvvvvv`，机器人最终停在右下角 $(r,c)=(3,4)$。此时，程序决定猜答案，输出了 `! 2 3`，惊喜地发现，这恰好是箱子的正确位置！

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

---

**数据范围**

对于全部数据，$1\le H,W\le 50$，箱子不会位于 $(0,0)$ 处（这意味着 $H+W\ge 3$），每次询问最多包含 $2\times 10^4$ 个指令，你可以询问至多 $2500$ 次（给出最终答案不被计入询问）。

你的程序会被测试于一定数量的测试点。如果你的程序在*任何*一个测试点失败（例如：给出错误的箱子坐标（WA）、程序崩了（RE）、超出时间限制（TLE）等），你会得到 $0$ 分和适当的评测结果。

如果你的程序在*所有*测试点都成功找到了箱子，你会得到 AC（**译者注：在洛谷，非满分即为 WA**），分数由下式决定：

$$
\textrm{score}=\min\left(\frac{100\sqrt{2}}{\sqrt{Q}},100\right)\textrm{ 分}
$$

其中 $Q$ 是所有测试点中询问次数的最大值。输出最终答案不被计入询问。分数将被四舍五入到最接近的整数。

具体地，要得到 $100$ 分，你的程序必须在 $Q=2$ 次询问内解决所有测试点。下表展示了一些 $Q$ 的值和其得分。

|$Q$|$2$|$3$|$4$|$5$|$\cdots$|$20$|$\cdots$|$50$|$\cdots$|$2500$|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|分数|$100$|$82$|$71$|$63$|$\cdots$|$32$|$\cdots$|$20$|$\cdots$|$3$|


title: [EGOI2023] Bikes vs Cars / 骑车与汽车

background:
Day 1 Problem D.

题面译自 [EGOI2023 bikesvscars](https://egoi23.se/assets/tasks/day1/bikesvscars.pdf)。

description:
在隆德，骑自行车是一种常见的交通方式，但有时狭窄的街道难以容纳骑车和自行车通行。为了改善这一状况，当地政府希望完全重新设计当地的街道网络。

隆德共有 $N$ 个关键位置（编号从 $0$ 到 $N-1$），人们常常在其间通行。人们通过一条路径在两地之间通行，其中路径是一系列的街道，从第一个地点到另一个。一种交通工具（车或自行车）可以在一条路径上通行，当且仅当经过的所有街道都至少与它一样宽。每个新修的街道连接关键位置其中之二，有着宽度 $W$。这个宽度可以被任意分割为自行车道和机动车道。在隆德，一些工程师最近发明了宽度为 $0$ 的车和自行车（它们可以在宽度为 $0$ 的道路通行）。

这些工程师测量了城市中车和自行车的宽度。对于每一对关键位置，他们知道其间通行的最宽的车和最宽的自行车的宽度，但政府还要求更宽的车和自行车不能在其间通行。

形式化地，对于任意 $i,j$（$0\le i < j\le N-1$），你都知道两个整数 $C_{i,j}$ 和 $B_{i,j}$。你的任务是构造一个街道网络连接这 $N$ 个位置。街道的宽度均为 $W$，但对于任意街道 $s$，你可以选择它的自行车道宽度 $b_s$ 和机动车道宽度 $W-b_s$。这个网络必须满足以下要求：

- 必须可以在任意两个位置间通行。这可能需要一辆宽度为 $0$ 的自行车或车。
- 对于每一对位置 $i,j$（其中 $i < j$），可以只借助宽度至少为 $C_{i,j}$ 的机动车道，在 $i,j$ 间通行。同时，$C_{i,j}$ 是最大的有这一性质的数。这意味着，对于所有 $i,j$ 间的路径，必须满足至少一条街道的机动车道宽度不超过 $C_{i,j}$。
- 对于每一对位置 $i,j$（其中 $i < j$），可以只借助宽度至少为 $B_{i,j}$ 的自行车道，在 $i,j$ 间通行。同时，$B_{i,j}$ 是最大的有这一性质的数。

你能帮隆德政府设计一个这样的街道网络吗？因为预算有限，你可以修建至多 $2023$ 条街道。你可以在同一对关键位置间修建多条街道，但你不能修建一条连接自己和自己的街道。所有街道都是双向的。

inputFormat:
第一行两个整数 $N,W$，表示关键位置数量和街道宽度。

接下来 $N-1$ 行包含 $C_{i,j}$。其中的第 $j$ 行包含所有满足 $i < j$ 的 $C_{i,j}$。因此第一行只会包含 $C_{0,1}$，第二行包含 $C_{0,2}$ 和 $C_{1,2}$，第三行包含 $C_{0,3},C_{1,3},C_{2,3}$，以此类推。

接下来 $N-1$ 行包含 $B_{i,j}$，格式同 $C_{i,j}$。

outputFormat:
如果不存在符合要求的街道网络，输出 `NO`。

否则，第一行一个整数 $M$，表示你修建的街道数。

接下来 $M$ 行，每行三个整数 $u,v,b$，表示一条自行车道宽度为 $b$（机动车道宽度为 $W-b$）的连接 $u,v$ 的街道。

你可以使用至多 $2023$ 条街道。你输出的街道必须满足 $0\le b\le W$，$0\le u,v\le N-1$ 且 $u\ne v$。你可以在同一对关键位置间使用多条街道（可以有不同的自行车道宽度）。

如果有多解，你可以输出任意一个。

hint:
**样例 $1$ 解释**

在样例 $1$ 中，街道的宽度为 $1$，我们需要宽度至少为 $1$ 的自行车道和机动车道各一条连接 $0,1$。解决方案是用两条分开的街道连接，一条自行车道宽度为 $1$，另一条机动车道宽度为 $1$。

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

---

**样例 $2$ 解释**

在样例 $2$ 中，街道的宽度依然是 $1$，需要有一条宽度为 $1$ 的自行车道连接任意两个关键位置，且有宽度为 $1$ 的机动车道连接 $1,2$ 和 $2,3$。这与 $C_{1,3}=0$ 矛盾，不应该有宽度为 $1$ 的从 $1$ 到 $3$ 的机动车道，而我们可以合并两条先前提到的路径组成这样一条路径。因此不可能构造出一个符合要求的街道网络。

---

**样例 $3$ 解释**

在样例 $3$ 中，下图的街道网络满足所有要求。例如，应该有一条宽度为 $1=C_{0,5}$ 的机动车道在 $0,5$ 之间（路径 $0\to 2\to 4\to 5$），一条宽度为 $3=B_{0,5}$ 的自行车道在 $0,5$ 之间（路径 $0\to 3\to 4\to 5$）。同时，可以验证，不存在路径有着更大的宽度下限。注意样例 $3$ 可能有很多其他解法。

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

---

**数据范围**

对于全部数据，$2\le N\le 500$，$1\le W\le 10^6$，$0\le C_{i,j},B_{i,j}\le W$。

- 子任务一（$10$ 分）：所有 $C_{i,j}$ 都相同，所有 $B_{i,j}$ 都相同，$N\le 40$。
- 子任务二（$5$ 分）：所有 $C_{i,j}$ 都相同，所有 $B_{i,j}$ 都相同。
- 子任务三（$17$ 分）：$N\le 40$。
- 子任务四（$18$ 分）：$W=1$。
- 子任务五（$19$ 分）：所有 $B_{i,j}$ 都相同。
- 子任务六（$31$ 分）：无特殊限制。


title: 「KDOI-06-S」合并序列

description:
给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots a_n$。

你可以对这个序列进行若干（可能为 $0$）次操作。在每次操作中，你将会：

* 选择三个正整数 $i<j<k$，满足 $a_i\oplus a_j\oplus a_k=0$ 且 $k$ 的值不超过此时序列的长度。记 $s=a_i\oplus a_{i+1}\oplus \cdots\oplus a_k$。
* 然后，删除 $a_i\sim a_k$，并在原来这 $k-i+1$ 个数所在的位置插入 $s$。注意，此时序列 $a$ 的长度将会减少 $(k-i)$。

请你判断是否能够使得序列 $a$ 仅剩一个数，也就是说，在所有操作结束后 $a$ 的长度为 $1$。若可以，你还需要给出一种操作方案。

inputFormat:
从标准输入读入数据。

**本题含有多组测试数据。**

输入的第一行包含一个正整数 $T$，表示数据组数。

对于每组测试数据，第一行一个正整数 $n$，表示初始序列长度。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示初始序列中每个元素的值。

outputFormat:
对于每组测试数据：

+ 若存在一种方案使得序列 $a$ 仅剩一个数，请在输出的第一行输出 `Huoyu`。
  + 接下来，在第二行你应该输出一个非负整数 $t$，表示你的操作次数。你需要保证 $0\le t\le n$。
  + 接下来 $t$ 行，每行输出三个正整数 $i,j,k$，表示你在这次操作中选择的三个数的值。你需要保证 $i<j<k$ 且 $k$ 的值不超过此时序列的长度。
+ 否则，请输出一行一个字符串 `Shuiniao`。


title: 「TFOI R1」Ride the Wind and Waves

background:
Z 教授是 C 班的老师。

Z 教授最近发现一个神奇的现象，他的学生竟然都有自己暗恋的对象，但是没有一个人勇于表白。

Z 教授作为过来人，当然懂得每一个学生心里最真实纯真的想法，以及自认为的爱意情愫。Z 教授想起了初恋蕉太狼，他不想让自己的学生在青春年华失去色彩，于是 Z 教授冒着被开除的风险，主动帮助学生表达心意。

然后 Z 教授被开除了。

description:
有一棵 $n$ 个节点的内向基环树（**保证弱连通**），树上每条边都有一个权值。现有一个特定参数 $k$。

由于基环树是内向的，所以一个点 $x$ 可能会有无法直接到达的节点。但是我们可以翻转树上的一些有向边，这样 $x$ 就可以到达树上每一个节点。如果一个节点 $x$ 需要**至少**翻转 $k$ 条边才能到达 $y$，则称 $y$ 是 $x$ 的乘风破浪点。在翻转了**最少的边**使得 $x$ 可以到达 $y$ 之后，在 $x$ 到 $y$ 的最短路径上，定义 $F(x, y)$ 为**未翻转**的边的权值之和，$R(x, y)$ 为**已翻转**的边的权值之和。

如果 $y$ 是 $x$ 的乘风破浪点，那么有一个值 $G(x, y)$ 表示 $x$ 到 $y$ 的浪涛值，定义 $G(x, y) = F(x, y) \times  R(x,y)$。

请你对于每一个节点 $i$，输出 $\sum G(i, y)$ 的值，其中 $y$ 是 $i$ 的乘风破浪点。

inputFormat:
第一行输入两个正整数 $n, k$，表示基环树大小和一个比较的参数。

接下来 $n$ 行，每行输入 $u, v, w$ 三个正整数，表示树上存在一条边 $(u, v, w)$，表示其起点为 $u$，终点为 $v$，权值为 $w$。

outputFormat: 输出 $n$ 行，每行一个正整数，表示每个节点到它的所有乘风破浪点的浪涛值之和。

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

拿 $3$ 节点的答案为例子，基环树的形状如图：

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

可知 $2,5,6,7$ 为 $3$ 的乘风破浪点，统计答案：

- $G(3, 2) = 6 \times 2 = 12$。

- $G(3, 5) = 6 \times 6 = 36$。

- $G(3, 6) = 9 \times 1 = 9$。

- $G(3, 7) = 6 \times 8 = 48$。

所以 $\sum G(3, j) = 12 + 36 + 9 + 48$，答案为 $105$。

#### 数据范围

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

- Subtask 1（5 points）：$1 \leqslant n \leqslant 10$，**包含特殊性质**。
- Subtask 2（10 points）：$1 \leqslant n \leqslant 5000$，**包含特殊性质**。
- Subtask 3（25 points）：$1 \leqslant n \leqslant 10^5$，**包含特殊性质**。
- Subtask 4（60 points）：$1 \leqslant n \leqslant 10^6$，无特殊限制。

**特殊性质：保证环上节点的个数在 $10^3$ 以内。**

对于所有数据，$1 \leqslant n \leqslant 10^6$，$1 \leqslant k \leqslant 10$，保证答案不会超过 $10^{18}$。


title: Hello, Solitude.

background: @【数据删除】 : 我【数据删除】了。 || @【数据删除】 : 你投哪个 || @【数据删除】 : 雪乃对美琴（悲）

description:
有一张很长的桌子，桌子一边摆了 $n+2$ 张椅子，从左到右依次标号为 $0,1,\dots,n+1$，任意两张相邻的椅子的距离相同。

初始 $0$ 号和 $n+1$ 号椅子上各坐着一个人。然后有 $m$ 个人依次按照如下的规则入座：

- 先均匀随机选择一个空着的座位。
- 若移动到相邻的座位，能使其到相邻的人的最小距离增大，则移动到相邻座位。可以证明上述操作进行有限步后一定会停下。

对于 $1\sim n$ 号的每一张椅子，求出其上面有人坐的概率。

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

outputFormat: 输出 $n$ 行，每行一个整数，第 $i$ 行的整数代表第 $i$ 张椅子上有人坐的概率对 $998\,244\,353$ 取模的结果。

hint:
#### 样例 1 解释

下面是一种可能的落座方法：

0. 初始 $1\sim n$ 都没有人落座。
1. 选定 $x=2$，到最近的人（位于座位 $0$）距离为 $2$；
   1. 向右移动到 $3$ 号椅子后，到最近的人的距离增大至 $3$，所以 $x\gets x+1$；
   2. 再向右移动到 $4$ 的话，到最近的人（位于座位 $6$）的距离依旧为 $3$，所以在 $3$ 号椅子落座。
2. 选定 $x=6$，到最近的人（位于座位 $7$）距离为 $1$；
   1. 向左移动到 $5$ 号椅子后，到最近的人的距离增大至 $2$，所以 $x\gets x-1$；
   2. 再向左/右移动话，到最近的人的距离均会减小，所以在 $5$ 号椅子落座。
3. 选定 $x=4$，由于无法左右移动，所以直接在 $4$ 号椅子落座。

最终，$3,4,5$ 号椅子上有人坐。

### 数据规模与约定

对于所有数据，$1\le n\le 5\times 10^5$，$0\le m\le n$。

### 子任务

| # | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: |
| 0 | 样例 | 0 |
| 1 | $n\le20$ | 9 |
| 2 | $n\le100$ | 10 |
| 3 | $n\le500$ | 12 |
| 4 | $n\le2000$ | 11 |
| 5 | $n\le5000$ | 12 |
| 6 | $\exists k\in \mathbb{N}$ 使得 $n=2^k-1$ | 13 |
| 7 | $n\le 10^5$ | 15 |
| 8 | - | 18 |


title: [YsOI2023] 连通图计数

background:
Ysuperman 模板测试的多项式题。

【数据删除】

description:
请问有多少个 $n$ 个点 $m$ 条边的**无向简单连通**图，无自环无重边，满足删掉编号为 $i$ 的点后无向图被分成了 $a_i$ 个连通块。特殊地，我们保证 $n-1\le m\le n+1$，且答案不为 $0$。

答案对 $998,244,353$ 取模。

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

第二行 $n$ 个整数，第 $i$ 个整数为 $a_i$。

outputFormat: 输出一行一个整数，表示答案对 $998,244,353$ 取模得到的结果。


title: [EGOI2023] Carnival General / 狂欢节总管

background:
Day 2 Problem A.

题面译自 [EGOI2023 carnival](https://egoi23.se/assets/tasks/day2/carnival.pdf)。

description:
每四年，隆德的学生都会聚到一起并举办隆德狂欢节。几天之内，公园内会挤满帐篷，并举办各种各样的庆祝活动。负责组织这一切的人被称为狂欢节总管。

共有 $N$ 个狂欢节，每个狂欢节都有不同的总管。这些总管按时间顺序被编号为 $0$ 到 $N-1$。每个总管 $i$ 都给出了他们对于前任总管的评价，他们公布了总管 $0,1,\cdots,i-1$ 从好到坏的排名。

下一届隆德狂欢节将于 2026 年举办。在此期间，所有曾经的狂欢节总管聚在一起拍了张合照。然而，如果总管 $i$ 和 $j$（其中 $i < j$）最终紧挨着对方，且 $i$ 在 $j$ 给出的排名中**严格**位于后一半，那么就会很尴尬。

例如：

- 如果总管 $4$ 给出的排名是 `3 2 1 0`，那么 $4$ 可以紧挨着 $3$ 或者 $2$ 站，但不能紧挨着 $1$ 或者 $0$。
- 如果总管 $5$ 给出的排名是 `4 3 2 1 0`，那么 $5$ 可以紧挨着 $4,3,2$ 站，但不能紧挨着 $1$ 或者 $0$。

下图为样例 $1$。其中，总管 $5$ 紧挨着总管 $2$ 和 $3$，且总管 $4$ 只紧挨着总管 $2$。

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

你已知所有总管给出的排名。你的任务是将所有总管 $0,1,\cdots,N-1$ 安排到一排，使得如果 $i$ 和 $j$ 紧挨着（其中 $i < j$），那么 $i$ **并非**严格位于 $j$ 给出排名的后一半。

inputFormat:
第一行一个整数 $N$，表示总管总数。

接下来 $N-1$ 行包含所有排名。其中的第一行是总管 $1$ 给出的排名，第二行是总管 $2$ 给出的排名，以此类推直到总管 $N-1$。总管 $0$ 不在输入中，因为总管 $0$ 没有任何前任总管可供排名。

总管 $i$ 的排名是一个长度为 $i$ 的列表 $p_{i,0},p_{i,1},\cdots,p_{i,i-1}$，其中每个整数从 $0$ 到 $i-1$ 且恰好出现一次。具体地，根据总管 $i$ 的排名，$p_{i,0}$ 是最好的总管，$p_{i,i-1}$ 是最差的总管。

outputFormat:
输出一列整数，一个整数 $0,1,\cdots,N-1$ 的排列，使得对于每对相邻整数，不存在一个在另一个排名的后一半。

可以证明一定有解。如果有多解，你可以输出任意一个。

hint:
**样例 $1$ 解释**

样例 $1$ 符合子任务一的要求。在样例中，总管 $2$ 和 $3$ 都不能紧挨着总管 $0$ 站，总管 $4$ 和 $5$ 都不能紧挨着总管 $0$ 和 $1$ 站。样例输出见上图。

---

**样例 $2$ 解释**

样例 $2$ 符合子任务二的要求。在样例中，总管 $2$ 不能紧挨着总管 $1$ 站，总管 $3$ 不能紧挨着总管 $2$ 站，总管 $4$ 不能紧挨着总管 $3$ 和 $2$ 站。

---

**样例 $3$ 解释**

样例 $3$ 符合子任务三的要求。在样例中，只有 $(1,3)$ 和 $(0,2)$ 两对总管不能彼此紧挨着站。因此，如果安排为 `3 0 1 2`，并不会有冲突。另一种可能的答案是 `0 1 2 3`。

---

**数据范围**

对于全部数据，$2\le N\le 10^3$，$0\le p_{i,0},p_{i,1},\cdots,p_{i,i-1}\le i-1$。

- 子任务一（$11$ 分）：总管 $i$ 给出的排名为 $i-1,i-2,\cdots,0$。
- 子任务二（$23$ 分）：总管 $i$ 给出的排名为 $0,1,\cdots,i-1$。
- 子任务三（$29$ 分）：$N\le 8$。
- 子任务四（$37$ 分）：无特殊限制。


title: [EGOI2023] Candy / 糖果

background:
Day 2 Problem B.

题面译自 [EGOI2023 candy](https://egoi23.se/assets/tasks/day2/candy.pdf)。

description:
在伊卡古城，据说有一座宫殿，其财富超乎想象。在其中，一个走廊中有 $N$ 盒来自世界各地的糖果。路过的旅行者只要用黄金支付糖果的重量，就可以拿走任意多的糖果。

装糖果的盒子被从左到右编号为 $0$ 到 $N-1$。在盒子 $i$ 中，剩余有 $a_i$ 单位的糖果，其中 $a_i$ 是一个非负整数。

作为宫殿的守护者，你需要移动这些盒子，使得有很多糖果的盒子更靠近入口。

你已知数组 $a_0,a_1,\cdots,a_{N-1}$，以及整数 $F$ 和 $T$。在一次操作中，你被允许交换 $a_0,a_1,\cdots,a_{N-1}$ 中的任意两个**相邻**元素。要使得数组前 $F$ 个元素的和至少为 $T$，至少需要多少次操作？

inputFormat:
第一行三个整数 $N,F,T$。

第二行 $N$ 个整数 $a_0,a_1,\cdots,a_{N-1}$。

outputFormat:
如果不可能达成目标，输出 `NO`。

否则，输出一个整数，表示最少操作数。

hint:
**样例 $1$ 解释**

在样例 $1$ 中，前两个元素的和应当至少为 $27$。一次相邻元素的交换就可以达成目标：交换 $4$ 和 $20$。在这次交换后，数组变成 `10 20 4 6 3 3`，前两个元素的和为 $10+20=30\ge 27$。

---

**样例 $2$ 解释**

在样例 $2$ 中，这个 $0$ 必须一路移动到数组末尾；这需要 $3$ 次交换。

---

**样例 $3$ 解释**

在样例 $3$ 中，不可能使得前两个元素和至少为 $100$；我们能做到的最好结果是 $60+30=90$。

---

**数据范围**

对于全部数据，$1\le N\le 100$，$1\le F\le N$，$0\le T\le 10^{11}$，$0\le a_i\le 10^9$。

- 子任务一（$6$ 分）：$N\le 2$，$a_i\le 100$，$T\le 10^9$。
- 子任务二（$19$ 分）：$a_i\le 1$。
- 子任务三（$16$ 分）：$N\le 20$。
- 子任务四（$30$ 分）：$a_i\le 100$。
- 子任务五（$29$ 分）：无特殊限制。

---

**提示**

答案可能不在 $32$ 位整型范围内，如果你使用 C++ 语言，请注意溢出的可能。


title: [YsOI2023] 前缀和

background:
Ysuperman 模板测试的试机题。

小心立秋，小心秋丽。

description:
立秋有一个长度为 $n$ 的数组 $a$，所有数字都是正整数，并且除了其中第一个数字以外其它数字都等于前面所有数字的和。

例如，数组 $[1,1,2,4,8,16]$ 就有可能是立秋有的一个数组，因为除了第一个数字 $1$，后面的每个数字都是前面数字的和，例如：

- 第二个数字 $1=1$。
- 第三个数字 $2=1+1$。
- 第四个数字 $4=1+1+2$。
- 第五个数字 $8=1+1+2+4$。
- 第六个数字 $16=1+1+2+4+8$。

现在立秋告诉了秋丽数字 $x$ 存在于这个数组中，秋丽希望知道 $a_n$ 最小会是多少，或者说整个数组最后一个数字最小有多少。

inputFormat:
本题有多组测试数据。

输入第一行一个数字 $T$ 表示测试数据组数。

接下来 $T$ 行每行两个正整数 $n,x$。

outputFormat:
输出共 $T$ 行，分别表示每组测试数据的答案。

对于某组数据 $n,x$，输出一行一个正整数表示可能的最小的 $a_n$。

hint:
#### 样例 1 解释

- 第一组数据只有唯一可能的数组 $[2,2]$，所以答案为 $2$；
- 第二组数据有两种可能的数组，分别是 $[2,2,4]$ 和 $[1,1,2]$，所以答案为 $2$；
- 第三组数据有两种可能的数组，分别是 $[2,2,4,8]$ 和 $[1,1,2,4]$，所以答案为 $4$。

#### 样例 2 解释

- 第一组数据只有唯一可能的数组 $[1,1,2]$，所以答案为 $2$；
- 第二组数据有两种可能的数组 $[1,1,2]$ 和 $[2,2,4]$，所以答案为 $2$；
- 第三组数据有两种可能的数组 $[2,2,4]$ 和 $[4,4,8]$，所以答案为 $4$。

#### 数据范围

对于前 $30\%$ 的数据，满足 $x$ 不能被 $2$ 整除，或者说 $2$ 不是 $x$ 的一个因数，或者说 $x$ 是奇数。

另有 $30\%$ 的数据，满足 $x$ 可以被 $2^{n-2}$ 整除，或者说 $2^{n-2}$ 是 $x$ 的一个因数。

另有 $20\%$ 的数据，满足 $x\le 1000$，可以证明在这个数据范围下答案可以使用一个 `int` 类型变量存储。

对于 $100\%$ 的数据，满足 $1\le T\le 10^4$，$2\le n\le 20$，$1\le x\le 10^9$。


title: [YsOI2023] 区间翻转区间异或和

background:
Ysuperman 模板测试的数据结构题。

符卡可以是人名也可以是队名。

description:
符卡有一个长度为 $n$ 的整数数组 $a$，符卡认为一个区间 $[l,r]$ 是灵异区间当且仅当 $\bigoplus_{i=l}^ra_i=0$，或者说这个区间内所有数字异或起来刚好等于 $0$。

符卡有特殊的魔法，可以把**任意**一个灵异区间翻转。具体来说，如果 $[l,r]$ 区间是灵异区间，那么符卡就可以对这个区间使用魔法，整个数组就会变成 $a_1,a_2,\dots,a_{l-1},a_r,a_{r-1},\dots,a_l,a_{r+1},a_{r+2}\dots,a_n$。

现在符卡可以使用任意次数的魔法，符卡希望最后得到的数组的灵异区间数量能够尽可能多，你能告诉她最后最多有多少个灵异区间吗？

inputFormat:
第一行一个正整数 $n$，表示数组长度。

第二行 $n$ 个非负整数 $a_1,a_2,\dots,a_n$ 表示整个数组。

outputFormat: 输出一行一个整数，表示符卡使用任意次魔法后灵异区间最多有多少个。

hint:
#### 样例 1 解释

无论符卡发动多少次魔法，数组都是 $1,1,1$，所以发不发动魔法都没有任何关系。灵异区间永远都是 $[1,2],[2,3]$ 两个。

#### 样例 2 解释

这里给出可能的一种魔法发动方法。

选择灵异区间 $[1,3]$ 发动魔法，得到的新数组是 $2,1,3,3$，这个数组共有两个灵异区间，分别是 $[1,3]$ 和 $[3,4]$。

可以证明答案无法超过 $2$。

#### 数据范围

对于前 $20\%$ 的数据，保证 $n\le 10$。

对于前 $40\%$ 的数据，保证 $n\le 2000$。

另有 $10\%$ 的数据，保证 $a_i$ 全部相等。

另有 $10\%$ 的数据，保证 $a_i$ 只有两种可能的取值。

另有 $10\%$ 的数据，保证 $0\le a_i<2^{10}$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^5$，$0\le a_i< 2^{20}$。

#### 彩蛋

灵异区间的名字其实是“零异（或）区间”的谐音。


title: 「Cfz Round 1」Dead Cells

background:
Cidoai 上完生物课后，突发奇想出了这么一道题。

太水了……吧。Cidoai 说着把这道题送给了你，让你去发掘这道题的快乐。

description:
有一天，在第 $0$ 个小时，一个细胞生成了，每过 $a$ 小时，细胞的数量就变成当前的两倍，每过 $b$ 小时，细胞的数量就变成当前的一半（向上取整）。

假如当前时间是 $a$ 和 $b$ 的公倍数，则细胞数量不变。问经过了 $k$ 小时后，细胞个数为多少，答案对 $998244353$ 取模。

inputFormat: 一行 $3$ 个正整数，分别表示 $a,b,k$。

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


title: 「Daily OI Round 1」Memory

description:
给定 $m$ 条线段，每条线段由四个正整数参数 $l_i,r_i,c_i,w_i$ 描述，其中 $l_i,r_i$ 是这条线段的端点，$c_i$ 是这条线段的种类，$w_i$ 是这条线段的权值。

你需要选出一些线段，满足以下条件且权值总和最高。

- 对于任意两条不同的线段 $i,j$，满足 $c_i = c_j$ 或 $[l_i,r_i]\cap[l_j,r_j]=\varnothing$。

inputFormat:
第一行一个正整数 $m$，代表线段数量。

接下来 $m$ 行，每行四个正整数 $l_i,r_i,c_i,w_i$ 描述线段的四个参数，含义如题所示。

outputFormat: 输出一行一个整数，表示能够得到的最大权值和。


title: 「TAOI-2」核心共振

background:
⚡超越一切震慑凡人⚡

⚡带来终结机械降神⚡

⚡风暴之力充满全身⚡

⚡最后一击核心共振⚡

description:
给定正整数 $p$ 和 $n$。对于一个排列，我们称其中相邻两项产生「共振」当且仅当这两个数的和为 $p$ 的倍数。

请你构造一个 $1 \sim n$ 的排列，最大化其中产生「共振」的次数。如果有多种方案，输出任意一种即可。

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

输入的第一行包含一个正整数 $T$，代表数据的组数。

对于每组测试数据，输入包含一行，为由空格隔开的两个正整数 $n$ 和 $p$。

outputFormat: 对于每组测试数据，输出一行，包含由空格隔开的 $n$ 个正整数，代表你构造的排列。

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

+ Subtask 0（15 pts）：$n \leq 9$，$T \le 10$。
+ Subtask 1（10 pts）：$p = 2$。
+ Subtask 2（30 pts）：$p = 3$。
+ Subtask 3（45 pts）：无特殊限制。

对于所有数据，$1 \leq n \leq 10^5$，$1 \leq p \leq 10^8$，$1 \leq T \leq 10^4$，$1 \leq \sum n \leq 3\times 10^5$。


title: 「HOI R1」杂分选约

background:
**请注意本题并不寻常的时间限制。**

由于 python 自带对于高精度乘法的实现，并且运行效率较高，导致其编写的暴力程序，在一般的时间限制下可以通过绝大部分点。故本题时限开到 $200\text{ms}$。
***

黄总是一名计算很强的数学老师，以黄氏约分而闻名。现在他请小 $\iiint$ A 了这道题。但小 $\iiint$ **似乎**有点菜，所以求助于你。

description:
把
$$\dfrac{\displaystyle\prod_{i=1}^n
a_i}{\displaystyle\prod_{j=1}^m b_j}$$
表示为*最简分数 $^{[1]}$* $\dfrac{p}{q}$，求 $p$ 和 $q$。

好心的同学还给了小 $\iiint$ 一个整数 $C$，即数据点所在的 Subtask。

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

第二行 $n$ 个整数 $a_{1\dots n}$。

第三行 $m$ 个整数 $b_{1\dots m}$。

outputFormat: 第一行两个数 $p$ 和 $q$。


title: 「Daily OI Round 1」Tree

description:
给定三个正整数参数 $n,d,k$，你需要构造出一棵根节点为 $1$ 的树，满足这棵树有 $n$ 个节点，每个节点到根节点的距离和为 $d$，除了叶节点以外每个节点的**直接**儿子数量**至少** $k$ 个，且所有节点的最大深度最小。

**注意事项：**

- 距离：两个点之间的简单路径上的边的条数。
- 叶子节点：没有儿子的非根节点。
- 根节点深度为 $0$。

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

第一行一个正整数 $T$，表示数据组数。
对于每组数据：共一行三个正整数 $n,d,k$，含义如题所示。

outputFormat:
对于每次询问，如果有解，第一行输出 `YES`，然后一行 $n-1$ 个正整数，第 $i$ 个正整数 $a_i$ 表示 $a_i$ 是 $i+1$ 的父亲节点，且 $a_i\leq i$；如果无解，输出 `NO`。

如果有多组合法的答案，可以任意输出其中一组。

**特别地，如果 $n=1$ 且有解，方案输出一行空行即可。**


title: 幽默的世界。

background: @【数据删除】 : 大家觉得呢 || @【数据删除】 : oi 生活总是充满了幽默。 不过学文化课或许也好不了多少？

description:
给定一个长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，定义 $a$ 的一个连续子序列 $a_l,a_{l+1},\cdots,a_r$ 是幽默的，当且仅当：

- $\sum\limits_{i=l}^ra_i>0$；
- 对于所有 $l\le x\le y<r$，满足 $\sum\limits_{i=x}^y a_i\le 0$。

$q$ 次询问，每次给定两个整数 $l,r$，查询满足以下条件的数对 $(l',r')$ 个数：

- $l\le l'\le r'\le r$；
- 连续子序列 $a_{l'},a_{l'+1},\cdots a_{r'}$ 是幽默的。

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

接下来一行输入 $n$ 个整数，第 $i$ 个整数代表 $a_i$。

接下来 $q$ 行，每行输入两个整数 $l,r$，代表一次询问。

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


title: 「QMSOI R1」 Distorted Fate

background:
![](https://cdn.luogu.com.cn/upload/image_hosting/oeu0ft9d.png)
**O Fortuna velut luna statu variabilis……**

（图片来自 Phigros 曲绘，侵删。）

加强版 [T512613](https://www.luogu.com.cn/problem/T512613)。

description:
Geopelia 需要捕捉到一种特殊的，不同于黑洞的引力波。

第 $i$ 个引力波有着一个频率 $A_i$，而多个引力波会互相影响，叠加，形成一个频率更快的引力波。

具体的，对于一个长度为 $n$ 的序列 $A$，$A$ 中所有引力波叠加起来的频率 $f(A)$ 为：$\bigcup\limits_{i=1}^n A_i$。其中 $\bigcup$ 表示按位或。

现在，Geopelia 需要知道几段以同一引力波开始的区间的频率之和。

也就是说，Geopelia 要向你询问：
$$
\sum_{i=l}^rf(A[l,i])
$$
的值，其中 $A[l,r]$ 为 $A_l,A_{l+1},\cdots,A_{r-1},A_r$ 组成的序列。

但不幸的是，由于幽蓝边界的引力影响，某一个区间 $[l,r]$ 中所有引力波的频率可能会异或上一个值 $x$。

Geopelia 想实时更新她的数据，你可以帮帮她吗？

她知道引力波的频率可能很高，所以你只需要告诉她答案 $\bmod \ 2^{30}$ 的值就可以了。

## 形式化题意

给定一个长度为 $n$ 的数组 $A$，你需要完成以下 $q$ 次操作。

1. ```1 l r x``` 将 $A_i(l\le i\le r)$ 异或上 $x$。

2. ```2 l r``` 求：
$$
(\sum_{i=l}^r\bigcup_{j=l}^i A_j) \bmod 2^{30}
$$
其中 $\bigcup$ 表示按位或。

inputFormat:
第一行输入两个数 $n$ 和 $q$，代表引力波的数量和操作的次数。

第二行输入 $n$ 个整数，第 $i$ 个数代表引力波 $i$ 初始的频率 $A_i$。

接下来 $q$ 行，每行输入三个整数 $opt,l,r$。

若 $opt=1$，则再输入一个整数 $x$ 表示将区间 $[l,r]$ 中引力波的频率异或上 $x$。

若 $opt=2$，则代表这是一次查询。

outputFormat: 对于每个查询，输出一行一个整数代表所求式子的值 $\bmod  \ 2^{30}$ 的结果。


title: drink

description:
你面前有 $n$ 个瓶子，从左到右依次编号为 $1 \sim n$，瓶子可能是空的也可能装着水。

你可以选择一对 $l,r(l \le r)$，然后把 $l\sim r$ 号瓶子中的所有水全部喝完。你想一口气把桌上剩的水全喝完，请问你最少要拿起几个瓶子？

你有可能一个瓶子都不需要拿起来。

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

第二行 $n$ 个整数，第 $i$ 个整数为 $1$ 表示第 $i$ 个瓶子装着水，为 $0$ 表示第 $i$ 个瓶子是空的。

outputFormat: 一行一个整数 $k$，表示最少拿起的瓶子数。

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

样例 $1$ 中，拿起 $4$ 号瓶子即可。总共拿起 $1$ 个瓶子。

样例 $2$ 中，拿起 $3\sim 6$ 号瓶子可以将所有的水喝完。总共拿起 $4$ 个瓶子。

**【数据范围】**

对于 $30\%$ 的数据，保证 $n\le 100$。

对于 $60\%$ 的数据，保证 $n\le 2000$。

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


title: queue

background: 你说的对，但是舞萌 DX 是一款后面忘了。

description:
**补充说明：这里的排队和传统的排队有出入。正在游玩的人为队列的前两位，所以正在游玩视为正在排队。**

机厅里有一台游戏机，每次可供最多两人同时游玩。但是来玩的人显然不止两个！这个时候他们就需要排队了，而你需要写一个程序维护这个队列，并在他人游玩结束后通知接下来上场的人。在整个过程中，有以下几种事件可能发生：

- `start`：一局游戏开始。若这不是第一局游戏，则上一局的参与者**在这一局游戏开始前一瞬间**按照原本的顺序回到队尾。此时你应该按在队列中的顺序输出这一局上场的人的名字（正常来讲是队列前两位或者唯一一个人），若有两个则以空格分割。若这一局无人上场，则输出 `Error` 并忽略这条事件。

- `arrive x`：$x$ 到达机厅并且将自己加入队尾，此时 $x$ 不应该在排队，否则输出 `Error` 并忽略这条事件。若该事件成功执行则输出 `OK`。

- `leave x`：$x$ 离开机厅并离开队列。此时 $x$ 应该在排队但不应该在游玩，否则输出 `Error` 并忽略这条事件。若该事件成功执行则输出 `OK`。

你需要维护队列信息，并输出上述事件中要求的输出。

inputFormat:
第一行一个整数 $n$，表示事件条数。

接下来 $n$ 行，每行表示一条事件。

outputFormat: 按照题目要求输出 $n$ 行，表示程序对事件的响应。

samples:
14
start
arrive A
start
arrive B
arrive C
arrive D
start
leave C
leave D
start
arrive A
arrive D
leave E
start

samples:
Error
OK
A
OK
OK
OK
B C
Error
OK
A B
Error
OK
Error
C D

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

样例 $1$ 中发生了如下的事件：

- 第一次 `start` 时队列并没有任何人，输出 `Error`。
- `A` 随即加入队列。
- 第二次 `start` 时仅有 `A` 一个人，所以输出 `A`。
- `B, C, D` 随即依次加入队列。
- 第三次 `start` 时 `B, C` 上场。
- `C` 试图离开，但是他在游玩。所以输出 `Error`。
- `D` 成功离开。
- 第四次 `start` 时 `A, B` 上场。
- `A` 试图加入队列，但是他已经在队列中。输出 `Error`。
- `D` 重新加入队列。
- `E` 试图离开，但是他根本不在排队，输出 `Error`。
- 第五次 `start` 时 `C, D` 上场。

样例 $2$ 中，`A, B, C` 依次入队，操作合法，输出三个 `OK`。

**【数据范围】**

对于 $20\%$ 的数据，保证 $n=1$。

对于 $40\%$ 的数据，保证 $n\le 2000$。

对于另外 $20\%$ 的数据，保证没有 `leave` 操作。

对于另外 $20\%$ 的数据，人名只有可能是单个大写字母。

对于 $100\%$ 的数据，保证 $1 \le n\le 10^5$，人名仅含有大小写字母且长度不超过 $10$。

**本题输入输出量较大，请注意使用合理的输入输出方式。**


title: 「Daily OI Round 4」Analysis

description:
小 C 的信息技术老师给小 C 布置了一项作业，作业内容如下：

> 有一个字符串，包含大小写字母和数字。你可以把任意一个字符变成另外一个字符，设变化之前字符的 ASCII 码为 $a$，变化之后字符的 ASCII 码为 $b$，则这次变化消耗 $|a-b|$ 的时间。你需要把整个字符串变成只包含大写字母的字符串。

小 C 还有语文数学英语等很多其他重要作业要做，为了节省时间，你需要计算小 C 最少需要多久才能令字符串只包含大写字母。

inputFormat: 一行一个字符串 $s$ 表示老师给的字符串。

outputFormat: 一行一个非负整数 $t$，表示令字符串只包含大写字母最少花费多少时间。

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

对于第一组样例，最好的办法是变成 $\texttt{AAAZZ}$，这样的话消耗就为 $0+0+|48-65|+|97-90|+|97-90|=31$，容易证明不存在更优的解法。

其中 $48$ 是字符 $\texttt{0}$ 的 ASCII 码，$65$ 是字符 $\texttt{A}$ 的 ASCII 码，$90$ 是字符 $\texttt{Z}$ 的 ASCII 码，$97$ 是字符 $\texttt{a}$ 的 ASCII 码。

#### 【数据范围】

**本题开启捆绑测试。**

设 $len$ 为字符串 $s$ 的长度。

| $\text{Subtask}$ | 分值 | $len \le$ |
| :-----------: | :-----------: | :-----------: |
| $0$ | $10$ | $3$ |
| $1$ | $30$ | $10$ |
| $2$ | $60$ | $10^5$ |

对于全部数据，保证：$1 \le len \le 10^5$，且 $s$ 中只包含大小写字母和数字。


title: 「LAOI-6」区间测速

background: [English statement](https://www.luogu.com.cn/problem/T503704). You must submit your code at the Chinese version of the statement.

description:
小 A 正在一条笔直的公路上行驶（可以随时掉头，掉头的时间和路程忽略不计），这条公路可以被抽象为一条数轴。

你现在得到了 $n$ 个监控的信息，第 $i$ 条信息记录到：小 A 在 $t_i$ 时刻经过了坐标为 $x_i$ 之处。

有 $m$ 次询问，第 $i$ 次询问给定 $u_i$ 和 $v_i$，表示：假如将第 $u_i$ 个监控记录到小 A 经过 $x_i$ 的时间改为 $v_i$，小 A 所有可能的行驶过程中，最快时速的最小值是多少（答案向下取整）？**询问之间互相独立，即每次询问的改动是暂时的**。

### 形式化题意

给定 $n,m$，有长度为 $n$ 的数组 $x$ 与 $t$。进行 $m$ 次独立的修改，第 $i$ 次会将 $t_{u_i}$ 修改为 $v_i$，并询问：

$$\max_{i=1}^{n}\max_{j=i+1}^n \left\lfloor\frac{|x_i-x_j|}{|t_i-t_j|}\right\rfloor$$

**前一次修改不会影响后一次修改，即询问结束后会撤销修改**。

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

接下来 $n$ 行，每行两个整数 $x_i,t_i$。

接下来 $m$ 行，每行两个整数 $u_i,v_i$。

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


title: pay

description:
今天是 L 公司发工资的一天。

$n$ 名员工排成一排准备领工资，编号为 $1\sim n$，第 $i$ 名员工有一个期望快乐值 $a_i$。

老板非常扣，在这 $n$ 名员工中只选择了 $m$ 名员工 $b_1,b_2,\cdots,b_m$ 发 $k$ 元工资。

员工们都非常具有同理心，不仅自己获得工资时会增加快乐值，当周围的员工获得工资时自己也会增加快乐值。

具体地，当与一名员工 A 距离为 $d$ 的员工获得了工资，A 的快乐值会增加 $\max(0, k - d)$。特别地，如果 A 本身就获得了工资，A 的快乐值会增加 $k$。

老板希望，你能找到最小的整数 $k$，使得所有员工的快乐值不低于他的期望。

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

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

第三行 $m$ 个整数 $b_1,b_2,\cdots,b_m$。

outputFormat: 一个整数，表示你求出的最小的 $k$。

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

样例 $1$ 中，$k=2$ 时，每个人的快乐值分别为 $3,4,4,4,3$，满足要求。

样例 $2$ 中，$k=5$ 时，每个人的快乐值分别为 $5,7,7,7,7$，满足要求。

**【数据范围】**

对于 $10\%$ 的数据，满足 $n=1$。

对于 $30\%$ 的数据，满足 $n\le 300$。

对于 $60\%$ 的数据，满足 $n\le 5000$。

对于另外 $10\%$ 的数据，满足 $m=1$。

对于 $100\%$ 的数据，满足 $1\le m\le n\le 10^6$，$0\le a_i\le 10^9$，$1\le b_i\le n$ 且 $b_i$ 互不相同。

**本题输入量较大，请注意使用合理的输入方式。**


title: 「JOC-1A」限时签到

background:
纵使寻不到身外的青春，

也总得自己来一掷我身中的迟暮。

但暗夜又在那里呢？

现在没有星，没有月光以至没有笑的渺茫和爱的翔舞；

青年们很平安，而我的面前又竟至于并且没有真的暗夜。

绝望之为虚妄，正与希望相同！

——@duanfeitong 摘自鲁迅《希望》

description: 你现在一条笔直的公路上，我们不妨把这条公路看做成一条数轴，你现在在数轴原点的位置上，此外还有 $n$ 个签到处，第 $i$ 个签到处的坐标为 $x_i$，并且其将在你出发后的第 $a_i$ 个时刻开始营业，每个签到处只有在开始营业了之后你才可以进去签到（签到的时间可以忽略不计），你在每个时刻内至多可移动 $1$ 个单位，你必须在 $t$ 时刻或者在此之前到达坐标为 $f$ 的点（$f\le t$），无论你在规定时间内何时到达 $f$ 点，从 $t$ 时刻起你就必须一直待在 $f$ 点，问你最多能去多少个签到处签到。**请注意，你不需要按照签到处的编号顺序签到。**

inputFormat:
共 $n+1$ 行。

第一行，三个整数 $n$、$t$ 和 $f$。

接下来 $n$ 行，每行两个整数 $x_i$ 和 $a_i$。

outputFormat: 共一行，一个非负整数，表示最多能去签到的签到处的数量。

hint:
### 样例 $\small\text{1}$ 解释

一种可行的行动方案如下：在 $5$ 时刻来到第三个签到处签到，然后在 $7$ 时刻来到第二个签到处签到，最后在 $14$ 时刻来到终点，可以证明最多只能去 $2$ 个签到处签到。

### 数据规模与约定

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

| $\textbf{Subtask}$ | $\textbf{Number}$ | $\textbf{Special conditions}$| $\textbf{Points}$ | $\textbf{Limit}$ |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $1-2$ | $n\leq 10$ | $10$ | $\small\texttt{1s，128MB}$ |
| $2$ | $3-4$ | $n\leq 5\times 10^3$ | $15$ | $\small\texttt{1s，128MB}$ |
| $3$ | $5$ | $n\leq 10^6$ | $25$ | $\small\texttt{1s，128MB}$  |
| $4$ | $6-7$ | $f\leq 10^5$ | $20$ | $\small\texttt{500ms，128MB}$ |
| $5$ | $8-9$ | $n\leq 10^6$ | $30$ | $\small\texttt{150ms，10MB}$ |

对于 $100\%$ 的数据，$1\leq n\leq 10^6$，$0\leq f\leq t\leq 10^{18}$，$0\leq x_i\leq f$，$0\leq a_i\leq t$，**不保证签到处的坐标互不相同**。

请注意：由于本题当 $n$ 接近 $10^7$ 时数据输入量过大，故我们决定在 $n\leq 10^6$ 的数据上修改时间限制和空间限制以代替 $n\leq 10^7$ 的数据的评测。

**请注意，本题输入数据量较大，建议使用较快的读入方式。**

---

在我永恒的记忆里，

你天真地微笑。

在我年轻的心中，

你是星星之火燃烧。

——@duanfeitong 摘自祁子《童年》


title: [NOI2023] 方格染色

description:
有一个 $n$ 列 $m$ 行的棋盘，共 $n \times m$ 个方格，我们约定行、列均从 $1$ 开始标号，且第 $i$ 列、第 $j$ 行的方格坐标记为 $(i, j)$。初始时，所有方格的颜色均为白色。现在，你要对这个棋盘进行 $q$ 次染色操作。

染色操作分为三种，分别为：

1. 将一条横线染为黑色。具体地说，给定两个方格 $(x_1, y_1)$ 和 $(x_2, y_2)$，保证 $x_1 \le x_2$，$y_1 = y_2$，将这两个方格之间的所有方格（包括这两个方格）染为黑色。
2. 将一条竖线染为黑色。具体地说，给定两个方格 $(x_1, y_1)$ 和 $(x_2, y_2)$，保证 $x_1 = x_2$，$y_1 \le y_2$，将这两个方格之间的所有方格（包括这两个方格）染为黑色。
3. 将一条斜线染为黑色。具体地说，给定两个方格 $(x_1, y_1)$ 和 $(x_2, y_2)$，保证 $x_1 \le x_2$，$x_2 - x_1 = y_2 - y_1$，将这两个方格之间斜线上所有形如 $(x_1 + i, y_1 + i)$（$0 \le i \le x_2 - x_1$）的方格染为黑色。**这种染色操作发生的次数不超过 $5$ 次。**

现在你想知道，在经过 $q$ 次染色后，棋盘上有多少个黑色的方格。

inputFormat:
输入的第一行包含一个整数 $c$，表示测试点编号。$c = 0$ 表示该测试点为样例。

输入的第二行包含三个正整数 $n, m, q$，分别表示棋盘的列、行和染色操作的次数。

接下来 $q$ 行，每行输入五个正整数 $t, x_1, y_1, x_2, y_2$，其中 $t = 1$ 表示第一种染色操作，$t = 2$ 表示第二种染色操作，$t = 3$ 表示第三种染色操作。$x_1, y_1, x_2, y_2$ 表示染色操作的四个参数。

outputFormat: 输出一行包含一个整数，表示棋盘上被染为黑色的方格的数量。

samples:
见附件中的 color/color2.in。
见附件中的 color/color2.ans。

samples:
见附件中的 color/color3.in。
见附件中的 color/color3.ans。

samples:
见附件中的 color/color4.in。
见附件中的 color/color4.ans。

samples:
见附件中的 color/color5.in。
见附件中的 color/color5.ans。

samples:
见附件中的 color/color6.in。
见附件中的 color/color6.ans。

samples:
见附件中的 color/color7.in。
见附件中的 color/color7.ans。

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

在这组样例中，我们一共做了三次染色操作，如下图所示。

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

第一次操作时，将 $(1, 3), (2, 3), (3, 3), (4, 3), (5, 3)$ 染为黑色。

第二次操作时，将 $(3, 1), (3, 2), (3, 3), (3, 4), (3, 5)$ 染为黑色。

第三次操作时，将 $(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)$ 染为黑色。

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

这个样例满足测试点 $1 \sim 5$ 的条件限制。

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

这个样例满足测试点 $6 \sim 9$ 的条件限制。

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

这个样例满足测试点 $10 \sim 13$ 的条件限制。

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

这个样例满足测试点 $14 \sim 17$ 的条件限制。

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

这个样例满足测试点 $18 \sim 19$ 的条件限制。

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

这个样例满足测试点 $20$ 的条件限制。

**【数据范围】**

对于所有测试数据保证：$1 \le n, m \le 10 ^ 9$，$1 \le q \le 10 ^ 5$，$1 \le x_1, x_2 \le n$，$1 \le y_1, y_2 \le m$，**且最多有 $5$ 次第三种染色操作**。

|测试点编号|$n, m \le$|$q \le$|特殊性质|
|:-:|:-:|:-:|:-:|
|$1 \sim 5$|$300$|$300$|无|
|$6 \sim 9$|$10 ^ 5$|$2,000$|无|
|$10 \sim 13$|$10 ^ 5$|$10 ^ 5$|A|
|$14 \sim 17$|$10 ^ 5$|$10 ^ 5$|B|
|$18 \sim 19$|$10 ^ 5$|$10 ^ 5$|无|
|$20$|$10 ^ 9$|$10 ^ 5$|无|

特殊性质 A：保证只有第一种染色操作。

特殊性质 B：保证只有第一种和第二种染色操作。

Update on 2023-08-04: 更新一组 Hack 数据，该 Hack 数据的 $c = 0$。


title: [NOI2023] 深搜

description:
深度优先搜索是一种常见的搜索算法。通过此算法，我们可以从一个无重边、无自环的无向连通图 $G = (V, E)$，和某个出发点 $s$，得到一棵树 $T$。

算法的流程描述如下:

1. 将栈 $S$ 设置为空，并令 $T = (V, \emptyset)$，即 $T$ 的边集初始为空。
2. 首先将出发点 $s$ 压入 $S$ 中。
3. 访问栈顶节点 $u$，并将 $u$ 标记为“已访问的”。
4. 如果存在与 $u$ 相邻且未被访问的节点，则**任意地**从这些节点中挑选一个记为 $v$。我们将边 $(u, v)$ 加入 $T$ 的边集中，并将 $v$ 压入栈 $S$ 中，然后**回到步骤 3**。若不存在这样的节点，则从栈中弹出节点 $u$。

可以证明，当图 $G$ 为连通图时，该算法会得到图的某一棵生成树 $T$。但**算法得到的树 $T$ 可能不是唯一的，它取决于搜索的顺序，也就是算法的第 4 步所选取的顶点**。指定出发点 $s$ 后，如果能够选取一种特定的搜索顺序，使得算法得到的树恰好是 $T$，则我们称 **$T$ 是 $G$ 的一棵 $s$-dfs 树**。

现在给定一棵 $n$ 个顶点的树 $T$，顶点编号为 $1 \sim n$，并额外给出 $m$ 条边。我们保证这 $m$ 条边两两不同，连接不同的顶点，且与 $T$ 中的 $n - 1$ 条树边两两不同。我们称额外给出的 $m$ 条边为**非树边**。在这 $n$ 个顶点中，我们指定了恰好 $k$ 个顶点作为**关键点**。

现在你想知道，有多少种选取这 $m$ 条非树边的方法（可以全部不选），使得：将 $T$ 的边与被选中的非树边构成图 $G$ 之后，存在某个**关键点** $s$，使得 $T$ 是 $G$ 的一棵 $s$-dfs 树。

由于答案可能十分巨大，你只需要输出方案数在模 $(10 ^ 9 + 7)$ 意义下的值。

inputFormat:
输入的第一行包含一个整数 $c$，表示测试点编号。$c = 0$ 表示该测试点为样例。

输入的第二行包含三个正整数 $n, m, k$，分别表示顶点个数，非树边的数量，关键点的数量。

接下来 $n - 1$ 行，每行包含两个正整数 $u, v$ 表示树 $T$ 的一条边。保证这 $n - 1$ 条边构成了一棵树。

接下来 $m$ 行，每行包含两个正整数 $a, b$ 表示一条非树边。保证 $(a, b)$ 不与树上的边重合，且没有重边。

输入的最后一行包含 $k$ 个正整数 $s_1, s_2, \dots, s_k$，表示 $k$ 个关键点的编号。保证 $s_1, s_2, \dots, s_k$ 互不相同。

outputFormat: 输出一行包含一个非负整数，表示方案数在模 $(10 ^ 9 + 7)$ 意义下的值。

samples:
见附件中的 dfs/dfs2.in。
见附件中的 dfs/dfs2.ans。

samples:
见附件中的 dfs/dfs3.in。
见附件中的 dfs/dfs3.ans。

samples:
见附件中的 dfs/dfs4.in。
见附件中的 dfs/dfs4.ans。

samples:
见附件中的 dfs/dfs5.in。
见附件中的 dfs/dfs5.ans。

samples:
见附件中的 dfs/dfs6.in。
见附件中的 dfs/dfs6.ans。

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

在这个样例中，有三种选取非树边的方法：只选取边 $(1, 3)$，只选取边 $(2, 4)$，或不选取任何条非树边。

如果只选取边 $(1, 3)$，或者不选取任何一条非树边，则我们发现 $T$ 都是图 $G$ 的 $3$-dfs 树。指定的搜索顺序如下：
1. 将 $3$ 放入栈 $S$ 中。此时 $S = [3]$。
2. 将 $3$ 标记为“已访问的”。
3. 由于 $3$ 与 $2$ 相连，且 $2$ 是“未访问的”，将 $2$ 放入栈 $S$ 中，并将 $(3, 2)$ 加入树 $T$ 中，此时 $S = [3, 2]$。
4. 将 $2$ 标记为“已访问的”。
5. 由于 $2$ 与 $1$ 相连，且 $1$ 是“未访问的”，将 $1$ 放入栈 $S$ 中，并将 $(2, 1)$ 加入树 $T$ 中，此时 $S = [3, 2, 1]$。
6. 由于与 $1$ 相邻的点都是“已访问的”，将 $1$ 弹出栈，此时 $S = [3, 2]$。
7. 由于与 $2$ 相邻的点都是“已访问的”，将 $2$ 弹出栈，此时 $S = [3]$。
8. 由于 $3$ 与 $4$ 相连，且 $4$ 是“未访问的”，将 $4$ 放入栈 $S$ 中，并将 $(3, 4)$ 加入树 $T$ 中，此时 $S = [3, 4]$。
9. 由于与 $4$ 相连的点都是“已访问的”，将 $4$ 弹出栈，此时 $S = [3]$。
10. 由于与 $3$ 相连的点都是“己访问的”，将 $3$ 弹出栈，此时 $S$重新变为空。

如果只选取边 $(2, 4)$，则我们可以说明 $T$ 是图 $G$ 的 $2$-dfs 树。指定的搜索顺序如下：

1. 将 $2$ 放入栈 $S$ 中。此时 $S = [2]$。
2. 将 $2$ 标记为“已访问的”。
3. 由于 $2$ 与 $3$ 相连，且 $3$ 是“未访问的”，将 $3$ 放入栈 $S$ 中，并将 $(2, 3)$ 加入树 $T$ 中，此时 $S = [2, 3]$。
4. 将 $3$ 标记为“已访问的”。
5. 由于 $3$ 与 $4$ 相连，且 $4$ 是“未访问的”，将 $4$ 放入栈 $S$ 中，并将 $(3, 4)$ 加入树 $T$ 中，此时 $S = [2, 3, 4]$。
6. 由于与 $4$ 相邻的点都是“己访问的”，将 $4$ 弹出栈，此时 $S = [2, 3]$。
7. 由于与 $3$ 相邻的点都是“已访问的”，将 $3$ 弹出栈，此时 $S= [2]$。
8. 由于 $2$ 与 $1$ 相连，且 $1$ 是“未访问的”，将 $1$ 放入栈 $S$ 中，并将 $(2, 1)$ 加入树 $T$ 中，此时 $S = [2, 1]$。
9. 由于与 $1$ 相连的点都是“已访问的”，将 $1$ 弹出栈此时 $S = [2]$。
10. 由于与 $2$ 相连的点都是“已访问的”，将 $2$ 弹出栈，此时 $S$ 重新变为空。

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

这个样例满足测试点 $4 \sim 6$ 的约束条件。

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

这个样例满足测试点 $10 \sim 11$ 的约束条件。

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

这个样例满足测试点 $12 \sim 13$ 的约束条件。

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

这个样例满足测试点 $14 \sim 16$ 的约束条件。

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

这个样例满足测试点 $23 \sim 24$ 的约束条件。

**【数据范围】**

对于所有测试数据保证：$1 \le k \le n \le 5 \times 10 ^ 5$，$1 \le m \le 5 \times 10 ^ 5$。

|测试点编号|$n \le$|$m \le$|$k \le$|特殊性质|
|:-:|:-:|:-:|:-:|:-:|
|$1 \sim 3$|$6$|$6$|$n$|无|
|$4 \sim 6$|$15$|$15$|$6$|无|
|$7 \sim 9$|$300$|$300$|$6$|无|
|$10 \sim 11$|$300$|$300$|$n$|A|
|$12 \sim 13$|$300$|$300$|$n$|B|
|$14 \sim 16$|$300$|$300$|$n$|无|
|$17 \sim 18$|$2 \times 10 ^ 5$|$2 \times 10 ^ 5$|$n$|A|
|$19 \sim 21$|$2 \times 10 ^ 5$|$2 \times 10 ^ 5$|$n$|B|
|$22$|$2 \times 10 ^ 5$|$2 \times 10 ^ 5$|$n$|无|
|$23 \sim 25$|$5 \times 10 ^ 5$|$5 \times 10 ^ 5$|$n$|无|

特殊性质 A：保证在 $T$ 中，$i$ 号点与 $i + 1$ 号点相连（$1 \le i < n$）。

特殊性质 B：保证若将 $T$ 的边与所有 $m$ 条非树边构成一个图 $G$，则 $T$ 是 $G$ 的棵 $1$-dfs 树。

**请注意，$1$ 号点不一定是 $k$ 个关键点之一。**


title: [LSOT-2] Tree and Xor

background: tyr 很唐。

description:
给定 $n$，你需要构造一棵 $n$ 个点的以 $1$ 为根的有根树，满足 $\bigoplus\limits_{i=1}^ndegree(i)=0$ 且 $fa_2 \sim fa_n$ 的字典序最小。其中，$\oplus$ 表示异或运算。

其中 $degree(i)$ 表示与点 $i$ 相连的点数，$fa_i$ 表示点 $i$ 的父节点且 $fa_i < i$。

你需要输出 $\sum\limits_{i=2}^ni \times fa_i$，若无解则输出 $-1$。

inputFormat:
第一行，一个正整数 $T$，表示询问数量。

接下来每 $T$ 行每行一个正整数 $n$ 表示一次询问。

outputFormat: 一共 $T$ 行，每行一个整数表示答案除 $998244353$ 的余数。

hint:
**「本题采用捆绑测试」**

- $\texttt{Subtask 1(5 pts)：}n \leq 7$。
- $\texttt{Subtask 2(10 pts)：} n \leq 20$。
- $\texttt{Subtask 3(20 pts)：}\sum n \leq 2000$。
- $\texttt{Subtask 4(15 pts)：}n = 2^k-1$，其中 $k$ 是自然数。
- $\texttt{Subtask 5(50 pts)：}$无特殊限制。

对于所有数据，$1\le T\le 10^6$，$2 \leq n \leq 10^{9}$。


title: [ROI 2019 Day 1] 拍照

background:
翻译自 [ROI 2019 D1T1](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day1.pdf)。

参加奥林匹克竞赛的学生来自 $n$ 个地区，每个地区的代表团由 $m$ 名学生组成。每个代表团的学生穿着有自己地区特色的衣服，第 $i$ 个代表团穿的衣服颜色编号为 $i$。

摄影师决定给所有参赛者拍一张照片。为了组织拍摄照片，摄影师计划按以下方式进行操作：

舞台上有一排学生站立的位置，他们沿着舞台从 $1$ 到 $m$ 进行编号。摄影师计划轮流找一些代表团的领队，要求该代表团的几名学生上台。摄影师指定 $L$ 和 $R$ 的值，选中的代表团的学生上台并站在从第 $L$ 个到第 $R$ 个（包括 $L$ 和 $R$）的所有位置上。如果这个位置上已经站了一名学生，则将这名学生请下台，让新的学生站上来。每个代表团的领队只能被摄影师找一次。

description:
为了在照片上的色彩更加和谐，摄影师希望照片上应该有 $m$ 名学生，而且穿着的衣服颜色必须按照给定的顺序排列。现在他想知道如何才能得到所需的照片。

编写一个程序，根据给定的颜色顺序，确定摄影师要找的代表团编号以及他们应该占据的位置的顺序，以制作期望中的照片。如果不可能，输出 `-1`。

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

第二行包含 $m$ 个整数 $a_1,a_2,\dots,a_m$（$1\le a_i\le n$），表示摄影师希望照片上的学生衣服颜色的顺序。

outputFormat:
输出的第一行应包含一个整数 $k$。如果无法拍出期望的照片，则此数字应为 $-1$。否则，它应该是摄影师需要找的代表团的数量，以便拍出期望的照片。

当 $k\ne-1$ 时，接下来的 $k$ 行应按照它们应该进行的顺序输出摄影师的请求。第 $i$ 个请求由三个整数 $c_i,L_i,R_i$ 表示，其中 $c_i$ 是代表团的编号，$L_i$ 和 $R_i$ 分别是代表团 $c_i$ 的学生应该占据的舞台上第一个和最后一个位置的编号。所有 $c_i$ 必须不同。

如果有多个解决方案，可以输出其中任意一个。


title: [ROI 2019 Day 1] 自动驾驶

background:
翻译自 [ROI 2019 D1T2](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day1.pdf)。

今天，需要在因诺波利斯的主广场上，展示最新试验的自动驾驶出租车的功能。广场是一个长 $n$ 米、宽 $m$ 米的矩形区域，被划分成 $n\times m$ 个单位方块。矩形的行从 $1$ 到 $n$ 编号，列从 $1$ 到 $m$ 编号。因此，每个方块可以由两个正整数 $r$ 和 $c$ 表示，分别代表所在行和列的编号。自动驾驶出租车可以在相邻的方块之间移动，每一步可以从当前方块移动到与之相邻的四个方块之一。

今年冬天下了很多雪，所以在展示自动驾驶出租车功能的过程中会用自动除雪机清理广场上的雪。由于自动驾驶交通系统正在测试阶段，因此广场上同一时间只能同时存在一辆自动驾驶交通工具（自动除雪机或自动驾驶出租车）。

由于整个展示期间一直在下雪，自动驾驶出租车的工程师决定借机发挥，展示出租车克服雪堆的能力。

description:
每个时刻广场上每个单位方块的雪深可以由一个非负整数表示，自动驾驶出租车的最大可通过雪深也由一个非负整数表示。在移动时，出租车只能停留在雪深不超过最大可通过雪深的方块上。每次展示自动驾驶出租车时，工程师可以设置出租车的最大可通过雪深。

初始状态下，广场上所有方块的雪深为零。每个小时开始时，每个方块的雪深增加一。随后，自动驾驶交通系统可以执行以下三个操作之一，每个操作需要一小时：
1) 沿着某一行启动除雪机，然后该行的所有方块的雪深变为零；
2) 沿着某一列启动除雪机，然后该列的所有方块的雪深变为零；
3) 展示自动驾驶出租车的功能：设置出租车的最大可通过雪深，选择起始和目标方格，并让出租车从起始方块到达目标方块。
   只有当存在一个以起始方块开始、以目标方块结束的单位方块序列，其中任意相邻的两个方块有共同的边界，并且序列中每个方块的雪深都不超过出租车的最大可通过雪深时，才可以从起始方块到达目标方块。如果设置的最大可通过雪深允许完成旅行，则出租车应选择步数最少的路径。

每次展示自动驾驶出租车时，需要确定是否可以顺利完成这次的展示（是否有从起始方块到目标方块的路径），如果可以，则需要知道完成此次旅行所需的最少步数。

inputFormat:
第一行包含三个整数 $n,m,q$，分别表示区域的大小和无人驾驶出租车的操作数。

接下来的 $q$ 行，每行输入一种操作，其中第 $i$ 行有以下三种操作类型之一：
- `1 ri`：在第 $r_i$ 行启动除雪机。
- `2 ci`：在第 $c_i$ 列启动除雪机。
- `3 ri1 ci1 ri2 ci2 ki`：设置出租车的最大可通过雪深为 $k_i$，并尝试从起始方格 $(r_{i1}, c_{i1})$ 开始行驶到结束方格 $(r_{i2}, c_{i2})$。

保证输入数据中至少存在一个类型为 $3$ 的操作。

outputFormat: 对于每个类型为 $3$ 的操作，需要输出一行一个整数。如果从起始方格到结束方格的行程是可行的，则输出需要实现该行程的最小步数。如果行程不可行，则输出 `-1`。


title: [ROI 2019 Day 1] 高速电车

background:
翻译自 [ROI 2019 D1T3](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day1.pdf)。

Flatland 的首都需要与邻近的城市之间建立铁路联系，而现有的铁路系统已经过时。为了优化铁路系统，需要开通一列从首都到另一个城市的高速电车。Flatland 铁路网络总共有 $n$ 个站点，从 $1$ 到 $n$ 进行编号，首都的编号是 $1$。在各个站点之间存在 $m$ 条单向线路，每条线路的行驶时间已知。

description:
计划部门打算考虑几个不同的高速电车路线方案。每个方案由一个目标站点和预计行驶时间来定义。然而，部门知道实际的行驶时间可能无法完全符合预期。因此，他们使用参数 $p$ 来评估路线的可行性：对于给定的预计时间 $r$，如果 $r\le x\le\frac{p}{p-1}\times r$，其中 $x$ 是行驶时间的总和，则认为路线是可行的。

编写一个程序，根据 Flatland 铁路网络的描述和各个路线方案，确定每个方案是否存在可行的高速电车路线。

inputFormat:
第一行包含一个整数 $t$，表示测试数据的组数。

接下来的若干行描述每组测试数据。

每组测试数据的第一行包含四个整数 $n,m,q,p$，分别表示站点数量、线路数量、要考虑的路线方案数量和允许的时间偏差参数。

接下来的 $m$ 行描述每条线路，每行包含三个整数 $v_i,u_i,d_i$，分别表示起始站点、终点站点和行驶时间。

接下来的 $q$ 行描述每个路线方案，每行包含两个整数 $f_i$ 和 $r_i$，分别表示目标站点和预计行驶时间。

outputFormat: 对于每个测试用例，输出一行长度为 $q$ 的字符串 $s$，其中第 $i$ 个字符 $s_i$ 等于 $1$ 表示存在可行的高速电车路线，行驶时间在区间 $[r_i,\frac{p}{p-1}\times r_i]$ 内；否则，$s_i$ 等于 $0$ 表示不存在可行的高速电车路线。


title: [ROI 2019 Day 1] 黑洞

background:
翻译自 [ROI 2019 D1T4](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day1.pdf)。

**这是一道 IO 交互题**。

科学家计划测量一系列黑洞的辐射等级。黑洞的辐射等级由一个从 $1$ 到 $n$ 的整数表示。为了测量每个黑洞的辐射等级，使用一个特殊的轨道探测器，上面安装有辐射传感器。安装在探测器上的传感器可以回答以下查询：根据给定的 $x$ 值，确定辐射等级是否大于或等于 $x$。不幸的是，由于软件错误，传感器的回复可能是错误的。不过，在第一个错误回复之后，该探测器的状态就会改变，对所有后续的查询只给出正确的回复。

科学家想要通过向其导向的探测器提出尽可能少的查询来确定几个黑洞的辐射等级。

description:
编写一个程序与模拟探测器传感器的交互库进行交互，并确定每个黑洞的辐射等级。

对于每次运行的解决方案程序，必须解决 $n$ 相同的多个黑洞的问题（即，需要确认多个黑洞的辐射等级，这些黑洞的辐射等级都在 $1$ 和 $n$ 之间）。每次的黑洞数量不超过 $100$。

对于每个测试点，交互库记录了 $q$ 的值，也就是允许对一个黑洞进行的最大查询次数。保证无论选择的交互程序如何回答，$q$ 个查询足以解决问题。此数字不会被告知给你的程序。如果你的程序对一个黑洞进行了超过 $q$ 个查询，则这个测试点将会返回 WA。

注：在上述 WA 的情况下，该测试点可能显示为 TLE，有可能是因为交互库已经结束并返回，但程序仍在等待该查询的回复。TLE 时可以查看该测试点返回的详细信息，以确认是程序超时还是询问次数超出限制导致的。

inputFormat:
首先输入一个数 $n$，也就是黑洞的最大辐射强度。这个数字对于本次运行中的所有黑洞是相同的。读取 $n$ 后，你的程序应与交互库进行交互并逐步确定一个或多个黑洞的辐射等级。

在输出完你对一个黑洞辐射等级的回答后，程序应另外读取一行。如果需要继续对下一个黑洞进行研究，则从交互库读入的字符串为 `Correct`；如果所有的黑洞都已经研究完成，则字符串应该为 `Done`。

outputFormat:
要进行查询，程序必须输出格式为 `? x` 的字符串，其中 $x$ 是一个正整数。作为回答，交互库将给你的程序一个字符串，要么是 `Yes`（如果传感器的回复没有出错，就代表该黑洞的辐射等级大于或等于查询中指定的 $x$ 值），要么是 `No`（如果传感器的回复没有出错，就代表该黑洞的辐射等级小于查询中指定的 $x$ 值）。

如果你的程序确定了问题的答案，则它应该输出一行 `! x`，其中 $x$ 是要查找的黑洞的辐射等级。如果 $x$ 是唯一那个与不多于一个交互库的回复相冲突的辐射水平值，则该答案被视为正确的。如果给出了错误答案，程序将被强制终止，并且该测试点的结果将会变为 WA。


title: [ROI 2019 Day 2] 灯串

background:
翻译自 [ROI 2019 D2T1](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day2.pdf)。

对于一个由 `0` 和 `1` 组成的序列，“美丽的”的定义是：如果这个序列的第一个 `1` 前面 `0` 的数量和最后一个 `1` 后面 `0` 的数量相等，且每两个 `1` 之间的 `0` 的数量也等于这个数值，则称这个序列是“美丽的”。

例如，`0101010` 和 `11111` 是“美丽的”，而 `10101` 和 `010100001000001010000` 就不是“美丽的”。

description: 给定一串由 `0` 和 `1` 组成的序列（保证 `1` 的数量不为 $0$），需要删除其中任意位置的一些元素，使得剩下的序列构成最长的美丽的串。

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

第二行输入一个字符串 $s$，只由 `0` 和 `1` 组成，表示这个序列。

outputFormat:
第一行输出一个数 $m$，表示删除后剩下的序列长度。

第二行输出通过删除操作后剩下的这个“美丽的”序列。

如果有多种方案，输出任意一种。**注意：全为 `0` 的串不是“美丽的”**。


title: [ROI 2019 Day 2] 学生座位

background:
翻译自 [ROI 2019 D2T2](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day2.pdf)。

学校要购买 $n$ 张双人桌用于新的功能教室。这些桌子有 $k$ 种类型，每种类型具有不同的尺寸。第 $i$ 种类型的桌子适合身高范围在 $L_i$ 到 $R_i$ 之间（包括边界）的学生坐，而对于其他学生来说，坐在这种桌子后是不舒服的，不舒服程度定义为学生身高与桌子适合的身高范围边界（即 $L_i$ 或 $R_i$）的差的绝对值。如果桌子适合学生，不舒服程度为零。

例如，如果 $L_i = 100,R_i = 120$，那么身高为 $80$ 的学生的不舒服程度为 $20$，身高为 $130$ 的学生的不舒服程度为 $10$，而身高为 $114$ 的学生的不舒服程度为 $0$。

$m$ 个班的学生将轮流进入功能教室上课，每个班级恰好有 $2n$ 名学生。购买的桌子将被摆放在教室中，每张桌子坐两名学生。

description:
已知每个学生在每个班中的身高，需要购买 $n$ 张桌子并安排每个班的学生的座位，以使得在教室中学习的所有学生的总不舒服程度最小。

请编写一个程序，根据每个桌子类型的信息和每个班中学生的身高值，确定通过购买桌子并以最优方式安排学生座位所能实现的不舒服程度之和的最小值。

inputFormat:
输入的第一行包含三个整数 $m,n,k$，分别表示将在教室中学习的班级数量、需要购买的桌子数量以及不同桌子类型的数量。

接下来的 $k$ 行中，每行包含两个整数 $L_i$ 和 $R_i$，表示适合第 $i$ 种桌子的学生身高范围。

接下来的 $m$ 行中，每行包含 $2n$ 个整数 $h_1,h_2,\dots,h_{2n}$，表示这个班中每个学生的身高。

outputFormat: 输出一个数 $P$，表示通过购买桌子并以最优方式安排学生座位后，能实现的不舒服程度之和的最小值。


title: [ROI 2019 Day 2] 机器人高尔夫

background:
翻译自 [ROI 2019 D2T3](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day2.pdf)。

在“机器人奥林匹克运动会”中，有一个“机器人高尔夫比赛”。比赛场地是一个由 $n \times m$ 个单位方块组成的矩形。场地的行用数字 $1$ 到 $n$ 编号，列用数字 $1$ 到 $m$ 编号。每个单位方块由两个正整数 $r$ 和 $c$ 表示，分别代表它所在的行和列的编号。

两个机器人轮流在场地上移动一个特殊的“高尔夫球”，场地的某些方块上可能有洞。如果“高尔夫球”位于方块 $(r, c)$ 上，执行当前操作的机器人可以将其移动到方块 $(r + 1, c)$ 或方块 $(r, c + 1)$。如果“高尔夫球”位于最后一行或最后一列，机器人可以将其移动到场地的边界外。游戏会在以下两种情况下结束：“高尔夫球”超出了场地的边界，或者“高尔夫球”落到一个洞里。

每个洞对应一个整数 $v_i$，表示它的价值。游戏的结果等于游戏结束时“高尔夫球”所在洞的价值，如果“高尔夫球”超出了场地的边界，则结果为 $0$。先手机器人的目标是最小化游戏结果，而后手机器人的目标是最大化游戏结果。

description: 假设 $g(r, c)$ 表示当“高尔夫球”初始位于方块 $(r, c)$ 时，先手机器人不论对手怎么行动都可以达到的最小游戏结果。由于比赛开始前不知道初始方块，机器人开发者想要计算出所有格子对应的 $g(r, c)$ 的总和，即 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}g(i,j)$。

inputFormat:
第一行包含三个整数 $n,m,k$，分别表示行数、列数和洞的个数。

接下来的 $k$ 行，每行包含三个整数 $r_i,c_i,v_i$，分别表示洞所在的行、列编号和洞的价值。没有两个洞会位于同一个方块上。


title: [ROI 2019 Day 2] 考古

background:
翻译自 [ROI 2019 D2T4](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day2.pdf)。

三〇一九年，在对古城市 Innopolis 进行挖掘时，考古学家发现了一件古代遗物——一个硬盘，里面存有一个文件，据推测，该文件包含了所有 ROI 题目的文本。

经过对文件的研究，发现其中的信息被编码成了一个由英文字母组成的字符串 $t$。题目文本相当长，并且包含了许多重复的内容，因此文件以压缩形式存储在硬盘上。解压缩文件使用以下算法：

在解压缩过程中，将生成一个由小写英文字母组成的字符串 $t$。初始时，字符串 $t$ 为空。压缩文件包含 $n$ 个块，必须按顺序处理每个块。每个块具有两种类型之一。
- 块 `1 w`，其中 $w$ 是一个字符串。处理此类块时，在字符串 $t$ 的末尾添加字符串 $w$。
- 块 `2 pos len`，其中 $pos$ 和 $len$ 是正整数。假设字符串 $t$ 中的字符从 $1$ 开始编号。处理此类块时，将字符串 $t$ 中从位置 $pos$ 开始的 $len$ 个连续字符依次添加到字符串 $t$ 的末尾。如果 $len$ 的值足够大，刚刚添加的一些字符可能会在处理同一块时再次使用。

description:
考古学家们决定统计一个算法在 ROI 中考察的次数。为此，他们构建了一个由小写英文字母组成的字符串 $p$，并希望找出这个字符串在解压缩后的字符串 $t$ 中的出现次数。

如果长度为 $m$ 的字符串 $p$ 作为子串从位置 $i$ 开始出现，那么从第 $i$ 个字符开始的连续 $m$ 个字符串将是字符串 $p$。例如，字符串 `aba` 在字符串 `ababaaba` 中作为子串出现三次，分别从第 $1,3,6$ 个字符开始。

请编写一个程序，确定给定字符串 $p$ 在解压缩后的字符串 $t$ 中出现的次数。

inputFormat:
第一行包含两个自然数 $m$ 和 $n$，分别表示字符串 $p$ 的长度和压缩文本中的块数。

第二行包含一个非空字符串 $p$，由小写英文字母组成。

接下来的 $n$ 行，包含按照题目背景的格式给出的块的描述。

outputFormat: 输出一个整数，表示字符串 $p$ 在文本中出现的次数。


title: [NordicOI 2023] ChatNOI

background: 翻译自 [NordicOI 2023 A 题](https://noi23.kattis.com/contests/noi23/problems/chatnoi) ChatNOI。

description:
你正在和你的机器人玩一个对话游戏，规则是这样的：

首先给定一个包含了 $n$ 个字符串的仅含小写字符组 $w$ 和一个数字 $k$。

定义一段字符的质量为其每个长度为 $k+1$ 的连续段的在 $w$ 中出现的次数的最小值。

有 $q$ 次询问，每次给定 $m_i$ 与 $k$ 个字符串，你需要接下来构造 $m_i$ 个字符串，使得这个字符串组质量最大，只需输出任意一个。

inputFormat:
第一行一个整数 $n(1 \leq n \leq 5 \times 10^5)$ 和 $k (1 \leq k < n)$。

第二行一句包含 $n$ 个单词的句子 $w_i( 1\leq|w_i|
\leq10)$。

第三行一个整数 $q(1 \leq q \leq 5 \times 10^5)$，表示一共有 $q$ 次询问。

然后 $q$ 行，每行一个数 $m_i$ 和长度为 $k$ 的 $s$ 的子字符串。

outputFormat: 你需要对于每个询问，输出 $k$ 之后的 $m_i$ 个单词。

samples:
13 2
ullen dullen doff kikke lane koff koffe lane bikke bane ullen dullen doff
3
1 ullen dullen
2 ullen dullen
3 ullen dullen

samples:
8 1
buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo
1
7 buffalo

samples:
16 1
have you not heard about the bird the bird bird bird the bird is the word
8
1 have
1 you
1 not
1 heard
1 about
1 the
1 bird
1 is

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

令 $M = \sum m_i$。

- Subtask 1（5 points）：$k < n \leq 100$，$k = 1$，$1 \leq q \leq 100$，$m_i = 1$。
- Subtask 2（7 points）：$k < n \leq 5 \times 10^5$，$1 \leq k \leq 10$，$1 \leq q \leq 100$，$m_i = 1$。
- Subtask 3（17 points）：$k < n \leq 6$，$1 \leq k \leq 10$，$1 \leq q \leq 10$，$1 \leq m_i \leq 6$。
- Subtask 4（18 points）：$k < n \leq 5000$，$1 \leq k \leq10$，$1 \leq q \leq 5000$，$q \leq M \leq 5000$。
- Subtask 5（24 points）：$k < n \leq 5 \times 10^5$，$1 \leq k \leq 10$，$1 \leq q \leq 10$，$q \leq M \leq 5 \times 10^5$。
- Subtask 6（16 points）：$k < n \leq 10^5$，$1 \leq k \leq10$，$1 \leq q \leq 10^5$，$q \leq M \leq 5 \times 10^5$。
- Subtask 7（13 points）：无特殊限制。

对于所有测试数据，$k < n \leq 5 \times 10^5$，$1 \leq k \leq 10$，$1 \leq q \leq 10^5$，$q \leq M \leq 5 \times 10^5$。


title: [NordicOI 2023] Ice Cream Machines

background: 翻译自 [NordicOI 2023 B 题](https://noi23.kattis.com/contests/noi23/problems/icecreammachines) Ice Cream Machines。

description:
在你的冰淇淋店里有 $n$ 个顾客在排队，店里一共有 $m$ 种口味，每个人都有想买的口味，但是很不幸，店内只有 $k$ 台机子，无法完全供应所有的口味，所以，如果下一个人要的和这台机子内原有的口味不同时，他需要清洗这台机子并更换成他喜欢的口味。

现在这 $n$ 个人按照从 $1 \sim n$ 的顺序买冰淇淋，你作为一个聪明绝顶的店主需要合理安排他们使用哪台机子，使得清洗机子的次数最少，输出这个最少次数。

注意一台机子如果之前没人用的时候默认需要被清洗（自始至终没人用则不需要）。

inputFormat:
第一行三个整数 $n (1 \leq n \leq 2 \times 10^5)$，$m (1 \leq m \leq 2 \times 10^5)$ 和 $k (1 \leq k \leq 2 \times 10^5)$，分别表示一共有 $n$ 个人，店里有 $m$ 种口味的冰淇淋和 $k$ 台机子。

然后 $n$ 行，每行一个整数 $c_i (1 \leq c_i \leq m)$，表示第 $i$ 个人喜欢吃的口味编号。

outputFormat: 输出清洗次数最少时所需的次数。

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

- Subtask 1（7 points）：$n \le 1000$，$m \leq 10$，$k = 1$。
- Subtask 2（12 points）：$n \le 1000$，$m \leq 10$，$k \leq 2$。
- Subtask 3（22 points）：$n \leq 1000$，$m \leq 10$，$k \leq 5$。
- Subtask 4（11 points）：$n \leq 1000$，$m \leq 200$，$k \leq 100$。
- Subtask 5（14 points）：$n \leq 2 \times 10^5$，$m \leq 500$，$k \leq 100$。
- Subtask 6（13 points）：$n \leq 2 \times 10^5$，$m \leq 2 \times 10^5$，$k \leq 100$。
- Subtask 7（21 points）：无特殊限制。

对于所有测试数据，$1 \le n \le 2\times 10^5$，$1 \leq m \leq 2 \times 10^5$，$1 \leq k \leq 2 \times 10^5$，$1 \leq c_i \leq m$。


title: [NordicOI 2023] Island Alliances

background: 翻译自 [NordicOI 2023 C 题](https://noi23.kattis.com/contests/noi23/problems/islandalliances) Island Alliances。

description:
海面上有 $n$ 个岛屿，其中有 $m$ 对岛屿关系恶劣，但是由于天气恶劣，岛屿肯定不能单独生存，所以有些岛屿提议“联盟”。

现有 $q$ 次联盟请求，每次包含了一对 $(a_i,b_i)$，表示 $a_i$ 想要与 $b_i$ 联盟，但是，考虑到某些岛屿恶劣的关系，所以这个提议不一定成立，如果 $a_i$ 原本所在联盟的岛屿都**不和** $b_i$ 所在的联盟的所有岛屿存在恶劣的关系，则两者可以同意联盟，否则将不同意。

注意此处一但同意了联盟，则两个岛屿所在联盟立即并成一个联盟。

inputFormat:
第一行三个整数 $n$，$m$ 和 $q$，依次表示有 $n$ 个岛屿，$m$ 对关系恶劣的岛屿和 $q$ 次提议。

接下来 $m$ 行，每行一对整数 $(u_i,v_i)$，表示 $u_i$ 座岛屿和 $v_i$ 座岛屿关系恶劣。

然后 $q$ 行，每行两个整数 $a_i$ 和 $b_i\ (a_i \neq b_i)$，表示 $a_i$ 座岛屿想与 $b_i$ 座岛屿联盟。

outputFormat: 对于每个提议，如果同意则输出 `APPROVE`，否则输出 `REFUSE`。

samples:
REFUSE
APPROVE
APPROVE
APPROVE
REFUSE
APPROVE
APPROVE

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

- Subtask 1（15 points）：$2 \leq n \leq 500$，$1 \leq m \leq 10^5$，$1 \leq q \leq 10^5$。
- Subtask 2（17 points）：$2 \leq n \leq 10^5$，$1 \leq m \leq 250$，$1 \leq q \leq 10^5$。
- Subtask 3（20 points）：$2 \leq n \leq 5000$，$1 \leq m \leq 5000$，$1 \leq q \leq 10^5$。
- Subtask 4（23 points）：保证不同意提议的情况最多只有一次。
- Subtask 5（25 points）：无特殊限制。

对于所有测试数据，$2 \le n \le 10^5$，$1 \le m,q \le 10^5$，$1 \le a_i,b_i \le n$，且每对 $(a_i,b_i)$ 互不相同。


title: [ROI 2021 Day 1] 穿孔卡片

background:
翻译自 [ROI 2021 D1T1](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day1.pdf)。

穿孔卡片是一条由 $m$ 个小方格组成的带状物，每个小方格要么包含一个小写英文字母，要么是一个孔洞。

description:
有 $n$ 张这样的穿孔卡片。给定一个长度为 $m$ 的字符串 $s$，将所有的穿孔卡片按照一定顺序排列，使得将它们从上到下依次叠放后可以变成 $s$。换句话说，要确定穿孔卡片的顺序，它们将叠放在一起，并考虑任意位置 $i(1 \le i \le m)$，字符串 $s$ 的第 $i$ 个字符必须与第 $i$ 个位置上第一个包含字母的那张穿孔卡片上的字符相同。

如果对于某个 $i$，不存在任何一个穿孔卡片上的这个位置有字母，那么就无法得到目标字符串 $s$。

inputFormat:
第一行包含两个整数 $n,m(1 \le n,m \le 100,000)$，分别表示穿孔卡片的数量和格子的数量。

第二行包含一个长度为 $m$ 的字符串 $s$，由小写英文字母组成。

接下来的 $n$ 行中，每行输入一张穿孔卡片的信息。

先输入一个整数 $k_i(0\le k_i\le m)$，表示该穿孔卡片上有多少个带字母的位置。保证所有 $k_i$ 的总和不超过 $200,000$。

然后是该穿孔卡片上字母的描述：对于每个整数 $j(1 \le j \le k_i)$，有一个整数 $a_{i,j}$ 和一个字符 $c_{i,j}$（$1 \le a_{i,j} \le m$，$c_{i,j}$ 是一个小写英文字母），表示位置 $a_{i,j}$ 上的字符是 $c_{i,j}$。其余位置都是孔洞。保证每张穿孔卡片上的带字母的位置按升序排列，即 $\forall1 \le j < k_,a_{i,j} < a_{i,{j+1}}$。

outputFormat:
如果存在一种正确排列穿孔卡片的方法，输出 $n$ 个整数 $p_1,p_2,\dots,p_n(1 \le pi \le n)$，其中 $p_1$ 表示最上面的卡片编号，$p_2$ 表示第二张卡片编号，依此类推，$p_n$ 表示最下面的卡片编号。

如果存在多个可能的答案，可以输出任意一个。如果不存在一种正确排列穿孔卡片的方法，输出 `-1`。


title: [ROI 2021 Day 1] 手机游戏

background: 翻译自 [ROI 2021 D1T2](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day1.pdf)。

description:
给定一个由 $n$ 个水晶组成的序列，从左到右排列。每个水晶属于 $k$ 种类型之一，用前 $k$ 个英文字母表示。因此，水晶序列可以用一串英文字母表示。

在游戏的一步中，可以从序列中移除一个水晶。玩家的目标是通过用允许的删除方式，得到字典序最小的字符串。

允许的删除方式由大小为 $k\times k$ 的表 $A$ 定义，表中的元素只包含 $0$ 和 $1$。如果 $A_{i,j} = 1$，则表示当前面紧邻它的水晶是类型 $i$ 时，允许删除类型 $j$ 的水晶。这些操作可以按任意顺序执行。

字符串 $x$ 在字典序上小于字符串 $y$，需要满足以下条件之一：
- 存在一个位置 $m$，在两个字符串中都存在，且在该位置之前，两个字符串的字符是相同的，但是 $x$ 的第 $m$ 个字符小于 $y$ 的第 $m$ 个字符，
- 字符串 $x$ 是字符串 $y$ 的严格前缀（即从字符串 $y$ 末尾删除一个或多个字符得到）。

举个例子，`ccf` 的字典序小于 `cff`，因为 `ccf` 的第 $2$ 位（`c`）小于 `cff` 的第 $2$ 位（`f`）；而 `noi` 的字典序小于 `noip`，因为 `noi` 是 `noip` 的严格前缀。

inputFormat:
第一行给出两个整数 $k$ 和 $n$（$1 \le k \le 26,1 \le n \le 500000$），分别表示水晶的种类数量和初始水晶序列的长度。

接下来的 $k$ 行给出表 $A$，第 $i$ 行包含 $k$ 个字符，都是 $0$ 或 $1$。第 $i$ 行第 $j$ 列的字符为 $A_{ij}$。

最后一行是由 $n$ 个小写英文字母组成的字符串，表示初始水晶序列。保证字符串中只包含前 $k$ 个英文字母（如前七个英文字母分别是 `a`，`b`，`c`，`d`，`e`，`f`，`g`），第 $i$ 个字母代表第 $i$ 种类型的水晶。

outputFormat: 输出可以通过操作得到的字典顺序最小的字符串。


title: [NOI2023] 字符串

description:
小 Y 是一名大学生，最近正在研究字符串方向的问题。

小 Y 了解到关于字符串的如下定义:

- 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其子串 $s[l: r]$（$1 \leq l \leq r \leq n$）为选择 $s[l], s[l+1], \dots, s[r]$, 将其顺次拼接得到的新字符串。
- 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其翻转后的结果 $R(s)$ 为将 $s[n], s[n-1], \dots, s[1]$ 顺次拼接，也就是将字符串反序拼接得到的字符串。
- 给定两个长度均为 $n$ 的字符串 $a[1: n], b[1: n]$，我们定义 $a$ 的字典序小于 $b$ 当且仅当存在 $1 \leq i \leq n$，使得对于任意 $1 \leq j < i$，$a[j] = b[j]$，且 $a[i] < b[i]$。

在了解了上述定义后，小 Y 想到了这样的问题:

给定一个长度为 $n$ 的字符串 $s[1: n]$。有 $q$ 次询问，每次询问给定两个参数 $i, r$。你需要求出有多少 $l$，满足如下条件:
- $1 \leq l \leq r$。
- $s[i: i+l-1]$ 字典序小于 $R(s[i+l: i+2l-1])$。

小 Y 想求助你帮忙解决这一问题。

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

输入的第一行包含两个整数 $c, t$，分别表示测试点编号和测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

输入的第一行包含两个正整数 $n, q$，表示字符串长度和询问次数。

输入的第二行包含一个长度为 $n$ 的仅包含小写字母的字符串 $s$。

输入的接下来 $q$ 行，每行包含两个正整数 $i, r$。表示一次询问，保证 $i+2r-1 \leq n$。

outputFormat: 对于每一组测试数据的每一次询问，输出一行一个整数，表示满足条件的 $l$ 的个数。

samples:
0 2
9 3
abacababa
1 4
2 4
3 3
9 3
abaabaaba
1 4
2 4
3 3

samples:
见附件中的 string/string2.in。
见附件中的 string/string2.ans。

samples:
见附件中的 string/string3.in。
见附件中的 string/string3.ans。

samples:
见附件中的 string/string4.in。
见附件中的 string/string4.ans。


title: [NOI2023] 合并书本

description:
小 C 有 $n$ 本书，每本书都有一个重量，他决定把它们合并成一摞。

每一次合并小 C 可以把一摞书放到另一摞书上面，使得它们合并到一摞。如果小 C 把第 $i$ 摞书放到第 $j$ 摞书上面，小 C 需要消耗的体力为**第 $i$ 摞书的重量**加上**两摞书的磨损值之和**。

初始时每本书自成一摞且磨损值均为 $0$。每当小 C 将两摞书合并后，形成的新的一摞书的磨损值为合并前的两摞书的磨损值的**较大值的两倍再加一**，重量为合并前的两摞书的**重量之和**。

你的任务是设计出合并的次序方案，使小 C 耗费的体力最少，并输出这个最小的体力耗费值。

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

输入的第一行包含一个正整数 $t$，表示数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

输入的第一行包含一个正整数 $n$，表示有 $n$ 本书。

输入的第二行包含 $n$ 个正整数，第 $i$ 个数 $w_i$ 表示第 $i$ 本书的重量。

outputFormat: 对于每组测试数据输出一行一个整数，表示将 $n$ 本书合并成一摞需要消耗的最少体力。

samples:
见附件中的 book/book2.in。
见附件中的 book/book2.ans。

samples:
见附件中的 book/book3.in。
见附件中的 book/book3.ans。

samples:
见附件中的 book/book4.in。
见附件中的 book/book4.ans。


title: [ROI 2021 Day 1] 工作报告

background:
翻译自 [ROI 2021 D1T4](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day1.pdf)。

公司中有 $n$ 个员工，编号从 $1$ 到 $n$。编号为 $1$ 的员工是公司的创始人，其他员工都有且只有一个直接上级。公司的组织结构形成了一棵树，每个节点的父节点是它的上级，而子节点是它的下属。拥有下属的员工被称为经理，其他员工被称为顾问。公司的结构保证每个经理最多有 $8$ 个下属，包括创始人。

创始人决定向投资者们汇报最近产品改进的情况。每个改进都是来自公司的某个顾问的工作成果。所有改进按照它们发生的时间顺序进行编号。

每个顾问需要选择一个改进并向他的经理汇报。因此，每个顾问的报告仅包含一个改进。

每个经理，包括创始人在内，需要汇总他们下属的报告，并按照报告的顺序将它们直接连续地组合起来。例如，如果第一个经理的报告包含改进 $[1, 3]$，而第二个经理的报告包含改进 $[2, 4, 10]$，那么可以得到两种组合结果：$[2, 4, 10, 1, 3]$ 或者 $[1, 3, 2, 4, 10]$，其他组合是不可能的。

description: 创始人希望以尽可能合理的方式讲述这些改进，因此他希望在他的报告中改进按照编号的升序排列。请帮助每个顾问选择要汇报的改进，并帮助每个经理选择组合下属报告的顺序，以使得创始人的报告中的改进能够按照时间顺序排列。

inputFormat:
第一行包含一个整数 $n $（$2 \le n \le 100000$），表示公司的员工数量。接下来的 $n$ 行描述每个员工，每行包含以下内容之一：
- 如果员工是经理或创始人，则以数字 $1$ 开头，接下来是数字 $k_i $（$1 \le k_i \le 8$），表示该经理的下属数量，然后是 $k_i$ 个不同的数字，范围在 $2$ 到 $n$，表示是其下属的员工编号。
- 如果员工是顾问，则以数字 $2$ 开头，接下来是数字 $m_i$，表示他可以汇报的改进数量，然后是 $m_i$ 个不同的整数，范围在 $1$ 到 $100000$，表示对应改进的编号。

保证每个改进都仅被一个顾问提及，即所有顾问提到的改进都是不同的。

outputFormat:
如果无法组合报告，输出 `No`。

如果能够组合报告，输出 `Yes`，然后你可以按照员工编号的顺序输出以下内容：
- 如果员工是经理，则输出他的下属在组合报告中的顺序。
- 如果员工是顾问，则输出他需要汇报的改进编号。

注：如果不输出组合报告的方式但正确判断了是否能够组合报告，将会得到 $10\%$ 的部分分。

hint:
### 样例解释：

在样例二中，没有输出具体的组合方法，所以只能得到部分分。正确的输出应该是这样的：
```text
Yes
2 3
1
2
```
在样例三中，每个顾问都只能选择那唯一的改进编号。第三位经理有两种可能的报告方式：$[1, 3]$ 或 $[3, 1]$。第一位经理有四种可能的报告方式，考虑到第三位经理的所有报告可能性：$[1, 3] + [2] = [1, 3, 2],[2] + [1, 3] = [2, 1, 3],[3, 1 ] + [2] = [3, 1, 2],[2] + [3, 1] = [2, 3, 1]$，但是在这些报告中没有一个改进是按照时间顺序排序的。

### 数据范围：

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

对于 $100\%$ 的数据，$n,\sum m_i \le 100 000$ 且 $\max k_i\le8$。


title: [语言月赛 202308] 小粉兔做麻辣兔头

description:
粉兔喜欢吃麻辣兔头，麻辣兔头的辣度分为若干级，用数字表示，数字越大，兔头越辣。为了庆祝粉兔专题赛 #1 的顺利举行，粉兔要做一些麻辣兔头送给扶苏、Max、小 F 和 Z，但是，粉兔不知道这些麻辣兔头应该做成什么辣度，TA 决定使用投骰子的方法来决定。

粉兔使用的骰子**不是**标准的 $6$ 面骰子。粉兔的骰子，每一面上写有 $1\sim 6$ 中的一个数字，$1$ 的对面为 $2$，$3$ 的对面为 $4$，$5$ 的对面为 $6$。粉兔将 $N$ 个骰子摞成一个骰子塔，从下向上数第 $i$ 个骰子，向上的一面写的数字为 $P_i$。

粉兔决定将麻辣兔头的总辣度做成这个骰子塔暴露在空气中所有面上数字之和，请问，总辣度为多少？

inputFormat:
输入共两行。

输入的第一行为一个整数 $N$。

输入的第二行为 $N$ 个整数，第 $i$ 个为 $P_i$。

outputFormat: 输出一行一个整数，代表兔头总辣度。

hint:
### 样例 1 解释

侧面上数字总和为 $84$，顶上数字为 $6$，加和得答案为 $90$。

### 数据规模与约定

- 对于 $20\%$ 的数据，$N=1$；
- 对于另外 $20\%$ 的数据，$P_i=6$；
- 对于 $100\%$ 的数据，$1 \le N \le 10^6$，$1 \le P_i \le 6$。


title: [ROI 2021 Day 2] 莫斯科数字

background:
翻译自 [ROI 2021 D2T1](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day2.pdf)。

你可能熟悉罗马数字，并且也听说过莫斯科是第三个罗马的说法，所以我们隆重推出莫斯科数字。这是罗马数字的进阶版本，与之类似。在莫斯科数字系统中，数字由大写英文字母 `A` 到 `Z` 表示。每个数字对应一个特定的值：

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

莫斯科数字规则如下：每个数字的值等于由它构成的各个数字的总和。数字可以有正负之分。如果一个数字右侧没有比它更大的数字，则该数字的值等于它本身；否则，该数字的值等于其本身取负。例如：

- 「`BBA`」的值为 $5 + 5 + 1 = 11$；
- 「`BBBC`」的值为 $-5 + (-5) + (-5) + 10 = -5$；
- 「`ABC`」的值为 $-1 + (-5) + 10 = 4$；
- 「`BAC`」的值为 $-5 + (-1) + 10 = 4$；
- 「`ACA`」的值为 $-1 + 10 + 1 = 10$；
- 「`CFF`」的值为 $-10 + 500 + 500 = 990$。

description: 给定了一些数字，每个数字由大写英文字母组成（即莫斯科数字），但是一部分被替换成了问号。对于每个数字，需要确定在将问号替换为莫斯科数字字母后，可以得到的最大数字。

inputFormat:
第一行是一个整数 $t$，表示数据组数，即数字的数量（$1 \le t \le 50000$）。

接下来的 $t$ 行，每行一个字符串 $s_i$，由大写英文字母和问号组成。所有字符串的长度之和不超过 $300000$。

outputFormat: 对于每个输入，输出两行，都表示的是将问号替换为莫斯科数字字母后可以得到的最大数字。第一行是以十进制表示的最大数字值，第二行就是替换后的这个最大莫斯科数字。


title: [ROI 2021 Day 2] 树制游戏

background:
翻译自 [ROI 2021 D2T2](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day2.pdf)。

Vasya 最近想到了一种新的娱乐方式。他想让一个有 $n$ 个顶点和 $2\times(n−1)$ 条边的有向连通图成为他的玩具。这个图满足以下条件：对于图中的每条边 $(u, v)$，都存在一条反向的边 $(v, u)$。换句话说，这个图是由一棵树转化而来的，其中每条无向边都被分成两个方向相反的边。

Vasya 将这样一对边 $(e_1, e_2)$ 称为“gadget”，其中 $e_1$ 的终点与 $e_2$ 的起点相同，或者 $e_2$ 的终点与 $e_1$ 的起点相同（特别地，两条方向相反的边也是一种“gadget”）。简单来说，“gadget”就是一条长度为 $2$ 的路径。Vasya 的娱乐方式是将图中的边划分为互不相交的“gadget”。当然，对于原始图来说，这很容易做到。

但是，Vasya 的好朋友 Petya 从树中删除了 $2k$ 条有向边，使得图中剩下 $m = 2\times (n - 1) - 2\times k$ 条有向边。

description: 现在 Vasya 想知道是否可以将剩下的边划分为互不相交的“gadget”，如果可能的话，还要找出这种划分的方法。

inputFormat:
第一行包含两个整数 $n$ 和 $m$，分别表示顶点数和剩余边数。保证 $m$ 是偶数。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示剩余边的起点和终点。

outputFormat:
如果无法将边分成“gadget”，则输出 `No`。

否则，输出 `Yes`，然后输出 $\frac{m}{2}$ 行，每行包含 $4$ 个数字，表示每个“gadget”中的两对边。每条边由起点和终点两个数字表示。


title: [ROI 2021 Day 2] 砍树

background:
翻译自 [ROI 2021 D2T3](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day2.pdf)。

“2D” 组织负责发放伐木许可证。他们收到了沿公路的伐木申请。

公路上有 $n$ 棵树，其中第 $i$ 棵树生长在坐标为 $x_i$ 的点上，高度为 $h_i$。关于这些树的信息被排序，满足 $x_1 < x_2 < \dots < x_{n-1} < x_n$。

可以按以下方式逐个砍伐树木：将树砍倒，并让它向左或向右倒下。为了防止树木在倒下时受损，它不应碰到距离它自身高度以内的未砍伐的树木。换句话说，如果位于坐标为 $x_i$，高度为 $h_i$ 的树木向右倒下，则不应该存在坐标为 $x_j$ 的未砍伐的树木，使得 $x_i < x_j < x_i + h_i$。如果同一树木向左倒下，则不应存在坐标为 $x_j$ 的未砍伐的树木，使得 $x_i − h_i < x_j < x_i$。

左边界 $x_1$ 处的树木和右边界 $x_n$ 处的树木旁边有重要的建筑物，因此不允许倒掉的树木落在区间 $[x_1, x_n]$ 之外。换句话说，如果 $x_i − h_i < x_1$，坐标为 $x_i$，高度为 $h_i$ 的树木不能向左倒下；如果 $x_i + h_i > x_n$，坐标为 $x_i$，高度为 $h_i$ 的树木不能向右倒下。

description:
组织收到了 $q$ 个伐木申请。每个申请由两个数字 $l_i$ 和 $r_i$ 组成，表示申请者希望砍伐第 $l_i$ 到第 $r_i$ 个树木（包括边界）。

在执行申请的过程中，只允许砍伐从 $l_i$ 到 $r_i$ 编号的树木。被砍伐的树木可以倒到 $l_i$ 的左边或 $r_i$ 的右边的区域，但不能超出 $[x_1, x_n]$ 范围，也不允许触碰 $l_i$ 到 $r_i$ 范围之外的其它树木。

对于每个申请，需要计算在不损坏任何树木的情况下可以砍倒的最大树木数量。每个申请都应独立处理（只是申请了，树没有真的被砍掉）。

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

接下来的 $n$ 行描述每棵树，每行包含两个整数 $x_i$ 和 $h_i$。保证 $x_1 < x_2 < \dots < x_n$。

然后是 $q$ 个伐木申请的描述，每个申请占一行。第i行包含两个整数 $l_i$ 和 $r_i$。

outputFormat: 对于每个申请，输出可以砍伐的最大树木数量。


title: [ROI 2021 Day 2] 旅行

background:
翻译自 [ROI 2021 D2T4](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day2.pdf)。

Sky 决定成为旅行 up 主，发布在全国各个城市旅行的视频。这个国家有 $n$ 个城市，编号从 $1$ 到 $n$。城市 $1$ 是国家的首都。城市之间有 $m$ 条双向道路，编号从 $1$ 到 $m$，每条道路连接两个不同的城市。同时，同一对城市可以通过多条不同的道路连接。从任何一个城市都能够通过道路到达其他任何一个城市。

Sky 和 Aqua 不能分开，所以 Sky 计划和 Aqua 一起从首都出发前往另一个城市，但目前尚未选择具体是哪个城市。到达城市 $k$ 的旅行路线将由城市 $s_1, s_2,\dots,s_q$ 和道路 $r_1,r_2,\dots,r_{q-1}$ 组成，其中：
- $s_1 = 1,s_q = k$；
- 道路 $r_i$ 连接城市 $s_i$ 和 $s_{i+1}$；
- Sky 和 Aqua 不会两次经过同一条道路，因此所有的 $r_i$ 都是不同的。可以多次经过同一个城市，包括旅行起始城市 $1$ 和旅行结束城市 $k$。

对于每条道路，Sky 都计算了在该道路上进行旅行拍摄的视频时长，第 $i$ 条道路的视频时长为 $t_i$。

在旅行过程中，Sky 和 Aqua 都会选择旅行路线中的其中一条道路并拍摄与该道路相关的视频。Sky 喜欢拍短视频，因此 Sky 会选择 $t_i$ 最小的道路；而 Aqua 喜欢拍长视频，因此 Aqua 会选择 $t_i$ 最大的道路。

两个视频的总时长为 $\min\limits_{1\le i \le q-1}t_{r_{i}} + \max\limits_{1\le i \le q-1}t_{r_{i}}$。

description: Sky 不愿意浪费素材，于是想把两个视频拼到一起，并发布到某知名视频网站上。因为现在短视频更受欢迎，所以 Sky 希望尽量减少两个视频的总时长。为了选择旅行的目的地和路线，需要计算出每个目的地 $k$ 在从城市 $1$ 到城市 $k$ 的所有可能路线中两个视频的最小总时长。

inputFormat:
第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 300000$，$1 \le m \le 300000$），分别表示城市和道路的数量。

接下来的 $m$ 行包含道路的描述。第 $i$ 行包含三个整数 $u_i,v_i,t_i$（$1 \le u_i,v_i \le n$，$u_i \ne v_i$，$0 \le t_i \le 10^9$），分别表示连接该道路的城市编号以及在该道路上拍摄视频的时长。

保证通过现有的道路可以从任何一个城市到达任何其他城市。

outputFormat: 对于每个 $2 \le k \le n$，输出从城市 $1$ 到城市 $k$ 的旅行中 Sky 和 Aqua 的视频总时长的最小值。


title: 图的遍历（简单版）

description: 给出 $N$ 个点，$M$ 条边的有向图，对于每个点 $v$，求 $A(v)$ 表示从点 $v$ 出发，能到达的编号最大的点。

inputFormat:
第 $1$ 行 $2$ 个整数 $N,M$，表示点数和边数。

接下来 $M$ 行，每行 $2$ 个整数 $U_i,V_i$，表示边 $(U_i,V_i)$。点用 $1,2,\dots,N$ 编号。


title: [ROI 2022 Day 1] 体育课

background:
翻译自 [ROI 2022 D1T1](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day1.pdf)。

在体育课前，一个由 $n$ 名学生组成的班级排成了一列。班级中的所有学生身高不同。在队列的第 $i(1\le i\le n)$ 个位置上站着一个身高为 $p_i(1\le p_i\le n)$ 的学生。

体育老师在课堂开始时可能想要改变学生在队列中的顺序。为此，他可以执行以下操作一次：选择从第 $l$ 到第 $r$ 位置（$1 \le l \le r \le n$）的一段队列，并将这段队列中的学生按照从左到右的升序进行排序。例如，如果 $n = 5$，并且最初学生们的顺序是 $[5, 2, 4, 1, 3]$，而老师选择 $l = 1,r = 4$，则在排序后学生们的顺序将变为 $[1, 2, 4, 5, 3]$。

description:
老师想要使得两个特定的学生尽可能远离彼此。学生之间的距离等于他们所站位置的编号之差。对于每对学生，老师想要知道在执行一次排序操作后他们可以达到的最大距离。请帮助老师算出这些值的总和。

如果用 $d(i, j)$ 表示老师通过选择一段队列并进行排序可以达到的刚开始在位置 $i$ 和 $j$ 上的学生之间的最大距离，需要计算的就是 $\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}d(i,j)$。

inputFormat:
第一行包含一个整数 $n$，表示班级中的学生数量（$2 \le n \le 3,000$）。

第二行包含 $n$ 个整数 $p_1,\dots , p_n$，表示队列中每个学生的身高（$1 \le p_i \le n$）。

保证所有 $p_i$ 都是不同的。


title: 半彩三重奏

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

帆帆不满足于只构建一棵深蓝之树，他觉得深蓝之树只有深蓝色太单调了，于是想给这棵树染上颜色。

description:
由于现在已经来到了魔幻的龙年，帆帆的深蓝之树已经被染上了颜色，结点 $i$ 的颜色为 $a_i$。

帆帆是一个喜新厌旧的人，在接下来的 $q$ 天中，他每天都会改变他喜欢的颜色，第 $i$ 天他喜欢的两种颜色是 $x_i,y_i$（$x_i\neq y_i$）。

但是为了照顾自己的树，他需要经常在树上移动，并且只会经过自己喜欢的颜色。

具体来说，第 $i$ 天，帆帆会选择一个有序结点对 $(u,v)$，然后沿着 $u\to v$ 的唯一简单路径移动，并且中间经过的结点（包含 $u,v$）颜色必须 $\in \{x_i,y_i\}$（$u$ 可以等于 $v$），之后可以抽取一次宵宫。

每一天你都需要抽取一个满命宵宫，然后告诉帆帆有多少种可能的选择有序结点对的方案。

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

接下来一行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ 表示每个点的颜色。

接下来一行 $n-1$ 个正整数 $p_2,p_3,\cdots,p_n$，表示对所有 $2\le i\le n$，树上存在一条边 $(p_i,i)$。

接下来 $q$ 行，每行两个正整数 $x_i,y_i$。

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


title: [ROI 2022 Day 1] 采购优化

background:
翻译自 [ROI 2022 D1T2](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day1.pdf)。

租赁滑雪设备的网点网络是一棵根节点为 $1$ 的树，由 $n$ 个节点组成，编号从 $1$ 到 $n$。每个节点上都有一个租赁点。位于第 $i$ 个节点的租赁点需要以 $c_i$ 卢布的价格购买设备套件。

设 $a_i$ 表示在位于节点 $i$ **子树的所有租赁点中**将要购买的滑雪设备套件的总数。根据市场调研，这个值必须要满足 $l_i\le a_i\le r_i$。

description: 需要确定在赛季开始时每个租赁点需要购买多少套设备，以便对于网络中任何一个子树，设备套件的总数量都在市场营销人员指定的范围内，并且购买的所有设备套件的总成本最小，或是否不可能满足所有市场营销条件。

inputFormat:
每个测试点包含多个测试数据。第一行给出一个整数 $t$，表示测试数据的数量。接下来是 $t$ 个测试数据。

每个测试数据的第一行给出一个整数 $n$（$1\le n\le100,000$），表示树中的节点数量。

接下来一行给出 $n-1$ 个整数 $p_2,p_3,\dots,p_n$（$1\le p_i<i$），表示节点 $i$ 的父节点为节点 $p_i$。

接下来一行给出 $n$ 个整数 $c_1,\dots,c_n$（$1\le c_i\le10^9$），其中 $c_i$ 表示 $i$ 号租赁点购买一个设备套件的价格。

接下来 $n$ 行，每行给出两个整数 $l_i$ 和 $r_i$（$0\le l_i\le r_i\le10^9$），表示对位于节点编号为 $i$ 的租赁点的子树中设备套件的总数的限制。

保证所有测试用例中 $n$ 的总和不超过 $100,000$。

outputFormat:
对于每个测试数据，以下面的格式输出答案。

如果无法满足所有市场营销条件，请输出 `-1`。

否则，在第一行中输出购买整个网络的滑雪设备需要花费的最小卢布数。在第二行中，输出 $n$ 个整数 $b_i$，其中 $b_i$ 表示编号为 $i$ 的租赁点需要购买的设备套件的数量。如果有多种方式以最小的成本满足所有市场营销条件，可以输出其中一种。


title: [ROI 2022 Day 1] 滑梯

background:
翻译自 [ROI 2022 D1T3](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day1.pdf)。

佩奇和她的弟弟乔治来到水上公园。乔治喜欢从滑梯上滑行，这个滑梯可以用三角网格的一部分来描述，其中的顶点是滑梯的节点。在每个节点上，可以选择继续沿着哪个管道前进——向左下或向右下。滑梯从上到下编号，从 $0$ 层开始。在第 $0$ 层，滑梯只有一个节点，在第 $1$ 层有两个节点，在第 $i$ 层有 $i + 1$ 个节点。总共有 $n + 1$ 层。每次从上到下滑都要经过恰好 $n$ 个管道。每个节点都有坐标，用两个数字 $(r, c)$ 表示在第 $r$ 层中从左边开始数的第 $c$ 个节点 ($0 \le c \le r \le n$)。请注意，每层和每层上的节点都是从 $0$ 开始编号的。如果乔治位于节点 $(r, c)$ 并向左下滑，他将进入节点 $(r + 1, c)$，如果他向右下滑，他将进入节点 $(r + 1, c + 1)$。

这是一个有 $5$ 层（$n=4$）的滑梯：

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

乔治想要从滑坡上滑下 $n + 1$ 次。在每次下滑之前，佩奇会给他一个指令，告诉他如何沿着滑坡滑行。每个指令由恰好 $n$ 个命令组成，要么是“向左下”，要么是“向右下”。乔治根据佩奇的命令从当前节点去往下一个节点。第一条指令只有“向右下”的命令。佩奇懒得想出新的指令，因此相邻两次下滑的指令只有一条命令不同：为了从第 $i$ 条指令得到第 $i + 1$ 条指令，需要将第 $a_i$ 个（不是第 $i$ 个）命令从“向右下”更改为“向左下”。每个命令只会被更改一次。到最后，第 $n+1$ 条指令将只包含“向左下”命令。可以证明，在这 $n+1$ 次下滑中，乔治会经过滑梯的每个节点（但不是每个管道）。

description:
在从水上乐园返回的途中，乔治遇到了以下问题。首先，考虑所有他滑过的管道的集合。给出两个节点的坐标：$(r_1, c_1)$ 和 $(r_2, c_2)$。你需要确定一个节点的坐标 $(r_3, c_3)$，使得从这个节点开始，通过这些他滑过的管道可以访问到节点 $(r_1, c_1)$ 和节点 $(r_2, c_2)$，并且在所有这样的节点中，它是最低的，即 $r_3$ 的值最大。可以证明，这样的节点总是存在且唯一。

乔治有很多个问题，但是因为他已经离开了水上乐园，所以他不能碰这个滑梯。他需要你帮忙回答他的所有问题！

inputFormat:
第一行给出一个整数 $n$（$1 \le n \le 500 000$）。

在第二行中，给出 $n$ 个整数 $a_1, a_2, \dots, a_n $（$1 \le a_i \le n$），其中 $a_i$ 是第 $i$ 次下滑后将要更改的命令的编号。保证所有的 $a_i$ 都是不同的。

在第三行中给出一个整数 $q $（$1 \le q \le 500 000$），表示乔治的问题数量。

在接下来的 $q$ 行中，每行给出四个整数 $r_{i,1}, c_{i,1}, r_{i,2},c_{i,2} $（$0 \le r_{i,1}, r_{i,2} \le n$，$0 \le c_{i,1} \le r_{i,1}$，$0 \le c_{i,2} \le r_{i,2}$），表示第 $i$ 个问题的两个节点的坐标。

outputFormat: 输出 $q$ 行，每行输出两个整数 $r_{i,3}$ 和 $c_{i,3}$，作为第 $i$ 个问题的答案的节点坐标。