title: BZOJ2720 [Violet 5] 列队春游

description:
给定正整数数列 $h_1,h_2,\cdots,h_n$。设 $p$ 为 $1\sim n$ 的随机排列。

定义 $h'_i=h_{p_i}$。定义 $\mathrm{pre}_i$ 为最大的 $j\lt i$ 满足 $h'_j\ge h'_i$（如果不存在，规定为 $0$）。

求出 $\displaystyle \sum_{i=1}^n (i-\mathrm{pre}_i)$ 的期望值，保留两位小数输出。

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

第二行 $n$ 个正整数 $h_i$。

outputFormat: 输出一行一个实数，表示答案，保留两位小数。

hint:
对于 $20\%$ 的数据，$1\leq n\leq 10$；

对于 $50\%$ 的数据，$1\leq n\leq 70$，且 $h_i$ 互不相同；

对于 $100\%$ 的数据，保证 $1\leq n\leq 300$，$1\leq h_i\leq 1000$。


title: BZOJ3118 Orz the MST

type: P

description:
给出一个带权的连通无向图，对于其中的每条边 $i$，在原来边权的基础上，其边权每增加 $1$ 需要付出的代价为 $a_i$，边权每减少 $1$ 需要付出的代价为 $b_i$。

现在指定该图的一棵生成树，求通过修改边权，使得该生成树成为图的一棵最小生成树，需要付出的最少总代价。

inputFormat:
第一行两个正整数 $n,m$，表示图的点数和边数，结点以 $1\sim n$ 编号。

接下来 $m$ 行，每行 $6$ 个正整数，$u_i,v_i,w_i,\textit{ff}_i,a_i,b_i$，表示一条边 $(u_i,v_i)$ 的权值为 $w_i$，在原边权基础上增加 $1$ 的代价为 $a_i$，减少 $1$ 的边权代价为 $b_i$，$\textit{ff}_i$ 若为 $1$ 则表示该边在指定的生成树中，若为 $0$ 则表示不在。数据保证 $\textit{ff}_i$ 值为 $1$ 的边刚好组成原图的一棵生成树。两点之间可能有多条不同的边，但没有连接同一点的边。

outputFormat: 输出一个正整数，表示所需付出的最少总代价。


title: 『DABOI Round 1』A Simple Problem

background: > 红题令人红温。

description: 求 $\prod \limits_{i=1}^{n} \prod\limits_{j=1}^{i} \prod \limits_{k=1}^{j} k^k$ 对 $998244353$ 取模后的值。

inputFormat: 输入共 $1$ 行 $1$ 个整数，表示 $n$。

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


title: BZOJ4174 tty 的求助

description:
计算下式对 $998244353$ 取模的值，其中 $x$ 为实数，其余参与运算的变量均为整数：

$$\sum_{n=1}^N \sum_{m=1}^M \sum_{k=0}^{m-1} \lfloor \dfrac{nk+x}{m}\rfloor$$

inputFormat: 输入一行，两个正整数 $N,M$ 和一个实数 $x$。

outputFormat: 输出一行一个整数，表示答案对 $998244353$ 取模的值。

hint: 数据保证，$1\leq N,M\leq 500000$，$0<x\leq 100000$，$x$ 精确到小数点后 $8$ 位小数。


title: BZOJ1278 向量 vector

description: 一个二维向量 $(x,y)$ 的权定义为 $x^2+y^2$。已知一个由 $n$ 个二维向量组成的集合，求该集合的一个子集，使该子集中的向量和的权尽可能大。

inputFormat:
第 $1$ 行一个正整数 $n$，表示 $n$ 个向量。

下面 $n$ 行，每行 $2$ 个实数，表示 $n$ 个向量 $(x_i,y_i)$。

outputFormat: 输出 $1$ 个实数，即向量和最大的权，精确到小数点后 $3$ 位。

hint: 数据保证，$1\leq n\leq 100000$。


title: 「SFMOI Round I」Strange Madoka Game

background:
[English statement](https://www.luogu.com.cn/problem/T510969). **You must submit your code at the Chinese version of the statement.**

> いつも君の側にいるから / 无论何时我都与你同在 \
> 儚すぎて / 世界如此虚幻 \
> 消えて行きそうな世界 / 似乎随时随地都会消失 \
> だけど君がいる / 然而只要有你 \
> それだけで守りたいと思った / 我就心甘情愿将它守护

description:
**本题和 B2 是不同的问题，请分别仔细阅读两题题面。**

**这是一道交互题。**

**提示**：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

圆和焰在玩游戏。

圆在心中想了一个非负整数 $m$，让焰猜出 $m$ 的值。当然，圆不会为难焰，所以 $\textcolor{red}{0}\le m\le 10^{17}$。圆不会作弊，也就是说，**圆不会悄悄更换想好的数字。**

焰可以问圆：对于**正**整数 $x$，$m\bmod x$ 的值是多少。焰需要用最少的询问次数来猜出 $m$ 的值。（为了得到全部分数，最多只能使用 $2$ 次询问。）

圆一共和焰玩了 $T$ 次游戏。然而，焰的数学很差，于是她找来了你，来帮她猜出这 $T$ 次游戏的答案。

**形式化地**：有一个隐藏的非负整数 $m\in [\textcolor{red}{0},10^{17}]$。每次询问给定**正**整数 $x$，回答 $m\bmod x$。用最少的询问次数找出 $m$。共有 $T$ 组测试数据。$m$ 的数值在事先确定，不会根据询问变化，也就是说，**交互库是非适应性的**。

【实现细节】

对于每个测试点，输入一行一个正整数 $T$，表示游戏次数。

对于每组测试数据，你可以用以下的格式发起一次询问：

- $\texttt{? }x$：询问 $m\bmod x$ 的值。你需要保证 $x$ 是**正**整数，且 $x \in \textcolor{red} {[1,4\times 10^8]}$。

	从标准输入流读入一个整数表示答案。特别地，若整数是 $\texttt{-1}$，你的程序已经被判定为 $\texttt{Wrong Answer}$，此时你需要立刻终止程序。

你可以用以下的格式回答答案：

- $\texttt{! }m$：回答 $m$ 的值。

在发起询问后，需要刷新缓冲区，否则可能导致 TLE。

- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。 特别地，利用 `std::endl` 来换行也会刷新缓冲区。
- 在 Pascal 中，使用 `flush(output)`。
- 在 Python 中，使用 `stdout.flush()`。
- 对于其它语言，可自行查阅文档。

inputFormat: 见【实现细节】。

outputFormat: 见【实现细节】。

hint:
#### 数据范围

对于 $100\%$ 的数据，保证 $1\le T\le 100$，$m$ 为非负整数，$\textcolor{red}{0}\le m\le 10^{17}$。

#### 评分方式

记单个测试点中，你的询问次数的最大值为 $Q$。则得分 $\mathrm{score}$ 如下所示：

$$
\begin{aligned}
\mathrm{score}=\begin{cases}
0, & Q\in [81,+\infty) \\
10, & Q\in [11,81) \\
25, & Q\in [3,11) \\
50, & Q\in [0,3) \\
\end{cases}
\end{aligned}
$$

本题得分为所有测试点得分的最小值。

本题数据点的范围是非严格单调递增的。


title: 「SFMOI Round I」Strange Homura Game

background:
[English statement](https://www.luogu.com.cn/problem/T514577). **You must submit your code at the Chinese version of the statement.**

> 伝えたいコトバは たったひとつ / 想要传达的言语 唯有一个 \
> キミがいたから 強くなれた / 因有你在 我变坚强了 \
> 2 人ならどんな空も飛べるね / 只要两人一起就能任意飞翔 \
> キミをいつでも 信じてるから / 因为一直都 坚信着你 \
> ずっとずっと夢を見ていよう / 能同做此梦不复醒吧

description:
**本题和 B1 是不同的问题，请分别仔细阅读两题题面。**

**这是一道交互题。**

**提示**：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

焰和圆在玩游戏。

焰在心中想了一个正整数 $m$，让圆猜出 $m$ 的值。当然，焰不会为难圆，所以 $\textcolor{red}{2}\le m\le 10^{17}$。焰不会作弊，也就是说，**焰不会悄悄更换想好的数字。**

圆可以问焰：对于**非负**整数 $x$，$x\bmod m$ 的值是多少。圆需要用最少的询问次数来猜出 $m$ 的值。（为了得到全部分数，最多只能使用 $2$ 次询问。）

焰一共和圆玩了 $T$ 次游戏。圆的数学很好，在 $\varepsilon $ 秒内就秒了这题，但是她在军训，于是她找来了你，来帮她猜出这 $T$ 次游戏的答案。

**形式化地**：有一个隐藏的正整数 $m\in [\textcolor{red}{2},10^{17}]$。每次询问给定**非负**整数 $x$，回答 $x\bmod m$。用最少的询问次数找出 $m$。共有 $T$ 组测试数据。$m$ 的数值在事先确定，不会根据询问变化，也就是说，**交互库是非适应性的**。

【实现细节】

对于每个测试点，输入一行一个正整数 $T$，表示游戏次数。

对于每组测试数据，你可以用以下的格式发起一次询问：

- $\texttt{? }x$：询问 $x\bmod m$ 的值。你需要保证 $x$ 是**非负**整数，且 $x \in \textcolor{red}{ [0,10^{18}]}$。

    从标准输入流读入一个整数表示答案。特别地，若整数是 $\texttt{-1}$，你的程序已经被判定为 $\texttt{Wrong Answer}$，此时你需要立刻终止程序。

你可以用以下的格式回答答案：

- $\texttt{! }m$：回答 $m$ 的值。

在发起询问后，需要刷新缓冲区，否则可能导致 TLE。

- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。 特别地，利用 `std::endl` 来换行也会刷新缓冲区。
- 在 Pascal 中，使用 `flush(output)`。
- 在 Python 中，使用 `stdout.flush()`。
- 对于其它语言，可自行查阅文档。

hint:
#### 数据范围

对于 $100\%$ 的数据，保证 $1\le T\le 100$，$m$ 为正整数，$\textcolor{red}{2}\le m\le 10^{17}$。

#### 评分方式

记单个测试点中，你的询问次数的最大值为 $Q$。则得分 $\mathrm{score}$ 如下所示：

$$
\begin{aligned}
\mathrm{score}=\begin{cases}
0, & Q\in [101,+\infty) \\
30, & Q\in [3,101) \\
50, & Q\in [0,3) \\
\end{cases}
\end{aligned}
$$

本题得分为所有测试点得分的最小值。


title: [语言月赛 202407] accomplishment

type: B

background: 对于一个国家来说粮食安全至关重要。所以小 A 认为最好的检验方法就是统计有多少粮食。

description:
小 A 打开了王国的地图，他的地图可以认为是一个 $n$ 行，$m$ 列的表格，每一个格子可以看做一个城市。

理论上来说小 A 只需要把每个城市的粮食统计并加起来就好了，但是小 A 发现他统计时出现了重大失误：他统计的每个城市的粮食数并不只是这一个城市的粮食数，而是和它相邻的所有的城市的粮食数的和。

这里的相邻指八连通，即一个城市的粮食数是它本身粮食数和它上、下、左、右、上左、下左、上右，下右的城市的粮食数的和：

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

现在给出小 A 统计的错误的结果，请你帮他计算出，他的国家实际到底共有多少粮食。

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

接下来 $n$ 行，每行 $m$ 个整数，表示小 A 地图上显示的粮食数。

outputFormat: 一行一个整数，表示小 A 的国家真正的粮食数的总和。


title: [COTS/CETS 2024] 双双决斗 Dvoboj

background:
译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D1T1。$\texttt{2s,1G}$。

> Two pharaonic yellow lines turned into an eye...

description:
Jusuf 手里有 $N$ 张卡牌，从左到右编号为 $1$ 到 $N$。每张卡牌的力量为 $p_i$。由于 Jusuf 即将参加比赛，他想要在脑中想象战斗。有时候，他也会更改卡牌的力量值。Jusuf 总共会做 $Q$ 次操作，每个操作属于以下两种类型之一：

1. `1 i r`：Jusuf 将位于位置 $i$ 的卡牌的力量设为 $r$，即 $p_i\gets r$。

2. `2 l k`：Jusuf 在脑中想象一场战斗。这场战斗使用从第 $l,l+1,\cdots,l + 2^k − 1$ 张，共 $2^k$ 张卡牌。

    战斗将会进行 $k$ 轮。每轮中，Jusuf 将第 $(2i-1)$ 和第 $2i$ 张卡牌分成一组（例如第 $1$ 张和第 $2$ 张卡牌为一组）。对于每组卡牌，Jusuf 比较它们的力量。不妨设两张卡牌的力量分别为 $A$ 和 $B$，力量更大的卡牌将获胜，且获胜卡牌的力量变为 $|A − B|$，另一张卡牌被移除。特别地，如果 $A=B$，则这场战斗的结果无法确定，将会随机一张卡牌获胜，力量变为 $0$。注意到，在 $k$ 轮后，只会剩下一张卡牌，Jusuf 想要知道此时它的力量大小。

由于 Jusuf 只是在脑中想象战斗，所以实际上牌的数量不会改变，$p_i$ 也不会改变。

inputFormat:
第一行，两个正整数 $N,Q$，含义见题面。

第二行，$n$ 个整数，第 $i$ 个整数表示 $p_i$。

接下来 $Q$ 行，每行 $3$ 个正整数，描述一个操作。

outputFormat: 对于每个操作 $2$，输出一行一个整数，表示所求的力量大小。


title: [COTS/CETS 2024] 奇偶矩阵 Tablica

background: 译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D1T2。$\texttt{1s,1G}。$

description:
考虑只包含 $0$ 和 $1$ 的 $N\times M$ 矩阵 $A$。

我们称满足以下条件的矩阵是好的：

- $\forall 1\le i\le N$，$\displaystyle \sum_{j=1}^M A_{i,j}\in \{1,2\}$；
- $\forall 1\le j\le M$，$\displaystyle \sum_{i=1}^N A_{i,j}\in \{1,2\}$。

求出 $N$ 行 $M$ 列的好的矩阵的数量，对 $(10^9+7)$ 取模。

inputFormat: 输入共一行两个正整数，即 $N,M$。

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


title: [COTS/CETS 2024] 奇偶南瓜 Tikvani

background: 译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D1T3。$\texttt{0.5s,1G}$。

description:
给定有向图 $G=(V,E)$，其中 $|V|=N,|E|=M$，满足 $\forall (u,v)\in E$，都有 $u\lt v$。

定义边的一种**着色方案**为一种给每条边分配 $0/1$ 权值的方式。记 $(u,v)$ 边权为 $w(u,v)$。

定义节点 $(u,v)$ 的路径为一个序列 $(a_1,a_2,\cdots,a_k)$，满足 $a_1=u,a_k=v$，且 $\forall 1\le i\lt k$，都有 $(a_i,a_{i+1})\in E$。定义路径的权值为其上所有边的权值之和，即 $\displaystyle \sum_{i=1}^{k-1} w(a_{i},a_{i+1})$。

定义一种着色方案是好的，当且仅当对于每一对 $(u,v)$，都有 $(u,v)$ 间的所有路径的权值模 $2$ 后的余数相等。

求出好的着色方案数，对 $(10^9+7)$ 取模。

inputFormat:
第一行，两个正整数，$N,M$，含义见题面。

接下来 $M$ 行，每行两个正整数 $u,v$，表示 $(u,v)\in E$。

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


title: [语言月赛 202407] speech

background: 从前有个荣光的王国，小 A 是里面的国王，他认为一个国家的人要交流必须有合适的语言，所以今天他要赐予他的子民以言语。

description:
为了让大家尽可能快地熟悉新语言，小 A 统计了国内的 $n$ 名居民使用的语言。

经过统计，目前国内一共有 $m$ 套语言（编号为 $1, 2, \cdots, m$），每套语言分别有 $a_i$ 个语法，而每个居民会且只会使用一套语言（依次用 $b_1, \cdots, b_n$ 表示）。

定义一套语言的魅力值 $=$ 这套语言的语法数量 $\times$ 这套语言的使用人数。现在小 A 想要知道，哪一套语言的魅力值最大。

inputFormat:
输入共三行。

第一行两个整数 $n,m$，分别表示居民数和语言数。
第二行 $m$ 个整数 $a_1, \cdots, a_m$ ，表示每套语言包含的语法数量。
第三行 $n$ 个整数 $b_1, \cdots, b_n$，表示每位居民使用的语言编号。

outputFormat:
一行一个整数，表示魅力值最大的语言的编号。

如果有多种语言的魅力值最大且相同，则输出最小的编号。

hint:
### 样例 1 解释

- 有 $2$ 人使用语言 $1$，而语言 $1$ 有 $1$ 个语法，因此其魅力值为 $1 \times 2 = 2$。
- 有 $1$ 人使用语言 $2$，而语言 $2$ 有 $2$ 个语法，因此其魅力值为 $2 \times 1 = 2$。

由于语言 $1$ 编号较小，所以选择语言 $1$。

### 样例 2 解释

- 有 $2$ 人使用语言 $1$，而语言 $1$ 有 $1$ 个语法，因此其魅力值为 $1 \times 2 = 2$。
- 有 $1$ 人使用语言 $2$，而语言 $2$ 有 $3$ 个语法，因此其魅力值为 $3 \times 1 = 3$。

故选择语言系统 $2$。

### 数据范围

对于 $20\%$ 的数据，$n,m \le 3$。
对于另外 $30\%$的数据，$m = 1$。
对于 $100\%$ 的数据，$1 \le n,m \le 10^3$，$0 \leq a_i \leq 10^3$，$1 \leq b_i \leq m$。


title: [COTS/CETS 2024] 划分 Particija

background: 译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D2T1。$\texttt{1s,512M}$。

description:
给定正整数 $ N $。定义集合 $ \{1, 2, \ldots, N\} $ 的一个**划分**是指一个由非空集合组成的集族，其中每个 $1\sim N$ 中的整数出现在恰好一个集合中。例如，$\{\{1,3\},\{2,4\},\{5\}\}$ 是集合 $ \{1, 2, 3, 4, 5\} $ 的一个划分。

可以用数列 $ x_1, x_2, \ldots, x_N $ 来表示一个划分，其中 $ 1 \leq x_i \leq N $。当且仅当 $ x_i = x_j $ 时，则 $ i $ 和 $ j $ 在同一个集合中。上面提到的划分 $\{\{1,3\},\{2,4\},\{5\}\}$ 可以由数组 $[1, 2, 1, 2, 3]$ 或者 $[5, 1, 5, 1, 4]$ 表示。

Patricija 拥有两个划分：第一个划分用数列 $ a_1, a_2, \ldots, a_N $ 表示，第二个划分用数列 $ b_1, b_2, \ldots, b_N $ 表示。Patricija 想知道以下问题的答案：如果她使用这两个划分中的集合，来构造集合 $ \{1, 2, \ldots, N\} $ 的划分，至少需要多少个集合。

给定参数 $k\in \{0,1,2\}$，

- 当 $k=0$ 时，你需要回答原问题的答案。
- 当 $k=1$ 时，允许更改 $2N$ 个数字（$a_1,\cdots,a_N,b_1,\cdots,b_N$）中**至多**一个，**最小化**构造划分需要的最少集合数。
- 当 $k=2$ 时，允许更改 $2N$ 个数字（$a_1,\cdots,a_N,b_1,\cdots,b_N$）中**至多**一个，**最大化**构造划分需要的最少集合数。

请注意，你需要保证在你修改后，$\forall 1\le i\le N$，$1\le a_i,b_i\le N$。

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

第一行，两个整数 $T,k$，分别表示测试数据数量，以及参数。

接下来依次描述 $T$ 组测试数据：

对于每组测试数据，输入三行。

第一行，一个正整数 $N$，含义见题面；

第二行，$N$ 个正整数，依次表示 $a_1,a_2,\cdots,a_N$；

第三行，$N$ 个正整数，依次表示 $b_1,b_2,\cdots,b_N$。

outputFormat: 对于每组测试数据，输出一行一个整数，表示所求的答案。


title: [COTS/CETS 2024] 分割 Segregacija

background:
译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D2T2。$\texttt{5s,512M}$。

**请不要滥用本题评测。滥用本题评测将被封号。**

description:
Pero 有一个 $2$ 行 $N$ 列的矩阵，每个格子里有一个红球或蓝球。

Pero 想要重排矩阵中的球，使得所有蓝球位于矩阵的左上侧，所有红球位于右下侧。更为具体地说，重排后，不能存在一个红球位于某个蓝球的上方或左侧。

为了实现这个目标，Pero 会多次交换相邻的两个球。**两个球是相邻的当且仅当它们所在的格子有公共边。** Pero 想知道达到目标所需的最少交换次数。

此外，Pero 会交换矩阵中的相邻两个球 $Q$ 次，并在每次变更后询问当前矩阵状态所需的最小交换次数。请帮助 Pero，输出初始矩阵下以及每次交换后所需的最小交换次数。

inputFormat:
第一行，两个整数 $N,Q$，含义见题面。

接下来两行，每行一个长度为 $N$ 的字符串，描述这个矩阵。其中 $\texttt{C}$ 代表红球，$\texttt{P}$ 代表蓝球。

接下来 $Q$ 行，每行三个正整数 $t,x,y$，描述一次交换操作。

- $t=1$ 时，表示交换 $(x,y),(x,y+1)$；
- $t=2$ 时，表示交换 $(x,y),(x+1,y)$。

保证交换的两个位置都在矩阵内。

outputFormat: 输出 $(Q+1)$ 行，分别表示初始矩阵的答案和每次修改后的答案。


title: [湖北省队互测 2014] 十万人的地铁

description:
从前有两个人叫陆仁甲和陆仁乙，他们去搭地铁。

陆仁甲要从循礼门出发去广埠屯，而陆仁乙要从广埠屯出发去循礼门。

作为地铁的脑残粉，陆仁甲和陆仁乙很清楚武汉地铁收费的规则。

武汉地铁 $2$ 号线是一条直线，一共 $m$ 个地铁站，依次编号为 $1,\cdots,m$。

搭乘地铁需要刷一种叫武汉通的公交卡。进站时刷一次，出站时刷一次，在出站时会根据起始站和终点站之间的距离给武汉通扣费。即，如果设 $cost(i, j)$ 表示从编号为 $i$ 的地铁站进，从编号为 $j$ 的地铁站出的代价，则：

$$cost(i,j)=|i-j|$$

机智的陆仁甲和陆仁乙发现，乘车时的起始站是在进站刷卡时记录在武汉通上面的。而且计费跟乘车时间无关，你可以在 $i$ 站进站，在地铁上玩一整天后从 $j$ 站出站，还是付出 $cost(i,j)$ 的代价。

于是陆仁甲和陆仁乙灵机一动，想出了一个绝妙的免费乘车方案。

首先，陆仁甲从循礼门站进站出发，在中途的螃蟹甲站下车逗留。与此同时，陆仁乙从广埠屯站进站出发，也在中途的螃蟹甲站下车逗留。

接着陆仁甲与陆仁乙在螃蟹甲站会面，交换武汉通。

最后，陆仁甲乘地铁前往广埠屯站，此时陆仁甲的武汉通记录的起始站是广埠屯站，所以扣费 $0$ 元。

陆仁乙乘地铁前往循礼门站，此时陆仁乙的武汉通记录的起始站是循礼门站，所以也扣费 $0$ 元。

这样他们就完成了一次免费乘车。

于是陆仁甲和陆仁乙开始思考：假设有 $n$ 个人来搭地铁，分别编号为 $1,\cdots,n$，第 $i$ 人从第 $s_i$ 站出发去第 $e_i$ 站 $s_i\ne e_i$，沿最短路坐地铁。即：

- 若 $s_i<e_i$ 则依次经过 $s_i,s_i+1,\cdots,e_i-1,e_i$。
- 若 $s_i>e_i$ 则依次经过 $s_i,s_i-1,\cdots,e_i+1,e_i$。

那么假设他们足够聪明，会在中途下车换票，那么他们乘车的**最小**总代价是多少？

具体乘车方式说明如下：

- 一开始，所有人刷卡进站，第 $i$ 个人在第 $s_i$ 站。
- 每次可以进行如下两个操作之一：
- $0\;x\;y$：让编号为 $x$ 的人乘地铁到第 $y$ 站下车。**不允许绕路**，即必须往接近 $e_x$ 的方向乘车。而且**不允许从原地出发前往原地**，即 $y$ 不能是第 $x$ 个人现在所在的地铁站编号。你需要保证 $1\le x\le n,1\le y\le m$。
- $1\;x\;y$：让编号为 $x$ 的人和编号为 $y$ 的人交换武汉通。注意**此时在同一个地铁站的两人**才可以交换车票。你需要保证 $1\le x\le n,1\le y\le n$。
- 每次操作时，没有在操作中提到的人会在原地逗留。
- 所有操作结束后，所有人一起刷卡出站。注意要保证**第 $\boldsymbol i$ 个人此时在第 $\boldsymbol{e_i}$ 站**。
- 最后要使得所有人出站后，武汉通上扣费总和**最小**。求一个最小的乘车方案。

陆仁甲和陆仁乙当然知道怎么做啦！但是他们想考考你……

inputFormat:
第一行一个正整数 $T$，表示有几组数据。接下来有 $T$ 个数据，对于每组数据：

第一行两个用空格隔开的正整数 $n,m$。表示有 $n$ 个人，$m$ 个地铁站。

接下来 $n$ 行每行两个用空格隔开的正整数 $s_i,e_i$。表示第 $i$ 个人的起始站和终点站。（$s_i\ne e_i,1\le s_i,e_i\le m$）

outputFormat:
对于每组数据，输出一个最优方案。如果有多组都能让扣费总和最小，输出任意一组即可。

第一行有两个用空格隔开的非负整数 $ans,s$，分别表示最小总代价和操作数。操作数不能太大，要满足 $s\le400000$。

接下来 $s$ 行每行三个正整数 $type\;x\;y$ 表示一个操作。（$type\in\{0,1\}$，$x,y$ 的限制如前所述）


title: [COTS/CETS 2024] 兔子 Zečevi

background:
译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D2T3。$\texttt{8s,512M}$。

**请不要滥用本题评测。滥用本题评测将被封号。**

description:
数轴上有 $N$ 只兔子，第 $i$ 只兔子位于 $x_i$，起初，第 $i$ 只兔子的能量为 $p_i$。

每秒钟会发生如下的事件：

- 若存在至少一只兔子的能量为 $0$，则过程结束。
- 否则，每只兔子向右跳跃一个单位长度，同时能量减少 $1$。

数轴上分布着 $M$ 根胡萝卜，第 $i$ 根胡萝卜位于位置 $y_i$，质量为 $t_i$ 千克。当某只兔子的位置上有胡萝卜时，它可以选择吃 $a$ 千克的胡萝卜，其中 $a\in [0, y]$，其中 $y$ 为胡萝卜的质量。吃掉 $a$ 千克的胡萝卜后，兔子的能量增加 $a$，胡萝卜的质量减少 $a$。

显然兔子一旦停止跳跃，就再也不会跳跃了。在最优的情况下，兔子最多能跳跃多少秒？

inputFormat:
第一行，两个整数 $N,M$，含义见题面。

接下来 $N$ 行，第 $i$ 行两个整数 $x_i,p_i$；

接下来 $M$ 行，第 $i$ 行两个整数 $y_i,t_i$。

outputFormat: 输出一行一个整数，表示最优情况下的答案。


title: [语言月赛 202407] respect

background: 从前有个荣光的王国，小 A 是里面的国王，他认为人活着要有尊严，今天他要赐予他的子民以尊严。

description:
小 A 认为，当一个人被尊重时，他便是有尊严的。

现在小 A 对小 B 说了 $n$ 句话，每句话可以被视作为不含空格且全是小写字母的字符串。

每句话是由若干个单词构成的。虽然我们把这些单词直接拼接成了字符串，但是句子的语义还是和单词本身相关。对于一个字符串 $s$，我们会给出一个划分序列 $p_1, p_2, \dots, p_k$，满足 $1 \leq p_1 \leq p_2 \leq \dots \leq p_k <|s|$，则我们认为 $s$ 这句话中，$[1, p_1], [p_1+1,p_2], [p_2+1,p_3],\dots [p_k + 1, |s|]$ 这 $k+1$ 段每一段都是一个单词。特别的，如果 $k=0$，说明这个句子本身就是一个单词。

例如，对字符串 $\texttt{irespectyou}$，如果给出的序列 $p$ 为 $1,8$ 则这个字符串有 $\texttt{i}$，$\texttt{respect}$，$\texttt{you}$ 三个单词；如果序列 $p$ 为 $2, 5,7$，则这个字符串有 $\texttt{ir}$，$\texttt{esp}$，$\texttt{ec}$，$\texttt{tyou}$ 四个单词构成。

对于一个字符串 $x$，我们称一个字符串 $y$ 是 $x$ 的子串，当且仅当将 $x$ 在开头和结尾删去若干个（可以为 $0$ 个）字符后得到的字符串和 $y$ 相等。例如 $\texttt{uog}$ 是 $\texttt{luogu}$ 的子串，但 $\texttt{ug}$ 不是 $\texttt{luogu}$ 的子串。

现在，给出这 $n$ 句话，对于每句话，你要求出这句话里有多少个单词含有子串 $\texttt{respect}$。

inputFormat:
第一行是一个整数 $n$，表示句子的数量。

接下来 $3n$ 行，每三行一组，表示小 A 对小 B 说的一句话：
- 每组第一行是一个字符串 $s$ 表示这句话。
- 第二行是一个整数 $k$ 表示划分序列的长度。
- 第三行是 $k$ 个整数 $p_1, p_2, \dots, p_k$ 表示划分序列。

注意，如果 $k=0$，输入仍在每组数据的第三行有一个空行。

outputFormat:
输出 $n$ 行。

对每个句子，输出一行一个整数表示其含有子串 $\texttt{respect}$ 的单词数量。

samples:
2
irespectyou
2
1 8
herespectsyou
2
2 10

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

- 对于 $30\%$ 的数据，划分出的子串的长度 $\leq 7$。
- 对于 $60\%$ 的数据，不存在一个单词不是 $\texttt{respect}$ 且以 $\texttt{respect}$ 为子串。
- 对于 $100\%$ 的数据，$1 \leq n \leq 10^3$，$1 \leq p_1 \leq p_2 \leq \dots \leq p_k < |s|$，$k \geq 0$，输入字符串仅含有小写英文字母，字符串长度不超过 $10^3$。


title: [GESP202406 三级] 移位

description:
小杨学习了加密技术移位，所有大写字母都向后按照⼀个固定数目进行偏移。偏移过程会将字母表视作首尾相接的环，例如，当偏移量是 $3$ 的时候，大写字母 A 会替换成 D，大写字母 Z 会替换成 C，总体来看，大写字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 会被替换成 DEFGHIJKLMNOPQRSTUVWXYZABC。

注：当偏移量是 $26$ 的倍数时，每个大写字母经过偏移后会恰好回到原来的位置，即大写字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 经过偏移后会保持不变。

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

outputFormat: 输出在偏移量为 $n$ 的情况下，大写字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 移位替换后的结果。

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

当偏移量是 $3$ 的时候，大写字母 A 会替换成 D，大写字母 Z 会替换成 C，总体来看，大写字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 会被替换成 DEFGHIJKLMNOPQRSTUVWXYZABC。

**【数据范围】**

对于全部数据，保证有 $1\leq n\leq 100$。


title: [GESP202406 一级] 休息时间

description:
小杨计划在某个时刻开始学习，并决定在学习 $k$ 秒后开始休息。

小杨想知道自己开始休息的时刻是多少。

inputFormat:
前三行每行包含一个整数，分别表示小杨开始学习时刻的时 $h$、分 $m$、秒 $s$（$h,m, s$ 的值符合
 $1 < h \le 12,0 \le m\le 59,0 \le s\le59$）。

第四行包含一个整数 $k$，表示小杨学习的总秒数（注：$k$ 的值符合 $1 \le k \le 3600$）。

outputFormat: 输出一行，包含三个整数，分别表示小杨开始休息时刻的时、分、秒。

hint:
小杨在时刻 12:59:59 开始学习，学习 10 秒后开始休息，即在 13:0:9 时刻开始休息。

对于全部数据，保证有  $1 < h \le 12$，$0 \le m\le 59$，$0 \le s\le 59$，$1 \le k \le 3600$。


title: [GESP202406 三级] 寻找倍数

description: 小杨有一个包含 $n$ 个正整数的序列 $A=[a_1,a_2,\dots,a_n]$，他想知道是否存在 $i(1\leq i\leq n)$ 使得 $a_i$ 是序列 $A$ 中所有数的倍数。

inputFormat:
第一行包含一个正整数 $t$，代表测试用例组数。

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

其中，第一行包含一个正整数 $n$；第二行包含 $n$ 个正整数，代表序列 $A$。

outputFormat: 对于每组测试用例，如果存在 $i(1\leq i\leq n)$ ，满足对于所有 $k(1\leq k\leq n)$ $a_i$ 是 $a_k$ 的倍数，输出 `Yes`，否则输出 `No`。

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

对于第⼀组数据，对于 $a_3=4$，满足 $a_3$ 是 $a_1$ 和 $a_2$ 的倍数。

**【数据范围】**

对于全部数据，保证有 $1\leq t\leq 10$，$1\leq n\leq 10^5$，$1\leq a_i\leq 10^9$。


title: [GESP202406 一级] 立方数

description: 小杨有一个正整数 $n$，他想知道 $n$ 是否是一个立方数。一个正整数 $n$ 是立方数当且仅当存在一个正整数 $x$ 满足 $x\times x\times x=n$ 。

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

outputFormat: 如果正整数 $n$ 是一个立方数，输出 `Yes`，否则输出 `No`。

hint:
对于样例 1，存在正整数 $2$ 使得 $8=2\times 2\times 2$ ，因此 $8$ 为立方数。

对于样例 $2$，不存在满足条件的正整数，因此 $9$ 不为立方数。

对于全部数据，保证有 $1 \le n \le 1000$。


title: [GESP202406 四级] 黑白方块

description: 小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。对于网格图中的一个子矩形，小杨认为它是平衡的当且仅当其中黑色格子与白色格子数量相同。小杨想知道最大的平衡子矩形包含了多少个格子。

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

之后 $n$ 行，每行一个长度为 $m$ 的 $01$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $0$，则对应格子为白色，否则为黑色。

outputFormat: 输出一个整数，代表最大的平衡子矩形包含格子的数量，如果不存在则输出 $0$。

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

对于样例 $1$，假设 $(i,j)$ 代表第 $i$ 行第 $j$ 列，最大的平衡子矩形的四个顶点分别为 $(1,2),(1,5),(4,2),(4,5)$。

**【数据范围】**

对于全部数据，保证有 $1\leq n,m\leq 10$。


title: [GESP202406 四级] 宝箱

description:
小杨发现了 $n$ 个宝箱，其中第 $i$ 个宝箱的价值是 $a_i$。

小杨可以选择一些宝箱放入背包并带走，但是小杨的背包比较特殊，假设小杨选择的宝箱中最大价值为 $x$，最小价值为 $y$，小杨需要保证 $x-y\leq k$，否则小杨的背包会损坏。

小杨想知道背包不损坏的情况下，自己能够带走宝箱的总价值最大是多少。

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

第二行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$，代表宝箱的价值。

outputFormat: 输出一个整数，代表带走宝箱的最大总价值。

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

在背包不损坏的情况下，小杨可以拿走两个价值为 $2$ 的宝箱和一个价值为 $3$ 的宝箱。

**【数据范围】**

对于全部数据，保证有 $1\leq n\leq 1000$，$0\leq k\leq 1000$，$1\leq a_i\leq 1000$。


title: [GESP202406 二级] 平方之和

description: 小杨有 $n$ 个正整数 $a_1,a_2,\dots,a_n$，他想知道对于所有的 $i (1\le i\le n)$，是否存在两个正整数 $x$ 和 $y$ 满足 $x\times x+y \times y=a_i$。

inputFormat:
第一行包含一个正整数 $n$，代表正整数数量。
之后 $n$ 行，每行包含一个正整数，代表 $a_i$。

outputFormat: 对于每个正整数 $a_i$，如果存在两个正整数 $x$ 和 $y$ 满足 $x\times x+y \times y=a_i$，输出 `Yes`，否则输出 `No`。

hint:
对于第一个正整数，存在 $1\times 1+2 \times 2=5$，因此答案为 `Yes`。

对于全部数据，保证有 $1 \le n \le 10,1 \le a_i \le 10^6$。


title: [GESP202406 二级] 计数

description: 小杨认为自己的幸运数是正整数 $k$（注：保证 $1 \le k\le 9$）。小杨想知道，对于从 $1$ 到 $n$ 的所有正整数中， $k$ 出现了多少次。

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

第二行包含一个正整数 $k$。

outputFormat: 输出从 $1$ 到 $n$ 的所有正整数中， $k$ 出现的次数。


title: [GESP202406 五级] 小杨的幸运数字

description:
小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，$12=2\times 2\times 3$ 的质因子有 $2,3$，恰好为两种不同的质因子，因此 $12$ 是幸运数字，而 $30=2\times3\times5$ 的质因子有 $2,3,5$，不符合要求，不为幸运数字。

小杨现在有 $n$ 个正整数，他想知道每个正整数是否是他的幸运数字。

inputFormat:
第一行包含一个正整数 $n$，代表正整数个数。

之后 $n$ 行，每行一个正整数。

outputFormat: 输出 $n$ 行，对于每个正整数，如果是幸运数字，输出 $1$，否则输出 $0$。


title: [GESP202406 六级] 计算得分

description:
小杨想要计算由 $m$ 个小写字母组成的字符串的得分。

小杨设置了一个包含 $n$ 个正整数的计分序列 $A=[a_1,a_2,\ldots,a_n]$，如果字符串的一个子串由 $k(1\leq k \leq n)$ 个 $\texttt{abc}$ 首尾相接组成，那么能够得到分数 $a_k$，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。

例如，假设 ，字符串 $\texttt{dabcabcabcabzabc}$ 的所有可能计分方式如下：
- $\texttt{d+abc+abcabc+abz+abc}$ 或者 $\texttt{d+abcabc+abc+abz+abc}$，其中 $\texttt{d}$ 和 $\texttt{abz}$ 不计算得分，总得分为 $a_1+a_2+a_1$。
- $\texttt{d+abc+abc+abc+abz+abc}$，总得分为 $a_1+a_1+a_1+a_1$。
- $\texttt{d+abcabcabc+abz+abc}$，总得分为 $a_3+a_1$。

小杨想知道对于给定的字符串，最大总得分是多少。

inputFormat:
- 第一行包含一个正整数 $n$，代表计分序列 $A$ 的长度。

- 第二行包含 $n$ 个正整数，代表计分序列 $A$。

- 第三行包含一个正整数 $m$，代表字符串的长度。

- 第四行包含一个由 $m$ 个小写字母组成的字符串。

outputFormat: 输出一个整数，代表给定字符串的最大总得分。


title: 「FSLOI Round I」山峦

background:
**[English statement.](https://www.luogu.com.cn/problem/T501030) You must submit your code at the Chinese version of the statement.**

山峦是造物主弃的酒杯。

description:
如果一个长度至少为三的序列 $a$ 满足以下条件，则称其为一个**山峰**：

- 设其长度为 $m$。存在一个 $x$，满足 $2\leq x \leq m-1$，并且使得 $a_1,a_2,\cdots,a_x$ 严格单调递增，$a_x,a_{x+1},\cdots,a_m$ 严格单调递减。

特别地，称 $a_x$ 为这个山峰的高度。

如果一个序列 $b$ 满足以下任一条件，则称其为一个**山峦**：

- $b$ 序列是一个**山峰**。

- 可以拆成至少两个连续的子序列，使得每个子序列都是**山峰**，且从左到右**山峰的高度**严格单调递增。

比如，序列 $\lbrace 2,4,3,1,5,2,1 \rbrace$ 是山峦，因为其可以拆分为 $\lbrace 2,4,3 \rbrace,\lbrace 1,5,2,1 \rbrace$ 两个山峰，且山峰高度严格递增。而序列 $\lbrace 2,4,3,5,2,1 \rbrace$ 不是山峦，因为其无法拆分成至少两个连续的子序列，使得每个子序列都是山峰。

现在给定一个长度为 $n$ 的序列 $a$，小 F 想知道，在 $a$ 的所有子序列中，有多少个是**山峦**。由于答案可能很大，请输出其对 $998244353$ 取余后的结果。

请注意，在本题中，即使子序列的元素相同，只要子序列的元素在 $a$ 中的位置不同，仍算作不同的子序列。

inputFormat:
共两行。

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

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示 $a$ 序列。

outputFormat:
共一行。

一个整数，表示是山峦的子序列数量对 $998244353$ 取余的结果。


title: [NOISG2024 Prelim] Tourist

background: 翻译自 [NOI SG 2024 Prelim A.Tourist](https://github.com/noisg/noi-2024-prelim)。

description:
你是一名游客，你想要在 $n$ 天内游览一座城市。

你已经为自己安排好了行程。第 $i$ 天你需要乘坐 $a_i$ 次火车。

你了解到有以下两种火车票：

- 单程票：花费 $x$ 元购买一张单程票，可以乘坐 $1$ 次火车。

- 单日票：花费 $y$ 元购买一张单日票，可以在一天中不限次数地乘坐任意次火车。

请你求出购买火车票需要的最小花费。

inputFormat:
第一行，三个整数 $N,x,y$；

第二行 $N$ 个整数，第 $i$ 个整数表示 $a_i$。

outputFormat: 一行一个整数表示最小花费。

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

你的行程有 $3$ 天，一张单程票 $4$ 元，一张单日票 $9$ 元。

在第一天，购买 $2$ 张单程票，花费 $8$ 元。

在第二天，购买 $1$ 张单日票，花费 $9$ 元。

在第三天，购买 $2$ 张单程票，花费 $8$ 元。

最小花费为 $8+9+8=25$ 元。

### 【数据范围】

|$\text{Subtask}$|分值|特殊性质|
|:-:|:-:|:-:|
|$0$|$0$|样例|
|$1$|$100$|无|

对于 $100\%$ 的数据，$1 \le n,x \le 1000,1 \le y \le 10^6,1 \le a_i \le 10^4$。


title: [GESP202406 八级] 最远点对

description:
小杨有⼀棵包含 $n$ 个节点的树，这棵树上的任意⼀个节点要么是白色，要么是黑色。

小杨想知道相距最远的一对不同颜色节点的距离是多少。

inputFormat:
第一行包含⼀个正整数 $n$，代表树的节点数。

第二行包含 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$（对于所有的 $1\le i\le n$，均有 $a_i$ 等于 $0$ 或 $1$），其中如果 $a_i=0$，则节点 $i$ 的颜色为白色；如果 $a_i=1$，则节点 $i$ 的颜色为黑色。

之后 $(n-1)$ 行，每行包含两个正整数 $x_i,y_i$，代表存在一条连接节点 $x_i$ 和 $y_i$ 的边。

保证输入的树中存在不同颜色的点。

outputFormat: 输出⼀个整数，代表相距最远的一对不同颜色节点的距离。


title: [NOISG2024 Prelim] Party

background: 翻译自 [NOI SG 2024 Prelim B.Party](https://github.com/noisg/noi-2024-prelim)。

description:
James 有 $n$ 个朋友，他想选择其中的 $0$ 个或者更多朋友来参加他的聚会。第 $i$ 个朋友如果参加了他的聚会，会产生 $a_i$ 点快乐值。注意：有些朋友并不想参加聚会，所以他们的 $a_i$ 会是负的。

然而，他家只有一排 $n$ 个座位，而且因为社交距离，两个人不能坐在相邻的座位上。现在 James 想知道，如果他按照最优方案邀请朋友，这些朋友的快乐值的和最大为多少。

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

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

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


title: [NOISG2024 Prelim] Explosives

background: 翻译自 [NOI SG 2024 Prelim E.Explosives](https://github.com/noisg/noi-2024-prelim)。

description:
你是一名运送炸弹的卡车司机。

有 $n$ 座工厂（生产炸弹）和 $n$ 座矿井（需要炸弹）排列在一条直线上。第 $i$ 座工厂的坐标为 $a_i$，第 $j$ 座矿井的坐标为 $b_j$。并且，所有 $a_i$ 和 $b_j$ 都均不相等。

你今天需要在每一座工厂各领取一个炸弹，并将每一个炸弹送到某一个矿井中。初始时，你的坐标为 $0$。为了完成此任务，你可以进行以下两种操作：

- `pickup(x)`：从你当前的位置驾驶卡车到坐落在 $x$ 的工厂。执行这次操作需要同时满足以下两个条件：

	- 有一个 $i$，满足 $x=a_i$。

   - 你的卡车最多装了 $c-1$ 个炸弹。

- `offload(x)`：从你当前的位置驾驶卡车到坐落在 $x$ 的矿井。执行这次操作需要同时满足以下两个条件：

	- 有一个 $j$，满足 $x=b_j$。

   - 你的卡车最少装了 $1$ 个炸弹。

由于炸弹十分危险，所以在你的卡车上需要一名安全员。如果你从点 $x$ 到点 $y$，且车上装有炸弹，那么你需要付给安全员 $|x-y|$ 元。如果车上没有炸药，则你不需要支付任何费用。

请求出在花费最小的情况下的操作序列。

inputFormat:
第一行，两个整数 $n,c$；

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

第三行，一行 $n$ 个整数，表示 $b$。

outputFormat:
第一行，一个整数表示最小花费。

第二行，输出 $2n$ 个整数，表示你访问的工厂和矿井坐标，按照访问顺序输出。

例如你执行了四次操作：`pickup(3)`，`offload(5)`，`pickup(6)`，`offload(2)`，则你应该输出 `3 5 6 2`。


title: [NOISG2024 Prelim] School Photo

background: 翻译自 [NOI SG 2024 Prelim C.School Photo](https://github.com/noisg/noi-2024-prelim)。

description:
Zane 是 NOI 学校的校长。NOI 学校有 $n$ 个班，每个班有 $s$ 名同学。第 $i$ 个班中的第 $j$ 名同学的身高是 $a_{i,j}$。

现在 Zane 想从每个班上选出一名同学拍照，使得这 $n$ 名同学中最高的同学和最低的同学的身高差最小。

请你输出这个最小值。

inputFormat:
第一行，两个整数 $n,s$；

接下来 $n$ 行，每行 $s$ 个整数，表示 $a$。

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


title: [NOISG2024 Prelim] Amusement Park

background: 翻译自 [NOI SG 2024 Prelim D.Amusement Park](https://github.com/noisg/noi-2024-prelim)。

description:
有一家游乐园，在大门处有一项观光车服务。很显然，一辆观光车只能承载有限的人数，那么如果一个团队来到大门时，发现观光车不够坐时，他们需要决定是否愿意分开。有些团队愿意，有些不愿意。

为了解决这个复杂的问题，公园的管理者蜗牛 Stuart 想请你帮忙写一个程序，支持以下三种操作：

- `join`：一个新的团队进入了队列。我们用两个整数 $s,w$ 描述此次操作：$s$ 表示该团队的总人数；如果 $w=1$，那么这个团队愿意在乘坐观光车时分开；如果 $w=0$，表示他们不愿意分开。假设这次操作是所有操作中第 $i$ 次 `join` 操作，则该团队的编号为 $i$。

- `leave`：给定 $i$，编号为 $i$ 的团队从队伍中离开。

- `board`：给定 $b$，表示新开来一辆能坐 $b$ 人的观光车。从队头开始，如果到一个团队时，观光车可以承载所有人，那么所有人上车；否则如果该团队愿意分开，那么部分人上车；否则该团队留在原位置，在下一个团队重复该过程，直到观光车坐满，或没有人愿意上车。

inputFormat:
第一行，一个整数 $q$；

接下来 $q$ 行，每行一次操作，分为以下三种：

- `1 s w`：描述一次 `join` 操作；

- `2 i`：描述一次 `leave` 操作；

- `3 b`：描述一次 `board` 操作。

outputFormat:
对于 `join` 和 `leave` 操作，你不需要输出任何内容。

对于每一次 `board` 操作，设有 $k$ 个团队有至少一个人上了观光车，你需要输出 $k+1$ 行：

- 第一行一个整数 $k$。

- 接下来 $k$ 行，每行两个整数，第一个表示团队编号，第二个表示该团队上观光车的人数。**注意：团队编号应从小到大输出。**（如果 $k=0$，忽略此部分。）


title: [GESP202406 五级] 黑白格

description:
小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。

小杨想知道至少包含 $k$ 个黑色格子的最小子矩形包含了多少个格子。

inputFormat:
第一行包含三个正整数 $n,m,k$，含义如题面所示。

之后 $n$ 行，每行⼀个长度为 $m$ 的 $\texttt{01}$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $\texttt{0}$，则对应格子为白色，否则为黑色。

outputFormat: 输出一个整数，代表至少包含 $k$ 个黑色格子的最小子矩形包含格子的数量，如果不存在则输出 $0$。


title: [GESP202406 六级] 二叉树

description:
小杨有⼀棵包含 $n$ 个节点的二叉树，且根节点的编号为 $1$。这棵二叉树任意⼀个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行 $q$ 次操作，每次小杨会选择⼀个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。

小杨想知道 $q$ 次操作全部完成之后每个节点的颜色。

inputFormat:
第⼀行一个正整数 $n$，表示二叉树的节点数量。

第二行 $(n-1)$ 个正整数，第 $i$（$1\le i\le n-1$）个数表示编号为 $(i+1)$ 的节点的父亲节点编号，数据保证是⼀棵二叉树。

第三行一个长度为 $n$ 的 $\texttt{01}$ 串，从左到右第 $i$（$1\le i\le n$）位如果为 $\texttt{0}$，表示编号为 $i$ 的节点颜色为白色，否则为黑色。

第四行⼀个正整数 $q$，表示操作次数。

接下来 $q$ 行每行⼀个正整数 $a_i$（$1\le a_i\le n$），表示第 $i$ 次操作选择的节点编号。

outputFormat: 输出一行一个长度为 $n$ 的 $\texttt{01}$ 串，表示 $q$ 次操作全部完成之后每个节点的颜色。从左到右第 $i$（$1\le i\le n$） 位如果为 $\texttt{0}$，表示编号为 $i$ 的节点颜色为白色，否则为黑色。


title: [GESP202406 七级] 区间乘积

description:
小杨有一个包含 $n$ 个正整数的序列 $A=[a_1,a_2,\ldots,a_n]$。

小杨想知道有多少对 $\langle l,r\rangle(1\leq l\leq r\leq n)$ 满足 $a_l\times a_{l+1}\times\ldots\times a_r$ 为完全平方数。

一个正整数 $x$ 为完全平方数当且仅当存在一个正整数 $y$ 使得 $x=y\times y$。

inputFormat:
第一行包含一个正整数 $n$，代表正整数个数。

第二行包含 $n$ 个正整数 $a_i$，代表序列 $A$。

outputFormat: 输出一个整数，代表满足要求的 $\langle l,r\rangle$ 数量。


title: 「ALFR Round 4」B 颜料

background: 在小山的观念里，画展因色彩不同而绚丽。

description:
小山一共有 $n$ 副画作，每副画作都有其主要的颜料。具体的，第 $i$ 副画作的主要颜料的种类为 $a_i$。小山可以选择一段**编号连续**的画作组成一个画展，而画展的绚丽程度为（设该画展由第 $l$ 到第 $r$ 副画组成）：$\sum_{i=1}^W\sum_{j=i+1}^W\min(c_i,c_j)$，其中 $c_i$ 表示种类为 $i$ 的颜料在画展中出现的次数，$W$ 为所有颜料种类的值域。

现在小山想知道，若要画展的绚丽程度至少为 $k$，应至少选出多少副连续的画作？若无绚丽程度至少为 $k$ 的画展，则答案为 $-1$。

inputFormat:
共两行，第一行两个整数 $n,k$，含义见**题目描述**。

第二行 $n$ 个整数，第 $i$ 个数为 $a_i$，表示第 $i$ 副画的主要颜料的种类。


title: 「KDOI-07」n1gr tS0i

background: 众所周知，小 T 不喜欢 01 串问题，于是小 R 出了另一个有关 01 串的题目：

description:
有一个长度为 $n$ 的 $\tt 01$ 串 $S$，你要对 $S$ 进行 **恰好** $n$ 次操作。每次操作选择 $1 \leq l \color{red}< \color{normal} r \leq n$，然后你按位翻转 $S_{l\dots r}$。这里的按位翻转指，$S_{l\dots r}$ 内所有 $\tt 0$ 同时变为 $\tt 1$，且所有 $\tt 1$ 同时变为 $\tt 0$。

求 $n$ 次操作后，所有可能不同的 $S$ 的个数。因为答案可能很大，所以请对 $998244353$ 取模。

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

第一行一个整数 $T$ 描述数据组数。对于每组数据：

- 第一行一个整数 $n$。
- 接下来一行，一个长度为 $n$ 的 $\tt 01$ 串 $S$。

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


title: [GESP202406 七级] 黑白翻转

description:
小杨有一棵包含 $n$ 个节点的树，这棵树上的任意一个节点要么是白色，要么是黑色。小杨认为一棵树是美丽树当且仅当在删除所有白色节点之后，剩余节点仍然组成一棵树。

小杨每次操作可以选择一个白色节点将它的颜色变为黑色，他想知道自己最少要执行多少次操作可以使得这棵树变为美丽树。

inputFormat:
第一行包含一个正整数 $n$，代表树的节点数。

第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，其中如果 $a_i=0$，则节点 $i$ 的颜色为白色，否则为黑色。

之后 $n-1$ 行，每行包含两个正整数 $x_i,y_i$，代表存在一条连接节点 $x_i$ 和 $y_i$ 的边。

outputFormat: 输出一个整数，代表最少执行的操作次数。

hint:
### 样例解释

将节点 $1$ 和 $3$ 变为黑色即可使这棵树变为美丽树，此时删除白色节点 $5$，剩余黑色节点仍然组成一棵树。

### 数据范围
子任务编号|数据点占比|$n$ |$a_i$ |特殊条件
:-:|:-:|:-:|:-:|:-:
$1$|$30\%$ |$\leq 10^5$ | $0\leq a_i\leq 1$|树的形态为一条链
$2$|$30\%$ | $\leq 10^5$ | $0\leq a_i\leq 1$| 只有两个节点颜色为黑色
$3$|$40\%$|$\leq 10^5$|$0\leq a_i\leq 1$|

对于全部数据，保证有 $1\leq n\leq 10^5$，$0\leq a_i\leq 1$。


title: [GESP202406 八级] 空间跳跃

description:
小杨在二维空间中有 $n$ 个水平挡板，并且挡板之间彼此不重叠，其中第 $i$ 个挡板处于水平高度 $h_i$，左右端点分别位于 $l_i$ 与 $r_i$。

小杨可以在挡板上左右移动，当小杨移动到右端点时，如果再向右移动会竖直掉落，从而落到下方第一个挡板上，移动到左端点时同理。小杨在挡板上每移动 $1$ 个单位长度会耗费 $1$ 个单位时间，掉落时每掉落 $1$ 个单位高度也会耗费 $1$ 个单位时间。

小杨想知道，从第 $s$ 个挡板上的左端点出发到第 $t$ 个挡板需要耗费的最少时间是多少？

注意：可能无法从第 $s$ 个挡板到达到第 $t$ 个挡板。

inputFormat:
第一行包含一个正整数 $n$，代表挡板数量。

第二行包含两个正整数 $s,t$，含义如题面所示。

之后 $n$ 行，每行包含三个正整数 $l_i,r_i,h_i$，代表第 $i$ 个挡板的左右端点位置与高度。

outputFormat: 输出一个整数代表需要耗费的最少时间，如果无法到达则输出 $-1$。

hint:
### 样例解释

耗费时间最少的移动方案为，从第 $3$ 个挡板左端点移动到右端点，耗费 $3$ 个单位时间，然后向右移动掉落到第 $2$ 个挡板上，耗费 $100000-6=99994$ 个单位时间，之后再向右移动 $1$ 个单位长度，耗费 $1$ 个单位时间，最后向右移动掉落到第 $1$ 个挡板上，耗费 $3$ 个单位时间。共耗费 $100001$ 个单位时间。

### 数据范围

子任务编号|数据点占比|$n$|特殊条件
:-:|:-:|:-:|:-:
$1$|$20\%$|$\leq 1000$|$l_i=1$
$2$|$40\%$|$\leq 1000$|$l_i=i,r_i=i+1$
$3$|$40\%$|$\leq 1000$|

对于全部数据，保证有 $1\leq n\leq 1000$，$1\leq l_i\leq r_i\leq 10^5$，$1\leq h_i\leq 10^5$。


title: [NOISG 2023 Qualification] Dolls

description:
Marc 正在教幼儿园的小朋友，他选择套娃来教小朋友们认识物体的大小。

一个套娃有一个自己的尺寸，记为 $a$。如果两个套娃 $x$ 和 $y$ 的尺寸 $a_x$ 和 $a_y$ 可以满足 $a_x-a_y\ge2$，那么套娃 $y$ 可以放在套娃 $x$ 中。

很显然，套娃之间是可以互相嵌套多层的。于是 Marc 想请你回答一些问题：

这些问题持续 $n$ 天。在第 $i$ 天，Marc 购买了一个大小为 $a_i$ 的套娃。他想请你求出，在买完第 $i$ 个套娃后，他用前 $i$ 个套娃最多可以套多少层。

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

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

outputFormat: 一行 $n$ 个正整数，第 $i$ 个表示用前 $i$ 个套娃最多能套多少层。


title: [NOISG2019 Prelim] Palindromic FizzBuzz

background: 翻译自 [NOISG2019 Prelim A.Palindromic FizzBuzz](https://github.com/noisg/sg_noi_archive/blob/master/2019_prelim/)。

description: 给定 $S,E$，对于在 $S,E$ 区间中的每一个数字，如果它不回文，输出它本身，否则输出 `Palindrome!`。

inputFormat: 一行两个整数 $S,E$。

outputFormat: 共 $E-S+1$ 行，每行一个整数，输出方式见题目描述。

samples:
Palindrome!
Palindrome!
10
Palindrome!
12
13

samples:
3 3
Palindrome!


title: [NOISG 2023 Qualification] Burgers

description:
龙虾 Kai 经营着一家汉堡店。做一个汉堡需要 $n$ 种原料，第 $i$ 种原料他有 $x_i$ 份。

他手中有两种汉堡食谱，这两种汉堡对于第 $i$ 种原料分别需要 $a_i$ 份和 $b_i$ 份来制作。

计算 Kai 最多能用这些原料制作多少个汉堡。

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

第二行 $n$ 个整数，表示 $x$。

第三行 $n$ 个整数，表示 $a$。

第四行 $n$ 个整数，表示 $b$。

outputFormat: 一行一个整数表示最多能制作多少个汉堡。


title: [NOISG2019 Prelim] Lost Array

background:
翻译自 [NOISG2019 Prelim B.Lost Array](https://github.com/noisg/sg_noi_archive/blob/master/2019_prelim/)。

**本题已启用 Special Judge，满足题目条件的任何答案都将视为正确。**

description:
给定 $M$ 组形如 $\min (X_{A_i},X_{B_i})=C_i$ 的关系式，请构造一个长度为 $N$ 的数组 $X$，使得数组中的每个数字在 $1$ 到 $10^9$ 之间，并且该数组满足所有的关系式。

题目保证数组存在。

inputFormat:
第一行两个整数 $N,M$。

接下来 $M$ 行，每行三个数字 $A_i,B_i,C_i$。

outputFormat: 共一行 $N$ 个整数，代表你构造的数组 $X$。


title: [NOISG 2023 Qualification] Network

description:
鸭子 Rui Yuan 有 $n$ 台服务器和 $n-1$ 条**双向**数据线，其中第 $i$ 条数据线**双向**连接 $u_i$ 和 $v_i$。保证对于所有 $1 \le i \not = j \le n$，可以通过数据线从第 $i$ 台服务器到达第 $j$ 台服务器，反之亦然。

Rui Yuan 还有 $m$ 个应用程序正在运行，第 $j$ 个程序分布在 $a_j$ 和 $b_j$ 两台服务器上运行。

初始时，所有服务器都在运行状态。

第 $j$ 个应用程序如果对下面两个条件中的一个条件成立时，可以运行：

- $a_j$ 和 $b_j$ 均为运行中的服务器。

- $a_j$ 和 $b_j$ 之间可以通过数据线和**正在运行的服务器**连接。

Rui Yuan 想请你求出，至少停止运行多少台服务器，才能使所有应用程序停止运行。

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

接下来 $n-1$ 行，每行两个整数 $u_i,v_i$。

接下来 $m$ 行，每行两个整数 $a_j,b_j$。

outputFormat:
第一行，一个整数 $x$，表示最少要停运多少台服务器。

接下来 $x$ 行，每行一个整数，表示要停运的服务器的编号。


title: [NOISG2019 Prelim] Experimental Charges

background: 翻译自 [NOISG2019 Prelim C.Experimental Charges](https://github.com/noisg/sg_noi_archive/blob/master/2019_prelim/)。

description:
现有 $N$ 个带电粒子，带正电子的粒子会和带负电子的粒子相互吸引，而带同一种电子的粒子会相互排斥。

有 $Q$ 次操作，每次操作表示为 $T_i,A_i,B_i$，可根据 $T_i$ 的不同分为三种类型：
- `A` 操作代表 $A_i,B_i$ 互相吸引。
- `R` 操作代表 $A_i,B_i$ 互相排斥。
- `Q` 操作询问按照目前已知的信息，如果 $A_i,B_i$ 放在一起，会发生什么。

对于每个 `Q` 操作，如果互相吸引，输出 `A`；如果互相排斥，输出 `R`；如果无法确定，输出 `?`。

保证至少有一种可能使得所有操作不冲突。

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

接下来的 $Q$ 行，每行一个字符 $T_i$ 与两个整数 $A_i,B_i$，表示一种操作。

outputFormat: 若干行，每行表示一次 `Q` 操作的回答。


title: [NOISG2019 Prelim] Square or Rectangle?

background:
翻译自 [NOISG2019 Prelim D.Square or Rectangle?](https://github.com/noisg/sg_noi_archive/blob/master/2019_prelim/)。

请注意，本题为**交互题**，请**尽量使用 C++ 进行作答**。同时，你**只需要实现题目中要求的函数**。**不要将答案输出在标准输出。**

description:
现在有一个 $N\times N$ 的网格，网格内**有一个至少占网格总大小 $4\%$ 的矩形**。但是，你现在不知道这个矩形是长方形还是正方形，你需要**定义一个函数**来完成这个问题。

### 【实现细节】
你需要定义以下函数：

`bool am_i_square(int N, int Q)`

- $N$：网格的大小
- $Q$：能询问评测机的次数。

为了确定形状，你可以向评测机至多调用 $Q$ 次 `bool inside_shape(int X, int Y)` 函数。调用这个来询问评测机方格 $(X,Y)$ 是否在这个矩形中。

一旦你确定了形状，你就可以返回一个 `bool` 类型的量，代表这个矩形是否为**正方形**。

评测机会调用你的函数 $T$ 次。$T$ 的大小见【数据范围与评测方法】。

inputFormat: 见【实现细节】。

outputFormat: 见【实现细节】。

hint:
### 【样例】
考虑以下调用：

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

`am_i_square(5, 25)`

这表示这是一个 $5 \times 5$ 大小的网格，你可以调用至多 $25$ 次。

`inside_shape(3, 3) = true`

这询问了方格 $(3,3)$ 是否在矩形内，它在正方形的正中间，所以返回 `true`。

`inside_shape(5, 4) = false`

这询问了方格 $(5,4)$ 是否在矩形内，它不在正方形内，所以返回 `false`。

`inside_shape(1, 1) = false`

这询问了方格 $(1,1)$ 是否在矩形内，它不在正方形内，所以返回 `false`。

`inside_shape(2, 4) = true`

这询问了方格 $(2,4)$ 是否在矩形内，它在正方形的左下角，所以返回 `true`。

综上，我们可以确定这是一个正方形，所以该函数返回 `true`。
### 【数据范围与评测方法】
对于 $100\%$ 的测试点：$N=100,1\leq T \leq 1000$。
| $\text{Subtask}$ | 分值 | 附加条件 |
| :----------: | :----------: | :----------: |
| $0$ | $14$ | $Q=10^4$ |
| $1$ | $19$ | $Q=100$ |
| $2$ | $18$ | $Q=40$，图形至少占网格总大小的 $25\%$ |
| $3$ | $49$ | $Q=50$，得分见下文 |
### 【Subtask 3 的计分方法】
记你在所有调用中最大使用了 $q$ 次询问。
- 若 $q >50$，你得到 $0$ 分。
- 若 $34 \leq q \leq 50$，你得到 $40-30\times \frac{q-34}{17}$ 的分数。
- 若 $q \leq 33$，你得到满分。
### 【提示】
请在你的函数前加上以下内容：
```cpp
#include <bits/stdc++.h>
using namespace std;
extern "C" bool inside_shape(int x,int y);
```
同时，请在你的 `bool am_i_square(int N, int Q)` 前加上`extern "C" `。


title: [NOISG2021 qualification] Competition

description:
你是一位老师，有 $n$ 个学生，每个学生都有物理成绩 $A_i$ 和生物成绩 $B_i$，你要从这些学生中选出 $a$ 个人参加物理竞赛，$b$ 个人参加生物竞赛。每个学生必须参加一种且只能参加一种竞赛。

定义你所在的学校的实力值为参加物理竞赛的人的物理成绩和参加生物竞赛的人的生物成绩的和。请你求出实力值最大是多少？

inputFormat:
第 $1$ 行三个整数 $n, a, b$。

第 $2$ 行 $n$ 个整数 $A_i$。

第 $3$ 行 $n$ 个整数 $B_i$。

outputFormat: 一行一个整数，最大的实力值。

hint:
#### 样例 1 解释

第一、三个人参加生物竞赛，第二个人参加物理竞赛。

#### 数据范围

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

Subtask0 是样例。

Subtask1（29 pts）$n \leq 20$。

Subtask2（22 pts）保证所有 $B_i=0$。

Subtask3（49 pts）无特殊限制。

数据保证 $1 \leq n \leq 10^5$，$0 \leq a,b \leq n$，$a+b=n$，$0 \leq A_i,B_i \leq 10^4$。


title: 【MX-X3-T5】「RiOI-4」Countless J-Light Decomposition

background:
「如果，如果，如果真的可以是那样的话，就好了啊。」

回想起自己做出的一个个选择，泠珞有时会想，自己是否有过更好的机会。

但是既然一切已经如此了，除了前进，别无他法。

无论结果是如何，接受结果，习得教训，然后……去争取更美好的未来。

那么，现在应该做的就是，尽可能避免，之后会走到的最坏结果了吧。

「规避风险。脚踏实地。做最可能实现的选择。」

「一定是的。」

description:
给定一棵有根**带权**树，结点以 $1\sim n$ 编号。根结点编号为 $1$，边权均为正整数。

定义这棵树的**剖分**为对于每个结点，选择一些儿子（可以都选或都不选）为**重儿子**的方案。重儿子和其父亲的边称为**重边**。不是重边的边称为**轻边**。

定义一个剖分是 $\textbf{\textit{i--}}$**重的**，当且仅当对于每个结点，其重儿子数量不超过 $i$。

定义一个剖分是 $\textbf{\textit{j--}}$**轻的**，当且仅当对于每条从根（编号为 $1$ 的结点）出发的简单路径，其经过的轻边的边权和不超过 $j$。

对于 $i=0,1,\cdots,n-1$，请求出最小的 $j$，使得存在一个 $\textit{i--}$重的剖分是 $\textit{j--}$轻的。

inputFormat:
第一行一个正整数 $n$，表示树的大小。

接下来 $n-1$ 行，每行三个正整数 $u_i,v_i,w_i$，表示编号为 $u_i,v_i$ 的结点间有一条边权为 $w_i$ 的边。

outputFormat: 一行 $n$ 个整数，表示 $i=0,1,2,\cdots,n-1$ 时的答案。

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

对于样例 1，其中的树如下所示：

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

当 $i=0$ 时，只存在一种剖分，不存在任何重儿子或重边。一条从根出发经过轻边边权和最大的简单路径为 $1\textit{---}2\textit{---}4$，边权和为 $2$。

当 $i=1$ 时，可以采用如图所示的剖分，加粗结点（根除外）为重儿子。一条从根出发经过轻边边权和最大的简单路径为 $1\textit{---}2\textit{---}5$，经过轻边的边权和为 $1$。

当 $i\ge 2$ 时，可以令所有的非根结点为重儿子，因此任何从根出发经过最多轻边的简单路径只能经过 $0$ 条轻边，故轻边最大边权和为 $0$。

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

当 $i\ge 3$ 时，可以令所有的非根结点为重儿子，因此任何从根出发经过最多轻边的简单路径只能经过 $0$ 条轻边，故轻边最大边权和为 $0$。

当 $i=0,1,2$ 时，我有一个很简洁的解释，但是这里空白太小写不下。

**【数据范围】**

**本题开启捆绑测试。**

|子任务|分数|$n\le$|特殊性质|
|:-:|:-:|:-:|:-:|
|$1$|$10$|$10^3$||
|$2$|$18$|$4\times10^4$||
|$3$|$16$|$10^5$|$w_i\le100$|
|$4$|$21$|$10^5$|$w_i\le10^5$|
|$5$|$35$|$2\times10^5$||

对于 $100\%$ 的数据，$1\le n\le2\times10^5$，$1\le w_i\le 10^9$，保证输入是一棵树。


title: [NOISG2021 qualification] Departure

description:
有一个城市，城市里有 $N$ 条路线，每条路线上，在每天午夜会有一辆巴士从起点出发，第二天午夜到达终点。第 $i$ 辆公交车的起点为 $S_i$，终点为 $E_i$。人们可以在巴士路线上的的**任何地方**上车、下车或者换乘。

体育馆是这个城市的中心，坐标为 $0$。在体育馆西边 $x$ 千米的点，坐标为 $-x$，在体育馆东边 $x$ 千米的点，坐标为 $x$。

现在有 $M$ 个人需要从体育馆回家，你需要求出每一个人回家的最短时间。

inputFormat:
第 $1$ 行两个整数 $N,M$。

第 $2$ 至 $N+1$ 行，每行两个整数 $S_i,E_i$。

第 $N+2$ 行 $M$ 个整数 $P_j$，表示每一个人的家。

outputFormat: $M$ 行，每行两个整数 $a,b$（$\gcd(a,b)=1$），表示这个人最早能在 $\dfrac{a}{b}$ 天后回家。

hint:
#### 数据范围

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

以下定义 $\operatorname{sign}(x) = \begin{cases}
1 &\text{if } x > 0 \\
0 &\text{if } x = 0 \\
-1 &\text{if } x < 0 \\
\end{cases}$。

Subtask0 为样例。

Subtask1（10 pts）$N \leq 10^4$，$M \leq 10^3$，$\operatorname{sign}(S_i)\neq\operatorname{sign}(E_i)$。

Subtask2（14 pts）$N \leq 100$，$M \leq 10^3$。

Subtask3（12 pts）$N \leq 10^3$，$M \leq 10^5$，保证最后答案的值均不大于 $10^3$，保证任意坐标在不超过 $10^2$ 条线路上。

Subtask4（8 pts）$M \leq 10^3$，保证任意坐标在不超过 $10^4$ 条线路上。

Subtask5（15 pts）$M \leq 10^4$，保证最后答案的值均不大于 $10^2$。

Subtask6（13 pts）$\operatorname{sign}(S_i)\neq\operatorname{sign}(E_i)$。

Subtask7（28 pts）无特殊限制。

数据保证 $1 \leq N,M \leq 10^6$，$-10^6 \leq S_i,E_i,P_j \leq 10^6$，$S_i \neq E_i$，$P_j \neq 0$。


title: [COI 2023-2024] CERN

background: 题目来源：<https://hsin.hr/hio2024/>。翻译来自 [文心一言](https://yiyan.baidu.com/)。如果有更好的翻译请在讨论区提供。

description:
CERN 是一个专注于核研究和粒子物理学的国际机构。CERN 的粒子加速器系统被用于进行高速粒子碰撞实验。

我们考虑按序列排列的 $N$ 个粒子。每个粒子由其类型 $v_i$ 定义，$v_i$ 是一个介于 $1$ 和 $N$ 之间的正整数。

在最新的研究中，需要进行 $Q$ 次实验。在第 $i$ 次实验中，我们观察序列中从第 $l$ 个到第 $r$ 个的所有粒子（其中 $l < r$）。在观察到的粒子中，我们可以选择任意两个类型不同的粒子并在加速器中进行碰撞，导致两个粒子都被摧毁。我们重复这个碰撞过程，直到观察到的粒子中没有两个类型不同的粒子为止。实验将在所有观察到的粒子都被摧毁或仅剩下同类型的粒子时结束。当然，根据我们碰撞粒子的顺序，最终可能留下各种类型的粒子。

由于粒子碰撞成本高昂，你决定只在理论上进行实验。现在，对于每次实验，你感兴趣的是有多少种类型的粒子，使得实验结束时可能剩下该类型的粒子。

inputFormat:
第一行包含两个正整数 $N$ 和 $Q$，分别表示粒子的数量和实验的次数。

第二行包含 $N$ 个数 $v_1, \dots, v_N$，表示粒子的类型。

接下来的 $Q$ 行中，每行包含两个正整数 $l$ 和 $r$（$1 \leq l < r \leq N$），表示第 $i$ 次实验中观察到的粒子区间。

outputFormat: 对于每次实验，在单独的一行中输出可能的结束实验时剩余的粒子类型数量。

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

在第一个实验中，我们可以使类型为 $3$ 和 $4$ 的粒子相撞，留下两个类型为 $2$ 的粒子。无法最终得到任何其他类型的粒子。

在第二个实验中，有可能最终剩下每种类型的一些粒子。

在第四和第五个实验中，不论选择哪种碰撞方式，最终都会剩下一些类型为 $4$ 的粒子。

**【数据范围】**

在所有子任务中，$2 \leq N \leq 5\times 10^5$ 且 $1 \leq Q \leq 5\times 10^5$。

- 子任务 1（13 分）：对于每个 $i = 1, \dots, N，v_i \leq 10$。
- 子任务 2（19 分）：每种类型的粒子最多只有两个。
- 子任务 3（17 分）：$N, Q \leq 2\times 10^3$。
- 子任务 4（19 分）：$N, Q \leq 1\times 10^5$。
- 子任务 5（32 分）：没有额外的约束条件。


title: [BalticOI 2024] Jobs

background: 翻译自 [BalticOI 2024 Day1 T1](https://boi2024.lmio.lt/tasks/d1-jobs-statement.pdf)。

description:
目前，你可以选择从 $1$ 到 $N$ 编号的 $N$ 个一次性工作。

完成第 $i$ 个工作将给你带来 $x$ 欧元的利润，当然，利润也可能是负的。

有些工作依赖于另一个工作。也就是说，可能有一个编号为 $p$ 的工作必须在第 $i$ 个工作开始之前完成。因此，一个利润较大的工作如果依赖于一个利润为负的工作，看起来收益可能会比较小。

如果 $p = 0$，则第 $i$ 个工作没有依赖。

你目前有 $s$ 欧元，可以决定做哪些工作以及以什么顺序去做，只要尊重依赖关系。此外，你所拥有的钱数在任何时候都不能变成负数。

请计算通过选择按照某种顺序完成（也可能某些选择不完成）这 $N$ 个工作所能获得的最大利润。

inputFormat:
第一行包含两个整数 $N$ 和 $s$，分别是工作的数量和你最初拥有的金额。

接下来的 $N$ 行，每行包含两个整数 $x$ 和 $p$，分别是第 $i$ 个工作的利润和它所依赖的前置工作的编号。如果 $p = 0$，则第 $i$ 个工作没有依赖。

outputFormat: 你的程序应该输出一个整数，即你能够获得的最大利润。


title: [BalticOI 2024] Portal

background: 翻译自 [BalticOI 2024 Day1 T2](https://boi2024.lmio.lt/tasks/d1-portal-statement.pdf)。

description:
你在和你的朋友玩一个恶作剧，朋友初始在 $(0,0)$ 位置，每个格子都有颜色，有 $N$ 个传送门，当你的朋友进入某个传送门之内时，会等概率地随机到 $N$ 个传送门其中之一（可能传送到原本的门，如果 $(0,0)$ 有传送门也要传送）。

可惜的是，你的朋友并不知道有传送门的存在，他只会根据他所走的格子确定他所在的格子与其颜色，你需要保证无论他怎么走，他所看到的格子颜色永远与他认为的格子颜色一样。

你可以随意染色，但是请最大化颜色数量，不难发现涂成一个颜色总是最小的解。

inputFormat:
第一行一个整数 $N$，表示有 $N$ 个传送门。

接下来 $N$ 行，每行两个整数 $(x_i,y_i)$，表示传送门的坐标。

outputFormat: 输出一个数表示你最大使用颜色的数量，如果可以使用无数种，输出 $-1$。

hint:
| 子任务编号 | 特殊性质 | 分值 |
| :-----------: | :-----------: | :-----------: |
| $1$ | $N \leq 2$ | $1$ |
| $2$ | $N \leq 3$ | $10$ |
| $3$ | 对于所有存在传送门的 $(x_1,y_1)$ 和 $(x_2,y_2)$，保证 $(x_1,y_2)$ 也存在传送门 | $10$ |
| $4$ | $N \leq 100$ 且 $-100 \leq x_i,y_i \leq 100$ | $29$ |
| $5$ | $N \leq 2000$ | $15$ |
| $6$ | 无特殊性质 | $35$ |

对于全部数据，$1 \leq N \leq 10^5$，$-10^6 \leq x_i,y_i \leq 10^6$，且保证 $(x_i,y_i)$ 互不相同。

对于样例一，传送门被放置在 $(1,1)$、$(1,3)$ 和 $(3,2)$ 位置，如果你的朋友按照以下顺序移动：上、右、下、左。

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

在移动序列结束后，你的朋友会认为他们回到了起始单元格$(0,0)$，但实际上他们也可能最终停在 $(0,2)$ 或 $(2,1)$。他们已经在开始时看到了 $(0,0)$ 单元格的颜色，所以如果现在他们看到不同的颜色，就会意识到必须有传送门的存在。我们不希望发生这种情况，所以我们必须为这三个单元格选择相同的颜色。

没有任何移动序列能让你的朋友认为他们最终停在 $(0,0)$ 单元格，而实际上他们却停在了 $(1,0)$ ，所以这些单元格可以放心地使用不同的颜色。

你可以看到下面例子中使用了 $4$ 种颜色的着色方案。对于这个例子来说，不可能使用超过 $4$ 种颜色。

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

对于样例二，让我们考虑一个不同的例子，其中在单元格 $(0,0)$、$(0,1)$、$(1,0)$、$(0,-1)$ 和 $(-1,0)$ 处设有传送门。假设你的朋友试图通过先向右移动一次，然后向上移动三次来到达单元格 $(1,3)$。一种可能是，如果他们在一开始和每一步之后都被传送到那里，那么他们最终会到达单元格 $(0,0)$。如果你的朋友现在通过向下移动三次然后向左移动一次来回到他们认为的 $(0,0)$ 单元格，并且在这个过程中没有被从当前单元格传送走，他们最终会到达 $(-1,-3)$。你的朋友会第二次认为自己处于 $(0, 0)$ 单元格，并期望看到相同的颜色。所以你需要用相同的颜色给 $(-1,-3)$ 和 $(0, 0)$ 着色。

请注意，我们选择单元格 $(1,3)$ 作为起点并没有什么特别之处。你同样可以证明其他单元格必须与 $(0,0)$ 共享同一种颜色。


title: [BalticOI 2024] Trains

background: 翻译自 [BalticOI 2024 Day1 T3](https://boi2024.lmio.lt/tasks/d1-trains-statement.pdf)。

description:
你已经抵达维尔纽斯，并希望参观立陶宛的不同城市。立陶宛的城市位于一条直线上，并按顺序从 $1$ 到 $N$ 编号。维尔纽斯是 $1$ 号城市。每个城市都有一个火车站，并且有一条从该站出发的单轨列车运营路线。你只能在该路线起点的城市上车，但可以在其任何一站下车。从第 $i$ 个城市开始的列车每行驶 $d_i$ 个城市就会停靠一站，并且其路线包含 $x_i$ 个停靠站（不包括起始城市）。如果 $d_i = 0$，则从第 $i$ 个城市出发的列车目前处于停运状态，因此你不能乘坐它们。

更具体地说，如果你在第 $i$ 个城市上车，你可以在任何编号为 $i + t \cdot d_i$ 的城市下车，其中 $1 \leq t \leq x_i$。请注意，由于你只希望参观立陶宛的城市，因此即使列车在其路线上有更多的停靠站，你也不会超过第 $N$ 个城市下车。

你打算使用列车前往参观一些城市。在规划你的旅行时，你开始思考从维尔纽斯出发的旅程有多少种不同的选择。如果两次旅行在不同的城市序列中停靠，则它们被视为不同。输出答案对 $10^9 + 7$ 取模的值。

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

接下来 $N$ 行每行两个整数 $d_i,x_i$。

outputFormat: 输出路线数对 $10^9 + 7$ 取模的值。


title: [BalticOI 2024] Fire

background: 翻译自 [BalticOI 2024 Day2 T1](https://boi2024.lmio.lt/tasks/d2-fire-statement.pdf)。

description:
我们将一天划分为 $M$ 个时间，同时有 $N$ 个人，每个人愿意工作的时间分别为 $(s_i,e_i)$，如果 $s_i > e_i$，说明这个人愿意工作到第二天的 $e_i$ 时间，每个人最多连续工作时间不会超过一整天。

你需要安排一些人工作，使得他们工作时间可以覆盖一整天，请求出这个人数。

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

接下来 $N$ 行，每行一对 $(s_i,e_i)$。

outputFormat: 输出一个数，表示多少要安排的人数，如果无法安排人数使得一天的时间被覆盖，输出 $-1$。


title: [BalticOI 2024] Tiles

background: 翻译自 [BalticOI 2024 Day2 T2](https://boi2024.lmio.lt/tasks/d2-tiles-statement.pdf)。

description:
有一个存在 $N$ 个顶点的大教堂，顶点坐标依次为 $(x_i,y_i)$，对于每个 $1 \leq i < N$，存在一条 $i$ 与 $i+1$ 之间的边，此外，还存在一条 $N$ 到 $1$ 的边。

大教堂每条边都与 $x$ 轴或 $y$ 轴平行。此外，大教堂是一个简单多边形，即：

- 每个顶点恰好由两条边相交
- 任何一对边只能在顶点处相交

你有无数块 $2 \times 2$ 的瓷砖，你希望用这些瓷砖覆盖大教堂的大部分区域，具体来说，你想选择一条垂直线，并覆盖该线左侧的大教堂部分。对于任何整数 $k$，设 $L_k$ 为包含 $x$ 坐标等于 $k$ 的点的垂直线。对 $L_k$ 左侧大教堂部分的覆盖，是指在平面上放置一定数量的瓷砖，使得：

- 多边形内部且 $x$ 坐标小于 $k$ 的每个点都被某块瓷砖覆盖
- 多边形外部或 $x$ 坐标大于 $k$ 的点都不被任何瓷砖覆盖
- 瓷砖的内部不重叠

大教堂中任何顶点的最小 $x$ 坐标为 $0$。我们设 $M$ 为大教堂中任何顶点的最大 $x$ 坐标。

请你求出最大的满足条件的 $k\ (0 \leq k \leq M)$，根据定义，一定存在答案为 $0$。

inputFormat:
第一行两个整数 $N,M$。

接下来 $N$ 行，每行两个整数 $(x_i,y_i)$。这些顶点按照顺时针或逆时针顺序给出。

outputFormat: 输出一个答案 $k$。

hint:
| 子任务编号 | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: |
| $1$ | $N=4$ | $4$ |
| $2$ | $N \leq 6$ | $9$ |
| $3$ | $x_N=0,y_N=0$，对于 $1 \leq i \leq N-2$，$x_i \leq x_{i+1},y_i \geq y_{i+1}$ | $11$ |
| $4$ | $M \leq 1000$ 且 $y_i \leq 1000$ | $19$ |
| $5$ | $y_i$ 都为偶数 | $22$ |
| $6$ | $x_i$ 都为偶数 | $25$ |
| $7$ | 无特殊性质 | $10$ |

对于所有数据，$4 \leq N \leq 2 \times 10^5$，$1 \leq M \leq 10^9$，$0 \leq y_i \leq 10^9$，$\min(\{x_i\}) = 0,\max(\{x_i\}) = M$。

对于样例一，下面是对于 $k=2$ 的覆盖。

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

可以发现这是最大的情况了。

对于样例二，没有正值 $k$，使得 $L_k$ 左侧的教堂部分可以用瓷砖覆盖。

对于样例三，图示如下。

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


title: [BalticOI 2024] Wall

background: 翻译自 [BalticOI 2024 Day2 T3](https://boi2024.lmio.lt/tasks/d2-wall-statement.pdf)。

description:
你想要修建一个围墙，它是由 $N$ 个墙组成的，每个墙 $i$ 可能的高度是 $a_i$ 或 $b_i$，对于每个可能的围墙序列 $h$，你想要求出它的积水量之和。

例如下图展示了一个 $N = 10$，围墙高度分别为 $4, 2, 1, 8, 6, 2, 7, 1, 2, 3$ 的例子，它的实际积水高度是 $4, 4, 4, 8, 7, 7, 7, 3, 3, 3$。

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

正式地，对于每个 $i$ 其可能的积水高度 $H$，必须要存在一个 $l \leq i \leq r$，使得 $h_l \geq H$，$h_r \geq H$，则 $i$ 这个位置的积水量为 $H - h_i$。

输出所有可能情况的积水量之和对 $10^9 +7$ 取模的值。

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

第二行 $N$ 个整数 $a_i$。

第三行 $N$ 个整数 $b_i$。

outputFormat: 输出可能的围墙积水量之和对 $10^9 +7$ 取模的值。


title: [COI 2023-2024] Ministarstvo（征集 checker）

description:
经过在派对中成功的职业生涯后（我们不会透露这个派对的名字），Pero 在旅游局找到了一份工作。他监管着一个由 $N$ 个城市组成的网络，这些城市从 $1$ 到 $N$ 进行编号，每对城市之间都有一条单向道路相连。为了增加收入，他决定引入交通许可。Pero 原本希望为每条道路都引入一种特殊的许可，但这会引起上级的注意。因此，他决定引入 $K$ 种不同的许可，从 $1$ 到 $K$ 进行编号，并规定每条道路上行驶都需要持有特定的许可。

为了确保可观的收入，Pero 将满足以下属性：

- 对于每个城市 $v$，都存在一个城市 $u$，使得无法仅凭一种许可从城市 $v$ 行驶到城市 $u$。

Pero 请求你的帮助来确定最小的 $K$ 值，如果存在满足上述属性的许可分配方案，则输出这个 $K$ 值以及许可分配方案。如果不存在这样的分配方案，则输出 $-1$。

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

接下来的 $N$ 行中，第 $i$ 行包含 $N$ 个数字 $a_{i,j}$，其中如果有一条从城市 $i$ 到城市 $j$ 的道路，则 $a_{i,j} = 1$。注意 $a_{i,i} = 0$，且对于 $i \neq j$，$a_{i,j}$ 和 $a_{j,i}$ 中只有一个非零。

outputFormat:
如果不存在满足属性的分配方案，则在第一行且仅第一行输出 $-1$。

否则，在第一行输出最小的正整数 $K$。

在接下来的 $N$ 行中，输出分配方案的描述。第 $i$ 行输出 $N$ 个数字 $b_{i,j}$，如果 $a_{i,j} = 0$，则 $b_{i,j} = 0$；否则，$1 \leq b_{i,j} \leq K$，表示在该道路上行驶需要哪种许可。

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

对于样例 $3$：需要第一个许可证的道路用红色标记，第二个许可证用蓝色，第三个许可证用绿色。从城市 $1$ 出发，仅使用一个许可证无法到达城市 $3$。从城市 $2$ 出发，仅使用一个许可证无法到达城市 $1$。从城市 $3$ 出发，仅使用一个许可证无法到达城市 $2$。从城市 $4$ 出发，仅使用一个许可证无法到达城市 $1$。

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

**【数据范围】**

在所有子任务中，$2 \leq N \leq 1000$。在每个子任务中， $15\%$ 的分数仅用于判断是否存在这样的分配方案。对于这些分数，如果你不输出 $-1$，你需要输出某个分配方案，但它不必满足 Pero 所期望的属性。

- 子任务 1（20 分）：$N\leq 5$；
- 子任务 2（80 分）：无其他约束限制。


title: [COI 2023-2024] Sirologija

description:
你是一只蚂蚁，但并非普通的蚂蚁——你是一只对奶酪学痴迷的蚂蚁！你在厨房里发现了一片新的奶酪，并希望尽可能多地派遣你的手下（小蚂蚁）去探索它。想象一下这片奶酪就像一个有 $N$ 行 $M$ 列的表格，从上到下行标号为 $1$ 到 $N$，从左到右列标号为 $1$ 到 $M$。一些区域有洞，而其他区域则有奶酪。我们将第 $r$ 行第 $s$ 列的区域表示为 $(r, s)$。左上角和右下角的区域肯定包含奶酪。

我们设手下的数量为 $K$。你的手下将从左上角的区域开始探索，并在右下角的区域结束。他们只能向下或向右移动。此外，他们的路径不能“交叉”，这意味着我们可以给他们从 $1$ 到 $K$ 的编号，使得没有从某个区域向右移动的是编号较低的手下，同时从该区域向下移动的是编号较高的手下。

此外，你希望这些路径在某种意义上“不同”，即对于每一对手下，都存在一个包含洞的区域 $(r, s)$，使得其中一只手下在某个时刻位于第 $s$ 列且行标号低于 $r$，而另一只手下在某个时刻（不一定同时）也位于第 $s$ 列但行标号高于 $r$ 。非正式地说，每一对手下都从洞的不同侧接近。

输出满足给定条件的路径选择的最大 $K$ 值。

以下是一些不满足条件的路径示例：

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

inputFormat:
第一行包含两个正整数 $N, M$。

接下来的 $N$ 行包含每行的描述。第 $i$ 行包含 $M$ 个字符，其中 `.` 表示奶酪，`#` 表示一个洞。

outputFormat: 输出满足给定条件的路径选择的最大 $K$ 值。

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

**【数据范围】**

- 子任务 1（15 分）：所有洞都在同一行。
- 子任务 2（18 分）：$N, M \leq 10$。
- 子任务 3（16 分）：$N, M \leq 50$，第一行、最后一行、第一列、最后一列中没有洞。
- 子任务 4（18 分）：$N, M \leq 50$。
- 子任务 5（16 分）：$N, M \leq 2000$，第一行、最后一行、第一列、最后一列中没有洞。
- 子任务 6（17 分）：没有额外的约束条件。

在所有子任务中，$2 \leq N, M \leq 2000$。


title: [COI 2022-2023] Bliskost

background: 题目来源：<https://hsin.hr/hio2023/>。翻译来自 [文心一言](https://yiyan.baidu.com/)。如果有更好的翻译请在讨论区提供。

description:
在春天的一个异常温暖的午后，莫斯科的 Patrijaršijskim Ribnjačama 出现了两位市民。第一位不是别人，正是编辑 Mihali Aleksandrovic Berlioz ，而另一位则是一位被称为“Bezdomni 无家可归者”的年轻诗人。他们各自带着一串长度为 $N$ 的字母。

不久之后，一位神秘的黑色魔法专家，Woland 教授加入了他们，并说道：“先生们，你们手中的字母串非常有趣，我能立刻判断出它们是否相近！”他解释道，通过选择一串字母中连续的两个字母，并将它们按照字母表顺序向前循环移动，例如将 `ab` 变为 `bc`，或者 `qz` 变为 `ra`，如果在两串字母上应用这一操作后，它们能够变得相同，那么这两串字母就被认为是相近的。

“当然，教授，您在说胡话。判断两串字母是否相近的问题显然很难。”

“不，Mihali Aleksandrovic，你错了，我现在就要向你证明这一点！这样吧，我现在就来告诉你，你们的字母串是否相近，然后你们再对自己的字母串进行 $Q$ 次变换。每次变换后，我都会再次判断你们字母串的相近性是否属实。”

“教授，您真是非常勇敢，确实非常勇敢……那么，我们开始吧！”

inputFormat:
第一行包含自然数 $N$ 和 $Q$，分别表示字符串的长度和变化次数。

第二行是一个长度为 $N$ 的字符数组，属于 Berlioz。

第三行也是一个长度为 $N$ 的字符数组，属于 Bezdomni（无家可归者）。

接下来的 $Q$ 行中，每行包含一个整数 $p$ 和 $p$ 个字符，表示在第 $i$ 次变化中，Berlioz 改变了第 $p_i$ 个字符到某个新字符。

outputFormat:
第一行需要输出 `da`（如果初始字符串是相近的）或 `ne`（如果不是相近的）。

接下来的 $Q$ 行，对于每一次 Berlioz 的变化，需要输出变化后两个字符串是否还是相近的。

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

在第一个示例中，更改后，单词在后续步骤中相近关系：
- $\tt abc \to bcc \to cdc \to dec \to dfd$
- $\tt ced \to dfd$

**【数据范围】**

对于所有子任务，都有 $N$ 和 $Q$ 的取值范围限制：$1 \leq N \leq 1\times 10^6$ 和 $0 ≤ Q ≤ 1\times 10^6$。

- 子任务 1（7 分）：$Q=0$，$N\leq 5$；
- 子任务 2（8 分）：$Q=0$，$N\leq 1000$；
- 子任务 3（13 分）：$Q=0$；
- 子任务 4（12 分）：$Q\leq 100000$，$N\leq 5$；
- 子任务 5（17 分）：$Q\leq 100000$，$N\leq 1000$；
- 子任务 6（43 分）：没有其他额外限制。


title: [COI 2022-2023] Nestabilnost

description:
Borova Suma，位于河流对岸，一小时前还被五月的阳光照亮，现在却变得朦胧、模糊并散开。只剩下一棵神奇的大树，一棵有 $N$ 个节点的树……

Ivan 从 119 号房间观察着这棵树，它坚固地扎根在标有数字 $1$ 的节点上。之后，他更近距离地观察了树，发现每个节点上都有一个数字 $a$。突然，他脑海中浮现出了 $k$-好子树的定义。一个子树是 $k$-好的，如果对于连接节点 $(u,v)$ 的每一条边（其中 $u$ 是 $v$ 的父节点），都有 $a_v = (a_u + 1) \bmod k$ 成立，并且对于子树内的每个节点 $v$，都满足 $a_v < k$。对于每个数字 $k$，都存在一个自然的 $k$-好子树的不稳定性，记作 $f(k)$。

当他再次回过神来时，他发现自己站在树前，右手拿着一把神奇的斧头。Ivan 决定砍掉一些树枝，并在移除某些边后得到的每个子树中，选择一个数字 $k$，使得该子树是 $k$-好的。对于选择哪些边进行砍伐以及为每个得到的子树选择的 $k$ 值，Ivan 决定称之为“砍伐”。我们将砍伐的不稳定性定义为所有得到的 $k$-好子树的 $f(k_i)$ 之和。请帮助 Ivan 确定砍伐的最小可能不稳定性。

inputFormat:
第一行是一个自然数 $N$，表示树中节点的数量。

第二行包含 $N$ 个数字，其中第 $i$ 个数字表示节点 $i$ 的权值 $a$（$0 \leq a \leq N - 1$）。

第三行包含 $N$ 个数字，其中第 $k$ 个数字表示函数 $f(k)$ 的值（$1 \leq f(k) \leq 10^9$）。

接下来的 $N-1$ 行描述了树的结构，第 $i$ 行包含两个数字 $u$ 和 $v$（$1 \leq u,v \leq N, u \neq v$），表示节点 $u$ 和节点 $v$ 之间存在一条边。

outputFormat: 在单独的一行中输出可能的最小“锯割不稳定性”。

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

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

左图为样例 1，右图为样例 2。

**【数据范围】**

在所有子任务中，都满足 $1 ≤ N ≤ 3\times 10^5$ 的条件。

- 子任务 1（12 分）：$N \leq 5 000$，树是一条链，且节点 $1$ 是链的一个端点。
- 子任务 2（20 分）：$N \leq 300 000$，树是一条链，且节点 $1$ 是链的一个端点。
- 子任务 3（7 分）：$N \leq 20$；
- 子任务 4（22 分）：$N \leq 5000$；
- 子任务 5（39 分）：没有其他额外限制。


title: [COI 2022-2023] Netrpeljivost

description:
夜幕降临，必须小心行事。在玛格丽塔成功地与所有客人打招呼之后，他们无阻碍地坐在了长椅上。

我们可以用从 $1$ 到 $N$ 的数字来标记客人，正好是他们坐在长椅上的顺序。由于未知的原因，在索托尼举办的盛大舞会上，客人的数量总是 $2$ 的幂次。然而，玛格丽塔现在遇到了问题，因为每对客人之间都存在着一定程度的不耐烦，我们可以用一个非负数字来表示这种不耐烦。客人之间的不耐烦可以标记为 $netrp(i, j)$。始终有 $netrp(i, j) = netrp(j, i)$，并且 $netrp(i, i) = 0$。由于客人们已经（不）舒适地就座，玛格丽塔不能突然改变他们的顺序。实际上，客人们也不知道自己处于完全二叉树（velikog Sotoninog potpunog binarnog stabla，VSPBS）的列表中，这在图片中以 $N=4$ 的情况展示了出来。

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

(a) 图 1：初始的树结构，(b) 图 2：操作后的树结构

玛格丽塔可以选择一个节点，并在一次操作中交换该节点的左孩子和右孩子，从而改变位于相应叶子节点上客人的顺序。展示的是树结构（以及长椅上的状态），在玛格丽塔对树的根节点进行一次操作之后的状态。玛格丽塔可以对任意节点进行任意次数的操作。长椅上的总不耐烦度定义为长椅上所有相邻客人之间的不耐烦度之和。帮助玛格丽塔确定她可以达到的最小可能的长椅不耐烦度。

inputFormat: 在第一行是一个自然数 $N$，表示客人数量。在接下来的 $N$ 行中，第 $i$ 行包含按顺序排列的数字 $netrp(i, j)$，这些数字满足上述属性。

outputFormat: 输出最小的不耐烦度。

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

在第二个例子中，一个可能的排列方式可以达到最小不耐受度的是 $2,1,4,3$。

**【数据范围】**

在所有子任务中，都满足 $1 \leq N \leq 2048$，且 $N$ 是 $2$ 的幂次，$0 \leq netrp(i,j) \leq 10^9$。

- 子任务 1（10 分）：$N\leq 16$；
- 子任务 2（17 分）：$N\leq 128$；
- 子任务 3（32 分）：$N\leq 512$；
- 子任务 4（41 分）：无特殊限制；


title: [COI 2022-2023] Sličnost

description:
她手里拿着讨厌的、令人不安的黄色花朵。然而，他喜欢它。

根据已知的定理，每个人的个性都可以表示为长度为 $N$ 的排列。因此，我们的主角“匠人”的个性可以表示为排列 $p$。而玛格丽特的个性，可以用排列 $q$ 来表示。

衡量排列的相似性，从而在婚姻生活中找到幸运与幸福，可以表示为某个长度为 $K$ 的排列 $p$ 与长度为 $K$ 的排列 $q$ 的最大交集。这里的交集是在集合意义上考虑的，即不考虑子区间中的顺序。例如，在 $N = 4,K = 3$ 的情况下，排列 $(2\ 4\ 1\ 3)$ 和 $(1\ 2\ 3\ 4)$ 的相似度为 $2$，这可以通过任意选择子区间实现。

自从看到玛格丽特，匠人就被自己排列的相似性所困扰，他的个性变得非常多变。因此，每天他的排列中有两个元素会互换位置。需要注意的是，这些变化是随机的。每天，这两个元素的交换会发生在接下来的 $Q$ 天中。现在他感兴趣的是，在看到玛格丽特后，每天的排列相似度是多少。此外，他也想知道在所有这些子区间对中，有多少对实现了这种相似度。在他的爱情烦恼中，他请求你帮忙！

inputFormat:
第一行包含整数 $N$、$K$ 和 $Q$。

第二行包含 $N$ 个数，其中第 $i$ 个数表示 $p_i$。

第三行包含 $N$ 个数，其中第 $j$ 个数表示 $q_j$。

接下来的 $Q$ 行描述了变化。第 $i$ 行包含整数 $t_i$（$1 \leq t_i < N$），表示在第 $i$ 天匠人的排列 $p$ 中，位置 $t_i$ 和 $t_i + 1$ 上的数进行了交换。

outputFormat:
第一行应输出初始排列相似度和实现该相似度的子区间对数。

接下来的 $Q$ 行应输出在那天变化后的相似度和子区间对数。


title: [WC2011] 关系挖掘

description:
有人说：“世界上任何两个人最多只需要通过 $6$ 个人就能建立联系”。小 B 对此非常感兴趣，于是着手开展了一些社会网络中关系挖掘的研究工作。

现在小 B 得到了一个包含 $N$ 个人的社会网络数据，该网络中有 $M$ 条关系信息。一条关系信息可以表示为 $(a_i, b_i, w_i)$，表示 $a_i$ 与 $b_i$ 两个人之间存在关系，且紧密度为 $w_i$（$w_i>0$）。现在小 B 希望挑选其中的 $K$（$K\leq N$）个人作为研究对象，为使研究工作具有较高的可信度，小 B 希望这 $K$ 个人之间的关系紧密度之和尽量大。

该问题可抽象为：给定一个带权无向图 $G=(V, E)$ 和整数 $K$，目标是求出点集 $V$ 的一个子集 $S$，使得 $|S|=K$ 且使下式最大化：

$$\sum_{(a_i,b_i,w_i)\in E \wedge a_i\in S \wedge b_i \in S} w_i$$

inputFormat:
这是一道提交答案的试题，在你的目录下有 $10$ 个输入文件  `relation*.in`。

输入文件的第一行为三个整数 $N$，$M$ 和 $K$，分别表示给定的社会网络中的点数（人数）、边数（关系数目）以及需要选择的点数（人数）$K$。

接下来 $M$ 行，每行三个正整数 $a_i$，$b_i$，$w_i$，表示一条边（关系）。所有的点（人）按 $1$ 到 $N$ 依次编号。

outputFormat:
对于每一个输入文件，在目录下给出对应的输出文件  `relation*.out`。

输出文件应包含 $K$ 行，每行一个整数，表示选出的 $K$ 个人的编号。

hint:
**【评分标准】**

对于每个测试点，如果你没有输出或者输出不合法则得 $0$ 分。

对于每个测试点，我们设有四个评分参数 $m_1$、$m_2$、$m_3$ 和 $m_4$。假设选手选出的 $K$ 个人之间关系紧密度之和为 $c$，
- 若 $c>m_1$，得 $12$ 分；
- 若 $c=m_1$，得 $10$ 分；
- 若 $m_1>c\geq m_2$，得 $8$ 分；
- 若 $m_2>c\geq m_3$，得 $5$ 分；
- 若 $m_3>c\geq m_4$，得 $3$ 分；
- 若 $c>0$，得 $1$ 分；
- 否则，得 $0$ 分。


title: [CTSC2011] 道路监控

description:
道路安全部门最近计划部署从 A 市到 B 市的道路监控系统，以提高该部门对于紧急事件的应对能力。A 市到 B 市的道路网可以描述为一个无向图 $G=(V, E)$，其中 $V$ 表示道路网中的节点集合，$E$ 表示连接节点的双向道路集合。所有的节点由 $1\sim n$ 进行编号，其中 $n$ 为节点个数。A 市所处的节点为 $s$，B 市所处的节点为 $t$。

该部门计划在其中一些道路中安装监控设备，以降低整个道路网的**响应难度**。当紧急事件发生时，部门需要派遣一些人力到一些道路中进行执勤，以使得**任何一条从节点 $s$ 到达节点 $t$ 的路径都经过至少一条监控道路**（安装了监控设备或者有人执勤）。因此**响应难度**定义为需要派遣人力的最少道路数，以使得任何一条从 $s$ 到 $t$ 的路径都经过至少一条监控道路。

由于自然环境不同，在不同的道路安装监控设备的代价也可能不同。具体而言，对于一条边 $e$，其安装设备的代价为 $W(e)$。由于经费有限，他们希望找到一个方案，使得该道路网的响应难度不超过 $k$。请你帮助他们寻找一个尽可能经济的部署方案。

inputFormat:
这是一道提交答案的试题，在你的目录下有 $10$ 个输入文件 `road*.in`。

输入文件的第一行为三个整数 $n$，$m$ 和 $k$，分别表示道路网中的节点数、道路数以及响应难度的上限值。

输入文件第二行包含两个整数 $s$ 和 $t$，表示 $A$ 市与 $B$ 市的节点编号。

接下来 $m$ 行，每行三个正整数 $a_i$，$b_i$，$w_i$，表示一条连接节点 $a_i$ 和节点 $b_i$ 的道路，其安装监控设备的费用为 $w_i$。

outputFormat:
对于每一个输入文件，在目录下给出对应的输出文件 `road*.out`。

输出文件第一行包含一个值 $s$，表示选手提供的方案中将在 $s$ 条道路上安装监控设备。接下来 $s$ 行每行包含一个整数 $p_i$，表示在输入文件中的第 $p_i$ 条道路上安装监控设备（边从 $1$ 开始编号）。

hint:
对于每个测试点，如果你没有输出或者输出不合法则得 $0$ 分。

对于每个测试点，我们设有五个评分参数 $m_1$、$m_2$、$m_3$、$m_4$ 和 $m_5$。假设选手的方案中费用为 $c$，

- 若 $c<m_1$，得 $12$ 分；（备注：赛场上实际为得 $10$ 分）
- 若 $c=m_1$，得 $10$ 分；
- 若 $m_1<c\leq m_2$，得 $8$ 分；
- 若 $m_2<c\leq m_3$，得 $5$ 分；
- 若 $m_3<c\leq m_4$，得 $3$ 分；
- 若 $c<m_5$，得 $1$ 分；
- 否则，得 $0$ 分。


title: [NOISG2021 qualification] Truck

description:
有一棵树，每条边有两个权值 $D_i$ 和 $T_i$，给定 $Q$ 次操作。操作分为两种：

`0 x y t`：表示把 $x$ 和 $y$ 之间的道路的费用改为 $t$。

`1 x y`：表示查询 $x$ 到 $y$ 的费用。

定义 $x$ 到 $y$ 的费用为：给定参数 $G$（对每组询问都相同），要求 $x$ 运送一些价值到 $y$，每经过一条权值为 $D_i$ 和 $T_i$ 的边，会产生运送的价值的 $D_i$ 倍的费用，然后运送的价值会减少 $T_i$。在运送到 $y$ 节点时，若运送到的价值刚好为 $G$，产生的费用就为 $x$ 到 $y$ 的费用。

你要对每组询问计算费用。

inputFormat:
第 $1$ 行两个整数 $N,G$。

第 $2 \sim N$ 行，每行四个整数 $A_i,B_i,D_i,T_i$，表示树上 $A_i$ 和 $B_i$ 有一条边，边权为 $D_i$ 和 $T_i$。

第 $N+1$ 行一个整数 $Q$，表示操作个数。

下面 $Q$ 行，每行一个操作，格式见上。

outputFormat: 若干行，对于每个查询操作，你需要求出费用。每行一个回答。

hint:
#### 数据范围

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

Subtask0 为样例。

Subtask1（5 pts）只有查询操作，每个节点度不超过 $2$，且 $T_i=0$。

Subtask2（9 pts）只有查询操作，且 $T_i = 0$。

Subtask3（12 pts）只有查询操作，$D_i=1$，且所有 $T_i$ 相等。

Subtask4（17 pts）只有查询操作，且每个节点度不超过 $2$。

Subtask5（20 pts）每个节点度不超过 $2$。

Subtask6（18 pts）$N,Q \leq 5000$。

Subtask7（19 pts）无特殊限制。

数据保证 $2 \leq N \leq 10^5$，$1 \leq Q \leq 10^5$，$1 \leq A_i,B_i \leq N$，$1 \leq D_i,T_i,G \leq 10^9$。


title: BZOJ3563 DZY Loves Chinese

description: 给定无向图 $G = (V, E)$，$q$ 次询问每次给定一个边集，求删除该边集后图是否连通。保证边集大小不超过 $15$。强制在线。

inputFormat:
第一行输入两个正整数 $n,m$，表示图的结点数和边数。

接下来 $m$ 行，每行两个正整数 $u_i,v_i$，表示第 $i$ 条边。

接下来输入一行 $Q$，表示询问次数。

接下来 $Q$ 行，每行第一个数为 $k$，而后 $k$ 个正整数 $c_1,c_2,\dots,c_k$ 表示一个大小为 $k$ 的边集，其中 $c_i$ 为边的序号。

为了强制在线，每次的 $k$ 与 $c_1,c_2,\dots,c_k$ 均需异或之前回答为连通的个数。

outputFormat: 对于每个询问输出：连通则为 `Connected`，不连通则为 `Disconnected`（不加引号）。

samples:
Connected
Connected
Connected
Connected
Disconnected

hint: 数据保证，$1\leq n\leq 10^5$，$1\leq m\leq 5\times 10^5$，$1\leq Q\leq 5\times 10^4$，$1\leq k\leq 15$。保证图中没有重边与自环。


title: BZOJ4162 shlw loves matrix II

background: **请注意：本题不是矩阵快速幂模板题。**

description: 给定矩阵 $M$，计算 $M^n$，并将其中每一个元素对 $10^9+7$ 取模输出。

inputFormat:
第一行两个整数 $n,k$，其中 $n$ 用二进制表示，可能含有前导零。

接下来 $k$ 行描述了一个 $k\times k$ 的矩阵 $M$。

outputFormat: 输出题目描述中要求的矩阵，格式同输入。


title: BZOJ3914 Jabby's shadows

description:
给出一棵 $n$ 个点的无根树，树有边权，每个点有两种颜色，最初所有点均为黑色。黑色为 1，白色为 2。每条边有正的权值。

需要维护 $m$ 次操作：
- `1 u`：询问 $u$ 所在树上同色连通块的直径。若为 0，则输出 QwQ。
- `2 u v c`：将 $u \sim v$ 的链覆盖为颜色 $c$。

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

第二行 $n-1$ 个正整数 $f_i$，表示结点 $2\sim n$ 的父结点。

第三行 $n-1$ 个正整数 $e_i$，表示 $2\sim n$ 号结点到父结点的边的边权。

第四行一个正整数 $m$，表示操作数。接下来 $m$ 行依次表示操作。

outputFormat: 对于每个 $1$ 操作输出一行作为答案。

hint: 数据保证，$1\leq n,m\leq 100000$，$1\leq e_i\leq 10000$。


title: BZOJ3706 反色刷

description:
给定 $n$ 个点，$m$ 条边的无向图，边有黑白两种颜色。现在你可以进行若干次回路反色操作，每次操作从任意点出发，每经过一条边，将其颜色反转，最后回到起点。判断能否通过若干次操作，使这张图所有边都变成白色。

因为某种原因，边的颜色是会改变的，即你相当于需要支持以下两种操作：
- `1 x` 将第 $x$ 条边反色（边的编号为 $0\sim m-1$）；
- `2` 求出最少操作次数；

inputFormat:
第一行两个整数 $n,m$ 表示这张图有 $n$ 个点 $m$ 条边。

接下来 $m$ 行，每行 $3$ 个整数 $u,v,c$ 表示一条无向边和这条边的颜色，其中 $0$ 为白色，$1$ 为黑色。

接下来一个整数 $q$，表示有 $q$ 个操作。接下来 $q$ 行操作，描述如上。

outputFormat: 对于每个询问，输出一行一个整数，表示最少需要的反色操作次数。如果没有合法方案输出 $-1$。

hint: 数据保证，$1\leq n,m,q \leq 1000000$，$c < 2$，没有重边自环。


title: BZOJ3569 DZY Loves Chinese II

inputFormat:
第一行输入两个正整数 $n,m$，表示图的结点数和边数。

接下来 $m$ 行，每行两个正整数 $u_i,v_i$，表示第 $i$ 条边。

接下来输入一行 $Q$，表示询问次数。

接下来 $Q$ 行，每行第一个数为 $k$，而后 $k$ 个正整数 $c_1,c_2,\dots,c_k$ 表示一个大小为 $k$ 的边集，其中 $c_i$ 为边的序号。

为了强制在线，每次的 $c_1,c_2,\dots,c_k$ 均需异或之前回答为连通的个数。


title: BZOJ4316 小 C 的独立集

description: 给定简单无向图 $G = (V, E)$，保证每条边属于且仅属于一个简单环，求 $G$ 的最大独立集大小。

inputFormat:
第一行输入两个正整数 $n,m$，表示图的点数与边数。

接下来 $m$ 行，每行两个正整数 $u,v$，描述一条无向边。

outputFormat: 输出 $G$ 的最大独立集大小。

hint: 对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^4$，$1\leq m\leq 6\times 10^4$。


title: BZOJ3028 食物

description:
明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！我们暂且不讨论他有多么 NC，他又幻想了他应该带一些什么东西。理所当然的，你当然要帮他计算携带 $n$ 件物品的方案数。

他这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等。

当然，他又有一些稀奇古怪的限制：

每种食物的限制如下：
- 承德汉堡：偶数个；
- 可乐：$0$ 个或 $1$ 个；
- 鸡腿：$0$ 个，$1$ 个或 $2$ 个；
- 蜜桃多：奇数个；
- 鸡块：$4$ 的倍数个；
- 包子：$0$ 个，$1$ 个，$2$ 个或 $3$ 个；
- 土豆片炒肉：不超过一个；
- 面包：$3$ 的倍数个；

注意，这里我们懒得考虑明明对于带的食物该怎么搭配着吃，也认为每种食物都是以『个』为单位（反正是幻想嘛），只要总数加起来是 $n$ 就算一种方案。因此，对于给出的 $n$，你需要计算出方案数，并对 $10007$ 取模。

inputFormat: 一个整数 $n$，表示总数。

outputFormat: 一个整数，表示方案数模 $10007$。

hint:
- 对于 $40\%$ 的数据，但是 $1\leq n\leq 10^5$；
- 对于所有数据，$1\leq n\leq 10^{500}$；


title: 『DABOI Round 1』Completely Unrelated

description:
我们知道，在平面几何中，三角形是稳定的图形。

小 L 在纸上画了一个图形，他告诉你了这个图形的点数以及哪两个点之间有连边。他想知道这个图形是否具有稳定性。

我们称一个图形具有稳定性当且仅当：确定任意一条边，使其固定住不能移动，则其它的所有边、点都不能移动。注意这里移动仅限在平面内，即不能作轴对称变换。特殊的，一个点具有稳定性。

例如，一条线段或一个三角形，都具有稳定性的，而四边形则不具有稳定性。

请注意，你可以认为稳定性跟边的长度并没有什么关系。所以只要有一组边长使得这个图形稳定，它就是稳定的。而如果没有这样的一组边长满足条件，它就是不稳定的。

inputFormat:
输入共若干行。

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

接下来，对于每组数据，输入共 $m+1$ 行：

- 第 $1$ 行 $2$ 个整数，表示顶点的数量 $n$ 和边的数量 $m$；
- 第 $2$ 至 $m+1$ 行，每行 $2$ 个整数，分别表示一条边连接的两个顶点的编号。

outputFormat:
输出共 $T$ 行。

对于每组数据，输出共 $1$ 行 $1$ 个字符串，其中 $\tt Yes$ 表示图形具有稳定性，反之 $\tt No$ 表示图形不具有稳定性。特别的，若给出的信息无法构成图形，则输出 $\tt No$。

hint:
**【数据范围】**

- 对于 $50\%$ 的数据，$n\le50$，$m\le2\times10^3$；
- 对于 $100\%$ 的数据，$1\le T\le10$，$1\le n\le2\times10^2$，$0\le m\le2\times10^4$。保证无自环，但可能出现重边。


title: 运输规划

background: 你需要规划卡车的运输方案，为了让您更好地解决问题，**请仔细阅读题面。**

description:
有 $n$ 个城市，对于任意 $1 < i \leq n$ 满足第 $i$ 个城市与第 $i-1$ 个城市间有一条双向的道路，每个城市有一个对卡车高度的限制 $h_i$，代表只有高度小于等于 $h_i$ 的卡车可以从这个城市经过，现在有 $m$ 个城市 $S_{1},S_{2},...,S_{m}$ 各有**恰好**一个运输任务，任务要求**编号为 $i$ 且高度为 $h_{S_{i}}$ 的**卡车从城市 $S_{i}$ 出发**到达**任意一个有机场的城市，而有 $m$ 个城市有机场，分别为 $T_{1},T_{2},...,T_{m}$，对于一个合法的运输方案而言，需要保证每个卡车都到达一个机场且每个机场**恰好**有一辆卡车**抵达**。一个机场**可以**同时被多辆卡车**经过**。请注意，如果你无法经过某个城市，那么你也无法抵达这个城市。

记 $c_i$ 表示抵达位于城市 $T_i$ 的机场的的**卡车编号**，令数组 $F = \{c_1,c_2,...,c_m\}$，请你最小化 $F$ 的字典序并输出 $F$。

我们定义两个长度为 $len$ 的数组 $A,B$ 满足 $A$ 的字典序小于 $B$ 当且仅当存在 $0 \leq i < len$ 满足对于任意 $1 \leq j \leq i$ 满足 $A_j = B_j$ 且 $A_{i+1} < B_{i+1}$。

数据保证有解，保证**所有 $h_i$ 互不相同**，所有 $T_i$ 互不相同，所有 $S_i$ 互不相同。但是**可能会**存在 $i,j$ 满足 $S_i = T_j$。

outputFormat: 输出一行 $m$ 个数表示 $F$。


title: [语言月赛 202407] eating

background: 从前有个荣光的王国，小 A 是里面的国王，今天他要赐予他的子民以仓廪。

description:
在一条街上有 $n$ 个饭店。小 A 站在这条街的最左端。

第 $i$ 个饭店离这条街最左端的距离是 $a_i$，它所售卖的菜品的美味值是 $b_i$。

小 A 不想走太多路，但是又想吃到好吃的东西。因此他定义一个饭店的吸引力是 $w_i = \frac{b_i}{a_i}$。

小 A 想知道吸引力最大的饭店的编号是多少。如果有多个吸引力最大的饭店，你要告诉他距离街道左端距离最近的那个饭店的编号。

inputFormat:
第一行是一个整数 $n$，表示商店的个数。
接下来 $n$ 行，每行两个整数，表示一个商店离街道左端的距离 $a_i$ 个菜品美味值 $b_i$。

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

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

- 对 $20\%$ 的数据，$n = 2$。
- 对 $40\%$ 的数据，保证 $b_i$ 是 $a_i$ 的倍数。
- 对 $60\%$ 的数据，保证给出的 $a_i$ 单调递增。
- 对 $80\%$ 的数据，保证 $n \leq 1000$。
- 对 $100\%$ 的数据，保证 $2 \leq n \leq 10^5$，$1 \leq a_i, b_i \leq 10^9$，$a_i$ 互不相同。


title: [NOI2024] 集合

description:
小 Y 和小 S 在玩一个游戏。

给定正整数 $m$，定义**基本集合**为大小为 $3$，元素在 $1\sim m$ 内的集合。例如：给定 $m=4$，则集合 $\{1,2,3\}$ 与集合 $\{2,3,4\}$ 都是基本集合。

定义**集合序列**为由基本集合构成的序列，例如，$A=[\{1,2,3\},\{2,3,4\}]$ 是一个集合序列，其中 $A[1]=\{1,2,3\}$，$A[2]=\{2,3,4\}$ 都是基本集合。

对于一个 $1\sim m$ 的排列 $p[1],p[2],\dots,p[m]$ 与集合 $S\subseteq \{1,2,\dots,m\}$，定义 $f_p(S)$ 为将 $S$ 内每一个元素 $x$ 置换为 $p[x]$ 后所得到的集合，即 $f_p(S)=\{p[x]|x\in S\}$。

对于两个长度为 $k$ 的集合序列 $A,B$，定义 $A$ 和 $B$ **等价**当且仅当存在一个 $1\sim m$ 的排列 $p$，使得 $A$ 置换排列 $p$ 后得到 $B$，即对于所有 $1\leq i\leq k$，$f_p(A[i])=B[i]$。

给定两个长度为 $n$ 的集合序列 $A,B$，有 $q$ 次询问。每次小 S 会询问小 Y，在给定 $l,r$ 的情况下，判断集合序列 $[A[l],A[l+1],\dots,A[r]]$ 与集合序列 $[B[l],B[l+1],\dots,B[r]]$ 是否等价。

时光荏苒，小 S 和小 Y 也会散去。而我们和一个人保持连接的方式就是记住，仅此而已。

inputFormat:
输入的第一行包含三个正整数 $n,m,q$，分别表示集合序列的长度，元素范围和询问次数。

输入的第二行包含 $3n$ 个正整数，第 $3i-2,3i-1,3i$（$1\leq i\leq n$）个正整数分别表示 $A[i]$ 的三个元素。保证这三个元素均在 $[1,m]$ 范围内且互不相同。

输入的第三行包含 $3n$ 个正整数，第 $3i-2,3i-1,3i$（$1\leq i\leq n$）个正整数分别表示 $B[i]$ 的三个元素。保证这三个元素均在 $[1,m]$ 范围内且互不相同。

接下来 $q$ 行，每行包含两个正整数 $l,r$，表示一次询问。

outputFormat: 输出 $q$ 行，每行包含一个字符串 $\tt{Yes}$ 或 $\tt{No}$，表示对应询问的两个序列是否等价。

samples:
见 set2.in/ans
这个样例满足测试点 1-3 的约束条件。

samples:
见 set3.in/ans
这个样例满足测试点 8 的约束条件。

samples:
见 set4.in/ans
这个样例满足测试点 15、16 的约束条件。


title: [NOI2024] 百万富翁

background:
**本题仅支持 C++ 语言评测。由于平台限制，使用 C++14 (GCC 9) 提交代码会导致 CE。请使用其他版本的 C++ 提交（推荐 C++14 及以上）。**

与 NOI 要求的提交格式不同，你的程序中**不应该**包含头文件 `richest.h`。同时，你的程序中应当在包含 `vector` 头文件的前提下，包含对以下函数的声明：

```cpp
std::vector<int> ask(std::vector<int> a, std::vector<int> b);
```

除此之外，其余要求与 NOI 要求一致。

description:
小 Y 的银行有 $N$ 个客户，编号为 $0$ 到 $N-1$。客户 $i$ 有 $W_i$ 元存款，且**客户之间的存款金额互不相同**。

小 P 是小 Y 的深度合作伙伴，他希望知道哪个客户的存款最多。小 P 无法直接获取客户的存款金额，但他可以依次发送若干次**请求**，每次请求包含若干个**查询**，每个查询是一个二元组 $(i,j)$，表示小 P 想知道客户 $i$ 和客户 $j$ 的存款金额哪个更多。如果 $W_i>W_j$，小 Y 会回答 $i$，否则回答 $j$。

小 P 的**请求数** $t$ 和所有请求的**查询**次数总和 $s$ 有上限，他希望你帮他写一个程序，来找到存款最多的客户。

inputFormat:
选手不需要，也不应该实现 main 函数。

选手应确保提交的程序包含头文件 `richest.h`，可在程序开头加入以下代码实现：

```cpp
#include "richest.h"
```

选手需要实现以下函数：
```cpp
int richest(int N,int T,int S);
```
- $N$ 表示客户的数量；
- $T$ 表示对于当前函数调用，**请求**数 $t$ 不应超过此值；
- $S$ 表示对于当前函数调用，所有请求的**查询**次数总和 $s$ 不应超过此值；
- 该函数需要返回存款最多的客户的编号；
- 对于每个测试点，该函数**会被交互库调用恰好 $10$ 次**；

选手可以通过调用以下函数向交互库发送一次**请求**：
```cpp
std::vector <int> ask(std::vector <int> a, std::vector <int> b);
```
- 在调用 `ask` 函数时需要保证传入参数 $a$ 和 $b$ 的长度相同，且其中的每个元素都必须是小于 $N$ 的非负整数，表示该**请求**中的所有**查询**。
- 该函数会返回一个类型为 `std::vector <int>` 且长度与 $a$ 和 $b$ 相同的变量，设为 $c$，其中 $c[i]$ 表示在客户 $a[i]$ 和 $b[i]$ 中存款较多的客户的编号。

题目保证在规定的**请求**和**查询**次数限制下，交互库运行的时间不超过 $3$ 秒，交互库使用的内存大小固定，且不超过 $256$ MiB。

**试题目录下的 `grader.cpp` 是提供的交互库参考实现，最终测试所用的交互库与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。**

选手可以在本题目录下使用如下命令编译得到可执行程序：

```
g++ grader.cpp richest.cpp -o richest -O2 -std=c++14 -static
```

对于编译得到的可执行程序：
- 可执行文件将从**标准输入**读入以下格式的数据：
  - 输入的第一行包含四个非负整数 $N,T,S,R$，其中 $R$ 是交互库生成测试数据的随机种子。
- 输入完成后，交互库将调用 $10$ 次函数 `richest`，用输入的参数生成的测试数据进行测试。`richest` 函数返回后，交互库会输出以下信息：
  - 输出的前 $10$ 行中，每行首先包含三个整数 $r,t,s$，表示该次执行的结果。其中 $r$ 是 `richest` 函数的返回值，$t$ 和 $s$ 的含义如题目描述中所示，然后包含该次运行的正确性等消息。
  - 输出的第 $11$ 行包含 $10$ 次运行的总信息。

hint:
**【下发文件说明】**

在本试题目录下：
- `grader.cpp` 是提供的交互库参考实现。
- `richest.h` 是头文件，选手不用关心具体内容。
- `template_richest.cpp` 是提供的示例代码，选手可在此代码的基础上实现。

选手注意对所有下发文件做好备份，最终评测时只测试本试题目录下的 `richest.cpp`，对该程序以外文件的修改不会影响评测结果。

**【数据范围】**

对于所有测试数据保证：所有 $W_i$ 两两不同。

本题共 $2$ 个测试点，每个测试点的分值和数据范围见下表。

| 测试点编号 | 分值 | $N=$ | $T=$ | $S=$ |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $15$ | $1\,000$ | $1$ | $499\,500$ |
| $2$ | $85$ | $1\,000\,000$ | $20$ | $2\,000\,000$ |

**【评分方式】**

注意：
- 选手不应通过非法方式获取交互库的内部信息，如试图直接读取数组 $W$ 的值，或直接与标准输入、输出流进行交互。此类行为将被视为作弊。
- **最终的评测交互库与样例交互库的实现不同，且可能是适应性的：在不与 `ask` 此前返回的结果相矛盾的前提下，最终的评测交互库可能会动态调整 $W$ 的值。**

**本题首先会受到和传统相同的限制**。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制都会导致相应测试点得 0 分。选手只能在程序中访问自己定义的和交互库给出的变量或数据，及其相应的内存空间。尝试访问其他位置空间将可能导致编译错误或运行错误。

在每次 `richest` 函数调用中，程序使用的请求次数 $t$ 和所有请求的查询次数总和 $s$ 需在对应限制下，否则将会获得 $0$ 分。

在上述条件基础上：
- 在测试点 $1$ 中，程序得到满分当且仅当 `ask` 函数调用合法且 `richest` 函数返回的答案正确；
- 在测试点 $2$ 中，程序得到的分数将按照以下方式计算：
  - 若 `ask` 函数调用不合法，则获得 $0$ 分；
  - 若 `ask` 函数调用均合法，设 $\max t$ 表示多次调用 `richest` 函数所得的 $t$ 的最大值，$\max s$ 表示 $s$ 的最大值，则程序将获得 $\lfloor 85 \cdot f(\max t) \cdot g(\max s)\rfloor$ 分，其中 $f$ 与 $g$ 的计算方式如下表所示：

| $\max t$ | $f(\max t)$ |
| :----------: | :----------: |
| $\max t\leq 8$ | $1$ |
| $9\leq \max t\leq 20$ | $1-\dfrac{1}{4}\sqrt{\max t-8}$ |

| $\max s$ | $g(\max s)$ |
| :----------: | :----------: |
| $\max s\leq 1\,099\,944$ | $1$ |
| $1\,099\,945\leq \max s\leq 1\,100\,043$ | $1-\dfrac{1}{6} \log_{10} (\max s-1\,099\,943)$ |
| $1\,100\,044\leq \max s\leq 2\,000\,000$ | $\dfrac{2}{3}-\dfrac{1}{1\,500}\sqrt{\max s-1\,100\,043}$|

以下是测试点 $2$ 中，不同的 $t$ 和 $s$ 对得分影响的示例。

| $\max t$ |            $\max s$            | 测试点 $2$ 的得分 |
| :------: | :----------------------------: | :---------------: |
|  $=20$   |       $\le 1\,099\,944$        |       $11$        |
|  $=19$   |       $\le 1\,099\,944$        |       $14$        |
|  $=18$   |       $\le 1\,099\,944$        |       $17$        |
|  $=17$   |       $\le 1\,099\,944$        |       $21$        |
|  $=16$   |       $\le 1\,099\,944$        |       $24$        |
|  $=15$   |       $\le 1\,099\,944$        |       $28$        |
|  $=14$   |       $\le 1\,099\,944$        |       $32$        |
|  $=13$   |       $\le 1\,099\,944$        |       $37$        |
|  $=12$   |       $\le 1\,099\,944$        |       $42$        |
|  $=11$   |       $\le 1\,099\,944$        |       $48$        |
|  $=10$   |       $\le 1\,099\,944$        |       $54$        |
|   $=9$   |       $\le 1\,099\,944$        |       $63$        |
| $\le 8$  | $\in [1\,099\,974,1\,099\,978]$ |       $63$        |
| $\le 8$  | $\in [1\,099\,969,1\,099\,973]$ |       $64$        |
| $\le 8$  | $\in [1\,099\,965,1\,099\,968]$ |       $65$        |
| $\le 8$  | $\in [1\,099\,962,1\,099\,964]$ |       $66$        |
| $\le 8$  | $\in [1\,099\,959,1\,099\,961]$ |       $67$        |
| $\le 8$  | $\in [1\,099\,957,1\,099\,958]$ |       $68$        |
| $\le 8$  | $\in [1\,099\,955,1\,099\,956]$ |       $69$        |
| $\le 8$  | $\in [1\,099\,953,1\,099\,954]$ |       $70$        |
| $\le 8$  |         $=1\,099\,952$          |       $71$        |
| $\le 8$  |         $=1\,099\,951$          |       $72$        |
| $\le 8$  | $\in [1\,099\,949,1\,099\,950]$ |       $73$        |
| $\le 8$  |         $=1\,099\,948$          |       $75$        |
| $\le 8$  |         $=1\,099\,947$          |       $76$        |
| $\le 8$  |         $=1\,099\,946$          |       $78$        |
| $\le 8$  |         $=1\,099\,945$          |       $80$        |
| $\le 8$  |       $\le 1\,099\,944$        |       $85$        |


title: [NOI2024] 树的定向

description:
给定一棵含有 $n$ 个顶点的树，顶点从 $1$ 到 $n$ 编号，树上第 $i(1\leq i\leq n-1)$ 条边连接顶点 $u_i$ 和 $v_i$。

现在，我们想要给树的每条边一个定向。任何一个定向都可以用一个长度为 $n-1$ 的字符串 $S=s_1s_2\ldots s_{n-1}$ 来描述。其中 $s_i=0$ 代表第 $i$ 条边定向为 $u_i \to v_i$，否则 $s_i=1$ 代表第 $i$ 条边定向为 $v_i\to u_i$。

给定 $m$ 个顶点对 $(a_i,b_i)$，其中 $1\leq a_i,b_i \leq n$ 且 $a_i\neq b_i$。

一个**完美定向**定义为：在此定向下，对于任意 $1\leq i\leq m$，$a_i$ ****不能到达**** $b_i$。

试求在所有完美定向中，所对应的字符串字典序最小的定向。**数据保证存在至少一个完美定向**。

定义字符串 $S=s_1s_2\ldots s_{n-1}$ 的字典序小于 $T=t_1t_2\ldots t_{n-1}$ 若存在一个下标 $k$ 使得 $s_1=t_1, s_2=t_2, \ldots, s_{k-1}=t_{k-1}$ 且 $s_k < t_k$。

inputFormat:
输入的第一行包含三个非负整数 $c,n,m$，分别表示测试点编号，树的点数，顶点对的个数。其中 $c=0$ 表示该测试点为样例。

接下来 $n-1$ 行，每行包含两个正整数 $u_i,v_i$ 表示树的一条边。保证 $1\leq u_i,v_i\leq n$ 且这 $n-1$ 条边构成了一棵树。

接下来 $m$ 行，每行包含两个正整数 $a_i,b_i$。保证 $1\leq a_i,b_i \leq n$ 且 $a_i\neq b_i$。

outputFormat: 输出一行包含一个字符串 $S=s_1s_2\ldots s_{n-1}$，表示字典序最小的完美定向所对应的 $01$ 字符串。

samples:
见 tree3.in/tree3.ans
这个样例满足测试点 1-3 的约束条件。

samples:
见 tree4.in/tree4.ans
这个样例满足测试点 4-6 的约束条件。

samples:
见 tree5.in/tree5.ans
这个样例满足测试点 7,8 的约束条件。

samples:
见 tree6.in/tree6.ans
这个样例满足测试点 9,10 的约束条件。


title: [入门赛 #25] sql

background: sql 是一种强大的数据库查询语言。在本题中，你需要实现一个部分功能的 sql 解析器。

description:
一个数据库可以看作若干张二维表的合集。

例如，一个学生信息管理系统的数据库可能会有如下两张二维表：

`basic_info`：

| name | sid | grade|
| :-: | :-: | :-: |
| Fusu | 001 | 1 |
| Maxmilite| 002 | 2|
| Expect2004 | 003 | 2 |

`GPA`:

| sid | GPA |
| :-: | :-: |
| 001 | 77.88|
| 002| 99.9 |
| 003| 99.7 |

上述表的第一行称作**表头**，接下来每一行表示表的一组信息。例如，`basic_info` 的第二行表示存在一名学生的姓名（`name`）是 $\texttt{Fusu}$，学号 (`sid`) 为 $\texttt{001}$，年级（`grade`）为 $\texttt{1}$

一个正式的 sql 语言应该支持跨表查询，但是在本题中，你只需要支持在单个表内的查询。我们认为表内的一切属性都以字符串的形式给出。

你需要支持如下格式的查询语句：

```sql
select [columns] from [table_name] where [header]=x
```

上式中，`columns` 是若干个**表头**，`table_name` 是**表名**，`header` 是**表头**，$x$ 是给出的条件。它表示在 `table_name` 这个表里查询 `header` 这一列为 $x$ 的所有行的所有 `columns` 列里的信息。

例如，如果对上述例子里的表执行如下语句：

```sql
select name from basic_info where grade=1
```
表示在 `basic_info` 表里查询 `grade` 列为 $1$ 的所有行，并输出它们的 `name` 列，因此结果为：

```plain
Fusu
```

如果执行

```sql
select name,sid,grade from basic_info where grade=2
```

那么就找到 `basic_info` 表里所有 `grade` 为 `2` 的行，并依次输出它们的 `name`、`sid`、`grade`。结果为：

```plain
Maxmilite 002 2
Expect2004 003 2
```

可以看到，`select` 语句的第一组参数 `columns` 可以是多个表头名称，此时应该按照 `columns` 给出的顺序输出每个对应的列信息。通过 `where` 后面的条件可以查询到多行满足要求的行时，应按照表的输入顺序（即从上到下）输出每行要求的信息。

你需要实现这个 sql 语句解析器，给出 sql 查询结果。注意，我们保证了在查询语句里表名只有一个，且 `where` 后面的条件有且仅有一个等式。

inputFormat:
输入的第一行是一个整数 $n$，表示数据库中表的个数。

接下来依次给出每张表的信息：
第一行是一个字符串 `table_name`，表示表的名称。
第二行有两个整数 $x,y$，表示这张表的大小为 $x$ 行 $y$ 列。
第三行有 $y$ 个字符串，表示这张表的表头。
接下来 $x - 1$ 行，每行 $y$ 个字符串，给出这张表上每一行的信息。

接下来是一个整数 $m$，表示 sql 语句的数量。

接下来 $m$ 行，每行一个 sql 语句，格式一定是

```sql
select [columns] from [table_name] where [header]=x
```

保证 `columns`、`table_name`、`header`、`x` 这四个参数内部没有空格。

数据保证查询语句合法，即 `columns`、`table_name`、`header` 这三个参数所提供的表头、表名都是存在的，且给出的查询条件一定能找到至少一行符合，即查询结果非空。

保证 `columns` 里没有重复的表头名。

outputFormat:
对于每个查询，输出若干行，依次表示查询结果。

一行查询结果里，如果有若干个列的信息要输出，输出字符串之间用一个空格隔开。

samples:
1
basic_info
4 3
name sid grade
Fusu 001 1
Maxmilite 002 2
Expect2004 003 2
2
select name from basic_info where grade=1
select sid,name from basic_info where grade=2

samples:
2
basic_info
4 3
name sid grade
Fusu 001 1
Maxmilite 002 2
Expect2004 003 2
GPA
2 2
sid GPA
001 77.88
1
select GPA from GPA where sid=001

samples:
2
show_corner
3 2
h1 h2
1 2
1 2
show_corner2
3 1
h0
1
1
2
select h1,h2 from show_corner where h1=1
select h0 from show_corner2 where h0=1

hint:
### 样例 3 解释

输入的表单可能有若干行是重复的，你无需对这些行做特殊处理，可以认为它们是不同的。每次查询需要输出所有符合要求的行。例如，在第一条 sql 中，`1 2` 这一行出现了两次且符合要求，因此输出了两次 `1 2`。

### 数据规模与约定

| 测试点编号 | 表的数量为 $1$ | 表头数量为 1 |  columns 里仅有一列表头 |
| :-: | :-: | :-: | :-:|
| 1, 2 | $\checkmark$ | $\checkmark$ | $\checkmark$ |
| 3, 4 | $\checkmark$ | $\times$ | $\checkmark$ |
| 5, 6 | $\times$ | $\checkmark$ |$\checkmark$ |
| 7, 8 | $\times$ | $\times$ | $\checkmark$ |
|9, 10 | $\times$ | $\times$ | $\times$ |

对全部的测试数据，保证：

- $1 \leq n \leq 10$。
- $1 \leq x\leq 100$，$1 \leq y \leq 10$。
- $1 \leq m \leq 1000$。
- 表头 `table_name` 长度不超过 $100$。
- 表的内容和表头的字符串长度不超过 $10$，`columns` 的长度不超过 $100$。
- 除了 `columns` 信息以外，输入的字符串均不含有逗号 `,`。
- 输入字符串均为可见字符，ASCII 范围为 $32\sim 126$（含两端），且不含符号 `=`。

### 提示

请注意大量数据输出对程序效率造成的影响，选择合适的输出方式，避免超时。


title: [语言月赛 202407] value

background: 从前有个荣光的王国，小 A 是里面的国王，今天他要赐予他的子民以价值。

description:
小 A 发现他的国家的价值可以使用 $x, y, z, w$ 四个非负整数衡量。但是为了维持平衡，现在他想要让 $x$ 和 $z$，$y$ 和 $w$ 保持一个相对稳定的比例。

现在他想要知道，是否可以找到一个正整数 $c$，使得 $x = z \times c$ 且 $y = w \times c$。请你帮助他找到这个正整数。

inputFormat: 一行四个整数 $x, y, z, w$。

outputFormat: 一行一个整数。如果可以找到一个正整数 $c$ 满足题目的条件，则输出这个 $c$。否则输出 $-1$。

hint:
### 样例解释

- 可以发现 $9 = 3 \times 3, 6 = 3 \times 2$，$3$ 可以成为样例 1 的 $c$。
- 对样例 2，不能找到任何一个正整数 $c$ 满足题目条件。
- 需要注意 $x, y, z, w$ 有可能是 $0$。

### 数据规模与约定

对 $100\%$ 的数据，保证 $0 \leq x, y, z, w \leq 10^3$，且 $x, y, z, w$ 不同时为 $0$。


title: [NOI2024] 分数

description:
小 Y 和小 C 在玩一个游戏。

定义正分数为分子、分母都为正整数的既约分数。

定义**完美正分数集合** $S$ 为满足以下五条性质的正分数集合：
- $\dfrac{1}{2}\in S$；
- 对于 $\dfrac{1}{2}<x<2$，$x\not \in S$；
- 对于所有 $x\in S$，$\dfrac{1}{x}\in S$；
- 对于所有 $x\in S$，$x+2 \in S$；
- 对于所有 $x\in S$ 且 $x>2$，$x-2 \in S$；

可以证明，上述五条性质确定了唯一的完美正分数集合 $S$。

所有完美正分数集合 $S$ 中的正分数被称为**完美正分数**。记 $f(i,j)$ 表示 $\dfrac{i}{j}$ 是否为完美正分数，即 $f(i,j)=1$ 当且仅当 $i$ 与 $j$ 互素且 $\dfrac{i}{j} \in S$，否则 $f(i,j)=0$。

小 C 问小 Y：给定 $n,m$，求所有分子不超过 $n$，分母不超过 $m$ 的完美正分数的个数，即求 $\sum_{i=1}^n \sum_{j=1}^m f(i,j)$。

时光走过，小 C 和小 Y 会再遇见。回首往事，大家都过上了各自想要的生活。

inputFormat: 输入的第一行包含两个正整数 $n$ 和 $m$，分别表示分子和分母的范围。

outputFormat: 输出一行包含一个非负整数，表示对应的答案。

samples:
见 fraction3.in/ans
这个样例满足测试点 11-14 的约束条件

samples:
见 fraction4.in/ans
这个样例满足测试点 15-17 的约束条件


title: [NOI2024] 登山

description:
“为什么要攀登？因为山就在那里。”

慕士塔格山上有 $n$ 处点位，点从 $1$ 到 $n$ 编号，$1$ 号点位为山顶。这 $n$ 个点位构成一棵有根树的结构，其中 $1$ 号点位为根，对于 $2\leq i\leq n$，$i$ 号点位的父亲结点为 $p_i$ 号点位。

记 $d_i$ 为 $i$ 号点位到山顶所需经过的边数。形式化地说，$d_1=0$，对于 $2\leq i\leq n$，$d_i=d_{p_i}+1$。

定义一条**登山路径**为从 $2\sim n$ 号点位中的某一个开始，经过若干次**移动**后**到达山顶**的方案。

定义一次从 $i(2\leq i\leq n)$ 号点位出发的**移动**为以下两种方式之一：
1. 冲刺：在给定的冲刺范围 $[l_i,r_i]$ 内，选择一个正整数 $k$ 满足 $l_i\leq k\leq r_i$，向山顶移动 $k$ 步，即移动至 $i$ 号点位在有根树上的 $k$ 级父亲处。保证 $1\leq l_i\leq r_i\leq d_i$。
2. 休息：由于慕士塔格山地形陡峭，休息时会滑落到某一个儿子结点处。形式化地说，选择一个满足 $p_j=i$ 的 $j$，移动至到 $j$ 号点位。特别地，若 $i$ 号点位为有根树的叶子结点，则不存在满足 $p_j=i$ 的 $j$，因此此时不能选择休息。

定义一条**登山路径**对应的**登山序列**为初始点位以及每次移动到的点位所构成的序列。形式化地说，一条从 $x$ 号点位开始的**登山路径**对应的****登山序列****是一个点序列 $a_1=x,a_2,\dots,a_m=1$ 满足对于 $1\leq i<m$，$a_{i+1}$ 是 $a_i$ 的 $k(l_{a_i}\leq k\leq r_{a_i})$ 级祖先或 $p_{a_{i+1}}=a_i$。

为了保证每次冲刺都能更接近山顶，一条**合法的登山路径**需要满足：对于初始点位或某次移动到的点位 $i$，以后冲刺到的点位 $j$ 都必须满足 $d_j<d_i-h_i$，其中 $h_i$ 是一个给定的参数，保证 $0\leq h_i<d_i$。形式化地说，一条**合法的登山路径**对应的**登山序列** $a_1,a_2,\dots,a_m$ 需要满足：对于所有 $1\leq i<j\leq m$，若 $p_{a_j} \neq a_{j-1}$，则 $d_{a_j}<d_{a_i}-h_{a_i}$。

对于 $2\sim n$ 号所有点位，求从这些点位开始的**合法的登山路径**条数。两条**登山路径**不同当且仅当其对应的**登山序列**不同。由于答案可能较大，你只需要求出答案对 $998\,244\,353$ 取模后的结果。

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

输入的第一行包含一个整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

输入的第二行包含一个整数 $t$，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

输入的第一行包含一个整数 $n$，表示慕士塔格山的点位数量。

接下来 $n-1$ 行，第 $i-1(2\leq i\leq n)$ 行包含四个整数 $p_i,l_i,r_i,h_i$。保证 $1\leq p_i<i$，$1\leq l_i\leq r_i\leq d_i$，$0\leq h_i<d_i$。

outputFormat: 对于每组测试数据，输出一行 $n-1$ 个整数，分别表示从点位 $2\sim n$ 到达山顶的方案数对 $998\,244\,353$ 取模后的结果。

samples:
见 mountain4.in/ans
这个样例满足测试点 11,12 的约束条件


title: [NOI2024] 树形图

background: 由于评测机性能差异，本题时限翻倍。

description:
给定一个 $n$ 个点 $m$ 条边的**简单有向图** $G$，顶点从 $1$ 到 $n$ 编号。其中简单有向图的定义为**不存在重边与自环**的有向图。

定义顶点 $r$ 是有向图 $G$ 的根当且仅当对于 $1\leq k\leq n$，顶点 $r$ 到顶点 $k$ 存在恰好一条**有向简单路径**，其中简单路径的定义为**不经过重复点的路径**。

定义每个点的种类如下：
- 若顶点 $r$ 是图 $G$ 的根，则称顶点 $r$ 为图 $G$ 的**一类点**。
- 若顶点 $r$ 不是图 $G$ 的一类点，且存在一种删边的方案，使得图 $G$ 在删去若干条边后得到的图 $G'$ 满足：所有图 $G$ 中的一类点都是 $G'$ 的根，且顶点 $r$ 也是图 $G'$ 的根，则称顶点 $r$ 为图 $G$ 的**二类点**。
- 若顶点 $r$ 不满足上述条件，则称顶点 $r$ 为图 $G$ 的**三类点**。

根据上述定义，图 $G$ 的每个点都恰好属于一类点，二类点，三类点之一。你需要判断点 $1\sim n$ 分别属于这三个种类中的哪一种。

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

输入的第一行包含一个非负整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

输入的第二行包含一个正整数 $t$，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

输入的第一行包含两个正整数 $n,m$，分别表示有向图的点数和边数。

接下来 $m$ 行，每行包含两个正整数 $u,v$，表示一条从 $u$ 到 $v$的有向边。保证 $1\leq u,v\leq n$，且给定的有向图 $G$ 不存在重边与自环。

outputFormat: 对于每组数据，输出一行包含一个长度恰好为 $n$ 的字符串 $s$ 表示每个点的种类。其中 $s_i=1$ 表示点 $i$ 为**一类点**，$s_i=2$ 表示点 $i$ 为**二类点**，$s_i=3$ 表示点 $i$ 为**三类点**。


title: 【MX-J2-T1】Turtle and Sequences

description:
给你一个序列 $a_1, a_2, \ldots, a_n$。你可以对这个序列进行若干次操作。

设一次操作前序列长度为 $m$，那么这次操作你可以选择一个整数 $i$ 使得 $1 \le i \le m - 1$ 且 $a_i \ne a_{i + 1}$，删除 $a_{i + 1}$ 并把 $a_i$ 的值设成**任意整数**。

求你最多能进行多少次操作。

inputFormat:
第一行包含一个正整数 $n$，表示序列的初始长度。

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

outputFormat: 一行一个非负整数，表示最多能进行的操作次数。


title: 【MX-J2-T2】Turtle and Strings

description:
给你一个仅由小写字母组成的字符串 $s$。

一个字符串序列 $t_1, t_2, \ldots, t_k$ 是合法的当且仅当：

- $s = t_1 + t_2 + \cdots + t_k$，此处 $+$ 为字符串拼接；
- $\forall 1 \le i \le k - 1, t_i \ne t_{i + 1}$。

求合法的字符串序列的长度的最大值。

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

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

对于每组测试数据：

第一行包含一个正整数 $n$，表示字符串的长度。

第二行包含一个长度为 $n$ 的仅由小写字母组成的字符串 $s$。

outputFormat: 对于每组数据，输出一行一个整数，表示合法的字符串序列的长度的最大值。


title: 【MX-J2-T3】Piggy and Trees

description:
给你一棵 $n$ 个结点的树。

定义 $f(u, v, i)$ 为，在所有满足 $^\dagger\text{dis}(u, x) + \text{dis}(v, x) = \text{dis}(u, v)$ 的点 $x$ 中，$\text{dis}(x, i)$ 的最小值。

求 $\sum\limits_{u = 1}^n \sum\limits_{v = u + 1}^n \sum\limits_{i = 1}^n f(u, v, i)$ 对 $10^9 + 7$ 取模的值。

$^\dagger\text{dis}(u, v)$ 为树上 $u, v$ 两点的路径长度。特别地，$\text{dis}(u, u) = 0$。

inputFormat:
第一行包含一个整数 $n$，表示树的结点数。

之后的 $n - 1$ 行中的第 $i$ 行包含两个整数 $u_i, v_i$，表示树上的一条边。

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


title: 【MX-J2-T4】Turtle and Cycles

description:
给你一个环形的 $0 \sim n - 1$ 的**排列** $a_0, a_1, \ldots, a_{n - 1}$。

一次操作你可以选择一个整数 $i \in [0, n - 1]$，把 $a_i$ 赋值成 $a_{(i - 1) \bmod n} + a_{(i + 1) \bmod n} - a_i$。

一个位置 $i \in [0, n - 1]$ 是好的当且仅当 $a_{(i - 1) \bmod n} < a_i$ 且 $a_{(i + 1) \bmod n} < a_i$。

环形序列 $a$ 是好的当且仅当存在**恰好**一个位置 $i \in [0, n - 1]$ 使得位置 $i$ 是好的。

求至少要进行多少次操作能让 $a$ 变成好的。可以证明一定有解。

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

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

对于每组测试数据：

第一行包含一个正整数 $n$。

第二行包含 $n$ 个非负整数 $a_0, a_1, \ldots, a_{n - 1}$。

outputFormat: 对于每组数据，输出一行一个整数，表示最少要进行的操作次数。


title: 【MX-S2-T1】变

description:
已知一个仅由小写英文字母构成的字符串 $s$。

每次操作时，你可以任意选择 $s$ 中的一个字符，并将它修改为任意小写英文字母。

你可以按任意顺序对其进行不超过 $k$ 次操作，以最小化 $s$ 的**严格循环节**的长度。当然，不进行操作也是可以的。

请输出在进行完所有操作后，最小的可能的 $s$ 的严格循环节的长度。

> 一个字符串 $t$ 被称为 $s$ 的严格循环节，当且仅当 $s$ 可以通过将 $t$ 重复若干次来构造。
>
> 例如：`mai` 是 `maimai` 的严格循环节，`dx` 是 `dx` 的严格循环节。但 `ov` 不是 `ovo` 的严格循环节。

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

第二行一个字符串 $s$，仅包含小写英文字母。

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

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

可以证明：最多进行一次操作的情况下，严格循环节长度至少为 $4$。

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

可以通过 $3$ 次操作，将 `test` 修改为 `ssss`，严格循环节长度为 $1$。

**【数据范围】**

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

- Subtask 0（17 pts）：$k = 0$，$|s| \leq 6$。
- Subtask 1（14 pts）：$k = 1$，$|s| \leq 20$。
- Subtask 2（16 pts）：$k = 1$，$|s| \leq 500$。
- Subtask 3（32 pts）：$k < |s| \leq 10^5$。
- Subtask 4（21 pts）： 无特殊限制。

对于所有测试数据，保证 $0 \leq k < |s| \leq 10^6$，$s$ 中仅包含小写英文字母。

**2024.7.28：新增了一组 Hack 数据。**


title: 【MX-S2-T3】跳

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

~~跳一跳世界第一。~~

~~不处，不收徒，差距自己找。~~

description:
给定一个坐标轴，范围是 $1\sim n$。每个点 $i$ 可以跳到 $i+1$（$i+1\le n$）或 $i-1$（$i-1\ge 1$）或他的因子处。每个点只能到达一次。问从点 $n$ 到点 $1$ 一共有多少方案。答案对 $p$ 取模。

两种方案不同当且仅当存在一次跳跃后的位置不同或存在一次跳跃的种类不同。

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

outputFormat: 一行一个整数，表示答案对 $p$ 取模后的结果。

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

设 $\rightarrow$ 表示向上或向下跳，$\Rightarrow$ 表示跳因子。共三种方案如下。
+ $3\Rightarrow1$
+ $3\rightarrow2\rightarrow1$
+ $3\rightarrow2\Rightarrow1$

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

设 $\rightarrow$ 表示向上或向下跳，$\Rightarrow$ 表示跳因子。共七种方案如下。

+ $4\rightarrow3\Rightarrow1$
+ $4\rightarrow3\rightarrow2\rightarrow1$
+ $4\rightarrow3\rightarrow2\Rightarrow1$
+ $4\Rightarrow2\rightarrow3\Rightarrow1$
+ $4\Rightarrow2\rightarrow1$
+ $4\Rightarrow2\Rightarrow1$
+ $4\Rightarrow1$

**【数据范围】**

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

- Subtask 0（8 pts）：$n\le20$。
- Subtask 1（11 pts）：$n\le150$。
- Subtask 2（23 pts）：$n\le300$。
- Subtask 3（26 pts）：$n\le1000$。
- Subtask 4（32 pts）：无特殊限制。

对于所有测试数据，$1\le n\le5\times10^3$，$2\le p\le 10^9+7$。


title: [CEOI2024] 海战

description:
**题目译自 [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day1 T1「[Naval battle](https://ceoi2024.fi.muni.cz/page/tasks/statements/battle.pdf)」**

捷克海军司令官翁德拉刚刚晋升为大元帅，正享受着新职位的安稳，却突然被政府通知海军将被裁撤。

翁德拉决心证明捷克海军的重要性。他通过间谍得知，一场四国海军巨舰对决即将展开。如果能赢得这场战役，无疑能向政府有力地展示海军价值。

然而，捷克海军既无战舰也无港口。但翁德拉想到，如果他的间谍能夺取几艘参战舰艇，或许还有一线生机。关键是，如何预知哪些船能在这场海战中幸存下来呢？

海战规则如下：
- 战前，第 $i$ 艘战舰位于坐标 $(x_i, y_i)$ 处，其中 $x_i$ 和 $y_i$ 均为偶数。每艘战舰隶属于北方、南方、东方或西方舰队之一。
- 海战分回合进行。每回合：
    - 每艘战舰同时向其所属舰队方向移动一格。
    - 如果两艘或以上战舰占据同一格，它们将相撞沉没，从海图上消失。
- 当不再发生碰撞时，海战结束。存活的战舰是指海战结束后仍留在海图上的战舰。

各舰队战舰的移动方向及坐标变化如下：
- 北方舰队：$y$ 坐标减 $1$
- 南方舰队：$y$ 坐标加 $1$
- 东方舰队：$x$ 坐标加 $1$
- 西方舰队：$x$ 坐标减 $1$

inputFormat:
第一行输入一个整数 $N$，代表参与海战的舰船总数。 接下来是 $N$ 行，每行包含三个用空格隔开的整数 $x_i, y_i, d_i$。$x_i$ 和 $y_i$ 表示第 $i$ 艘舰船的初始位置，字符 $d_i$ 表示第 $i$ 艘舰船所属舰队的方向，它可以是 `N`、`S`、`E` 或 `W` 之一。

初始时没有两艘舰船的坐标相同。换句话说，对于任何两艘不同的舰船 $i$ 和 $j$，它们的横坐标 $x_i$ 和 $x_j$ 不可能同时相等，纵坐标 $y_i$ 和 $y_j$ 也不可能同时相等。

outputFormat:
对于每艘存活的战舰，单独输出一行，包含该舰船的编号 $i\ (1 \leq i \leq N)$。你可以按照任何顺序输出幸存舰船的编号。

如果没有存活的战舰，则输出为空。


title: [CEOI2024] 核酸检测

description:
**题目译自 [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day1 T2「[COVID tests](https://ceoi2024.fi.muni.cz/page/tasks/statements/covid.pdf)」**

亚当的学校最近爆发了新一波 COVID 疫情。为了防止疫情进一步蔓延，学校决定用唾液抗原检测试剂对所有学生进行检测。

由于老师们很久没用过这些试剂了，亚当自告奋勇地成为了检测志愿者。他拿到了来自 $N$ 个学生的唾液样本（出于隐私保护，他只能看到编号从 $0$ 到 $N-1$ 的标识符），他的任务是确定哪些样本呈阳性。

然而，亚当很快意识到，挨个检测所有学生的样本实在太耗时费力了。他灵机一动，想到了一种比逐个检测更巧妙的方法。如果他将部分样本混合在一起进行检测，他就能知道整个混合物是全部阴性，还是至少有一个阳性。这样一来，他就可以通过这种方式减少所需的检测次数！

每个样本的唾液量都足够进行多次检测。而且，这些检测试剂非常精准，同一个样本绝不会出现不同的检测结果。

在这样的条件下，亚当希望优化检测流程，尽量减少使用的检测次数。但是他目前正在进行检测，所以优化过程就交给你啦！

通过当地的统计数据，亚当了解到任何一个样本呈阳性的概率都等于 $P$，并且一个样本是阳性还是阴性不会影响其他样本的检测结果。也许你可以利用这些信息来帮助亚当优化检测方案？

inputFormat:
这是一道交互题。

你的程序将会处理若干个测试数据。每个测试数据（即程序的一次运行）中，你需要解决 $T$ 个不同的场景。所有场景中，学生数量 $N$ 和阳性样本概率 $P$ 都保持不变，但是哪些学生的样本呈阳性（很可能）在每个场景中都会不同。

你可以自己实现交互协议，也可以使用提供的模板。你可以在「文件」中找到名为 `template.cpp` 的附件，它就是提供的模板。

首先，你的程序应该从标准输入读取一行，包含空格隔开的三个整数 $N, P, T$，分别表示学生数量、阳性样本概率和场景数量。

然后，程序可以向标准输出输出询问信息。每个询问信息应该单独占一行，格式为 `Q`、空格和一个长度为 $N$ 的字符串 $s$。字符串 $s$ 中的每个字符 $s_i$ 都为 `1` 或 `0`，`1` 表示应该将第 $i$ 个学生的样本加入混合物进行检测，`0` 表示不加入。输出完询问信息后，程序需要刷新标准输出缓冲区，然后从标准输入读取一个字符。这个字符会是 `P`（表示混合物中至少有一个样本呈阳性）或 `N`（表示混合物中所有样本均为阴性）。

程序也可以输出最终答案。答案信息应该单独占一行，格式为 `A`、空格和一个长度为 $N$ 的字符串 $s$。字符串 $s$ 中的每个字符 $s_i$ 都为 `1` 或 `0`，`1` 表示第 $i$ 个学生的样本呈阳性，`0` 表示呈阴性。输出完答案信息后，程序同样需要刷新标准输出缓冲区，然后从标准输入读取一个字符。

如果读取到的字符为 `C`，则表示你的答案正确。在这种情况下，程序可以开始处理下一个场景的询问，或者如果是第 $T$ 个场景的答案，则程序可以退出。

如果读取到的字符为 `W`，则表示你的答案错误。程序应该立即退出。

请注意，在收到 `W` 后退出对于交互器给出正确的反馈非常重要。如果你的程序继续运行，它可能会崩溃或收到其他错误的判定。

交互器不会根据你的程序运行结果来动态调整测试数据。这意味着每个样本的阳性与否会在程序运行之前就确定好。并且，每个样本的阳性与否都是通过公平的随机数生成器，以概率 $P$ 独立决定的。

如果你使用 `template.cpp` 中的交互协议实现，你需要实现函数 `std::vector<bool> find_positive()`。这个函数会在每个场景中被调用一次。它需要返回一个长度为 $N$ 的布尔型向量，其中第 $i$ 个元素为 `true` 当且仅当第 $i$ 个学生的样本呈阳性。

实现过程中，你可以使用函数 `bool test_students(std::vector<bool> mask)`。这个函数可以对部分样本进行混合检测。它唯一的参数是一个长度为 $N$ 的布尔型数组，其中第 $i$ 个元素为 `true` 表示应该将第 $i$ 个样本加入混合物进行检测。该函数返回 `true` 当且仅当混合物中至少有一个样本呈阳性。

你也可以使用全局变量 `N` 和 `P`，它们分别代表着总学生人数和阳性样本概率。你可以在 `main` 函数中，首次调用 `scanf` 之后进行初始化操作。

| 示例输入 | 示例输出 |
|------------|----------------|
| `10 0.4 2` |                |
|            | `Q 1000000000` |
| `P`        |                |
|            | `Q 0000001000` |
| `P`        |                |
|            | `Q 0000000001` |
| `P`        |                |
|            | `Q 0111110110` |
| `N`        |                |
|            | `A 1000001001` |
| `C`        |                |
|            | `A 0000000000` |
| `W`        |           |

hint:
本题分为两个子任务。

#### Subtask 1 (10 分)

- 学生总数 $N = 1000$
- 场景数 $T = 1$
- 阳性样本概率 $P$ 在 $0$ 到 $1$ 之间

如果程序能正确回答并且每个测试数据的询问次数不超过 $2$ 倍的总学生人数 $2N$，则认为该程序通过测试。

#### Subtask2 (90 分)

- 学生总数 $N = 1000$
- 场景数 $T = 300$
- 阳性样本概率 $P$ 在 $0.001$ 到 $0.2$ 之间

该子任务具有部分分。

如果你的程序在任何场景的回答错误，你将得 $0$ 分。否则，每个测试数据的得分将基于平均询问次数计算。一般来说，询问次数越少，得分越高。记作程序在所有场景的平均询问次数为 $Q$，四舍五入到小数点后一位。对于每个测试数据，我们计算了一个值 $F$（见下文）。给定测试数据的得分将根据以下规则计算：

- 如果 $Q > 10$ 倍的 $F$，你将得 $0$ 分 (错误答案)。
- 如果 $F < Q \leq 10$ 倍的 $F$，得分由以下公式计算：
  $$ 90 \cdot \frac{F}{F + 4 \cdot (Q-F)} $$
- 如果 $Q \leq F$，你将获得满分 $90$ 分。

你的程序将会在不同 $P$ 值的测试数据上进行评分。你将获得的总分是所有测试数据（所有概率 $P$）中的最低分。

测试数据如下：

| $P$ | $F$ |
|-------|-------|
| $0.001$ | $15.1$ |
| $0.005256$ | $51.1$ |
| $0.011546$ | $94.9$ |
| $0.028545$ | $191.5$ |
| $0.039856$ | $246.3$ |
| $0.068648$ | $366.2$ |
| $0.104571$ | $490.3$ |
| $0.158765$ | $639.1$ |
| $0.2$ | $731.4$ |

交互器会为每个测试数据提供反馈。这些反馈将包括你在得分非零的测试数据上的平均询问次数 $Q$。


title: [CEOI2024] 文本编辑器

description:
**题目译自 [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day1 T3「[Text editor](https://ceoi2024.fi.muni.cz/page/tasks/statements/editor.pdf)」**

罗伯特正在参加 2024 年 CEOI 编程竞赛。他几乎完成了当天最难的一道题的代码，而且他确信能拿满分！但问题出在一个小小的细节上：他打错了一个字！更糟糕的是，他从 2008 年就开始使用的那只心爱鼠标彻底罢工了，一点反应也没有。因此，他只能用键盘上的方向键移动光标去找到那个错别字。

罗伯特的程序有 $N$ 行，每行的长度分别为 $l_1, l_2, \ldots , l_N$。罗伯特总是以空行作为程序的结尾，所以 $l_N = 0$。光标可以放在两个字符之间，也可以放在行的开头或结尾。因此，第 $i$ 行有 $l_i + 1$ 个可用的光标位置（称为列），编号从 $1$ 到 $l_i + 1$。例如，下面是光标位于第 $2$ 行第 $6$ 列的情况：

![editor-position.svg](https://img.loj.ac.cn/2024/07/15/494252df91f49.svg)

罗伯特想把光标从第 $s_l$ 行的第 $s_c$ 列移动到第 $e_l$ 行的第 $e_c$ 列。他想求出最少需要的按键次数。

水平方向键的使用比较简单。按下 **左键** 会将光标移动到前一列，除非光标位于行首，则会移动到前一行的行尾。类似地，按下 **右键** 会将光标移动到后一列，或者如果光标位于行尾，则会移动到下一行的行首。

例如，**左键** 的移动可以像这样：

![editor-key-left.svg](https://img.loj.ac.cn/2024/07/15/33f67480b78c1.svg)

而 **右键** 的移动可以像这样：

![editor-key-right.svg](https://img.loj.ac.cn/2024/07/15/e081311871660.svg)

在文件的最开头按下 **左键** 或在文件的最结尾按下 **右键** 都不会有任何效果。

垂直方向键的使用稍微复杂一些。按下 **上键** 会将光标移动到上一行，按下 **下键** 会将光标移动到下一行，列数不会改变。但是，如果这样会使光标超出新行的结尾，光标则会跳到该行末尾。

例如，**上键** 的移动可以像这样：

![editor-key-up.svg](https://img.loj.ac.cn/2024/07/15/73d9a46afefd8.svg)

而 **下键** 的移动可以像这样：

![editor-key-down.svg](https://img.loj.ac.cn/2024/07/15/f0985815bbb5a.svg)

如果按下 **上键** 或 **下键** 会把光标移动到不存在的行，则光标根本不会移动。

inputFormat:
输入的第一行包含一个整数 $N$，表示罗伯特程序的行数。

第二行包含两个空格隔开的整数 $s_l$ 和 $s_c$，表示初始光标位置。

类似地，第三行包含两个空格隔开的整数 $e_l$ 和 $e_c$，表示目标光标位置。

第四行包含 $N$ 个空格隔开的整数 $l_1, l_2, \ldots , l_N$，表示每行的长度。

outputFormat: 输出一行包含一个整数，表示将光标从 $(s_l, s_c)$ 移动到 $(e_l, e_c)$ 最少的按键次数。

hint:
**样例解释 1**

罗伯特可以通过按顺序按 **上键**、**左键** 和 **下键**三个键来将光标移动到目标位置：

![editor-sample-1.svg](https://img.loj.ac.cn/2024/07/15/7521983c53ac2.svg)

或者，他也可以通过按 **左键**、**上键** 和 **下键** 来同样快速地将光标移动到目标位置。

**样例解释 2**

可以很容易地证明，不可能使用最多两个按键到达目标位置。

最短的可能按键序列是按两次 **下键** 然后按十四次 **右键**。

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

- $1 \leq N \leq 10^6$
- $0 \leq l_i \leq 10^9\ (1\leq i\leq n)$
- $l_N = 0$
- $1 \leq s_l, e_l \leq N$
- $1 \leq s_c \leq l_{s_l} + 1$
- $1 \leq e_c \leq l_{e_l} + 1$

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

| 子任务 | 附加限制 | 分值 |
| :--: | :--: | :--: |
|  $1$  | $N \leq 2$ | $5$  |
|  $2$  | $N \leq 1\,000, l_i \leq 5\,000\ (1 \leq i \leq N)$| $14$ |
|  $3$  | $N \leq 1\,000$ | $26$ |
|  $4$  | $l_i = l_j\ (1 \leq i, j \leq N - 1)$ | $11$ |
|  $5$  | 无附加限制| $44$ |


title: [CEOI2024] 玩具谜题

description:
**题目译自 [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day2 T1「[Toy](https://ceoi2024.fi.muni.cz/page/tasks/statements/toy.pdf)」**

CEOI 2024 的命题人 Ben 从科学委员会收到了一份礼物——一个玩具。这个玩具是个谜题，可以想象成一个 $H$ 行 $W$ 列的网格，上面放着一个金属物体。这个金属物体由两部分组成：一个横向的 $1$ 行 $K$ 列的部分和一个纵向的 $L$ 行 $1$ 列的部分，这两部分松散地连接在一起。它们都不能旋转，但可以在网格内水平或垂直滑动，只要它们始终重叠在一个方格上。

网格里还有一些障碍物。金属物体的任何部分都不能穿过障碍物，更糟糕的是，它们也不能（即使部分）移出网格。Ben 的任务是将金属物体从指定起始位置移动到（可能不同的）目标位置，使得两部分重叠在指定的目标方格上。

然而，Ben 玩这个玩具已经有一段时间了，还没有解开谜题。事实上，他开始怀疑组织者在捉弄他，给了他一个无解的谜题。因此，他向你求助，想知道这个谜题是否有解。

inputFormat:
输入的第一行包含四个空格分隔的整数 $W, H, K, L$，分别表示谜题的宽度、高度、横向部分的宽度和纵向部分的高度。第二行包含四个整数 $x_h, y_h, x_v, y_v$，表示横向部分最左上角方格的坐标和纵向部分最左上角方格的坐标。

行从上到下编号为 $0$ 到 $H-1$，列从左到右编号为 $0$ 到 $W-1$。$x$ 坐标表示列号，$y$ 坐标表示行号。

接下来的 $H$ 行每行包含 $W$ 个字符，表示网格。字符 `.` 表示空方格，字符 `X` 表示障碍物，字符 `*` 表示目标方格。

保证金属物体的初始位置合法，即两部分重叠在一个方格上，并且两部分不与障碍物重叠也不超出网格。

只有一个目标方格，即玩具中只有一个字符 `*`，它可能与金属物体的初始位置重叠。

outputFormat: 如果可以将金属物体移动到目标方格，则输出一行 `YES`，否则输出 `NO`。

hint:
**样例解释 1**

初始状态如下：

![toy-sample1-v3.svg](https://img.loj.ac.cn/2024/07/15/154b44c9149f4.svg)

我们可以先将纵向部分向下移动一格，然后尽可能地交替移动横向和纵向部分，直到无法继续。接着，我们可以将纵向部分向上并向右移动，到达目标方格，最后将横向部分向上移动，也到达目标方格。

**样例解释 2**

无法移动纵向部分而不碰到障碍物，因此永远无法到达目标方格。

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

- $2 \leq W, H \leq 1\,500$
- $2 \leq K \leq W, 2 \leq L \leq H$
- $0 \leq x_h \leq W - K, 0 \leq y_h \leq H - 1$
- $0 \leq x_v \leq W - 1, 0 \leq y_v \leq H - L$

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

| 子任务 | 附加限制 | 分值 |
| :--: | :--: | :--: |
|  $1$  | $W, H \le 50$ | $14$  |
|  $2$  | $W, H \le 90$| $21$ |
|  $3$  | $W, H \le 300, K, L \le 10$ | $9$ |
|  $4$  | $W, H \le 360$ | $29$ |
|  $5$  | 无附加限制| $27$ |


title: [CEOI2024] 加油站

description:
**题目译自 [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day2 T2「[Petrol stations](https://ceoi2024.fi.muni.cz/page/tasks/statements/stations.pdf)」**

捷克的高速公路网络由 $N$ 个城市和 $N-1$ 条路组成，每条路的长度（公里）已知。我们知道任意两个城市之间只有一条路径。此外，每个城市恰好有一个加油站，其他地方没有。

有一天，许多人决定开车旅行。总共有 $N^2$ 辆车在路上。奇怪的是，对于每个有序城市对 $(a, b)$，恰好有一辆车从城市 $a$ 开往城市 $b$，沿着这两个城市之间唯一的路径行驶。由于捷克人全都开斯柯达车，每辆车的油箱容量都是 $K$ 升，并且每公里消耗一升汽油。出发前，每辆车的油箱都是满的。此外，捷克人非常有规律。由于懒惰，他们只在汽油不足以到达下一个城市时才加油（油箱为空时可以进入城市）。一旦他们被迫停在加油站，他们总是把油箱加满。

捷克税务部门想知道当天每个加油站停了多少辆车。鉴于这种可预测的行为，你应该能够轻松计算出来。

inputFormat:
输入的第一行包含两个空格分隔的整数 $N$ 和 $K$，分别表示城市数量和每辆车的油箱容量。

接下来的 $N-1$ 行描述道路。每行包含三个空格分隔的整数 $u_i, v_i, l_i$，其中 $u_i$ 和 $v_i$ 是第 $i$ 条路连接的城市编号，$l_i$ 是这条路的长度（公里）。城市从 $0$ 到 $N-1$ 编号。保证任意两个城市之间只有一条路径。

outputFormat: 输出 $N$ 行，表示从城市 $0$ 到城市 $N-1$ 每个城市加油站停靠的汽车数。

hint:
**样例解释 1**

有 $3$ 座城市呈直线排列，连接它们的道路长度为 $1$，油箱容量为 $1$ 升。只有在两个外围城市之间行驶的汽车会在中间城市加油。

**样例解释 2**

有 $6$ 个城市呈直线排列，油箱容量为 $2$ 升。许多汽车需要在城市 $3$ 和城市 $4$ 加油。这是有道理的，因为城市 $3$ 和城市 $4$ 之间的道路长度为 $2$ 公里。

对于所有输入数据，满足：
- $2 \leq N \leq 70\,000$
- $1 \leq K \leq 10^9$
- $0 \leq l_i \leq K\ (0 \leq i \leq N-2)$

令 $D$ 表示连接到单个城市的道路的最大数量。详细子任务附加限制及分值如下表所示。

| 子任务 | 附加限制 | 分值 |
| :--: | :--: | :--: |
|  $1$  | $N \leq 1\,000, K \leq 1\,000$ | $18$  |
|  $2$  | $D\le 2$ 且 $l_i = 1\ (0 \leq i \leq N-2)$ | $8$ |
|  $3$  | $D\le 2$| $10$ |
|  $4$  | $K\leq 10, D\leq 10$ | $12$ |
|  $5$  | $K\leq 10$ | $17$ |
|  $6$  | 无附加限制| $35$ |


title: [CEOI2024] 洒水器

description:
**题目译自 [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day2 T3「[Sprinklers](https://ceoi2024.fi.muni.cz/page/tasks/statements/sprinklers.pdf)」**

瓦茨拉夫有一个美丽的花园，花园里种了一排 $M$ 朵花。在这一排上，瓦茨拉夫还放置了 $N$ 个洒水器来浇花。

洒水器的位置由数字 $s_1, s_2, \ldots , s_N$ 给出。花的位置由数字 $f_1, f_2, \ldots , f_M$ 给出。两者都是非递减顺序，即：
- $s_1 \leq s_2 \leq \ldots \leq s_N$
- $f_1 \leq f_2 \leq \ldots \leq f_M$

瓦茨拉夫很快就要去参加 CEOI 了。他想确保在他离开期间所有的花都能得到适当的浇水。为此，他可以单独将每个洒水器向左或向右旋转，并设置它们的喷水强度——所有洒水器共享同一个水管，因此喷射距离相同。

如果喷水强度为 $K$，并且第 $i$ 个洒水器向左旋转，它将浇灌位置在 $s_i - K$ 到 $s_i$ 之间的所有花。类似地，如果第 $j$ 个洒水器向右旋转，它将浇灌位置在 $s_j$ 到 $s_j+K$ 之间的所有花。单个洒水器可以浇灌多朵花，一朵花也可以被多个洒水器浇灌。

你的任务是决定是否可以浇灌所有的花。如果是，你应该找到最小的足够喷水强度，以及相应的洒水器配置。如果存在多个具有最小喷水强度的有效配置，输出其中任何一个。

inputFormat: 输入的第一行包含两个用空格隔开的整数 $N$ 和 $M$。第二行包含 $N$ 个空格分隔的整数 $s_1, s_2, \ldots , s_N$，表示洒水器的位置。第三行包含 $M$ 个空格分隔的整数 $f_1, f_2, \ldots , f_M$，表示花的位置。

outputFormat:
如果无法浇灌所有的花，则输出数字 $-1$。

如果可以，输出应该包含两行。第一行输出数字 $K$，表示浇灌所有花所需的最小的喷水强度。在第二行，输出长度为 $N$ 的字符串 $c$，其中 $c_i$ 为 `L`，如果第 $i$ 个洒水器应该向左旋转，否则为 `R`。

hint:
**样例解释 1**

每朵花至少被一个洒水器浇水。喷水强度低于 $6$ 是不可能的，因为位置 $16$ 的花离最近的洒水器有 $6$ 个单位距离。

**样例解释 2**

无论洒水器的方向如何，一次最多只能浇灌一朵花。

对于所有输入数据，满足：
- $1 \leq N,M \leq 10^5$
- $0 \leq s_{i} \leq 10^9\ (1 \leq i \leq N)$
- $0 \leq f_{i} \leq 10^9\ (1 \leq i \leq M)$
- $s_{i} \leq s_{j}\ (i \leq j)$
- $f_{i} \leq f_{j}\ (i \leq j)$

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

| 子任务 | 附加限制 | 分值 |
| :--: | :--: | :--: |
|  $1$  | $N = 1$ | $3$  |
|  $2$  | $N = 3x$，$x$ 是一个整数，$s_{3i+1}=s_{3i+2}=s_{3i+3}\ (0 \leq i \leq x-1)$（即洒水器总是成组放置三个）| $6$ |
|  $3$  | $N \leq 10, M \leq 1\,000$| $17$ |
|  $4$  | $K\leq 8$（即在所有测试数据中，存在一种洒水器配置，使得喷水强度最多为 $8$ 就足以浇灌所有的花） | $27$ |
|  $5$  | 无附加限制| $47$ |


title: 「ALFR Round 4」A 点的覆盖

description:
在平面直角坐标系中，若一个点的横坐标和纵坐标均为整数，则我们称之为整数点。给定一个顶点均为整数点且各边与一条坐标轴平行的矩形 $A$ 和矩形内（可能在其边缘上）的 $n$ 个整数点 $p_1,p_2,p_3,\cdots,p_n$，请问 $A$ 有多少个子矩形满足：

- 顶点均为整数点；

- 四边均与一条坐标轴平行；

- 能全部覆盖（允许在边缘上） $p_1,p_2,p_3,\cdots,p_n$。

本题中矩阵长或宽可以为 $0$。

inputFormat:
第一行五个整数，分别表示给定整数点的个数 $n$，矩形 $A$ 的左上端点的横坐标，左上端点的纵坐标，右下端点的横坐标和右下端点的纵坐标。

第 $2$ 到第 $n+1$ 行，第 $i$ 行两个整数分别表示 $p_{i-1}$ 的横坐标和纵坐标。

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


title: 「ALFR Round 4」D 罪人的终幕

background:
> 而我承诺你，一切都将在一场盛大的，如同戏剧般的审判中结束……
> 小小地旋转，轻轻地跳跃，然后便是「罪人」的谢幕。

description:
定义函数 $a(x)$ 表示自然数 $x$ 的不同的质因子的和。

若 $x=\prod\limits_{p_i\in\mathbb{P}}p_i^{d_i}$，则 $a(x)=\sum\limits_{p_i\in \mathbb{P}}p_i\times[d_i\ge1]$，其中 $\mathbb{P}$ 是质数集，$a(1)=0$。

从诞生的第一天开始，Furina 便有了一个期待值 $m_1$。

在最终的审判来临前，她每天都会选择整理自己的心情，具体的方法如下：

假设今天是第 $i$ 天，Furina 会把今天的期待值 $m_i$ 定为 $\max\{\dfrac{m_j}{a(\operatorname{lcm}(w_i,w_j))+a(\gcd(w_i,w_j))}+k\}$，其中 $2\le i\le n$，$1\le j<i$，$k$ 是观看审判所获得的期待值。

请你求出 $\sum\limits_{i=1}^nm_i$。

inputFormat:
第一行三个整数 $n,m_1,k$ 分别表示第一天距最终的审判（包括第一天）的天数，第一天的期待值和观看审判能获得的期待值。

第二行共 $n$ 个整数表示 $w_1,w_2,w_3,\cdots,w_n$。

outputFormat: 一行一个实数表示 $\sum\limits_{i=1}^nm_i$。**答案与正确答案的绝对误差不超过 $10^{-6}$ 即判为正确**。


title: 【MX-J3-T1】Seats

description:
**注意：题面中所有数组下标都从 $1$ 开始。**

现有一次讲座，有 $a$ 个学生和 $b$ 个老师报名。主办方准备了若干座位，并用一个字符串 $s$ 表示每个座位的类型。对于从左到右的第 $i$ 个座位，$s_i=\texttt{T}$ 表示这是教师座位，$s_i=\texttt{S}$ 表示这是学生座位。

教师座位只能给老师坐，学生座位只能给学生坐，且每个座位只能坐一个人。

然而根据目前的安排方式，并不是所有老师和学生都有自己的座位坐。为此主办方打算进行一些修改。**一次修改**可以选择一个教师座位，将其改成学生座位，或者选择一个学生座位，将其改成教师座位。

请判断至少要多少次修改才能让老师和学生都够坐。特别地，如果无论怎么修改，都无法让所有人有座位，输出 $-1$。

inputFormat:
第一行有两个正整数 $a,b$，分别表示学生和老师人数。

第二行有一个字符串，表示主办方每个座位的类型。

outputFormat: 输出一行一个整数表示答案，见题目描述。

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

有 $3$ 位学生和 $4$ 位老师报名。如果把第 $2$ 个座位调成学生座位，那么学生可以坐第 $1,2,4$ 个座位，教师可以坐第 $3,5,6,7,8$ 个座位中的任意四个。

显然，如果不调整座位，那么学生是不够坐的。

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

无论如何修改，$100$ 名学生和 $100$ 名老师显然不可能只坐在 $4$ 个座位里，因此输出 $-1$。

**【数据范围】**

本题共 $25$ 个测试点，每个 $4$ 分。设 $n$ 为字符串 $s$ 的字符个数。

|测试点编号|$a,b,n\le$|特殊性质|
|:-:|:-:|:-:|
|$1$|$100$|$a=b=100$|
|$2\sim 8$|$100$|$a+b=n$|
|$9\sim 11$|$100$|$s$ 内全是 `S`|
|$12\sim 14$|$100$|$s$ 内全是 `T`|
|$15\sim 21$|$100$|无特殊性质|
|$22\sim 25$|$10^5$|无特殊性质|

对于全体数据，保证 $1\le a,b,n\le 10^5$，字符串 $s$ 内只有大写字母 `S` 或 `T`。


title: 【MX-J3-T3】Tuple

description: 你有 $m$ 个三元组 $(u_i,v_i,w_i)$，保证 $1\le u_i<v_i<w_i\le n$ 且三元组两两不同。有多少组 $(a,b,c,d)$ 满足 $1\le a<b<c<d\le n$，且在这 $m$ 个三元组当中，存在四个三元组 $(a,b,c),\allowbreak (a,b,d),\allowbreak (a,c,d),\allowbreak (b,c,d)$？

inputFormat:
输入的第一行有两个正整数 $n,m$ 表示三元组数字范围和三元组个数。

之后 $m$ 行，每行一组 $u_i,v_i,w_i$ 表示一个三元组。

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


title: 【MX-J3-T4】Partition

description:
你有 $n$ 行 $m$ 列的一个矩阵，第 $i$ 行第 $j$ 列的格子（记作 $(i,j)$）上写有一个整数 $a_{i,j}$。

- 称 $(a,b)$ 在 $(c,d)$ 的**下方**，当且仅当 $b=d,a>c$，即**同一列中，行编号更大**。
- 称 $(a,b)$ 在 $(c,d)$ 的**上方**，当且仅当 $(c,d)$ 在 $(a,b)$ 的**下方**。
- 称 $(a,b)$ 在 $(c,d)$ 的**右边**，当且仅当 $a=c,b>d$，即**同一行中，列编号更大**。
- 称 $(a,b)$ 在 $(c,d)$ 的**左边**，当且仅当 $(c,d)$ 在 $(a,b)$ 的**右边**。

如图，$A(2,2)$ 下方有 $D(3,2),E(4,2)$，右边有 $B(2,3),C(2,4)$。

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

为了让矩阵更加美观，你想要给每个格子涂上红、橙、黄、绿四种颜色之一，有很多种方案，但是如果一个方案满足如下要求，就称这个方案是**简单**的：

- 红色格子的**上方**只能是红色格子，**左边**只能是红色或黄色格子，**右边**只能是红色或橙色格子。
- 橙色格子的**右边**只能是橙色格子，**上方**只能是橙色或红色格子，**下方**只能是橙色或绿色格子。
- 绿色格子的**下方**只能是绿色格子，**右边**只能是绿色或橙色格子，**左边**只能是绿色或黄色格子。
- 黄色格子的**左边**只能是黄色格子，**下方**只能是黄色或绿色格子，**上方**只能是黄色或红色格子。

上图中展示了一些可能的染色方案，其中：

- 第一幅图是简单的。
- 第二幅图也是简单的。注意如果一种颜色的格子不存在，那么可以直接忽略对应要求。
- 第三幅图不是简单的，因为 $F(3,2)$ 绿色格子下方有 $G(4,2)$ 是黄色，不符合第四条要求。

若 $(i,j)$ 的颜色为红、橙、黄、绿，则这个格子的权值 $w_{i,j}$ 分别为 $1,2,3,4$。计算所有简单的方案中，$\sum\limits_{i=1}^n\sum\limits_{j=1}^m a_{i,j} w_{i,j}$ 的最大值。

inputFormat:
输入的第一行是两个正整数 $n,m$，表示矩阵的行数和列数。

之后有 $n$ 行，每行 $m$ 个整数。第 $i$ 行第 $j$ 个整数表示 $a_{i,j}$。

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


title: [COTS/CETS 2023] 三元图 Graf

background:
译自 [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) D1T1。$\texttt{2s,0.5G}$。

祝 NaCly_Fish 生日快乐！（2024.7.28）

description:
对于非负整数 $k$，我们递归地给出 $k-{}$三元图的定义。

- $k-{}$三元图是无向图。
- 对于 $k=0$，$k-{}$三元图 是一个仅包含 $1$ 个节点和 $0$ 条边的图。
- 对于 $k\gt 0$，$k-{}$三元图由三个 $(k-1)-{}$三元图组合而成。具体地说，在这三个 $(k-1)-{}$三元图中各选择一个节点，然后在这三个节点之间两两连边，得到的就是 $k-{}$三元图。

下图展示了一张 $3-{}$三元图。

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

给定无向图 $G$，判断它是否是 $k-{}$三元图。

inputFormat:
第一行，两个正整数，$N,M$，表示 $G$ 的点数和边数。

接下来 $M$ 行，每行两个正整数 $u,v$，表示 $G$ 中的一条边 $(u,v)$。

outputFormat: 如果 $G$ 是 $k-{}$三元图，输出 $\texttt{da}$（克罗地亚语「是」）；否则输出 $\texttt{ne}$（克罗地亚语「否」）。


title: [COTS/CETS 2023] 平均数 Prosjek

background:
译自 [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) D1T2。$\texttt{3s,0.5G}$。

祝 NaCly_Fish 生日快乐！（2024.7.28）

~~**交互库好像出锅了 qwqwq。修复中。**~~

UPD：感谢 @Rainbow_qwq 修复交互库。警示后人：慎用 multiset.count。

description:
在黑板上有 $N$ 个非负整数。在一次操作中，可以选择黑板上的两个整数 $a,b$ 满足 $2\mid (a+b)$，将 $a,b$ 从黑板上擦去，然后写下 $\dfrac{a+b}{2}$。注意到每次操作后，黑板上的数都是整数。

试判断是否能让黑板上只剩下一个数。如果可以的话，还需要给出一组解。

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

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

接下来依次描述 $T$ 组数据。

对于每组数据，第一行，一个正整数 $N$，代表黑板上数的数量。

第二行，$N$ 个非负整数，描述黑板上的数。

outputFormat:
对于每组数据，输出若干行。

如果不可行，输出一行一个 $\texttt{-1}$；

否则，输出 $(N-1)$ 行，每行两个整数，表示每次要擦除的数。你需要保证操作的数是存在的，且它们的和能被 $2$ 整除。

hint:
#### 样例解释

样例 $2$ 解释：$[\boldsymbol{\textcolor{red}{1}},2,3,4,\boldsymbol{\textcolor{red}{5}},6] \to [\boldsymbol{\textcolor{red}{3}},2,\boldsymbol{\textcolor{red}{3}},4,6]\to [3,2,\boldsymbol{\textcolor{red}{4}},\boldsymbol{\textcolor{red}{6}}]\to [\boldsymbol{\textcolor{red}{5}},\boldsymbol{\textcolor{red}{3}},2]\to [\boldsymbol{\textcolor{red}{4}},\boldsymbol{\textcolor{red}{2}}]\to [3]$。

#### 数据范围

对于 $100\%$ 的数据，保证：

- $1\le T\le 10^5$；
- $1\le N,\sum N\le 10^6$；
- $0\le a_i\le 10^{18}$。

| 子任务编号 | 分值 | 约束  |
|:-----:|:------:|:-------:|
| $1$  | $9$  | $T\le 100$，$N\le 7$   |
| $2$  | $23$  | $T\le 100$，$a_i\le 10$  |
| $3$  | $16$  | $a_i$ 都为偶数 |
| $4$  | $52$  | 无额外约束 |


title: [COTS/CETS 2023] 三角形 Trokuti

background:
译自 [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) D1T3。$\texttt{1s,0.5G}$。

祝 NaCly_Fish 生日快乐！（2024.7.28）

description:
有一个隐藏的简单无向图 $G$，其中恰有 $100$ 个节点。试通过以下询问重建 $G$：

> **询问** 给定两两不同的节点 $u,v,w$，回答这三个节点的导出子图（induced subgraph）的边数。注意到答案只会是 $0,1,2,3$。

【实现细节】

你的程序通过标准输入输出与交互库交互。

- $\texttt{? u v w}$：发起一次询问，回答 $u,v,w$ 的导出子图的边数（从标准输入读取），注意到答案只会是 $0,1,2,3$。

    你需要保证 $1\le u,v,w\le 100$，$u,v,w$ 两两不同。最多询问 $161\, 700$ 次。
- $\texttt{!}$：回答答案。在输出 $\texttt{!}$ 后换行，接下来输出 $N$ 行，每行一个长度为 $N$ 的 $\texttt{01}$ 字符串。

    第 $i$ 行第 $j$ 个字符如果是 $\texttt{1}$，代表 $(i,j)$ 间有边；否则代表 $(i,j)$ 间无边。

每次输出后，你需要刷新缓冲区。如：C++ 中的 `cout.flush()`。

inputFormat: 见【实现细节】。

outputFormat: 见【实现细节】。


title: [COTS/CETS 2023] 下 Niz

background:
译自 [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) D2T2。$\texttt{1s,0.5G}$。

祝 NaCly_Fish 生日快乐！（2024.7.28）

description:
给定长度为 $N$ 的序列 $a$，求满足以下条件的 $(l,r)$ 对数：

- $1\le l\le r\le N$；
- $a_l,a_{l+1},\cdots,a_{r-1},a_r$ 是 $1\sim r-l+1$ 的排列。

inputFormat:
第一行，一个正整数 $N$，表示序列长度；

第二行，$N$ 个正整数，描述序列 $a$。

outputFormat: 一行一个整数，即满足条件的 $(l,r)$ 的数量。


title: [COTS/CETS 2023] 题 Zadatak

background:
译自 [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) D2T3。$\texttt{1s,0.5G}$。

祝 NaCly_Fish 生日快乐！（2024.7.28）

description:
Jura 有 $N$ 个正方形，标号为 $1\sim N$，第 $i$ 个正方形边长为 $a_i$，且 $2\mid a_i$。起初，这些正方形都是黑色的。

Jura 决定花费他生命中的 $(N-1)$ 秒来玩这些正方形。在第 $i$ 秒时，Jura 将第 $x_i$ 和第 $y_i$ 个正方形合并成第 $(N+i)$ 个正方形（合并后，第 $x_i$ 和第 $y_i$ 个正方形不再存在）。

合并正方形时，将两个正方形的中心对齐，边缘平行对齐地摆在平面中。新的正方形的大小为合并的两个正方形中较大那个的大小；它的颜色是原来两个正方形颜色的「异或和」（黑+黑=白，白+白=白，黑+白=黑，白+黑=黑）。合并正方形的**代价**为，两个正方形合并前（但是已经按照刚才的要求摆好），正方形的交中，满足在两个正方形中均为黑色的区域的面积。

你需要输出每次合并操作的代价。

下图为正方形合并的示例：

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

inputFormat:
第一行，一个正整数 $N$，表示正方形数量；

第二行，$N$ 个正整数，描述序列 $a$。

接下来 $(N-1)$ 行，每行两个正整数 $x_i,y_i$，描述一次操作。

outputFormat: 输出 $(N-1)$ 行，每行一个整数，表示操作的代价。


title: [JRKSJ R9] 在相思树下 III

background:
>我知
>
>再迷恋他也非我能私有
>
>就当神爱世人遥远温柔
>
>未必要牵手
>
>隔千万光年宇宙献吻
>
>亦真切感受
>
>不用
>
>强求
>
>对号入座那虚构

description:
给你一个长为 $n$ 的序列 $a_{1\dots n}$，你需要对它进行两种操作共 $n-1$ 次。

对一个长度为 $l$ 的序列 $b_{1\dots l}$ 进行一次操作将会把序列变为一个长为 $l-1$ 的序列 $c_{1\dots l-1}$：

- 操作一中，$\forall i\in[1,l),c_i=\max(b_i,b_{i+1})$；
- 操作二中，$\forall i\in[1,l),c_i=\min(b_i,b_{i+1})$。

给定整数 $m$，你只能进行**至多** $m$ 次操作一。进行 $n-1$ 次操作后序列 $a$ 的长度变为 $1$。你可以任意安排操作的顺序，求最终剩余的数 $a_1$ 的最大值。

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

第二行 $n$ 个整数 $a_i$ 表示初始序列。

outputFormat: 一个整数，代表最终剩余的数的最大可能值。


title: [语言月赛 202408] 相识于 2016

background:
> 谨以此作别。
>
> 风，2024 年 7 月 27 日夜

description:
风和清曾经是很好的朋友。清曾说，“……可能走不到最后，但友谊可是能长久一辈子的”。风也曾这么相信。但是，语言的承诺总是那样无力。

风与清相识于 2016 年 8 月。2016 年 8 月是他们认识的第 1 个月，2016 年 9 月是他们认识的第 2 个月……

时光荏苒，现在已经是 $x$ 年 $y$ 月，请问这是他们认识的第几个月？

inputFormat: 输入一行两个整数 $x,y$。

outputFormat: 输出一行一个整数，表示这是他们认识的第几个月。


title: [语言月赛 202408] 两座城市的 543 千米

background:
> 2022 年 6 月，风与清完成了普通高等学校招生全国统一考试。
>
> 于是，风去了 W 市，清去了 N 市，朋友至此相距 543 千米。
>
> 地理的阻隔，他们难以再相见。但通过网络，他们依然维持着很好的友谊。

description:
全国共有 $N$ 座城市，依次编号为 $1,2,\cdots,N$。每座城市都有高铁站。

每天全国有 $M$ 次高铁开行，第 $i$ 次高铁将**依次**经过 $l_i$ 个城市。其经过的第 $j$ 个城市为 $c_{i,j}$。

风所在的城市为 $a$，清所在的城市为 $b$。如果一列高铁先经过 $a$，再经过 $b$，则称其为**一列由 $a$ 市直达 $b$ 市的高铁**。

现在，给出所有高铁列车的信息，请问一共有多少列**由 $a$ 市直达 $b$ 市的高铁**。

inputFormat:
输入的第一行为四个整数 $N,M,a,b$。

接下来 $M$ 行，每行的第一个整数为 $l_i$，接下来 $l_i$ 个数，依次表示 $c_{i,1},c_{i,2},\cdots,c_{i,l_i}$。

**保证同一次高铁不会重复停靠某座城市。**

outputFormat: 输出一行一个整数，表示符合题意的高铁列数。

hint:
### 样例解释

题目要求求解由 $1$ 市直达 $10$ 市的高铁。

第 $2$ 列、第 $3$ 列火车停靠的站点中，先出现过 $1$，再出现过 $10$。

### 数据规模与约定

对于 $30\%$ 的测试数据，$M=1$；
对于 $100\%$ 的测试数据，$2 \le N \le 100$，$1 \le M \le 1000$，$1 \le l_i,a,b,c_{i,j}\le N$，$a \neq b$。对于 $1 \le i \le M$，$c_{i,j}$ 互不相同。


title: [语言月赛 202408] 因友情而终结

background:
> 友情是什么？
> 风不知道。
> 但当友情让爱情出现猜忌
> 风选择因友情而终结友情

description:
字符串 $S$ 是一个仅由英文小写字母构成的串。现在，你可以对字符串 $S$ 执行任意次如下操作：

- 选择 $S$ 长度为 $4$ 的一个子串，将其替换为 `love`。

请问，至少操作多少次，字符串 $S$ 不再有子串 `friend`。

> 定义：子串指的是一个字符串中连续的一段字符序列。例如，字符串 `aabbcc` 有子串 `aab`、`aabb`，但 `abc` 不是字符串 `aabbcc` 的子串，因为其不连续。

inputFormat: 输入一行一个字符串 $S$。

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

hint:
对于 $20\%$ 的测试数据，$1 \le |S| \le 6$；
对于 $100\%$ 的测试数据，$1 \le |S| \le 10^6$，$S$ 仅由小写英文字母组成。


title: [语言月赛 202408] 保持连接的方式

background:
> 时光荏苒，小 S 和小 Y 也会散去。
> 而我们和一个人保持连接的方式就是记住，仅此而已。
> —— [[NOI 2024] 集合](https://www.luogu.com.cn/problem/P10785)
>
> 风将这句话写在纸上，折成了纸飞机，扔出窗外。
> 纸飞机飞吧，飞向天空。
>
> 以此铭记。

description:
风有一只小木箱，内部被划分为了 $n$ 行 $m$ 列的小格子，第 $i$ 行第 $j$ 列的小格子用 $(i,j)$ 表示。风将日记放在小木箱中。每一个小格子可以堆叠的放下至多 $k$ 份日记。风每次只能从小格子的最顶部取出日记，放入日记时，会放在某一个小格子的最顶端。

如果风希望取出被压在下面的日记，他需要先将上面的日记取出，再逐个放回。例如，某个小格子从底部至顶部，依次有编号为 $1,2,3,4,5$ 的五份日记，风希望取出编号为 $3$ 的日记，需要先依次取出编号为 $5,4$ 的两份日记，拿走编号为 $3$ 的日记后，再按照 $4,5$ 的顺序放回。我们称移走 $3$ 号日记需要移动 $2$ 份日记。

在接下来的 $t$ 天，风每一天都会写日记，第 $i$ 天撰写的日记编号为 $a_i$，将存放在 $(x_i,y_i)$ 中。如果 $(x_i,y_i)$ 已满，风需要从 $(x_i,y_i)$ 中先取走编号最小的日记并销毁，销毁后，将新的日记存放在 $(x_i,y_i)$ 顶部。如果存在多份编号最小的日记，销毁最靠上的一份。请问，每一天，风是否需要销毁日记？若需要，需要移动几份日记？

inputFormat:
第一行为四个正整数 $n,m,k,t$。

接下来 $t$ 行，每行三个正整数，第 $i$ 行为 $a_i,x_i,y_i$，表示第 $i$ 天日记编号为 $a_i$，存放在 $(x_i,y_i)$。

outputFormat:
输出 $t$ 行，每行一或两个整数，对于第 $i$ 行：

- 若第 $i$ 天不需要销毁日记，输出一行一个整数 $-1$
- 若第 $i$ 天需要销毁日记，输出一行两个整数，由空格隔开，分别表示销毁的日记编号和需要移动的日记份数

hint:
对于 $30\%$ 的测试数据，$n=m=1$；
对于另外 $30\%$ 的测试数据，$k=1$；
对于 $100\%$ 的测试数据，$1 \le n,m \le 100$，$1 \le k \le 50$，$1 \le t \le 2 \times 10^5$，$1 \le a_i \le 10^9$，$1 \le x_i \le n$，$1 \le y_i \le m$。


title: 【模板】离线二维数点

background: 青蛙。

description: 给你一个长为 $n$ 的序列 $a$，有 $m$ 次询问，每次询问给定 $l,r,x$，求 $[l,r]$ 区间中小于等于 $x$ 的元素个数。

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

第二行 $n$ 个数表示序列 $a$。

之后 $m$ 行，每行三个数 $l,r,x$ 表示一次询问。

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