title: [传智杯 #4 决赛] [yLOI2021] 生活在树上（hard version）

background:
**本题是 P8200 的较难版本，两道题目的解法略有不同。本题和 P8200 在题意上的区别在于本题给定树上的点权，而不是边权。**

小智生活在「传智国」，这是一个有 $n$ 个城市的国家，各个城市由 $n-1$ 条道路相连。

每个城市都有一个财富指数 $w_i$ ，我们定义，小智从城市 $a$ 走到城市 $b$ 的代价是 $\mathrm{dis}_{a, b} = \bigoplus \limits_{u \in \mathrm{path}\left(a, b\right)} w_u$，其中 $\bigoplus$ 表示**按位异或**（如果你不知道什么是**按位异或**，请参见题目下方的提示/说明），$\mathrm{path}\left(a,b\right)$ 表示 $a$ 到 $b$ 的简单路径上的点集（包括 $a$ 和 $b$）。也即 $\mathrm{dis}_{a, b}$ 表示将 $a$ 与 $b$ 的简单路径上所有点写作 $u_1, u_2, u_3, \dots$ 后，求 $w_{u_1} \bigoplus w_{u_2}\bigoplus w_{u_3} \dots$ 的结果。

有一天，小智获得了去参加传智杯的机会，他在前往比赛地的路上想到了一个问题，但他好像不会做，于是他把这个题告诉了你。聪明的同学，你可以帮帮他吗？

description:
小智说：「由于我们的国家只有 $n$ 个城市和 $n-1$ 条道路，那么我们的国家就相当于是一棵树。我在想，在我们的国家中，是否存在城市满足『到城市 $a$ 的代价和到城市 $b$ 的代价的异或等于 $k$』。好难哦，我想不出来，你能帮帮我吗？」

也就是说，给定城市 $a, b$ 和整数 $k$，请你计算是否存在城市 $t$ 满足 $\mathrm{dis}_{t, a} \bigoplus \mathrm{dis}_{t, b} = k$。

inputFormat:
第一行有两个整数 $n$，$m$，表示国家的城市数和询问的个数。

第二行有 $n$ 个整数 $w_i$，表示 $i$ 号城市的财富指数。

接下来 $n-1$ 行，每行有两个整数 $x, y$，表示城市 $x$ 与城市 $y$ 有一条边相连。

接下来 $m$ 行，每行有三个整数 $a, b, k$，表示小智从城市 $a$ 走到城市 $b$，$k$ 的含义与题目描述一致。

outputFormat:
输出共 $m$ 行。

对于第 $i$ 个询问，如果存在至少一个城市 $t$ 满足要求，则输出 `Yes`。

如果不存在任何一个城市满足条件，则输出 `No`。

输出字符串大小写不敏感，例如，`Yes`、`yES`、`YES`、`yes` 等都算作 `Yes`。

hint:
### 相关概念解释
「树」：树是一个有 $n$ 个结点和 $n-1$ 条边的无向简单连通图。

「按位异或」：按位异或是一个二元运算，步骤是将两个数的二进制位按位比较，相同为 $0$，不同为 $1$ 。例如：$3 \bigoplus 5 = (011)_2 \bigoplus (101)_2 = (110)_2 = 6$。
### 样例 1 解释
下图为传智国的地图。

$\forall t \in \{1, 2, 3, 4, 5\}$，都不可能有 $\mathrm{dis} _{t,1} \bigoplus \mathrm{dis}_{t, 2} = 4$，$\mathrm{dis}_{t, 2} \bigoplus \mathrm{dis}_{t, 3} = 12$，于是输出 `No`；

而取 $t=4$，有 $\mathrm{dis}_{t, 2} \bigoplus \mathrm{dis}_{t, 3} = 10$，于是输出 `Yes`。

![](https://cdn.luogu.com.cn/upload/image_hosting/d3phj9di.png)
### 数据规模与约定
对于所有测试点，保证 $1 < n \leq 5 \times 10^5$，$1 \leq m \leq 5 \times 10^5$，$0 \leq w_i \leq 1\times 10^7$。

对于每次询问，保证 $1 \leq a,b \leq n$ 且 $a \neq b$，$0 \leq k \leq 1\times 10^7$。
### 提示
- 请注意常数因子对程序效率造成的影响。
- 对于两个 $x, y \leq 10^7$，$x \bigoplus y$ 可能大于 $10^7$，请特别注意这一点。


title: 「SvR-1」Problem

type: P

background: 小 L 打颓被 nodgd 发现，于是他开始做题了。

description:
他的 DS 非常菜，于是他把一共 $n$ 道 DS 题加到了自己的计划题单里，其中第 $i$ 道题的有趣程度为 $a_i$。

由于他并不精通 DS，他发现他在做一些题目之前需要先做另一些题目。这样的关系共有 $n - 1$ 组，他还发现每道题都出现在了这些关系中且没有重复。

他发现 $\forall 2 \leq i \leq n$，第 $i$ 题和第 $fa_i$ 题间存在上文所述的关系，且 $1 \leq fa_i < i$。**他必须先做第 $fa_i$ 题后才能做第 $i$ 题**。

他发现，如果他在做一道题之前高兴程度为 $k$，则他做完第 $i$ 题后，他的高兴程度便会变为 $\min(k, a_i)$。**他做题前的高兴程度为无穷大**。

他想问你**在必须先做第 $1$ 题且不能重复做某一道题**的情况下，他在做题的全过程中每做完一道题后**高兴程度之和的最大值**。

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

由于输入量较大，我们采用如下方式生成 $a_i, fa_i$。

C++：

```cpp
typedef unsigned int uint;

inline uint get_next(uint &seed){
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return seed;
}

int main(){
	// ...
	for (int i = 1; i <= n; i++){
		a[i] = get_next(seed);
	}
	for (int i = 2; i <= n; i++){
		fa[i] = get_next(seed) % (i - 1) + 1;
	}
	// ...
	return 0;
}
```
使用其他语言的选手请参考「**说明/提示**」中的「**伪代码参考**」。

outputFormat: 一行，一个整数，表示所求的值。


title: [COCI2013-2014#3] RIJEČI

description:
一天，Mirko 发现了一个非常大的屏幕，这个屏幕上一开始只有一个字母 $\texttt{A}$。Mirko 在这个屏幕旁边找到了一个按钮。当他按一次时，屏幕上的字母变成了 $\texttt B$。随后他又按了若干次，屏幕上依次显示 $\texttt{BA}$、$\texttt{BAB}$、$\texttt{BABBA}$、……这时他才发现，每当他按一次按钮，屏幕上的字母 $\texttt B$ 变为 $\texttt{BA}$，而字母 $\texttt A$ 变为 $\texttt{B}$。

现在，Mirko 已经按了 $k$ 次按钮，他想知道屏幕上分别有多少个字母 $\texttt A$ 和字母 $\texttt B$。

inputFormat: 输入一个整数 $k$，表示 Mirko 按下按钮的次数。

outputFormat: 输出两个整数，以空格间隔，分别表示字母 $\texttt A$ 的个数和字母 $\texttt B$ 的个数。

hint:
**【数据范围与限制】**

对于 $20\%$ 的数据，保证 $k\leqslant 10$。
对于所有数据，$1\leqslant k\leqslant 45$。

**【题目来源】**

本题来源自 **_[COCI 2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 3](https://hsin.hr/coci/archive/2013_2014/contest3_tasks.pdf) T1 RIJEČI_**，按照原题数据配置，满分 $50$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2013-2014#3] OKVIR

description:
Mirko 制作出了一个绝妙的纵横字谜，现在他想把这个纵横字谜用边框给框起来。

Mirko 的纵横字谜可以看作是一个 $m\times n$ 的网格图，每个格子上都有一个小写字母。他希望上面、左边、右边和下面的边框的宽度分别为 $u,l,r,d$。边框上也被分割成若干个网格，每个网格上要么是 `#`，要么是 `.`。他还希望，如果框架扩展到整个字谜上，那么左上角的网格必定是 `#`，且相邻网格上的字符不能相同。当然，如果该网格原来是纵横字谜上的，那么最终制作边框时应当保留字谜网格上的原有字母，而不是 `#` 或 `.`。

现在，请你帮 Mirko 得到最终框起来的字谜的所有网格上的字符。

如果你不能很好地理解题意，请参考本题的样例。

inputFormat:
第一行输入两个整数 $m,n$，分别表示行数和列数。
第二行输入四个整数 $u,l,r,d$，分别表示上面、左边、右边和下面的边框的宽度。
随后 $m$ 行，每行输入 $n$ 个字符，描述字谜的所有网格上的字符。

outputFormat: 输出 $u+m+d$ 行，每行输出 $l+n+r$ 个字符，表示框起来的字谜的所有网格上的字符。

hint:
**【数据范围与限制】**

对于所有数据，$1\leqslant m,n\leqslant 10$，$0\leqslant u,l,r,d\leqslant 5$。

**【题目来源】**

本题来源自 **_[COCI 2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 3](https://hsin.hr/coci/archive/2013_2014/contest3_tasks.pdf) T2 OKVIR_**，按照原题数据配置，满分 $80$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2013-2014#3] REČENICE

description:
很久以前，在一个只有数学学生居住的遥远国度里，Iva 和 Vedran 正在讨论一种特殊的句子。这些句子中正好有一个单词表示一个数字，并且这个数字等于句子中字母的总数。例如 `This sentence has thirtyone
letters.` 和 `Blah Blah seventeen`。

Jurica 无意中听到了朋友们的谈话，决定用他背诵的大量特殊的句子给他们留下深刻印象。他急忙回家，写了一个程序，给定一个句子，求出使得句子变得特殊的能放进去的最小数字。

不幸的是，他的电脑坏了，现在他需要你的帮助。写一个程序来帮助 Jurica！

以下是一些补充说明：

- 句子的形式是：$\textit{word}_1~\textit{word}_2~\textit{word}_3~\cdots~\textit{word}_{n-1}~\textit{word}_n$。这 $n$ 个单词中恰好有一个 `$`，表示需要填入的表示一个数字的单词。例如，`this sentence has thirtyone letters` 将变为 `this sentence has $ letters`。
- 用来表示数字的单词遵循如下规则：
    - 对于所有 $1\sim 19$ 的整数，表示它们的单词从小到大依次为 `one`、`two`、`three`、`four`、`five`、`six`、`seven`、`eight`、`nine`、`ten`、`eleven`、`twelve`、`thirteen`、`fourteen`、`fifteen`、`sixteen`、`seventeen`、`eighteen` 和 `nineteen`。
    - 对于所有 $20\sim 90$ 的整十数，表示它们的单词从小到大依次为 `twenty`、`thirty`、`forty`、`fifty`、`sixty`、`seventy`、`eighty`、`ninety`。
    - 对于所有 $100\sim 900$ 的整百数，表示它们的单词从小到大依次为 `onehundred`、`twohundred`、`threehundred`、`fourhundred`、
    `fivehundred`、
    `sixhundred`、
    `sevenhundred`、
    `eighthundred`、
    `ninehundred`。
    - 对于其它所有的两位数，先在开头放入表示不超过该数的最大的整十数的单词，再在后面拼接表示该两位数的个位数的单词。例如，表示整数 $68$ 的单词为 `sixtyeight`。
    - 对于其它所有的三位数，先在开头放入表示不超过该数的最大的整百数的单词，再在后面拼接表示其后两位数的单词（按照前面的规则）。例如，表示整数 $319,530,971$ 的单词分别为 `threehundrednineteen`、`fivehundredthirty` 和 `ninehundredseventyone`。

inputFormat:
第一行输入一个整数 $n$，表示句子中的单词个数。
随后 $n$ 行，每行一个字符串，表示句子中的所有单词。保证 `$` 在其中恰好出现一次。

outputFormat: 输出一行 $n$ 个字符串，表示将 `$` 替换为使得句子特殊的表示最小数字的单词后的句子。

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

`$` 填入表示整数 $30$ 的单词 `thirty`，此时所有单词的字母总数为 $6+2+3+6+2+7+4=30$。

**【样例 3 解释】**

请注意本题中的句子可能并不满足英语语法要求。

**【数据范围与限制】**

**本题开启捆绑测试**。各个子任务的分值和特殊限制如下所述：

- Subtask 1（40 pts）：`$` 中填入的单词所对应的数字不超过 $50$。
- Subtask 2（60 pts）：无特殊限制。

对于所有数据，$1\leqslant n\leqslant 20$，`$` 中填入的单词所对应的数字不超过 $1000$。

**【题目来源】**

本题来源自 **_[COCI 2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 3](https://hsin.hr/coci/archive/2013_2014/contest3_tasks.pdf) T3 REČENICE_**，按照原题数据配置，满分 $100$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2013-2014#3] KOLINJE

description:
在一年一度的生猪屠宰会上，屠夫 Bajs 正在进行活动的最后一个环节——将自己那条屡获殊荣的火腿拿出一部分，分给参加活动的所有人。

今年的生猪屠宰会一共有 $n$ 个人参加，其中第 $i$ 个人目前已经吃了 $a_i$ 千克火腿。Bajs 将自己的火腿按照 $b_1:b_2:\cdots:b_n$ 的比例分给所有人，换句话说，令 $S=\sum\limits_{j=1}^nb_j$，则第 $i$ 个人将分到总火腿重量的 $\dfrac{b_i}S$。

但是，直到现在，Bajs 也没能确定他要拿出的火腿总量，因为在给每个人分完火腿并吃完以后，现场将根据每个人吃的火腿的千克数从大到小列出一个排名表（如果有两个人吃的肉的千克数相同，则按照两个人的编号从小到大排序），并宣布本次生猪屠宰会的年度人物，即排名表的第一位。虽然 Bajs 曾多次受到他人贿赂，但是他仍旧不愿改变分配的比例，并说他很诚实并且心地善良。Bajs 是个重度强迫症患者，因此他希望排名表上的人的编号从前往后依次为 $1,2,\cdots,n$。请你帮助 Bajs 确定他要拿出的火腿总量，以满足 Bajs 的要求。

inputFormat:
第一行输入一个整数 $n$，表示参加生猪屠宰会的人数。
随后 $n$ 行，每行输入两个整数 $a_i,b_i$，分别表示第 $i$ 个人已经吃的火腿的千克数和在火腿的分配中所占的比重（具体见『题目描述』部分）。

outputFormat:
如果无论 Bajs 拿出多少火腿都不能满足要求，输出 `-1`。

否则，输出一个**实数** $x$，表示 Bajs 拿出的火腿千克数。你需要保证：

- $0\leqslant x\leqslant 10^7$。
- $x$ 的小数点后不得超过 $12$ 个数位。建议自行对答案四舍五入后再输出。

上面两点中若有至少一点不满足，均会被判定为 `WA`。

如有多解，输出任意一个解即可。即**你不需要保证 Bajs 拿出的火腿千克数最小**。

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

Bajs 拿出了 $10.5$ 千克火腿，由于分配的比例为 $1:2:0$，因此三个人依次分配到 $3.5$ 千克、$7$ 千克和 $0$ 千克火腿，最终三个人依次共吃了 $10.5$ 千克、$10$ 千克和 $10$ 千克火腿。这满足 Bajs 的要求。

**【数据范围与限制】**

对于所有数据，$2\leqslant n\leqslant 1000$，$0\leqslant a_i,b_i\leqslant 10^6$。

**【题目来源】**

本题来源自 **_[COCI 2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 3](https://hsin.hr/coci/archive/2013_2014/contest3_tasks.pdf) T4 KOLINJE_**，按照原题数据配置，满分 $120$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。

欢迎对[本题 checker](https://www.luogu.com.cn/paste/7p24epxh) 提出改进意见。


title: [COCI2013-2014#3] PAROVI

description:
定义两个整数 $A,B$ 之间的**距离**为这两个整数所有对应位上的数的差的绝对值之和，记为 $\operatorname{dist}(A,B)$。特别地，如果 $A,B$ 两数的位数不相同，则在位数较小的数前补足前导 $0$。例如：

- $\operatorname{dist}(4561,3278)=\left|4-3\right|+\left|5-2\right|+\left|6-7\right|+\left|1-8\right|=12$。
- $\operatorname{dist}(32,5678)=\left|0-5\right|+\left|0-6\right|+\left|3-7\right|+\left|2-8\right|=21$。

现在，给定两个整数 $L,R$，请你求出所有在区间 $[L,R]$ 内的整数对的距离和。由于答案可能很大，因此**请对 $\bf 10^9+7$ 取模**。

inputFormat: 输入仅一行，包含两个整数 $L,R$。

outputFormat: 输出一行一个整数，表示所有在区间 $[L,R]$ 内的整数对的距离和对 $\bf 10^9+7$ 取模之后的值。

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

所有在区间 $[288,291]$ 内的整数对的距离如下：

- $\operatorname{dist}(288,289)=\operatorname{dist}(289,288)=1$。
- $\operatorname{dist}(288,290)=\operatorname{dist}(290,288)=9$。
- $\operatorname{dist}(288,291)=\operatorname{dist}(291,288)=8$。
- $\operatorname{dist}(289,290)=\operatorname{dist}(290,289)=10$。
- $\operatorname{dist}(289,291)=\operatorname{dist}(291,289)=9$。
- $\operatorname{dist}(290,291)=\operatorname{dist}(291,290)=1$。

因此距离和为 $2\times (1+9+8+10+9+1)=76$。

**【数据范围与限制】**

对于 $20\%$ 的数据，满足 $A,B\leqslant 10^4$。
对于 $40\%$ 的数据，满足 $A,B\leqslant 10^{100}$。
对于所有数据，$1\leqslant A\leqslant B\leqslant 10^{50000}$。

**【题目来源】**

本题来源自 **_[COCI 2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 3](https://hsin.hr/coci/archive/2013_2014/contest3_tasks.pdf) T5 PAROVI_**，按照原题数据配置，满分 $140$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2013-2014#3] ODAŠILJAČI

description:
一个二维平面中有一条长度为 $d$ ，以原点为最左端，且与 $x$ 轴重合的线段 $L$。另有 $n$ 条垂直于 $x$ 轴，垂足在线段 $L$ 上，且在 $x$ 轴上方的线段 $l_1,l_2,\cdots,l_n$，其中第 $i$ 条线段到原点的距离为 $x_i$，其长度为 $h_i$。

除了线段 $L$ 之外，若干条线段的最上端装有一个大小可忽略的发光点，可以向其左右发射激光。激光只能够沿着一条直线传播，且不能够穿过任意一条线段（包括线段 $L$）。我们称线段 $L$ 中的一个点 $A$ 是被覆盖的，当且仅当存在某个发光点，使得其向某个方向发射激光，最终会落在点 $A$ 上。

现在请求出线段 $L$ 上所有被覆盖的部分的总长度。

请前往样例及样例解释以更好地理解题面。

inputFormat:
第一行输入两个整数 $n,d$，分别表示**除线段 $L$ 外**的线段的条数和线段 $L$ 的长度。

随后 $n$ 行，每行输入三个整数 $op_i,x_i,h_i$，分别表示第 $i$ 条线段最上端是否有发光点，第 $i$ 条线段到原点的距离和其长度。具体地，如果 $op_i=0$，则表示第 $i$ 条线段最上端没有发光点，否则表示第 $i$ 条线段最上端有发光点。

outputFormat: 输出一个**实数**，表示线段 $L$ 上所有被覆盖的部分的总长度。你需要保证你输出的答案和标准答案的相对误差不超过 $10^{-3}$。

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

下图为对应样例 2 的图片，其中加粗部分为**未被覆盖的区域**。

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

**【数据范围与限制】**

**本题开启捆绑测试**。各个子任务的分值和特殊限制如下所述：
- Subtask 1（48 pts）：$n\leqslant 10^3$。
- Subtask 2（112 pts）：无特殊限制。

对于所有数据，$1\leqslant n\leqslant 3\times 10^5$，$1\leqslant d\leqslant 10^9$，$op_i\in\{0,1\}$，$0\leqslant x_i\leqslant d$，$1\leqslant h_i\leqslant 10^9$。保证 $\forall i\neq j$，$x_i\neq x_j$。

**【题目来源】**

本题来源自 **_[COCI 2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 3](https://hsin.hr/coci/archive/2013_2014/contest3_tasks.pdf) T6 ODAŠILJAČI_**，按照原题数据配置，满分 $160$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [AGM 2022 资格赛] 抛硬币

description:
伊利找到了一个魔法数字 $K$，一个装满草莓的魔法篮子，还有一个魔法硬币。

伊利注意到，当抛硬币时，它有 $P$ 的概率概率朝上。随后她抛了 $n$ 次硬币，如果硬币朝上篮子里的草莓会变成原来的 $K$ 倍。否则，她会吃掉篮子里的所有草莓，吃完后篮子会神奇地变出一颗新的草莓。

伊利现在很好奇她在抛 $n$ 次硬币后期望会吃多少草莓。请你告诉她答案在 $\bmod\ 998244353$ 意义下的答案。

inputFormat:
第一行一个数 $T$，表示数据组数。

接下来 $T$ 行，每一行三个数表示 $n,K,P$。

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

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

对于 $100\%$ 的数据，满足 $1\leq T\leq 10^5$，$1\leq n \leq 10^{18}$，$0\leq K,P<998244353$。

#### 说明

翻译自 [AGM 2022 Qualification Round A CoinFlip](https://judge.agm-contest.com/public/problems/21/text)。


title: [AGM 2022 资格赛] 地牢

description:
丹尼是 Dungeon Crawlers 的狂热粉丝。最近，他想知道电脑是否可以玩这个游戏，而他想让你帮他试一试。

游戏分为 $L$ 个关卡，每个关卡都有 $N\times M$ 个单元格。单元格有以下几种：

* `0` 代表一个空单元格。

* `-1` 代表通往下一个关卡的出口，进入下一关后初始位置在这个出口的位置，除了最后一关没有出口，每个关卡都只有一个出口。

* `-9` 代表无法通过的障碍物。

* `x` 一个整数 $x(1\leq x\leq 10^9)$ ，代表敌人的能力值。

为了击败敌人，你的能力值需要大于或等于它的能力值。打败它后，你自己的能力值就会增加与被击败的敌人的能力值相等的值。你可以走上下左右四个单元格，有敌人的格子必须击败才能通过。出口是强制传送的，不能经过出口而不传送。

假设初始的能力值为 $1$，你从地牢第一层左上角的 $(1,1)$ 开始，在最后一层的任意位置结束游戏。那么你能达到的最大能力值是多少？数据保证始终存在一条通往最后一关的路径。

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

接下来 $L$ 个矩阵，每个矩阵有 $N$ 行 $M$ 列共 $N\times M$ 个整数表示单元格的种类。

保证 $(1,1)$ 位置上数为 $0$。

outputFormat: 一个整数表示答案。

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

对于 $100\%$ 的数据，保证 $1\leq L\times N\times M\leq 10^6$。

#### 说明

翻译自 [AGM 2022 Qualification Round B Dungeon](https://judge.agm-contest.com/public/problems/7/text)。


title: 「CGOI-2」No voice to cry suffering

background:
父亲，您的王国在崩塌；

父亲，您的人民在离去；

父亲，但您说我不该有为苦难哭泣的声音；

所以我将无能为力，所以我独自分崩离析。

description:
容器面前有 $n$ 个感染者，这 $n$ 个感染者排成一列，编号依次从 $1$ 到 $n$，第 $i$ 个感染者的感染深度为 $a_i$。

容器会从第 $x$ 个感染者处开始向第 $n$ 个感染者走，依次经过第 $x$ 到 $n$ 个感染者。容器会击杀所有经过的感染者。然而，如果击杀了两个**编号连续，感染深度严格递增**的感染者，那么它会略过下一个感染者（如果存在下一个）。

记 $f_x$ 表示若容器从第 $x$ 个位置开始，击杀的感染者数量（$f$ 之间两两独立）。例如有五个感染者，他们的感染深度依次为：

```plain
2 6 4 5 1
```

那么对应的 $f$ 序列为 $\{4,3,2,2,1\}$。

你不知道每个感染者的感染深度，只知道 $m$ 组 $f_i-f_{i+1}$ 的值，对于请输出满足条件的不同 $f$ 序列的数量对 $998244353$ 取模的结果。

序列 $f,g$ 不同，当且仅当存在 $1\le i \le n$ 满足 $f_i\not= g_i$。

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

接下来 $m$ 行，每行一个二元组 $(x,y)$，表示 $f_x-f_{x+1}=y$。

注意，数据中可能存在错误的二元组，您需要自行忽略它们。具体地，若二元组 $(x_i,y_i)$ 使得考虑 $1\sim i-1$ 的所有合法二元组及该二元组后，不存在满足条件的 $f$ 序列，那么该二元组不合法，您在计算答案时不应考虑该二元组。

outputFormat:
输出为 $(m+1)$ 行，每行 $1$ 个数。

第一行表示不考虑任何二元组时的答案对 $998244353$ 取模的结果。

第 $i(2 \le i \le m+1)$ 行表示考虑 $1 \sim i-1$ 中所有合法二元组时的答案对 $998244353$ 取模的结果。

hint:
### 样例一解释

初始：符合条件的 $f$ 序列有 $\{3,2,1\},\{2,2,1\}$。

约束一：初始的 $f$ 序列都不符合约束一，忽略该条件。

约束二：只有 $\{3,2,1\}$ 符合约束条件。

约束三：只有 $\{2,2,1\}$ 符合约束条件。结合约束二，不存在合法的 $f$ 序列，忽略该条件。

---

### 数据范围及约定

对于 $20\%$ 的数据，$n,m\le5$。

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

对于另外 $10\%$ 的数据，$m=0$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^{11},0 \leq m \leq 5\times 10^4,0 \leq |y| \leq n,1 \leq x <n$。


title: 古籍翻译

type: B

description: 机器猫跑到外星人的图书馆去读书。有一本外星古籍，里面的内容是用八进制写成的；但机器猫只能处理十六进制的数据。请你帮忙写一个翻译软件，帮机器猫把八进制串翻译成十六进制串。

inputFormat: 仅一行，一个八进制字符串 $s$，表示古籍内容。

outputFormat: 仅一行，一个十六进制字符串，表示翻译结果。

hint:
#### 样例解释

第一组样例：八进制 `144` 即十进制下的 100，其十六进制表示为 `64`。

第二组样例：八进制 `1572061125` 即十进制下的 233333333，其十六进制表示为 `de86255`。

#### 数据规模与约定

对于 $40\%$ 的数据，有 $|s| \leq 10$，即输入字符串**长度**不超过 $10$。

对于 $100\%$ 的数据，有 $|s| \leq 1000$，即输入字符串**长度**不超过 $1000$。


title: 〈 TREEのOI 2022 Spring 〉Dimension-2 Square

background:
# 本题可能轻微卡精度，建议改用 $\tt long\ double$

正月十五夜空中。

一行人望着一棵树，一棵飘在天上的树，期待着它变成一个环。

这棵树有 $4$ 个节点。

“它变成环了！”有人大喊。
我顿时向天上望去……

多么标准的正方形啊！无论哪个天文学家过来测量，它的角都是标准的 $90^{\circ}$，它的边都是完美的 $1:1:1:1$……

只见那棵树，不，那标致而又完美的环，缓缓飞过，恰巧嵌在了那轮明月中心……

![](https://cdn.pixabay.com/photo/2016/11/29/13/14/full-moon-1869760_960_720.jpg)

description:
给定平面直角坐标系上 $4$ 个点的坐标。

你需要使用 ~~%法~~ 魔法，做一个正方形，使得这 $4$ 个点分别在正方形每条边的**直线**上。

inputFormat:
**本题采用多组数据评测。**

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

对于每组数据，共 $4$ 行，每行两个整数 $x_i,y_i$，表示点的坐标。

outputFormat: 对于每组数据，输出共 $4$ 行，每行两个实数，表示正方形上的四个点的坐标。你需要保证给出的第 $i$ 个点位于正方形的第 $i$ 个和第 $i\ \text{mod}\ 4+1 $ 个顶点形成的边上，且给出的第 $i$ 个点和第 $i\ \text{mod}\ 4+1$ 个点所在的边为邻边。

hint:
**本题采用 $\tt SPJ$。**

如答案不唯一，输出一种即可。
四边长度的之差 $\le 10^{-2}$ 且相邻两边夹角在 $\frac{\pi}{2}\pm10^{-2}$ 内且设给定的点为 $(p,q)$，则存在一点 $(p,q+k)\ (|k|\leq1)$ 在对应边所在直线上即可 $\tt \green {AC}$。

对于 $30\%$ 的数据，$T=1,|x_i|,|y_i|\le10^3$。

对于 $70\%$ 的数据，$1\leq T\leq 5\times 10^4,|x_i|,|y_i|\le10^6$。

对于 $100\%$ 的数据，$1\leq T\leq 5\times 10^5,|x_i|,|y_i|\le10^9$。

数据保证任意两点连成的 $6$ 直线两两之间互不垂直，且没有平行于轴的直线，任意三点不共线。保证不存在一组解的边与轴平行。保证有解。

**为了数据的精确性，您输出时至少需要保留 $8$ 位小数。**


title: 寻找团伙

description:
世界局势风云变幻，你想办一件大事。办事自然要有人参与，你能从 $n$ 个人里面挑选一部分人共襄盛举。

要办这件事，一共涉及 $k$ 方面的能力，例如游说他人的能力、玩游戏的能力、睡觉的能力。每位人士都会具备某一些能力，例如机器猫就可能擅长睡觉、擅长玩游戏，而不擅长游说他人。

你的计划很宏伟，因此你希望团队拥有很全面的能力。不幸的是，如果团队中有偶数个人拥有同一类能力，那么他们就会分成两派，争执不下，导致整个团队丧失这方面的能力。相应地，如果这项能力只有奇数个人拥有，那么他们总能形成一个多数派，帮团队去做这方面的工作。

需要注意的是，团队拥有的每一项能力，对计划的成功率的贡献是不一样的。第一项能力最重要，它的权重是 $2^{k-1}$；第二项能力的权重是 $2^{k-2}$；依次类推。第 $k$ 项能力最不重要，权重只有 $1$。

计划的成功率得分，即是**团队拥有的所有能力对应的权重之和**。

你希望计划成功率最大。因此，你需要选出合适的人士，来参与到你的宏图伟业中。

inputFormat:
第一行，两个正整数 $n, k$。分别表示供你挑选的人的数量，以及能力的种类数。
接下来 $n$ 行，每行表示每个人拥有的能力。这一行首先有一个整数 $c$，表示该人士拥有多少种能力；接下来是 $c$ 个 $[1, k]$ 之间的正整数，表示该人士拥有哪些能力。

outputFormat: 仅一行，一个整数，表示计划的成功率得分。

hint:
#### 样例解释

第一组样例，共 5 个人，每个人拥有的能力不一样。最终选择的结果是让这 5 个人都参与计划，得分 $16+8+4+2+1 = 31$。

第二组样例，我们选择只让 $1$ 参与。那么团队具有能力 $1,2, 3$，得分 $16+8+4=28$。

第三组样例，我们让 $1,2,3$ 参与。由于团队中有偶数个成员拥有能力 $5$，故团队并不拥有能力 $5$。奇数个成员拥有能力 $2$，故团队拥有能力 $2$。最终，团队具有能力 $1,2,3,4$。得分 $16+8+4+2=30$。

#### 数据规模与约定

对于 $100\%$ 的数据，有 $n\leq 21, k\leq 60$。


title: [AGM 2022 资格赛] 农场

description:
你是一个资本家，你经营着一块大小为 $n\times m$ 的方格形状的田地，第 $i$ 行第 $j$ 列上初始有 $a_{i,j}$ 数量的小麦。

在这个田地上，你圈了 $Q$ 块矩形，每块矩形表示一个农场（农场之间可能有重叠的格子）。每一个农场的小麦数量等于这个农场内每个格子的小麦的数量之和，一个农场盈利当且仅当这个农场上的小麦数量大于等于这个农场盈利所需要的小麦数 $b_i$。

不幸的是，接下来连续 $T$ 天都有强降雨，每一天都会有一些格子上的小麦数量变少。

你需要对于每个农场，确定它能盈利几天，如果 $T$ 天后仍然盈利则输出 $-1$。

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

接下来 $n$ 行，每行 $m$ 个整数 $a_{i,j}$。

下一行一个整数 $Q$。接下来 $Q$ 行，每行五个数 $l,r,L,R,b$ 表示第 $i$ 个农场的左上角坐标，右下角坐标以及盈利所需的小麦数。

下一行一个整数 $T$。接下来 $T$ 段输入，每一段先输入一个 $p$ 表示这一天发生的事件，接下来 $p$ 行每一行三个整数 $x,y,z$ 表示 $(x,y)$ 格子上的小麦减少了 $z$。

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

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

对于 $100\%$ 的数据，保证 $1\leq n,m\leq 500$，$1\leq Q \leq 50000$，$0\leq a_{i,j}\leq 10^9$，$1\leq l<L\leq n$，$1<r<R\leq m$，$0\leq b_i\leq 10^{18}$，$1\leq T \leq 50000$，$1\leq x\leq n$，$1\leq y\leq m$，$1\leq z\leq 10^9$，$1\leq \sum p\leq 10^5$。保证任何时刻 $z\leq a_{x,y}$。

#### 说明

翻译自 [AGM 2022 Qualification Round C TimeToFarm](https://judge.agm-contest.com/team/problems/10/text)。


title: [AGM 2022 资格赛] 区间

description:
给你一个一行无限列的方格，刚开始每个格子都是白色。

你需要维护以下两种操作：

* `1 l r`：将 $l$ 到 $r$ 中每个格子都填成黑色。

* `2 l r`：查询 $[l,r]$ 有多少个子区间满足区间内格子都是黑色。

inputFormat:
第一行一个整数 $n$ 表示操作次数。

接下来 $n$ 行，每行三个数 $opt,l,r$ 表示操作种类和区间。

outputFormat: 对于每个 $2$ 操作输出一行一个整数表示答案在 $\bmod\ 1000000007$ 意义下的值。

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

对于 $100\%$ 的数据，保证 $1\leq n\leq 10^6$，$1\leq opt\leq 2$，$1\leq l\leq r\leq 10^{18}$。

#### 说明

翻译自 [AGM 2022 Qualification Round E Intervals](https://judge.agm-contest.com/public/problems/4/text)。


title: [AGM 2022 资格赛] 括号

description: 给你一棵 $n$ 个节点的树，其中一号点填了一个左括号，你需要给其余每个点填上 `(` 或 `)`，使得树上合法括号路径数量最多，保证答案唯一。

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

接下来 $n-1$ 行，每行两个正整数 $x,y$ 表示 $x$ 与 $y$ 有一条边相连。

outputFormat: 一行一个长度为 $n$ 的括号串。

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

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

#### 说明

翻译自 [AGM 2022 Qualification Round G Parenthesis](https://judge.agm-contest.com/public/problems/5/text)。


title: [AGM 2022 资格赛] 魔法的力量

description:
你有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个石子。你会执行 $n-1$ 次操作，每次可以选择两堆石子将它们合并成一堆，得分为两堆石子大小之和。

现在问你，如果你每次随机选择两堆石子合并，期望得分为多少。

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

接下来一行 $n$ 个数 $a_i$。

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

答案误差不超过 $10^{-6}$ 即视为正确。

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

对于 $100\%$ 的数据，保证 $2\leq n\leq 500$，$1\leq a_i\leq 10^9$。

#### 说明

翻译自 [AGM 2022 Qualification Round H Magic Powers](https://judge.agm-contest.com/public/problems/22/text)。


title: [AGM 2022 资格赛] 过河

description:
有一个人前来过河。

河可以抽象为一个二维坐标系上的图形。人所在的河的左岸即为 $y$ 轴，河的右岸为 $x=10^9+5$ 的直线。

河上有 $n$ 个横着的木头，第 $i$ 个木头的横坐标为 $x_i$，覆盖的点纵坐标范围为 $y_{i,1}$ 到 $y_{i,2}$。

人可以在木头与岸之间反复横跳，第 $i$ 根木头能跳到第 $j$ 根木头上，当且仅当 $x_i \not= x_j$ 且存在一个实数 $y$ 满足 $y_{i,1}<y<y_{i,2},y_{j,1}<y<y_{j,2}$ 且不存在一个木头 $k$ 满足 $\min(x_i,x_j)<x_k<\max(x_i,x_j)$ 且 $y_{k,1}<y<y_{k,2}$。同理如果一根木头想跳到岸上，把岸覆盖的 $y$ 坐标看成 $(-inf,inf)$ 也要满足这个条件。

从第 $i$ 根木头跳到别处的花费是 $c_i$，从岸上跳到别处不需要花费。左岸不能直接跳到右岸。

这个人想知道他跳到右岸最小的花费是多少。

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

接下来 $n$ 行，每行四个整数 $x_i,y_{i,1},y_{i,2},c_i$。

outputFormat: 一个数表示答案。保证存在一种方法使得他跳到右岸。

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

对于 $100\%$ 的数据，保证 $1\leq n\leq 2.5\times 10^5$，$1\leq x_i,c_i\leq 10^9$，$1\leq y_{i,1}\leq y_{i,2}\leq 10^9$。

数据保证木头之间没有重叠，即不存在 $i,j$ 满足 $x_i=x_j$ 且 $y_{i,2}>y_{j,1}$。

#### 说明

翻译自 [AGM 2022 Qualification Round I River](https://judge.agm-contest.com/public/problems/14/text)。


title: [AGM 2022 资格赛] 避难所

description:
U 国有 $n$ 栋建筑，其中第一栋是避难所，它们被 $n-1$ 条道路相连通着。建筑中都分别有一定数量的难民，初始，第 $i$ 个建筑中的难民数量为 $a_i$。

在战争进行过程中，发生了 $q$ 次事件，有以下两种事件：

* `1 x y`：第 $x$ 栋建筑中难民数量变为 $y$。

* `2 x`：第 $x$ 栋建筑通往避难所的最近的那条道路改变了状态，如果原来通畅现在就封堵，反之通畅。刚开始每条道路都是通畅的。保证 $x \neq 1$。

每次事件之后你都需要输出有多少难民能够顺着通畅的道路到达避难所。

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

接下来 $n-1$ 行，每行两个整数 $u,v$ 表示有一条边连接 $u,v$。

接下来一行 $n$ 个整数 $a_i$。

下面 $q$ 行，每行两个或三个整数表示一次事件。

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

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

对于 $100\%$ 的数据，保证 $1\leq n,q\leq 10^5$，$0\leq a_i,y\leq 10^9$。
#### 说明

翻译自 [AGM 2022 Qualification Round J Shelters](https://judge.agm-contest.com/public/problems/6/text)。


title: [AGM 2022 资格赛] 偷铀计划

description:
你是一个小偷，你决定偷点铀来让自己在 Digdig.io 游戏中能够迅速变大。

你有一张地图，这个矿洞是一张 $n$ 个点 $m$ 条边的无向图。有 $K$ 个守卫保护着矿洞的安全，第 $i$ 个守卫守在第 $P_i$ 个点上。

你偷了 $x$ 千克铀，准备选一条路径从 $S$ 点转移到 $T$ 点。如果 $x>0$，那么在转移过程中，你需要保证在任意时刻与每个守卫的距离都大于 $x$。不然就会被发现！

显然，你不会只偷一次，你需要偷 $Q$ 次铀，每次给定 $S$ 和 $T$，询问你最多能偷多少千克的铀。

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

接下来 $m$ 行，每一行三个数 $x,y,z$ 表示 $x$ 和 $y$ 有一条长度为 $z$ 的无向边。

下一行一个整数 $K$。接下来一行 $K$ 个整数 $P_i$。

接下来一个正整数 $Q$。紧接着 $Q$ 行每行两个数 $S,T$。

outputFormat: $Q$ 行，每行一个数表示答案。如果无法完成偷窃任务输出 $0$。

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

对于 $100\%$ 的数据，保证 $1\leq n,K,Q\leq 10^5$，$1\leq m\leq 2\times 10^5$，$1\leq x,y,P_i\leq n$，$1\leq z\leq 10^9$。
#### 说明

翻译自 [AGM 2022 Qualification Round L Uranium](https://judge.agm-contest.com/public/problems/13/text)。


title: [UESTCPC 2024] 取数游戏

description:
有一个长度为 $n$ 的序列，第 $i$ 个数的权值为 $a_i$。两位选手 A 和 B 在做游戏，他们将对轮流对序列进行操作。每位选手每次有两种操作可以选择：

- 删除序列中的任意两个的数 $a_i,a_j$ $(i \neq j)$，并在序列中添加一个权值为 $a_i+a_j$ 的数。当序列中只有一个数时，不能执行该操作。
- 取走序列中一个数，将序列中剩下的数的权值全部累加给对方，结束游戏。

如果最后 A 得到的权值更多，则他胜利，否则 B 胜利。

A 先进行操作，问他是否有必胜策略。**保证 $a_i$ 之和为奇数。**

inputFormat:
本题包含多组数据。

第一行输入一个整数 $T$ $(1\leq T\leq 10^5)$，表示数据组数。

对于每组数据，输入格式如下。

第一行一个整数 $n$ $(1\leq n\leq 5 \times 10^5)$，表示序列的初始长度。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq 10^9)$，表示初始的序列。

数据保证 $\sum n\leq 10^6$ 且 $\sum a_i$ 为奇数。

outputFormat: 对于每组数据，如果 A 有必胜策略，输出 `YES`，否则输出 `NO`。

hint:
样例一解释如下：

- 如果 A 选择权值 $3$，则 B 能得到的权值为 $6+4=10$。
- 如果 A 选择权值 $4$，则 B 能得到的权值为 $3+6=9$。
- 如果 A 选择权值 $6$，则 B 能得到的权值为 $3+4=7$。
- 如果 A 选择合并权值 $3,6$，序列变为 $9,4$。若 B 选择权值 $9$，则 A 能得到的权值为 $4$。
- 如果 A 选择合并权值 $3,4$，序列变为 $7,6$。若 B 选择权值 $7$，则 A 能得到的权值为 $6$。
- 如果 A 选择合并权值 $4,6$，序列变为 $10,3$。若 B 选择权值 $10$，则 A 能得到的权值为 $3$。

在所有情况下 B 均能以最优策略取得更高的权值，故 A 无法胜利。

样例二解释如下：

如果 A 选择权值 $2$，则 B 能得到的权值为 $1$。

因此 A 有必胜策略。


title: 旭日东升

background:
238 神教 #3

——还有多久，太阳才会出来？

——不知道……

在古老的传说中，你家附近的小村，由于惹怒了太阳神而被罚去了日光。庄稼纷纷枯死了，人们在寒冷与饥饿中求生。而小村的附近，除了你家以外，就是一片大荒。

神学开始在小村中兴起。越来越多的人成为了神学家，在当年集资修建的图书馆中没日没夜地研读着古籍。终于，大家在图书馆仓库的一个阴暗潮湿的角落里发现了一本——

古老而破旧的，据说早已失传的《祈日术》。

description:
书里的许多记载已不可辨识。根据残存的篇章，大家只能推测是要举办一场比赛，非常困难的比赛。至于比完之后怎么处理，完全没有头绪。

但大家决定试试，哪怕是自己摸索呢？

于是当你路过村子的时候，便看见展板上挂了这么一道题——唯一的比赛题。

> 维护一个不可重集合的序列 $a$，长度为 $n$。支持以下两种操作：
> 1. 给定 $l,r,x$，对于每个 $l\le i\le r$，将 $x$ 并入 $a_i$。
> 2. 给定 $l,r$，设 $S$ 把每个 $l\le i\le r$ 的 $a_i$ 并在一起的集合，输出 $S$ 中所有元素的和。

你看了看自己随身带着的电脑，决定去捧（za）个场。

那么，加油吧！

inputFormat:
输入数据的起始会有一个长度为 $2$ 的字符串，见【提示说明】处。它们可以用来帮你快速判断数据性质。

第二行两个正整数 $n,m$ 表示集合序列的长度和操作的次数，初始的集合 $a_1,a_2,\cdots,a_n$ 均为空。

接下来 $m$ 行每行先是三个正整数 $op,l,r$ 如题。如果 $op=1$，那么这一行还会有一个正整数 $x$ 如题。

outputFormat: 对于每行 $op=2$ 的输入，分别输出一个正整数，依次表示每次查询的结果。

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

对于 $100\%$ 的数据，保证 $1\le n,m,x\le10^5,1\le l\le r\le n$。

Subtask 1：对于 $10\%$ 的数据，保证 $1\le n,m,x\le100$;

Subtask 2：对于 $10\%$ 的数据，保证 $1\le n,m,x\le10^5$，第一行的字符串为 `PP`;

Subtask 3：对于 $20\%$ 的数据，保证 $1\le n,m,x\le10^5$，第一行的字符串为 `IP`;

Subtask 4：对于 $30\%$ 的数据，保证 $1\le n,m,x\le10^5$，第一行的字符串为 `PI`;

Subtask 5：对于最后 $30\%$ 的数据，无特殊限制。

---

输入第一行的字符串作用：该字符串包含两个为 `P` 或 `I` 的字符。如果第一个字符为 `P`，那么所有修改操作均满足 $l=r$；如果第二个字符为 `P`，那么所有查询操作均满足 $l=r$。对应位置为 `I` 表示无限制。

---

毫无疑问，你获得了第一名。

“好的，那么我们现在来宣读获奖名单！”

“第三名：……”（掌声，颁奖）

“第二名：……”（掌声，颁奖）

“第一……”

主持人突然停下来，揉揉眼睛，随即惶恐地看着天空。附近的人们好奇地凑上去看主持人手中的名单。只见第一名的名字正以一种不可名状的方式剧烈扭曲重构着，反复地在两种不同形态之间变换。

名单的上方突然出现了几个字符。随着字符逐渐变得清晰，人们看清了，是四个意义不明，但看着十分不耐烦的字符：“div1”。

这时，第一名的名字的变动也稳定了下来——就好像其中有一方主动退出了一样。

最终，名字固定在了五个字母：“David”。这并不是你随口报的那个假名。

人们又随主持人一并看向天际，一个看着大概五六岁的孩子正跌跌撞撞地跑来。“我是第一名！”他高兴地笑着。他的母亲——太阳神就站在远方，一脸怜爱地看着那个小小的背影。

一轮红日从地平线上喷薄而出。


title: [AGM 2022 资格赛] 分裂

description:
你有一个长度为 $n$ 的数组 $a$，你需要将其分成 $K$ 个非空子段，最终的得分为 $\sum_{i=1}^K mx_i^{b_i}-mn_i^{b_i}$，$b_i$ 是给定常数，$mx_i$ 是第 $i$ 段中的最大值，$mn_i$ 为第 $i$ 中的最小值。

你能获得的最大得分为多少？

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

接下来一行 $n$ 个整数表示 $a_i$。

接下来一行 $K$ 个整数表示 $b_i$。

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

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

对于 $100\%$ 的数据，保证 $1\leq K\leq n\leq 5000$，$1\leq a_i\leq 10^5$，$1\leq b_i\leq 3$。
#### 说明

翻译自 [AGM 2022 Qualification Round K Split](https://judge.agm-contest.com/public/problems/11/text)。


title: [AGM 2022 资格赛] 2048 花园

description:
这是一个类似 2048 的游戏，你有一个 $n$ 行 $m$ 列的方格，每个方格上有一个数 $a_{i,j}$。

你总共可以操作 $K$ 次魔法，每次操作之前，系统都会将行号最小的前提下最靠左的空格子的 $a$ 值变为 $1$，如果不存在这样的空格子，那么这次魔法被停止执行并且游戏结束。

操作如下：你可以将每个格子向上/下/左/右“移动”。向一个方向移动的定义是，先将所有格子向那个方向移动直到不能移动，然后从对应的方向边界处开始不断合并两个值相同的格子然后生成一个新的值为原来的值 $+1$ 的格子。如下图即为一次完整的操作（包括操作前系统的改动）：

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

现在你想最大化 $K$ 次魔法后（假设游戏中途结束你的分数依然可以结算）你的每个格子上的最大值，请你求出这个值。

inputFormat:
输入有若干组数据，每组数据第一行三个数 $n,m,K$。

接下来 $n$ 行每行 $m$ 个数 $a_{i,j}$。

outputFormat: 对于每组数据，输出答案。

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

对于 $100\%$ 的数据，保证 $1\leq n,m\leq 2500$，$1\leq \sum (n\times m)\leq 2500$，$1\leq K\times K \leq \min(n,m)$，$0\leq a_{i,j}\leq 10^6$。

#### 说明

翻译自 [AGM 2022 Qualification Round D Rainy Garden](https://judge.agm-contest.com/public/problems/18/text)。


title: [AGM 2022 资格赛] 拼图

description:
你有一张形状为正 $n$ 边形的柱形拼图，它由一个中间块，$n$ 个边缘块和 $n$ 个角块拼成，正 $n$ 边形的每条边上有两个角块和一个边缘块。（如下图即为 $n=5$ 时拼图的俯视图，蓝色为角块，红色为边缘块，灰色为中间块）

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

每个边缘块有顶部底部和向外裸露的面总共三个面上是有颜色的，每个面上的颜色不一定相同。而每个角块上向外裸露的面有两个，所以总共四个面上是有颜色的，每个面上的颜色也不一定相同。而中间块只有顶部和底部是有颜色的。

我们将角块与边缘块逆时针标号，正 $n$ 边形的第 $i(i<n)$ 条边的侧面由第 $i$ 块角块的逆时针方向侧面，第 $i$ 块边缘块与第 $i+1$ 块的角块的顺时针方向侧面组成。特别地，第 $n$ 条边的侧面由第 $n$ 块角块的逆时针方向侧面，第 $n$ 块边缘块与第 $1$ 块的角块的顺时针方向侧面组成。

接着，你可以执行如下的操作：选择拼图的一条边并将两边的角块交换后上下反转（注意此时两个侧面会互换）并且边上的边缘块也上下反转。

我们称一个平面是整齐的当且仅当平面上颜色均相同，现在你要通过若干次操作，来使得这个拼图上的每个面都是整齐的。

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

接下来两个正整数 $col_{tp},col_{bt}$ 分别表示中间块顶部的颜色和底部的颜色。

接下来 $n$ 行，每行四个整数 $ct_i,cl_i,cr_i,cb_i$ 分别表示第 $i$ 个角块的顶部颜色，逆时针方向侧面颜色，顺时针方向侧面颜色以及底部颜色。

接下来 $n$ 行，每行三个整数 $et_i,es_i,eb_i$ 分别表示第 $i$ 个边缘块的顶部颜色，侧面颜色以及底部颜色。

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

否则先输出一行一个整数表示操作次数 $m$，接下来一行 $m$ 个整数表示第 $i$ 操作的边编号。

你需要保证操作次数不超过 $100000$，多解输出任意一种即可。

hint:
#### 样例解释

如下图

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

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $4\leq n \leq 100$，$0\leq ct_i,cl_i,cr_i,cb_i\leq n+1$，$\{es_1,es_2,...,es_n,col_{tp},col_{bt}\}$ 构成一个 $0\sim n+1$ 的排列。

#### 说明

翻译自 [AGM 2022 Qualification Round F Kube](https://judge.agm-contest.com/public/problems/20/text)。


title: [Ynoi2005] tdnmo

description:
给定一棵 $n$ 个顶点的有根树，顶点编号为 $1,2,\dots,n$，$1$ 号顶点为根。定义有向邻域 $N(x,y)$ 为以 $x$ 为根的子树中，距离 $x$ 小于 $y$ 的顶点构成的集合，其中 $1\le x\le n,\;0\le y\le n$，$x,y$ 为整数。

给出 $m$ 个有向邻域 $N(x_i,y_i)_{i=1}^m$，你可以从 $N(1,0)$ 出发，经过不超过 $5m$ 次操作到达每个给出的有向邻域，可以使用的操作有：

1. 从有向邻域 $N(x,y)$ 移动到 $N(x',y')$，满足 $N(x,y)\subseteq N(x',y')$；
2. 撤销一次 $1$ 操作，即回到之前最后一次未撤销的 $1$ 操作前的位置，并将这次 $1$ 操作标为已撤销；
3. 声明当前到达了有向邻域 $N(x_i,y_i)$，满足当前所在邻域是 $N(x_i,y_i)$；

其中操作1的代价为移动前后两个有向邻域的元素个数之差，操作2和3不计代价，要求操作2执行时必须存在未撤销的操作1，操作3必须对每个 $1\le i\le m$ 恰好各执行一次。

你需要保证操作的总代价不超过 $2.5\times{10}^{9}$。

inputFormat:
第一行两个整数 $n\ m$；

接下来一行，共 $n-1$ 个整数，依次表示编号为 $2,3,\dots,n$ 的顶点的父亲 $f_2,\dots,f_n$，保证父亲的编号小于孩子的编号；

接下来的 $m$ 行中，第 $i$ 行两个整数 $x_i\ y_i$，表示给出的每个有向邻域。

outputFormat:
第一行一个整数 $m'$，表示你进行的操作次数；

接下来 $m'$ 行，依次表示每个操作；

操作 $1$ 表示为 $1\ x'\ y'$；

操作 $2$ 表示为 $2$；

操作 $3$ 表示为 $3\ i$。

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

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^6$，$1\le f_i\le i-1$，$1\le x_i\le n,\;0\le y_i\le n$，所有数值为整数。


title: [Ynoi2005] vti

description:
给定一棵包含 $n$ 个结点的树，边的编号从 $1$ 到 $n-1$，第 $i$ 条边有一个权值 $b_i$，树的根节点为 $1$ 号节点；

定义两条边 $x,y$ 构成祖先关系，当且仅当构成边 $x$ 的两个节点中深度最深的一个，是构成边 $y$ 的两个节点中深度最深的一个的祖先。

共 $m$ 次询问，第 $i$ 次询问给出 $t_i$ 个可能相同的点，考虑这些点两两之间简单路径经过的边的并集，问无序地选出两条编号不同的边 $x,y$，使得 $x$ 为 $y$ 祖先，且 $b_x<b_y$ 的方案数。

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

接下来 $n-1$ 行，每行两个整数 $a_i,b_i$，表示 $i+1$ 和 $a_i$ 之间有一条边，权值为 $b_i$。

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

接下来 $m$ 行，每行 $t_i+1$ 个整数，第一个整数为 $t_i$，之后 $t_i$ 个整数表示这次询问的点的集合。

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

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

对于 $100\%$ 的数据，满足 $1\le n\le 10^5$，$1\le m\le 10^6$，$1\le a_i\le i-1$，$1\le b_i\le n$，$1\le t_i$，$t_1+\dots+t_m\le 10^6$，以上所有数值为整数。


title: [THUPC2022 初赛] 最小公倍树

background: 听说有人嫌题面描述都太长了。

description:
对于任意 $V\subset\mathbb{N}^*$，$|V|<+\infty$，构造一张无向完全图 $G=(V,E)$，其中 $(u, v)$ 的边权为 $u,v$ 的最小公倍数 $\mathrm{lcm}(u, v)$。称 $G$ 的最小生成树为 $V$ 的最小公倍树（LCT, Lowest Common Tree）。

现在给出 $L, R$，请你求出 $V={L, L+1, \cdots, R}$ 的最小公倍树 $LCT(V)$。

inputFormat: 输入仅一行，包括两个正整数 $L, R$。

outputFormat: 输出一个正整数，表示 $LCT(V)$ 的边权和。


title: [THUPC2022 初赛] 骰子旅行

description:
在乐队 f 开巡演之前，按照惯例是要先组织乐队成员进行骰子旅行放松身心的。一次骰子旅行包括 $N$ 个地点，这些地点分别标号为 $1, 2, \cdots, N$。乐队成员们事先约好在 $s_0$ 处集合；而到了骰子旅行当天，大家都来到了集合地点 $s_0$，骰子旅行就算正式开始了。

骰子旅行的一大乐趣就是由骰子决定旅行的下一个目的地。当然，这个骰子不一定非得是六面的。我们可以认为，如果当前乐队成员们位于地点 $i$，那么下一个目的地会等概率地从 $m_i$ 个互不相同的候选地点中产生，这些候选地点分别是 $l_{i, 1}, l_{i, 2}, \cdots, l_{i, m_i}$。我们记第 $t$ 次投掷的结果是 $s_t$，那么第 $(t+1)$ 次将会前往 $s_t$ 处掷骰子。第 1 次投掷在起点 $s_0$ 处进行；而由于乐队之后还需要为了巡演排练，事先约定无论前往了哪些地点，投掷完第 $T$ 次骰子，前往 $s_T$ 后骰子旅行都得结束。

当然，享受 $s_0, s_1, \cdots, s_T$ 这些景点也是骰子旅行的一大乐趣。无论是否之前来过，每次到一个地点 $s_t$，乐队成员们都会尽情地浏览美景，品尝美食。只是如果之前来过 $s_t$，负责掷骰子的键盘手 S 在掷这第 $(t+1)$ 次骰子之前一定会说：“上次来到 $s_t$ 仿佛还是上一次 $t'$，上一次在这里掷出了 $s_{t'+1}$，不知道这一次会掷出什么结果。”鼓手 Y 特别喜欢废话梗，所以每次 S 说这句话时，他都会把 $s_{t'+1}$ 记下来。特别地，如果 $s_T$ 是之前经过的地点，那么 S 会说：“上次来到 $s_t$ 仿佛还是上一次 $t'$，上一次在这里掷出了 $s_{t'+1}$，不过这一次就不投掷了，因为骰子旅行到这里就要告一段落了。”当然，Y 也会把这个 $s_{t'+1}$ 记下来。

作为这次骰子旅行的总结，Y 会把所有记录下来的 $s_{t'+1}$ 加起来，作为 S 的废话指数。

f 的下一次巡演马上就要开始了，于是 S 又盘算着带大家去参加骰子旅行。听说你是 f 的粉丝，S 找到了你，希望你能帮他算一下他这次骰子旅行的废话指数的期望值。

inputFormat:
输入的第一行包括三个正整数 $N, s_0, T$，分别表示可能涉及地点的个数，骰子旅行的起点和骰子旅行中投掷骰子的次数。

接下来 $N$ 行，第 $i\ (1\le i\le N)$ 行先输入一个正整数 $m_i$，表示地点 $i$ 的下一个目的地的候选地点数；接着输入 $m_i$ 个正整数，表示这 $m_i$ 个地点 $l_{i, 1}, l_{i, 2}, \cdots, l_{i, m_i}$。保证对于任意 $i$，$m_i$ 个输入的地点互不相同。

outputFormat: 输出一个数表示废话指数的期望。假设废话指数的期望化为最简分式后的形式为 $p/q$（即其中 $p, q$ 互质），请输出 $x$ 使得 $qx\equiv p \pmod{998,244,353}$ 且 $0\le x<998,244,353$。可以证明，在本题数据范围下，$x$ 存在且唯一。


title: [THUPC2022 初赛] 赛程制定

description:
Lewis 热爱打拳，因此他组建了一家拳击俱乐部，希望通过举办表演赛卖票以筹集自己训练的资金，但是，很遗憾，Lewis 人缘并不好，因此这个俱乐部只有两个成员——Lewis 和他的好基友 Valtteri，而观众们很快就厌倦了每晚都是他们两人出场的表演赛，票卖不出去了，拳击俱乐部濒临倒闭。穷则思变，Lewis 决定通过请外援的方式，尝试拯救自己的俱乐部。

通过支票攻势，Lewis 很快就请到了两个拳坛明星——Max 和 Checo，他们将作为飞行嘉宾加入 Lewis 的俱乐部。在接下来的一个赛季里，Lewis 总共会安排 $n$ $(1 \le n \le 2*10^5)$ 场比赛，每场比赛会从现有的4个成员中选出2人比赛，对于第 $i$ $(1 \le i \le n)$ 场比赛，如果是 Lewis 和 Valtteri 的比赛，只能卖出 $a_{i}$ 元的门票，如果是他们中一人和一个明星的比赛，能卖出 $b_i$ 元的门票，如果是两个明星 Max 和 Checo 之间的比赛，能卖出 $c_i$ 元的门票。观众们喜欢看明星之间的高水平比赛，而不是 Lewis 和 Valtteri 的菜鸡互啄，因此有 $1 \le a_{i} < b_{i} < c_{i} \le 10^9$ 。除此之外，安排比赛时还有如下要求——

因为明星都是日理万机的，他们只同意分别在Lewis的俱乐部停留最多 $t_m, t_c$ 场比赛的时间。设Max出席的第一场比赛是第 $p_m$ 场，最后一场是 $q_{m}$ 场，Checo出席的第一场比赛是第 $p_c$ 场，最后一场是 $q_c$ 场，则需要满足 $q_m - p_m +1 \le t_m$ 且 $q_c - p_c +1 \le t_c$ ；
Lewis 深知自己不会是两个明星的对手，他不会愿意自己被打得鼻青脸肿直接 KO，因此，他不会安排自己与两位明星的比赛（言下之意，挨打的工作就被 Lewis 偷偷安排给了自己的好基友 Valterri，让我们为可怜的工具人 Valterri 默哀）；
同时，Lewis 希望最大化自己的总收入，但是，他不太聪明，因此，如果一种方案满足以下条件，他就认为此方案满足”收入最大“——

定义 (“Lewis 的最优方案”)：对于一种方案，可以看作一个长度为 $2n$ 的序列，序列的第 $(2i-1)$ 和 $2i$ 项为第 $i$ 场比赛的对阵双方，如果通过修改序列的任意 $1$ 个位置，都无法得到一个收入严格大于当前收入的合法方案，则称此方案为“Lewis 的最优方案”。

聪明的你很快就发现了，“Lewis 的最优方案”不一定能最大化总收入且可能不唯一。已知 Lewis 会从所有“Lewis 的最优方案”（两个方案相同，当且仅当每一天的对阵均相同，注意，Max vs Valtteri 和 Checo vs Valtteri 虽然卖出门票相当，但视为两种不同的方案）等概率随机选一个方案执行，那么，请问在 Lewis 可能最终选择的所有方案中，门票收入的中位数是多少呢？（答案保留一位小数输出）

inputFormat:
第 $1$ 行：3个正整数 $n,t_m, t_c$ ，意义见题面；

接下来 $n$ 行：每行3个正整数 $a_i, b_i, c_i$ 表示三种情况下卖出的门票价格。

outputFormat: 一行一个正整数表示在 Lewis 最终选择的所有方案中，门票收入的中位数。

hint:
【样例解释】

Lewis的“收入最大方案”总共有以下 $4$ 种：

- Max vs Checo, Lewis vs Valtteri，门票收入为 $100+1=101$；
- Valtteri vs Max, Valtteri vs Checo，门票收入为 $10+2=12$；
- Valtteri vs Checo, Valtteri vs Max，门票收入为 $10+2=12$；
- Lewis vs Valterri, Max vs Checo，门票收入为 $1+3=4$。

中位数为 $\frac{12+12}{2} = 12$。

【数据范围】

对于 $100\%$ 的数据，$1 \le n, t_m, t_c \le 2*10^5$ , $1 \le a_{i} < b_{i} < c_{i} \le 10^9$。


title: [THUPC2022 初赛] 造计算机

description:
小R和小C听说贵系有一门造计算机的课之后吓得连夜提交了退学申请。

开玩笑的啦！正处于大一的他们对这门课不但不害怕，甚至有些想笑。他们超强的动手能力甚至驱使他们想造一个玩意玩玩。

当然由于他们毕竟才大一，计算机专业课基本上都没上过，经过长时间的艰苦奋战，他们终于造出了一个奇怪的玩意：

这台计算机只有 $n$ 个内存单元，反而有足够多个寄存器。内存单元的编号从 $1$ 到 $n$ ，寄存器从 $n+1$ 开始往上编号。每个内存单元和寄存器可以存储一个整数。

目前他们已经设计好了一类指令：`swap i, j`，表示交换编号为 $i$ 和 $j$ 的单元里的数，其中 $i$ 和 $j$ 均为正整数且 $i \neq j$ 。他们打算写一段程序来测试这条指令。

最开始， $n$ 个内存单元中乱序存放着 $1\thicksim n$ 这些数，且每个数恰好出现一次。而每个寄存器里存放的是它的编号。

两人打算设计一段指令序列，使得计算机依次执行完这些指令后，所有内存和寄存器中的数都归位，也就是恰好等于它自己的编号。

虽然没学过计算机专业课，小R和小C还是懂一点皮毛的，因此他们规定每条 `swap` 指令操作的两个位置至少有一个需要是寄存器，也就是 $i$ 和 $j$ 至少有一者应当大于 $n$。

然而，正当他们写完程序开始运行时，却发现系统崩溃了！在查找了半天原因后，他们发现了一个奇怪的 bug：他们设计出来的计算机不能运行两条相同的指令！也就是说，他们不能在一段程序里出现两条相同的 `swap i, j` 指令。更进一步他们发现即使出现一条 `swap i, j` 一条 `swap j, i` 也不行，因为计算机会自动将这两条指令视为同一条。

然后可怜的小R和小C就斯巴达了。不过他们在弃疗之前还是打算利用现有的架构把程序写出来。不仅如此，他们还希望用到的寄存器数量尽可能少。你能帮帮他们吗？

inputFormat:
第一行：一个正整数 $n\ (1 \leq n \leq 10^5)$ 表示内存单元的数量。

第二行： $n$ 个正整数$a_i$ 依次表示第 $i$ 个内存单元中的初始值，保证所有 $a_i$ 构成一个 $1 \thicksim n$ 的排列。

outputFormat:
第一行：两个非负整数 $m,k$，分别表示你用到的寄存器数量和指令的条数。

接下来 $k$ 行，每行输出两个正整数 $i, j$，依次表示你设计的每一条指令中交换的两个位置。你需要保证 $1 \leq i,j \leq n+m$，并且满足题目中对于指令的限制条件。

如果有多种设计指令的方案满足题目所需，输出任意一种即可。

你需要最小化 $m$ 而无需最小化 $k$，但需要保证 $k \leq 10^6$。输入数据保证符合要求的解存在。

hint:
【样例解释】

最初，前 $4$ 个单元的值依次为 $(2,1,3,4)$ 。

执行指令 `swap 3, 4`，各单元的值变为 $(2,1,4,3)$ 。

执行指令 `swap 1, 3`，各单元的值变为 $(4,1,2,3)$ 。

执行指令 `swap 2, 4`，各单元的值变为 $(4,3,2,1)$ 。

执行指令 `swap 1, 4`，各单元的值变为 $(1,3,2,4)$ 。

执行指令 `swap 2, 3`，各单元的值变为 $(1,2,3,4)$ 。

可以证明 $m=1$ 是不行的。


title: [THUPC2022 初赛] 搬砖

background: 张华考上了北京大学；李萍进了中等技术学校；小 E 在工地搬砖：他们都有光明的前途。

description:
**温馨提示：请不要模仿小 E 的搬砖方式，那样很累。**

为了能够快乐地搬砖，小 E 有一种特殊的搬砖方式。

假设他的面前有 $n$ 摞砖，他会在一个小时内搬走每一摞砖最上面的 $d$ 块。其中 $d$ 是小 E 当前的精力值。如果一摞砖不够 $d$ 块，小 E 会把这一摞砖剩下的所有砖搬走。

当小 E 工作完一个小时后发现自己搬完了至少一摞砖，那么他会觉得很快乐，并且继续工作一个小时；但是由于完成了一部分工作，小 E 可能会产生懈怠的心理，导致精力值有所下降。具体地，对于每一摞砖都有一个属性 $b$，当小 E 搬完这一摞砖后，精力值就会下降 $b$。

如果没有任何一摞砖被搬完，小 E 就会停止工作。如果精力值下降到 $0$ 或以下，小 E 也会停止工作。如果小 E 发现自己需要工作但是所有的砖已被搬完，他会用别的方式来度过这一小时，但这一小时仍算作小 E 的工作时间。

工地的砖在不停增加，问如果小 E 初始的精力值为 $d$，那么他可以连续工作几个小时？

inputFormat:
第一行一个正整数 $T$，表示事件总数。

接下来 $T$ 行，每行若干个整数，其中第一个整数为 $op$ 表示事件类型。

若 $op=1$，则后面跟着两个整数 $a,b$，表示新增了一摞砖，砖有 $a$ 块，搬完后小 E 的精力值会下降 $b$。

若 $op=2$，则后面跟着一个正整数 $d$，询问若小 E 初始的精力值为 $d$，那么他可以连续工作几个小时。

注意 $op=2$ 的操作**不会**改变任何一摞砖的数量。

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

hint:
【样例解释】

第一组询问：

初始有 $3$ 摞砖，数量分别为 $(6,3,9)$，小 E 的初始精力是 $3$。

第一个小时，小 E 在每一摞砖中各搬了 $3$ 块，数量变成 $(3,0,6)$。其中第二摞砖被搬完，小 E 的精力因此下降 $0$ 并且继续工作一个小时。

第二个小时，小 E 在每一摞砖中各搬了 $3$ 块，数量变成 $(0,0,3)$。其中第一摞砖被搬完，小 E 的精力因此下降 $1$ 并且继续工作一个小时。

第三个小时，小 E 在每一摞砖中各搬了 $2$ 块，数量变成 $(0,0,1)$。由于没有新的砖摞被搬完，小 E 停止工作。

第二组询问：

初始有 $3$ 摞砖，数量分别为 $(6,3,9)$，小 E 的初始精力是 $4$。

第一个小时，小 E 在每一摞砖中各搬了 $4$ 块（第二摞砖由于只有 $3$ 块就只搬了 $3$ 块，以下省略），数量变成 $(2,0,5)$。其中第二摞砖被搬完，小 E 的精力因此下降 $0$ 并且继续工作一个小时。

第二个小时，小 E 在每一摞砖中各搬了 $4$ 块，数量变成 $(0,0,1)$。其中第一摞砖被搬完，小 E 的精力因此下降 $1$ 并且继续工作一个小时。

第三个小时，小 E 在每一摞砖中各搬了 $3$ 块，数量变成 $(0,0,0)$。其中第三摞砖被搬完，小 E 的精力因此下降 $2$ 并且继续工作一个小时。

第四个小时，小 E 在每一摞砖中各搬了 $1$ 块，但其实此时已经没有砖了，不过这一小时仍然算进小 E 的工作时间。由于没有新的砖摞被搬完，小 E 停止工作。

【样例解释 2】

第一组询问：

初始有 $1$ 摞砖，数量为 $2$，小 E 的初始精力是 $2$。

第一个小时，小 E 在每一摞砖中各搬了 $2$ 块，数量变成 $0$。这一摞砖被搬完，小 E 的精力因此下降 $1$ 并且继续工作一个小时。

第二个小时，小 E 在每一摞砖中各搬了 $1$ 块，但其实此时已经没有砖了，不过这一小时仍然算进小 E 的工作时间。由于没有新的砖摞被搬完，小 E 停止工作。

第二组询问：

初始有 $2$ 摞砖，数量为 $(2,2)$，小 E 的初始精力是 $2$。

第一个小时，小 E 在每一摞砖中各搬了 $2$ 块， 数量变成 $(0,0)$。两摞砖都被搬完，小 E 的精力因此下降 $1+1=2$。由于小 E 的精力下降到 $0$，他停止工作。

【数据范围】

保证 $T\le 351493,1\le op\le 2,1\le a\le 100000,0\le b\le 100000,1\le d \le 100000$。


title: [THUPC2022 初赛] 喵喵花園

description:
喵喵是一只非常富有的猫咪，他在海淀区拥有一个大花园。

这个大花园是由一些旧栅栏为边界所形成的 $N$-gon（即具有 $N$ 边的多边形）。

由于圣诞节快到了，喵喵想用 $K$ 棵圣诞树来装饰一下花园。 同时，喵喵坚信找到一些好的位置来种树会给他带来好运。

作为一只好猫咪，他决定寻找最佳位置如下：

- 所有的树都应该在花园的边界上。
- 这些 $K$ 树应该平均划分花园的周长。
- 由树木形成的新凸面$K$-gon 的面积应尽可能小。

虽然喵喵比你有钱，但他没有你那么聪明。 因此，他给了你一些钱，让你帮他找出凸$K$-gon 的最小面积。

inputFormat:
第一行包含两个整数，$N$ 和 $K$，代表原本花园边界的顶点数和树的数量。

接下来的每行 $N$ 行包含两个整数 $x_i$ 和 $y_i$，表示花园边界顶点的坐标。

所有座标均为逆时针给出的。

outputFormat: 输出凸面 $K$-gon 的最小面积。 如果相对或绝对误差不超过 $10^{-8}$，则您的答案被认为是正确的。


title: [THUPC2022 初赛] 挑战

description:
**足够聪明**的 Alice 和 Bob 在玩一种棋盘游戏。这个游戏需要用到一个有 $(n+1)$ 个格子的长条棋盘，按从左到右的顺序给每个格子编号 $0, 1, \cdots, n$。除了编号为 $n$ 的格以外，每一格都有两个数 $p_i, q_i$。游戏开始前，将一个棋子放在第 $0$ 格。游戏由二人轮流操作，这里我们不妨假设 Alice 先手。

轮到其中一位玩家进行操作时，这位玩家可以根据当前格子的 $p$ 值决定前进的步数。具体地说，假设当前棋子位于第 $k$ 格，那么当前进行操作的玩家可以将棋子向前移动 $x$ 格，其中 $x$ 可以是满足 $1\le x\le p_k$ 的任意整数。如果玩家没有走满 $p_k$ 格，即 $x<p_k$，那么该玩家可以在完成移动后选择是否进行一次挑战。如果选择不进行挑战，那么由另一位玩家进行下一轮操作。否则，如果当前玩家选择挑战，那么系统将会产生两个随机**整数** $u$ 和 $v$，其中：$u$ 表示挑战的能量，它在 $\left[1, p_k-x\right]$ 中等概率产生；$v$ 表示挑战所需的活化能，它在 $\left[0, q_k + q_{k+x}\right]$ 中等概率产生。根据 $u$ 和 $v$ 的值，系统会根据以下规则自动判定挑战结果：

如果 $u>v$，则挑战成功，对方玩家的操作被跳过一轮，由当前玩家继续操作；
如果 $u=v$，则挑战结果为平手，什么事情都不会发生，由对方玩家进行操作；
如果 $u<v$，则挑战失败，当前玩家下一轮操作将会被跳过，即对方玩家可以连续操作两轮。
为了防止其中一方玩家一直被跳过，规定：

如果当前玩家通过自身的挑战获得额外操作机会，则该玩家在该额外操作机会中不能进行第二次挑战；
如果当前玩家通过对方玩家的挑战获得额外操作机会，则该玩家不能在其第一次操作结束时发起挑战，只能在第二次操作结束时选择是否进行挑战，并且当且仅当挑战成功时可以进行第三次操作。
需要注意的是，无论连续进行多少次操作，每次操作都需要将棋子向前移动至少 $1$ 格。同大多数游戏一样，谁将棋子移动到终点（即编号为 $n$ 的格）谁就获胜。

Alice 和 Bob 都足够聪明，可以心算出对于当前棋子的位置，能使自己获胜概率最大的操作。作为一名旁观者，你没有他们那么强的心算能力；但是你也想通过自己编程的能力，计算出当 Alice 先手从第 $0$ 格开始进行操作时，Alice 的胜率。

inputFormat:
输入的第一行包含一个正整数 $n$，表示棋盘包含 $(n+1)$ 格，分别标号 $0, 1, \cdots, n$。

输入的第二行包含 $n$ 个正整数 $p_0, p_1, \cdots, p_{n-1}$，分别表示第 $0$ 格至第 $(n-1)$ 格的 $p$ 值。

输入的第三行包含 $n$ 个正整数 $q_0, q_1, \cdots, q_{n-1}$，分别表示第 $0$ 格至第 $(n-1)$ 格的 $q$ 值。

outputFormat: 输出一个实数，表示 Alice 先手开始游戏的胜率。当你的输出与标准输出的绝对误差不超过 $10^{-6}$ 时，我们认为你的输出是正确的。

hint:
【样例解释 1】

Alice 先手，由于可以直接从第 $0$ 格移动到终点的第 $3$ 格，Alice 会直接将棋子移动到第 $3$ 格，故 Alice 必胜。

【样例解释 2】

Alice 先手，但是不能直接移动到第 $3$ 格，并且无论结束操作时棋子在第 $1$ 格还是第 $2$ 格，Bob 都可以直接将其移动到终点的第 $3$ 格，因此 Alice 必须尝试挑战。将棋子移动到第 $1$ 格并发动挑战，挑战成功的概率为 $1/4$，故 Alice 的胜率为 $1/4$。

【数据范围】

对于 $100\%$ 的数据，保证 $1\le n\le 100000$，$1\le p_i, q_i\le 333$。


title: [THUPC2022 初赛] 分组作业

description:
老师布置了分组作业。在此之前，老师将班上 $2n$ 个学生分成了 $n$ 组，每组两个人。其中 $1$ 号和 $2$ 号为一组，$3$ 号和 $4$ 号为一组，……，$2n-1$ 号和 $2n$ 号为一组。

老师让每个队伍自行安排分工。这样是否合作就成了一个大问题。大家决定用表决的方式来确定。首先每个人决定是否愿意和队友合作。不同的人因为自己的原因和分配的队友的原因，对合作的意愿不一样，对于第 $i$ 个学生，选择“愿意”会产生 $c_i$ 的不满，选择“不愿意”会产生 $d_i$ 的不满。

如果两名队友都选择“愿意”，那么根据实际情况他们可以合作或者不合作。但是如果有一名队友选择“不愿意”，那么他们只能不合作。

学生中还有 $m$ 个单向的喜欢关系，一个关系形如“$A$ 喜欢 $B$”。在这样一个关系中，如果 $A$ 没有和队友合作，且 $B$ 选择了“愿意”，$A$ 会有略微沮丧，产生 $a_i$ 的不满；如果 $A$ 表决了“不愿意”，但 $B$ 成功与队友合作，那么 $A$ 会羡慕嫉妒恨并产生 $b_i$ 的不满。（由于当 $A$ 和 $B$ 在同一组时这种设定会变得很奇怪，所以题目保证不会有这种情况）其中 $i$ 表示第 $i$ 个关系。

如果一个学生 $i$ 选择了“愿意”但是他的队友选择了“不愿意”，那么他会因为队友产生 $e_i$ 的不满。

问所有情况下最小的不满之和是多少。

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

接下来 $2n$ 行，每行三个整数 $c_i,d_i,e_i$。

接下来 $m$ 行，每行四个正整数 $A,B,a_i,b_i$ 。

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


title: [THUPC2022 初赛] 画图

description:
一年两度的THUPC又要来了，小C和小Z作为参赛无数届的老选手，自然也要来凑一番热闹。不过因为已经是老年人了，参赛自然是免谈了，但是他们对THUPC几年不换的logo产生了审美疲劳，为了更好地吸引大家报名，他们打算重画一个更花里胡哨的。

笑死，你怎么可能指望两个宅男码农有丝毫的艺术细菌？

他们深知这件事不在自己的能力范围之内，于是打算写一个人工智障来帮自己来画logo！

经过不懈的努力，他们的人工智障终于能跑起来了，不过他们很快就发现这个人工智障比自己还没有艺术细菌——它只会在平面上画水平和竖直的线段来拼成“THUPC”字样！

不过程序写都写了，不用白不用。小C和小Z针对程序的这一特性进行深入研究后制定了这样的规则：

对于每一条水平线段，设其横坐标区间为 $[l_i,r_i]$ ，纵坐标为 $y_i$； 对于每一条竖直线段，设其纵坐标区间为 $[d_i,u_i]$ ，横坐标为 $x_i$ 。上述所有数值均为整数，且满足$r_i > l_i,u_i > d_i$。

“THUPC”字样应当由 $15$ 条线段拼成，设其编号为 $1 \thicksim 15$ 。对于每一个字母，规则如下：

字母"T"由 $1$ 号水平线段和 $2$ 号竖直线段组成，满足 $d_2<y_1=u_2,l_1<x_2<r_1$ 。

字母"H"由 $3$ 号竖直线段、$4$ 号水平线段和 $5$ 号竖直线段组成，满足 $d_3=d_5<y_4<u_3=u_5,x_3=l_4<r_4=x_5$ 。

字母"U"由 $6$ 号竖直线段、$7$ 号水平线段和 $8$ 号竖直线段组成，满足 $d_6=d_8=y_7<u_6=u_8,x_6=l_7<r_7=x_8$ 。

字母"P"由 $9$ 号竖直线段、$10$ 号水平线段、$11$ 号水平线段和 $12$ 号竖直线段组成，满足 $d_9<y_{11}=d_{12}<u_9=y_{10}=u_{12},x_9=l_{10}=l_{11}<r_{10}=r_{11}=x_{12}$ 。

字母"C"由 $13$ 号竖直线段、$14$ 号水平线段和 $15$ 号水平线段组成，满足 $d_{13}=y_{15}<u_{13}=y_{14},x_{13}=l_{14}=l_{15}<r_{14}=r_{15}$ 。

生成的这 $5$ 个字母可以排布在平面的任何地方而无需从左到右排列，但是组成任意两个不同字母的任意两条线段不得相交。

需要注意的是，人工智障给出的线段顺序可能并不按照上述编号顺序；另外，给出的线段可能出现同方向线段的首尾相连、重叠或包含，此时应将其视为连续的一整条线段。

只有生成的线段在连接和排序后符合上述规范，才认为人工智障生成了一幅正确的logo；否则，如果出现多余的线段、缺少某条线段或坐标不满足要求等情况均为不正确的。

最后，小C和小Z要写一个程序来检验人工智障的每一份输出结果是否符合上述规范，不过熬夜连肝三天的他们终于累得爬不起来了，于是他们请你来帮忙。

inputFormat:
第 $1$ 行：一个正整数 $n$ 表示线段的个数，保证 $1 \leq n \leq 10^5$ 。

接下来 $n$ 行，每行先输入一个整数 $op_i$ ，必定为 $0$ 或 $1$ ：如果 $op_i=0$ ，表示第 $i$ 条线段为水平线段，接下来输入 $3$ 个整数 $l_i,r_i,y_i$ 描述这条线段，保证 $l_i<r_i$ ；如果 $op_i=1$ ，表示第 $i$ 条线段为竖直线段，接下来输入 $3$ 个整数 $d_i,u_i,x_i$ 描述这条线段，保证 $d_i<u_i$ 。

保证输入的坐标均在 $[-10^9,10^9]$ 范围内。

outputFormat: 如果符合规范，输出一个字符串 `Yes`，否则输出一个字符串`No`。

hint:
【样例解释】

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

这组样例中，字母 `T` 的水平线段和 `C` 的竖直线段分别是由两条线段拼成的。


title: [THUPC2022 初赛] 数正方体

description:
小 E 有一块面积为 $n\times m$ 的矩形区域，上面有 $n\times m$ 个边长为 $1$ 的格子，第 $i$ 行 $j$ 列的格子上堆了 $ A_{i,j}$ 个同样大小的正方体积木。小 E 做了某道题之后，突发奇想把这些正方体画成了字符画，然后让你帮他数一数他一共有多少个正方体。我们定义每个正方体为如下格式，并且不会做任何旋转，只会严格以这一种形式摆放：

```
..+---+
./   /| 高
+---+ |
|   | +
|   |/.宽
+---+..
长
```

每个顶点用 $1$ 个 + 表示，长用 $3$ 个 - 表示，宽用 $1$ 个 / 表示，高用两个 | 表示。字符 . 作为背景。中间的空白是空格（ASCII 码为 $32$ ）。

若两个正方体左右相邻，图示为

```
..+---+---+
./   /   /|
+---+---+ |
|   |   | +
|   |   |/.
+---+---+..
```

若两个正方体积木上下相邻，图示为

```
..+---+
./   /|
+---+ |
|   | +
|   |/|
+---+ |
|   | +
|   |/.
+---+..
```

若两个正方体前后相邻，图示为

```
....+---+
.../   /|
..+---+ |
./   /| +
+---+ |/.
|   | +..
|   |/...
+---+....
```

位于前面的正方体的面会遮挡住位于后面的正方体的面。为了让你看得清楚，没有整列正方体被挡在后面，小E保证了 $1\le A_{ij} \le A_{i-1,j}$，$1\le A_{ij}\le A_{i,j-1}$。并且图中没有整行或者整列的 . 。所以，一个字符画对应唯一的矩阵 $A$，一个矩阵 $A$ 也对应一个唯一的字符画。

inputFormat:
第一行两个正整数 $r,c$，表示图的高度和宽度。（注意不是 $n$ 和 $m$）

接下来是一个 $r$ 行 $c$ 列的字符画，表示小E堆叠的正方体。

outputFormat: 一行一个整数，表示正方体的数量。

hint:
【样例解释】

此时 $A$ 矩阵为

$$\begin{bmatrix}3 & 3 & 2 \\ 3 & 2 & 1\end{bmatrix}$$

，因为 $3+3+3+2+2+1=14$，所以图中共有 $14$ 个正方体。

【数据范围】

保证 $1\le n,m \le 50$，$1\le A_{ij}\le 100$。（注意这里是 $n$ 和 $m$ 不是 $r$ 和 $c$）

保证 $\forall 1<i\le n$, $A_{ij}\le A_{i-1,j}$。

保证 $\forall 1<j<m$, $A_{ij}\le A_{i,j-1}$。

保证字符画中没有一整行或者一整列是 . 。

小 E 的话：做出这题并不难。不过还是建议在 AC 本题之后看一看题解。


title: 〈 TREEのOI 2022 Spring 〉Counting By Ternary

background:
黑土地上，一棵小苗破土而出。

几个月里，它吮吸着甘甜的雨露，享受着温暖的阳光，愈发翠绿了起来。

![](https://cdn.pixabay.com/photo/2019/03/05/12/52/plant-4036131_960_720.jpg)

它越长越高，越长越壮，似乎要突破云霄。

它长成了一棵大树，渴望着去天空中，看一看这美丽的世界。

![](https://cdn.pixabay.com/photo/2015/02/24/15/41/wolf-647528_960_720.jpg)

description:
**请留意本题并不寻常的时空限制。**

给定一个数 $x$，用如下规则建立一棵有根树：

- 根节点为 $\lang0,x\rang$。

- 对于一个节点 $\lang i,j\rang$，若 $j < 3$，则它是叶子节点，否则它的子节点为对于任意 $1 \le k$ 且 $j$ 的位数 $\ge k$， $\lang j_k, k\rang$，其中 $j_k$ 为它三进制表示从左向右的第 $k$ 位。

求这棵树的叶子节点的数目。

inputFormat: 一行两个整数 $p, q$，表示 $x = p^q$。

outputFormat:
一行一个整数，即为所求。

题目保证答案在 $\tt int64$ 范围内。


title: 『JROI-7』PMK 配匹串符字

background:
> 限制很宽泛，构造也就很憨批。

——command_block 《考前小贴士》

description:
对于一个字符串 $S$，记 $|S|$ 表示 $S$ 的长度，记 $S_i$ 表示 $S$ 的第 $i$ 个字符，记 $S_{l,r}$ 表示 $S_l,S_{l+1},...,S_r$ 组成的字符串。定义两个字符串相等，当且仅当他们长度相等，且每个位置的字符相同。

对于一个字符串 $S$ 和一个正整数 $i\le |S|$，若 $k$ 是满足 $k<i$ 且 $S_{1,k}=S_{i-k+1,i}$ 的最大的正整数，则 $next_i=k$。特别的，若不存在 $k$ 满足条件，则 $next_i=0$。

请你构造一个由小写字母组成的字符串 $S$，满足 $|S|=n$，且对于所有正整数 $i\le |S|$，$next_i$ 之和最小。

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

outputFormat: 一行一个字符串，表示你构造的 $S$。**输出任意一种方案即可。**

hint:
### 数据规模
本题采用捆绑测试。

对于 $50\%$ 的数据，$n\le 26$。

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


title: 【深进1.例1】求区间和

description:
给定 $n$ 个正整数组成的数列 $a_1, a_2, \cdots, a_n$ 和 $m$ 个区间 $[l_i,r_i]$，分别求这 $m$ 个区间的区间和。

对于所有测试数据，$n,m\le10^5,a_i\le 10^4$

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

第二行，为 $n$ 个正整数 $a_1,a_2, \cdots ,a_n$

第三行，为一个正整数 $m$ 。

接下来 $m$ 行，每行为两个正整数 $l_i,r_i$ ，满足$1\le l_i\le r_i\le n$

outputFormat:
共 $m$ 行。

第 $i$ 行为第 $i$ 组答案的询问。


title: 「SvR-2」Work

description:
给定 $n$ 个**由小写字母组成**的字符串，定义第 $i$ 个字符串的价值为其有意义的子串的数量（**如果有多个本质相同的子串也统计多次**），第 $i$ 个字符串的一个子串有意义，当且仅当这个子串能被分成若干个串，其中每个串都是这 $n$ 个字符串中任意一个字符串的任意一个后缀。

这里有一个 $n=4$ 的例子：
```plain
int
printf
scanf
ntnt
```

- 对于 `printf` 这个字符串而言，`intf` 是有意义的，因为可以表示成 `int` 和 `f` ，分别是 `int` 和 `scanf` 的后缀，而 `rint` 则不是。

- 对于 `ntnt` 这个字符串而言，`ntnt` 也是有意义的，因为可以表示成 `nt` 和 `nt`，它们都是 `int` 同一个后缀，或者可以表示成 `ntnt`，是 `ntnt` 的一个后缀。

现在，小 Z 想知道这 $n$ 个字符串价值之和。

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

之后 $n$ 行，每行一个字符串。

outputFormat: 一行一个整数，表示价值之和。

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

**本题开启捆绑测试和 O2 优化。**

令 $s_i$ 表示第 $i$ 个字符串长度。
| Subtask | 数据范围/特殊性质 | 分值 |
| :------: | :------: | :------: |
| $1$ |  $n\le 3$，$\sum\limits \lvert s_i\rvert\le10$| $5 \operatorname{pts}$ |
| $2$ | $n=26$，每种字符串均由一种字符组成 | $5 \operatorname{pts}$ |
| $3$ |$n=1$ | $15 \operatorname{pts}$ |
| $4$ | $\sum\limits \lvert s_i \rvert \le 2000$ | $15 \operatorname{pts}$ |
| $5$ | $\sum\limits \lvert s_i \rvert \le 2\times10^5$ | $30 \operatorname{pts}$ |
| $6$ | $\sum\limits \lvert s_i \rvert \le 10^6$ | $30 \operatorname{pts}$ |

对于 $100\%$ 的数据，$1\le n \le 5\times10^5$，$n\le \sum\limits \lvert s_i \rvert \le 10^6$。


title: [JRKSJ R5] Concvssion

background:
![](https://cdn.luogu.com.cn/upload/image_hosting/no6azjmn.png?x-oss-process=image)

你很喜欢 Concvssion，但这并不妨碍你来做一道并不困难的有趣题目。

（题目背景图片来自 Phigros 曲绘，如有侵权，请告知出题人。）

description:
给定长度为 $n$ 的序列 $a,b$，满足 $\forall i\in[1,n],a_i,b_i\in[1,n]$。

定义一次操作为，$\forall i\in[1,n],b_i\gets a_{b_i}$。

你需要依次进行 $n$ 次操作，每次操作后求出 $\displaystyle\sum_{i=1}^n b_i$ 对 $998244353$ 取模的答案。

inputFormat:
第一行一个整数 $n$。\
第二行 $n$ 个整数表示 $a$。\
第三行 $n$ 个整数表示 $b$。

outputFormat: 共 $n$ 行，每行一个整数表示答案，答案对 $998244353$ 取模。

hint:
Idea：cyffff，Solution：Ntokisq / WhisperingSnowflakes，Code：cyffff / WhisperingSnowflakes，Data：cyffff

**Concvssion - Halv (Insane15.5)**
### 数据规模
本题采用捆绑测试。

| $\text{Subtask}$ | $n\le$ | 特殊限制 | $\text{Score}$ |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $10^4$ | 无 | $10$ |
| $2$ | $10^5$ | $\forall i\in[1,n],a_i\le10^3$ | $10$ |
| $3$ | $10^5$ | $\forall i\in[1,n],a_i=i\bmod n+1$ | $10$ |
| $4$ | $10^5$ | $a$ 是一个 $[1,n]$ 的排列 | $15$ |
| $5$ | $10^5$ | $a_1=1,\forall i\in[2,n],a_i< i$ | $25$ |
| $6$ | $10^5$ | 无 | $20$ |
| $7$ | $3\times10^5$ | 无 | $10$ |

对于 $100\%$ 的数据，$1\le a_i,b_i\le n\le 3\times10^5$。
### 特殊评分方式
本题开启子任务依赖，具体如下：
- 对于子任务 $i\in\{1,2,3,5\}$，您只需答对子任务 $i$ 即可获得子任务 $i$ 的分数。
- 对于子任务 $i=4$，您需要答对所有 $j\in[3,4]$ 的子任务 $j$ 才能获得子任务 $i$ 的分数。
- 对于子任务 $i\in\{6,7\}$，您需要答对所有 $j\in[1,i]$ 的子任务 $j$ 才能获得子任务 $i$ 的分数。


title: Altale (Fan-made FTR 7)

background:
[![](https://cdn.luogu.com.cn/upload/image_hosting/inglwsjz.png)](https://music.163.com/#/program?id=2067229684)

为什么评级 7？

Powerless：Equilibrium FTR 9.

description:
小机器人又在钓星星了。

星星在天空中形成了若干个星座，每个星座有一个“中心点”，如果星星脱离了与中心点的直接或间接的联系，那么星星就会从星座中脱离，掉落到地面上。

经过小机器人日日夜夜的观测，他发现了这些星座的性质：每一个星座内部都是联通的，星星的联系的数量总与星座中星星的数量相等。

另外，不同的星座之间星星没有联系，同一个星座中的星星都有间接或直接的联系。

他通过观测天体运动给星星编了号，他发现每个星座的中心点都是星座中编号最小的星星。

可惜的是，小机器人只能通过随（diao）缘（yu）的方式获得取消这些联系的钥匙。

小机器人非常贪心，想要用尽量少的时间获得尽量多的星星。

他想要 $k$ 颗星星，你能告诉他他至少需要钓上几把钥匙吗？

如果你解决了这个问题，说不定小机器人会送给你几颗星星哦~

**[简化题意](https://www.luogu.com.cn/paste/5nhqqjzm)**

inputFormat:
第一行两个整数 $n,k$，表示**天空中**所有的星星的**总数**和星星之间联系**总数**，和小机器人希望获得的星星数。

接下来 $n$ 行，每行两个整数 $u,v$ 表示 第 $u$ 颗和第 $v$ 颗星星之间存在联系。

保证任意星座内星星联系条数等于星星数，星星不会有自己到自己的联系，不会有两条联系建立在同样两颗星星上。

outputFormat: 一行一个整数，表示小机器人需要获得足够的星星所需最少的钥匙数。

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

设星座共有 $l$ 个。

对于 $100\%$ 的数据，保证 $1\le n\le 10^6,1\le k\le n-l$。

Subtask 1：对于 $20\%$ 的数据，保证 $n\le 1000$。

Subtask 2：对于 $10\%$ 的数据，保证 $l\le 5$。

Subtask 3：对于 $20\%$ 的数据，保证 $l\le 15$。

Subtask 4：无特殊限制。

----

样例解释 $1$：

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

消除 $(1,4)$ 间联系即可。

样例解释 $2$：

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

消除 $(8,14),(8,10),(8,16)$ 三条联系即可。

可以证明没有消除联系更少的方法。

可能有别的方法也仅需要消除 $3$ 条联系。


title: 「WHOI-1」Derives

background: 你的钱里面混进去了一个假币。

description:
你有 $n$ 枚硬币。经过准确的测量，你发现一定有一枚是假币，假币的质量与其他硬币不同。你想要找出这枚假币。

第 $i$ 轮，假设你当时有 $x_i$ 枚硬币，你会把当前钱堆所有钱分配到若干组，每组 $k_i$ 个，最终剩下的再单独分一组。每个硬币你要拿起来需要 $a$ 秒，那么这将会花费你 $ax_i$ 秒的时间。接下来，你会称量每一组，称量每组需要 $b$ 秒，所以这将会花费你 $b\cdot\lceil\frac{x_i}{k_i}\rceil$ 秒的时间。由于只有一枚假币，那么只会有一堆的质量与正常的质量不同。**在称量所有堆之后**，你将会选出与正常质量不同的那一堆，并进入下一轮，让 $x_{i+1}=k_i$。一直执行，直到 $x_i=1$。假设进行了 $m$ 轮，那么花费时间 $f=\sum\limits_{i=1}^{m}{(ax_i+b\cdot\lceil\frac{x_i}{k_i}\rceil)}$

请问，你在最差情况下（**即每轮选出不正常的都是 $k_i$ 个一堆的**）最少需要多长时间找出那枚假币？

inputFormat: 一行三个正整数，代表 $n,a,b$。

outputFormat:
第一行两个个非负整数 $f,m$，代表最小可能的时间和你的方案的轮数。

接下来一行 $m$ 个正整数，代表 $k_i$。

hint:
**说明**

**你需要尽量使得花费的时间更少。**

本题采用 Special Judge。

首先，你输出的答案一定要合法，也就是你输出的答案要与下面的选择方法符合，否则将获得 $0$ 分。

接下来，评测机会对你的输出进行判断。如果你输出的答案合法且与正确答案的差 $\le9$，那么你将获得 $(10-d)\times100\%$ 的分数。例如，如果你输出的答案与正确答案的差为 $4$，那么你将获得 $60\%$ 的分数。如果你输出的答案等于正确答案，你将获得 $100\%$ 的分数。请不要输出多余的数字或少输出。

**数据范围**

- $\text{subtask 1(10pts)}:$ $1\le n\le2000$。
- $\text{subtask 2(20pts)}:$ $1\le n\le75000$。
- $\text{subtask 3(30pts)}:$ $1\le n\le10^7$。
- $\text{subtask 4(40pts)}:$ $1\le n\le10^9$。

对于所有数据，满足 $0<a,b\le10^9$。

**样例说明**

对于第一个样例，进行两轮。$x_1=20,k_1=4,x_2=4,k_2=1$。答案 $f=20+15+4+12=51$。


title: 「GMOI R1-T2」Light

background:
前置芝士：平面镜成像原理。

因为百度的不太清楚，所以大家有不懂的可以自行搜索，也可以看本题的样例解释。

description:
通道可以认为是一个无限长的坐标轴，在原点 $O$ 上有一盏灯，在坐标为 $-L$ 和 $R$ 的地方分别有两面镜子，这两个镜子构成了无尽的灯廊。

为什么说无尽呢？是因为这两面镜子上理论上能呈现无穷个灯的像。现在，请你求出这盏灯左边或右边第 $x$ 个像的坐标。

inputFormat:
第一行一个整数 $T$，代表询问个数。

第二行两个整数 $L,R$，意思如题意中所描述。

接下来 $T$ 行，每行先输入一个字符，再输入一个数 $x$。其中如果输入的字符是 `L` 表示左侧，如果是 `R` 表示右侧。请求出左侧或右侧第 $x$ 个像的坐标。

保证字符是 `L` 或 `R` 中的一个。

outputFormat: $T$ 行，每行一个整数，为坐标值。


title: 不等价交换法则

background:
天弓千亦，市场之神，拥有着剥夺所有权的能力。

她希望着重建市场，在严格而公正的交易中一点点恢复自己的神力。但她看向世间一处处交易之所时，无力感却又遮住了她心中虹色的月光，把她的不甘一点点化作现实的泪。

她一次次在梦中经历着那个晚上。孤独的、神力尽失的她，紧紧攥住她那空白的卡牌，却被灵梦一把夺走。最后一张希望，也伴着虹色的月，消逝在永远的幻想中了。

也许交易本身就是不等价的吧，她想。

description:
你有 $n$ **件**商品可以买，其中第 $i$ 件的价格为 $a_i$。

蓝会给出一个正整数 $w$，代表你有 $w$ 元钱。你仅可以选择**一件**商品购买。店主允许你用已有的商品交换剩余的商品（当然了，也可以不换），但你交换获得的商品的价值和必须小于等于你用于交换的商品价值和。你想要知道，你最多能获得多少件商品。

注意：不能用空集交换其他商品。

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

接下来一行 $n$ 个正整数，表示 $\{a_n\}$。

接下来一行 $1$ 个正整数，表示 $w$。

outputFormat: 一个正整数，表示询问的结果。

hint:
【样例解释】

买价值为 $2$ 的物品，并交换为两个价值为 $1$ 的物品。

【数据范围及约束】

对于 $40\%$ 的数据，$n\leq 10$。

对于 $100\%$ 的数据，$1 \leq n\leq10^6$，$0 \leq a_i\leq 10^9$，$1 \leq w\leq2\times10^{9}$。


title: [COCI2012-2013#2] MORTADELA

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

description:
全国连锁超市（NSC）喜欢吹嘘它们的意式肉肠是全国最低的。

实际上，如果顾客打算在其他连锁超市里找到更便宜的肉肠，那么 NSC 会向其补上差价。

Matej 和 Filip 决定接受这个挑战。他们将会挨个走访 $N$ 家不同连锁店，来找到不仅比 NSC 便宜的熟香肠，而且在市场上最便宜的。如果他们成功了，他们就可以在他们学校附近的 NSC 分店买到最便宜的香肠。

NSC 希望没有人能找到更便宜的香肠，因为所有所有连锁超市（包括 NSC）都以一种复杂的方式表示香肠的价格：$X$ 元 $Y$ 克香肠。

请编写一个程序，给定 NSC 与其余 $N$ 家连锁店中的香肠价格，求 Matej 和 Filip 必须为靠近学校的 NSC 中的 $1000$ 克熟香肠支付的价格。

inputFormat:
第一行两个正整数 $X_{\textrm{NSC}}\ (1\le X_{\textrm{NSC}} \le 100)$ 和 $Y_{\textrm{NSC}}\ (1\le Y_{\textrm{NSC}} \le 10^3)$，表示 $X_{\textrm{NSC}}$ 是在 NSC 连锁店中 $Y_{\textrm{NSC}}$ 克香肠的价格。

第二行一个正整数 $N\ (1\le N\le 100)$，表示连锁店的数目（不包括 NSC）。

接下来 $N$ 行，每行两个正整数 $X_i,Y_i\ (X_i\le 100, Y_i\le 10^3)$，表示 $X_i$ 是在第 $i$ 家连锁店中 $Y_i$ 克香肠的价格。

outputFormat: 输出仅一行，一个实数，表示结果，保留 $2$ 位小数。


title: [COCI2012-2013#2] KRIZALJKA

background: **本题分值按 COCI 原题设置，满分 $80$。**

description:
你喜欢玩填字游戏吗？如果是，你可能会知道传统的初学游戏，如下所示：

***

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

- 水平方向上：

  1. 用于冷却电脑的设备

  2. 固态水

  3. 用来获得

- 垂直方向上：

  1. 又小又软又甜的水果

  2. 强力纸牌

  3. 渔夫的工具
***

给定六个有三个字母的单词，你需要把它们放在 $3\times 3$ 的方格上，使得水平与垂直均出现这几个单词。

inputFormat: 输入共 $6$ 行，每行一个有三个大写字母的单词。保证按字典序给出。

outputFormat:
如果不存在解法，输出 $0$。否则输出三行三列的字母矩阵。

如果存在多解，输出每行头尾相接形成的九个字符的字典序最小的方案。


title: [COCI2012-2013#2] LANCI

background: **本题分值按 COCI 原题设置，满分 $100$。**

description:
Mirko 在阁楼里发现了 $N$ 个链。每个链由一些节组成，其中每个节最多有两个相邻节。每个节都可以打开或合上，因此可以将链分开或连成更长的链。

Mirko 希望把所有链连成一条巨大的链，并且打开或合上尽可能少的节。

例如，假设 Mirko 只有 $3$ 个链，每个链只有一个节，他可以打开其中一个，并且连上另外两个再合上。

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

给定链的数量以及每个链的长度，找到 Mirko 必须打开和关闭的最小节数，使它们全部在一个长链上。

inputFormat:
第一行一个整数 $N\ (2\le N\le 5\times 10^5)$，表示链的数量。

第二行 $N$ 个正整数 $L_i\ (1\le L_i\le 10^6)$，表示第 $i$ 个链的长度。

outputFormat: 输出仅一行一个整数，表示最少要打开的节数。


title: [COCI2012-2013#2] POPUST

background: **本题分值按 COCI 原题设置，满分 $120$。**

description:
Mirko 像熊一样饥饿，发现了一家当地餐馆。这家餐厅提供 $N$ 顿饭，并且有一个有趣的定价政策：每顿饭都有两个指定价格，$A_i$ 和 $B_i$。Mirko 点的第一道菜只需要付 $A$ 元，其他菜都需要付 $B$ 元。

Mirko 无法决定点多少菜。为了更简单地作出决定，他向你求助。对于任意 $k\in[1,N]$，点 $k$ 道菜最少要付的钱。Mirko 不在乎他点了哪些特别的饭菜，也不管他点菜的顺序，但他不会点两道同样的菜。

inputFormat:
第一行一个正整数 $N\ (2\le N\le 5\times 10^5)$，表示菜品数量。

接下来 $N$ 行，每行两个正整数 $A_i,B_i\ (1\le A_i,B_i\le 10^9)$，题目已经描述。

outputFormat: 输出包含 $N$ 行，第 $k$ 行表示点 $k$ 道互不相同的菜最少需要花多少钱。

hint:
#### 样例#1 解释/说明

- $k=1$: Mirko 开始点第 $2$ 道菜，共花费 $A_2=9$ 元。

- $k=2$: Mirko 开始点第 $1$ 道菜，接着点第 $2$ 道菜，共花费 $A_1+B_2=13$ 元。

- $k=3$: Mirko 开始点第 $1$ 道菜，接着点第 $2,3$ 道菜，共花费 $A_1+B_2+B_3=18$ 元。


title: [COCI2012-2013#2] INFORMACIJE

background: **本题分值按 COCI 原题设置，满分 $140$。**

description:
Mirko 很无聊，所以他拿起一张纸，写下了一个含有 $N$ 个元素的序列 $A$，$1\sim N$ 的所有正整数在其中恰好仅出现一次。然后，他拿了另外一张纸，写下了 $M$ 个关于 $A$ 的描述。

每个描述有两种方式：

- `1 x y v`：表示 $[x,y]$ 区间中最大的数为 $v$。

- `2 x y v`：表示 $[x,y]$ 区间中最小的数为 $v$。

随后 Slavko 来偷走了他的第一张纸。Mirko 感到绝望，他想要你找到满足这些描述的序列，不需要跟原序列完全相同。

inputFormat:
第一行两个整数 $N,M\ (1\le N\le 200, 0\le M\le 4\times 10^4)$，分别表示序列长度以及描述的数量。

接下来 $M$ 行每行一个描述。

outputFormat: 输出仅一行，一个满足所有描述的长为 $N$ 的序列，并且 $1\sim N$ 在其中出现并仅出现一次，用空格隔开。如无解，输出 $-1$。


title: [COCI2012-2013#2] INSPEKTOR

background: **本题分值按 COCI 原题设置，满分 $160$。**

description:
一个新城镇刚刚在一个小国家落成。 像往常一样，Mirko 获得了首席税务监察员的职位。 他的职责是确保镇上所有不同公司的充分会计处理。

沿大街有 $N$ 个营业厅，从左到右编号为 $1\sim N$。一开始所有的办公室都是空的； 随着时间的推移，公司将进出这些办公室。 不时，Mirko 会经过一些办公室，只检查这些办公室中目前最富有的一家。

搬入的公司用四个整数来描述：

- $T$：搬入的日期。此处设小镇建成当天为 $1$。

- $K$：办公室序号。

- $Z$：公司的每日利润（如果公司亏损，则可能为负数）。

- $S$：搬入当天公司账户余额。

如果办公室 $K$ 中已经有一家公司，则当新公司搬入时，该公司搬出。

新公司直到搬入后的第二天才开始营业（或赚取利润）。

米尔科的巡视由三个整数描述：

- $T$：巡视的日期。小镇建成当天为 $1$。

- $A,B$：Mirko 将会经过 $[A,B]$ 内所有办公室。

由于 Mirko 只在一天结束时工作，所以到 Mirko 散步时，所有公司都已经完成了当天的业务并公布了当天的利润。

帮助 Mirko 编写一个程序，在每次闲逛时查找 Mirko 路过的当前最富有的公司的账户余额。

inputFormat:
输入的第一行包含两个正整数，$N\ (1 ≤ N ≤ 10^5)$ 和 $M \ (1 ≤ M ≤ 3\times 10^5)$，
分别表示办公室和巡视的数量。

接下来 $M$ 行，每一行包含一个事件的描述，格式为 `1 T K Z S`（公司搬入）或 `2 T A B`（Mirko 的巡视）。

所有事件都按时间顺序给出，每天最多发生一个事件（即 $T$ 将是严格递增）。 最后一个事件的天数将小于 $10^6$, 所有 $Z$ 和 $S$ 数字的绝对值
值将小于 $10^6$。

outputFormat: 对于 Mirko 的每一次巡视，输出一行包含 Mirko 检查的公司的账户余额，或者如果他将经过的所有办公室都是空的，则输出单词 `nema`。


title: 「GLR-R3」春分

background:
  「解冻群芳盛，馀寒百卉稀」

---

  吉他　贝斯　键盘　架子鼓

  她们的声嗓　七八点的太阳光

  炖作一隅　所谓青春的模样

  可惜他们　还得把那胜负扛在

  佯作成熟的肩上

---

  **春分** 「你我间有无形磁场　追赶着终有天碰撞　迸发火光吧」

description:
休息室外的走廊上有一块电视屏幕，除了高考倒计时外，还偶尔整些无聊的活。练习的间隙，枕在某位阿绫腿上的天依竖起耳朵听着，但闻——

今有一外国小哥，整了个笨重、花哨、无用的原电池装置，天依的脑补图如下：

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

我们只关心中间的红色部分，它们是若干分隔板，用于分隔左右两侧的溶液。这些分隔板**可拆下，可任意顺序同时组装入任意块，可翻转左右方向**。

现在小哥有两组溶液，第一组为 $X=\{x_1,x_2,\cdots,x_n\}$，第二组为 $Y=\{y_1,y_2,\cdots,y_n\}$，这 $2n$ 种溶液**两两不同**。小哥想将每种 $X$ 组内溶液置于容器左侧，每种 $Y$ 组内溶液置于容器右侧，一共进行 $n^2$ 次原电池实验。每次实验结束后，严谨的小哥会清洗装置，但是他不想清洗分隔板。

实验过程中，若分隔板的某侧**直接接触**了实验溶液，则此种溶液会沾在分隔板对应侧。为了防止溶液的污染，任意分隔板沾上任何一种溶液的**一侧**都不能和**非同种**的实验用溶液接触。例如下图（红色竖线表示分隔板，蓝色标号表示两侧已沾上的溶液，黑色标号表示实验中的溶液，下同）：

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

此外，若一次使用了多个分隔板，由于分隔板贴合紧密，所以若某块分隔板的一侧与另一分隔板沾有某种溶液的一侧相接触，这种溶液就会残留在两块分隔板各自的接触侧。例如下图（绿色标号表示本次实验后两块分隔板**新**沾上的溶液）：

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

小哥称他希望用较少（**不必最少**）数量的分隔板完成所有实验，并邀请观众给出使用分隔板的数量 $m$ 和此时**依次进行**的 $n^2$ 次实验中，所用的左右两侧溶液种类以及使用分隔板的方案。

天依预料到评论区的答案一定质量堪忧，所以邀请你来构造一个优秀的方案。

inputFormat: 一行一个整数 $n$，表示集合 $X,Y$ 的大小。

outputFormat:
输出 $n^2+1$ 行，描述你的构造。

第一行一个整数 $m$，表示需要的集合分隔板的数量。**你应当保证 $1\le m\le 712$。** 为方便后文描述，将分隔板记为 $C_1,C_2,\cdots,C_m$。

接下来 $n^2$ 行，第 $i$ 行按次序进行的第 $i$ 次实验：

1. 首先输出一个整数 $k\in[1,m]$，表示本次实验安装的分隔板数量。

2. 接着输出整数 $u\in[1,n]$，表示左侧所用溶液为 $x_u$。

3. 然后依次输出 $k$ 个整数 $p_1,p_2,\cdots,p_k$。对于其中第 $t$ 个整数 $p_t\in[-m,0)\cup(0,m]$ 描述了从左到右第 $t$ 块分隔板：

	- 若 $p_t>0$，则其为 $C_{p_t}$；

	- 否则 $p_t<0$，则表示翻转 $C_{-p_t}$ 的左右面，然后将其安装。注意本次实验完成后，$C_{-p_t}$ 的默认左右面仍然是翻转前的左右面。（即翻转的效果**不会保持**。）

4. 最后输出整数 $v\in[1,n]$，表示右侧所用溶液为 $y_v$。

一行内的多个整数间应用单个半角空格隔开，不允许行末出现多余的空格。不符合格式的答案可能被判为 Wrong Answer。


title: 虹色的北斗七星

background:
**【题目背景与题意无关，可以直接阅读题目描述】**

（本题目背景部分改编自真实案例）

宇佐见莲子是外界的一名大学生，在京都的一所大学中专攻超统一物理学，最近在做弦论方面的研究。

莲子与梅莉一同经营着名为秘封俱乐部的社团。进行着在科学世纪探寻遍布四处的结界的活动。

这个月梅莉和莲子又商量着去进行新一轮的探索与发现与贴贴，但是在两人手牵手出门的时候甜腻腻的气氛却被一通电话打破。

莲子因为经常外出探险，同时与梅莉增进感情交流，所以作业一拖再拖。她的物理学教授忍无可忍（毕竟莲子可是拖了一个学期的物理作业一个字都没有动呢），规定她必须在 $\sqrt9$ 天之内交上一篇学习报告，然后才同意给她的“课外实践活动”报备。

这可就没有办法了呢（笑），莲子只好先努力在 deadline 之前糊弄完她的学习报告，然后才能执行她们观赏夜空的计划。

description:
由于前两天都被莲子用来进行活动的筹备工作了，所以现在她只有几分钟的时间糊弄作业。尽管这样不太好，但是她别无选择，只能从之前的课堂笔记中摘取一段内容。

莲子的课堂笔记共有 $n$ 章，每章分别记着不同的内容。她可以选择其中任意连续的一段 $[l,r]$（表示选取了第 $l$ 章到第 $r$ 章）作为最终的成果。

每一章的内容各不相同，老师对每章内容有一个评价分 $a_i$。因为学习报告要体现出学生的进步，所以老师的满意度将会加上其中最差（$\min\{a_i\}$）和最好章节（$\max\{a_i\}$）的评价分差距。因为直接把冗长的课堂笔记作为报告提交显得太敷衍，所以每存在一章内容，老师的满意度就会 $-1$。

形式化地来说，如果莲子提交了 $[l,r]$ 这一段区间的笔记，老师的满意度将会是 $\max\{a_l,a_{l+1},\cdots,a_r\}-\min\{a_l,a_{l+1},\cdots,a_r\}-(r-l+1)$。

莲子希望你能帮她找出一种使得老师的满意度最大的方案。因为她非常聪明，所以只需要你告诉她这个最大的满意度，她就会知道应该怎么做。

**【形式化题意】**

你有一个长度为 $n$ 的序列 $a$，它的一个区间 $[l,r]$ 的价值是 $\max\{a_l,a_{l+1},\cdots,a_r\}-\min\{a_l,a_{l+1},\cdots,a_r\}-r+l-1$。求这个序列价值最大的子区间并输出这个价值。

inputFormat:
第一行输入一个正整数 $n$，表示笔记的章节数。

第二行输入评价分序列 $a$，以空格隔开每一个元素。

outputFormat: 输出这个评价分序列中，老师满意度最大的子区间的满意度。

hint:
**【样例解释和说明】**

令 $l=4,r=5$，则有 $\min\{a_4,a_5\}=2$，$\max\{a_4,a_5\}=8$，贡献值为 $4$。易证这是满意度最大的子区间。

**【数据范围】**

- 对于 $20\%$ 的数据，$n\leq 5\times 10^3$。
- 另有 $20\%$ 的数据，所有的 $a_i$ 都相等。
- 对于 $100\%$ 的数据，$1\le n\le 4\times10^6$，$1 \leq a_i \leq 10^9$。


title: x 进制转 10 进制

description: 给一个小整数 $x$ 和一个 $x$ 进制的数 $S$。将 $S$ 转为 $10$ 进制数。对于超过十进制的数码，用 `A`，`B`，$\ldots$ 表示。

inputFormat:
第一行一个整数 $x$;

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

outputFormat: 输出仅包含一个整数，表示答案。

hint:
【数据规模和约定】

保证目标数在十进制下不超过 $10^9$，$1 \leq x \leq 36$。


title: [NOI Online 2022 提高组] 丹钓战

background:
**经过管理员的考虑，我们打算将民间数据单独存放在最后一个 Subtask 中。这些测试点分数均为 0 分，但是没有通过其中的任何测试点将会视为此题不通过。**

**这一题中出现了评测记录测试点编号错乱的问题，是民间数据命名方式冲突导致的。但是我们保证其相对顺序没有混乱。**

民间数据提供者：@Froggy。

description:
有 $n$ 个二元组 $(a_i, b_i)$，编号为 $1$ 到 $n$。

有一个初始为空的栈 $S$，向其中加入元素 $(a_i, b_i)$ 时，先不断弹出栈顶元素直至栈空或栈顶元素 $(a_j , b_j)$ 满足 $a_i \neq a_j$ 且 $b_i < b_j$，然后再将其加入栈中。

如果一个二元组入栈后栈内只有这一个元素，则称该二元组是“成功的”。

有 $q$ 个询问 $[l_i, r_i]$，表示若将编号在 $[l_i, r_i]$ 中的二元组按编号从小到大依次入栈，会有多少个二元组是“成功的”。

询问之间相互独立。

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

第二行 $n$ 个正整数表示 $a_i$。

第三行 $n$ 个正整数表示 $b_i$。

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

outputFormat: $q$ 行，每行一个自然数表示一组询问的答案。

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

以第一次询问 $[1, 4]$ 为例。

一开始栈为 $\{\}$。

加入 $1$ 号二元组后栈为 $\{(3, 10)\}$，栈中只有一个元素，该二元组是“成功的”。

加入 $2$ 号二元组 $(1, 10)$ 时，栈顶的 $(3, 10)$ 的 $b$ 值不大于 $2$ 号二元组的，因此弹栈。此时栈空，$2$
号二元组入栈，栈为 $\{(1, 10)\}$，该二元组是“成功的”。

加入 $3$ 号二元组 $(3, 2)$，此时栈顶元素与之 $a$ 值不同，$b$ 值比它更大，因而不需要弹栈，直接将 $3$ 号二元组入栈，栈为 $\{(1, 10),(3, 2)\}$，栈中有多个元素，该二元组不是“成功的”。

加入 $4$ 号二元组 $(1, 9)$，此时栈顶元素 $(3, 2)$ 的 $b$ 值比它小，弹栈。弹栈后栈顶元素 $(1, 10)$ 与
$(1, 9)$ 的 $a$ 值相同，继续弹栈。此时栈空，$4$ 号二元组入栈，栈为 $\{(1, 9)\}$，该二元组是“成功的”。共有 $3$ 个二元组是“成功的”，因而答案为 $3$。

**【样例 2,3,4】**

见附件 $\texttt{stack/stack*.in}$ 与 $\texttt{stack/stack*.ans}$。

链接：<https://pan.baidu.com/s/14XxLN63bxvpJAod81foGOg>
提取码：gugu

**【数据范围与提示】**

对于所有测试点：$1 \leq n, q \leq 5 \times 10^5$，$1 \leq a_i, b_i \leq n$，$1 \leq l_i \leq r_i \leq n$。

每个测试点的具体限制见下表：

| 测试点编号   | 特殊性质        |
| ------------ | --------------- |
| $1 \sim 3$   | $n,q \leq 1000$ |
| $4 \sim 6$   | $n \leq 5000$   |
| $7 \sim 10$  | $n,q \leq 10^5$ |
| $11 \sim 12$ | $b_i=n-i+1$     |
| $13 \sim 15$ | $a_i=i$         |
| $16 \sim 20$ | 无              |


title: [NOI Online 2022 提高组] 如何正确地排序

background:
**经过管理员的考虑，我们打算将民间数据单独存放在最后一个 Subtask 中。这些测试点分数均为 0 分，但是没有通过其中的任何测试点将会视为此题不通过。**

**这一题中出现了评测记录测试点编号错乱的问题，是民间数据命名方式冲突导致的。但是我们保证其相对顺序没有混乱。**

民间数据提供者：@QwQcOrZ。

description:
有一个 $m\times n$ 的数组 $a_{i,j}$。
定义：

$$f(i,j)=\min\limits_{k=1}^m(a_{k,i}+a_{k,j})+\max\limits_{k=1}^m(a_{k,i}+a_{k,j})$$

你需要求出 $\sum\limits_{i=1}^n\sum\limits_{j=1}^nf(i,j)$。

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

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

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


title: [NOI Online 2022 提高组] 讨论

background:
**经过管理员的考虑，我们打算将民间数据单独存放在最后一个 Subtask 中。这些测试点分数均为 0 分，但是没有通过其中的任何测试点将会视为此题不通过。**

**这一题中出现了评测记录测试点编号错乱的问题，是民间数据命名方式冲突导致的。但是我们保证其相对顺序没有混乱。**

民间数据提供者：@AutumnKite，由 @tiger2005 进行加强。

description:
有 $n$ 个人正在打模拟赛，模拟赛有 $n$ 道题目。
有两人都会的题目并且没有人会的题目包含另一个人时，两者之间才会讨论。
（定义第 $i$ 个人会的题目的集合为 $S_i$ ，即当 $S_x\cap S_y\neq\varnothing\land S_x\not\subseteq S_y\land S_y\not\subseteq S_x$ 时，第 $x$ 人和第 $y$ 人会讨论）
为了让模拟赛的效果更好，希望你可以找出一对会讨论的人或判断不存在。

inputFormat:
第一行一个正整数 $T$ 表示数据组数，对于每组数据：
第一行一个正整数 $n$ 表示人数和题目数量。
接下来 $n$ 行，第 $i$ 行第一个自然数 $k_i$ 表示第 $i$ 个人会 $k_i$ 道题。接下来 $k_i$ 个正整数，每个数 $x$ 表示第 $i$ 个人会第 $x$ 道题。

outputFormat:
对于每组数据：
如果没有会讨论的人，输出 `NO`。
否则第一行输出 `YES`，第二行输出两个正整数 $x$ 和 $y$，表示第 $x$ 人和第 $y$ 人会讨论。
如果有多种方案，输出任意一种即可。

hint:
**【样例 2】**

见附件中的 `discuss/discuss2.in` 与 `discuss/discuss2.ans`。

**【数据范围与提示】**

对于所有测试点：令一组数据中 $m=\sum k_i$，则 $1\le T\le 5$，$1\le \sum n\le {10}^6$，$1\le \sum m\le 2\times {10}^6$，$0\le k_i\le n$。

每个测试点的具体限制见下表：

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


title: [NOI Online 2022 入门组] 王国比赛

background:
**经过管理员的考虑，我们打算将民间数据单独存放在最后一个 Subtask 中。这些测试点分数均为 0 分，但是没有通过其中的任何测试点将会视为此题不通过。**

民间数据提供者：@一扶苏一。

description:
智慧之王 Kri 统治着一座王国。

这天 Kri 决定举行一场比赛，来检验自己大臣的智慧。

比赛由 $n$ 道判断题组成，有 $m$ 位大臣参加。现在你已经知道了所有大臣的答题情况，但尚未拿到答案，于是你决定先行预测。

具体来说，对于第 $i$ 道题，有 $x$ 个大臣选对，$y$ 个大臣选错（显然有 $x+y=m$），如果 $x>y$，那么你预测这题答案为对，否则为错。为了方便，我们保证 $m$ 是奇数。

在统计完成后，你拿到了答案，你想知道通过你的预测方式你最后有几道题预测正确。

inputFormat:
第一行两个正整数 $n,m$，保证 $m$ 是奇数。

接下来 $m$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个整数代表第 $i$ 位大臣对第 $j$ 道题的答案，$1$ 表示他选对，$0$ 表示他选错。

接下来 $1$ 行 $n$ 个整数， 表示比赛答案，第 $i$ 个数 $b_i$ 若为 $1$ 表示第 $i$ 道题答案是对，若为 $0$ 表示答案是错。

outputFormat: 输出一个整数，表示你最后有几题预测正确。

samples:
见附件中的 kingdom3.in
见附件中的 kingdom3.out

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

- 第一题 $x=1,y=2$ 你预测答案为错（即 $0$），实际答案为1，预测错误。
- 第二题 $x=2,y=1$ 你预测答案为对（即 $1$），实际答案为1，预测正确。
- 第三题 $x=2,y=1$ 你预测答案为对（即 $1$），实际答案为1，预测正确。

所以预测正确的题数为 $2$。

**【数据范围】**

对于 $20\%$ 的数据，$n\le 5$，$m=1$。

对于 $50\%$ 的数据，$n\le 10$，$m\le 10$。

对于 $100\%$ 的数据，$1 \le n\le 1000$，$1 \le m\le 1000$，$m$ 为奇数。


title: [NOI Online 2022 入门组] 数学游戏

background:
**经过管理员的考虑，我们打算将民间数据单独存放在最后一个 Subtask 中。这些测试点分数均为 0 分，但是没有通过其中的任何测试点将会视为此题不通过。**

民间数据提供者：@一扶苏一。本题不保证民间数据强度，详见[这个帖子](https://www.luogu.com.cn/discuss/422596)。

description:
Kri 喜欢玩数字游戏。

一天，他在草稿纸上写下了 $t$ 对正整数 $(x,y)$，并对于每一对正整数计算出了 $z=x\times y\times\gcd(x,y)$。

可是调皮的 Zay 找到了 Kri 的草稿纸，并把每一组的 $y$ 都擦除了，还可能改动了一些 $z$。

现在 Kri 想请你帮忙还原每一组的 $y$，具体地，对于每一组中的 $x$ 和 $z$，你需要输出最小的正整数 $y$，使得 $z=x\times y\times\gcd(x,y)$。如果这样的 $y$ 不存在，也就是 Zay 一定改动了 $z$，那么请输出 $-1$。

注：$\gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公约数，也就是最大的正整数 $d$，满足 $d$ 既是 $x$ 的约数，又是 $y$ 的约数。

inputFormat:
第一行一个整数 ，表示有 $t$ 对正整数 $x$ 和 $z$。

接下来 $t$ 行，每行两个正整数 $x$ 和 $z$，含义见题目描述。

outputFormat: 对于每对数字输出一行，如果不存在满足条件的正整数 $y$，请输出 $-1$，否则输出满足条件的最小正整数 $y$。

samples:
见附件中的 math3.in
见附件中的 math3.out

samples:
见附件中的 math4.in
见附件中的 math4.out


title: [NOI Online 2022 入门组] 字符串

background:
**经过管理员的考虑，我们打算将民间数据单独存放在最后一个 Subtask 中。这些测试点分数均为 0 分，但是没有通过其中的任何测试点将会视为此题不通过。**

**这一题中出现了评测记录测试点编号错乱的问题，是民间数据命名方式冲突导致的。但是我们保证其相对顺序没有混乱。**

民间数据提供者：@tiger2005。

description:
Kri 非常喜欢字符串，所以他准备找 $t$ 组字符串研究。

第 $i$ 次研究中，Kri 准备了两个字符串 $S$ 和 $R$ ，其中 $S$ 长度为 $n$，且只由 `0`, `1`, `-` 三种字符构成（注：这里的第三种字符是减号），$R$ 初始时为空。

每次研究，Zay 会带着一个美丽的长度为 $m$ 的字符串 $T$ 来找 Kri 玩，Kri 非常羡慕 Zay 拥有如此美丽的字符串，便也想用字符串 $S$ 和 $R$ 变出字符串 $T$。

具体地，Kri 将会进行 $n$ 次操作。每次操作中，Kri 会取出 $S$ 的第一个字符（记为 $c$），并将其从 $S$ 中删去。如果 $c = \texttt{-}$，则 Kri 要删去 $R$ 的开头字符或结尾字符（数据保证删去后 $R$ 不为空）。否则，Kri 会将 $c$ 加入到 $R$ 的末尾。

当进行完所有操作后，Kri 会检查 $R$ 是否和 $T$ 相等。如果 $R = T$，Kri 就会感到开心；否则，Kri 会感到难受。

请问在每次研究中，Kri 有多少种操作方式使自己最后感到开心？我们定义两种方案不同，当且仅当在某种方案的某次操作中， Kri 删去了 $R$ 的开头字符。而在另一种方案的这次操作中， Kri 删去了 $R$ 的结尾字符。

由于答案可能很大，你只需要输出答案除以 $1,000,000,007$（即 $10^9+7$）的余数。

inputFormat:
第一行一个正整数 $t$。

接下来有 $t$ 组数据分别表示 $t$ 次字符串的研究，对于每组数据：

第一行有两个正整数 $n,m$，分别表示字符串 $S,T$ 的长度。

第二行是字符串 $S$。

第三行是字符串 $T$。

outputFormat: 共 $t$ 行，第 $i$ 行表示第 $i$ 组研究的答案。

samples:
见附件中的 string2.in
见附件中的 string2.out

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

对于第一组数据，有以下两种方案：

- 第一个 `-` 删 $R$ 的开头，第二个 `-` 删 $R$ 的开头。
- 第一个 `-` 删 $R$ 的结尾，第二个 `-` 删 $R$ 的开头。

**【数据范围】**

对于 $20\%$ 的数据，$n,m\le 15$。

对于 $30\%$ 的数据，$n,m\le 30$。

对于 $70\%$ 的数据，$n,m\le 80$。

对于另 $10\%$ 的数据，保证答案不超过 $1$。

对于 $100\%$ 的数据，$1\le t\le 5$，$1\le n,m\le 400$。


title: [CTS2022] 普罗霍洛夫卡

description: 给定序列 $a_1,\dots,a_n$，共 $m$ 次询问，每次询问给出 $l,r$，查询所有满足 $l\le L\le R\le r$ 的 $(L,R)$ 的权值的按位异或和，二元组 $(L,R)$ 的权值是 $|\{a_i\mid L\le i\le R\}|$。

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

第一行两个整数 $n\ m$；

接下来一行 $n$ 个整数 $a_1,\dots,a_n$；

接下来 $m$ 行，每行两个整数 $l\ r$ 表示一次查询。

outputFormat:
输出到标准输出。

输出 $m$ 行，依次表示每个询问的答案。

hint:
对于 $5\%$ 的数据，满足 $1\le n,m\le 100$。

对于 $10\%$ 的数据，满足 $1\le n,m\le 5000$。

对于 $20\%$ 的数据，满足 $1\le n,m\le 10^5$。

对于 $30\%$ 的数据，满足 $1\le n,m\le 2\times 10^5$。

对于 $40\%$ 的数据，满足 $1\le n,m\le 3\times 10^5$。

对于 $50\%$ 的数据，满足 $1\le n,m\le 3.5\times 10^5$。

对于另外 $10\%$ 的数据，满足 $m=n^2$。

对于另外 $10\%$ 的数据，满足对任意 $i=1\cdots n$，$a_i\le 2$。

对于另外 $10\%$ 的数据，满足对任意 $i=1\cdots n$，$a_i\le 10$。

对于 $100\%$ 的数据，满足 $1\le n,m\le 4\times 10^5$，$1\le a_i\le n$，所有数值为整数。

每类数据构成子任务。


title: [CTS2022] 独立集问题

description:
小 E 喜欢出最大权独立集问题。

接下来，他还想了 $n$ 道最大权独立集问题。

但是和之前不一样，这回他想把 $n$ 道题整合成一道题出出来。

小 E 有 $n$ 个 AI，编号为 $1\sim n$ 。

开始第 $i$ 个 AI 里面存有一道小 E 事先出好的一道难度为 $d_i$ 的最大权独立集问题。

有些 AI 之间可以互相通信，对于所有的 $2 \le i \le n$ ，第 $i$ 个 AI 可以和第 $c_i$ 个 AI 互相通信。其中 $c_i<i$。所以，这些 AI 连成了一个树的形状。此外，其他对 AI 不可以互相通信。

小 E 每次可以选择一个存有一道最大权独立集问题的 AI，结合它能够直接互相通信的所有 AI 中的问题，变成一道新的最大权独立集问题。整合问题时总有难度损失，不可能是把所有问题的难度直接相加。这道新的最大权独立集问题的难度是那些能够直接互相通信的 AI 中的题目难度和减去原本存在该 AI 上的问题的难度。然后那些能够直接互相通信的 AI 中的问题难度会变成 $0$。

小 E 希望通过若干次操作，把 $n-1$ 个 AI 中的题目难度都变成 $0$，然后把最后一个 AI 中的题目出出来。

由于出题人的丧病心理，小 E 想要出出来的最大权独立集问题的难度尽量大。

他想叫你帮他解决这个问题，还说如果你成功解决了这个问题，那么在出那道最大权独立集问题的时候，他会帮你提交一份标程代码。

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

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

第三行 $n-1$ 个正整数，第 $i$ 个表示 $c_{i+1}$。

hint:
保证 $1\le n\le 351493$。

保证 $1\le c_i <i$。

保证 $|d_i|\le 10^9$。

子任务 1（13 分）：$c_i=i-1$。

子任务 2（6 分）：$d_i>0$。

子任务 3（11 分）：$n\le 7$。

子任务 4（13 分）：$n\le 16$。

子任务 5（22 分）：$n\le 100$。

子任务 6（35 分）：无特殊性质。


title: [CTS2022] 回

description:
你需要维护平面上的整点，每个点初始有点权 $0$，共 $m$ 次操作。

修改操作：给定 $x,y,d,w$，将满足 $|X-x|<d,|Y-y|<d$ 的整点 $(X,Y)$ 的点权增加 $w\cdot(d-\max(|X-x|,|Y-y|))$；

查询操作：给定 $x_1,x_2,y_1,y_2$，查询满足 $x_1\le X\le x_2,\;y_1\le Y\le y_2$ 的整点 $(X,Y)$ 的点权之和，答案对 $2^{30}$ 取模。

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

第一行一个整数 $m$，接下来 $m$ 行，每行表示一个操作。

修改操作表示为 `1 x y d w`；

查询操作表示为 `2 x1 x2 y1 y2`。

outputFormat:
输出到标准输出。

对每个查询操作，输出一行，包含一个整数，表示取模后的答案。

hint:
对于 $23\%$ 的数据，满足 $1\le m\le 10^3$。

对于 $31\%$ 的数据，满足 $1\le m\le 2\times 10^4$。

对于 $39\%$ 的数据，满足 $1\le m\le 4\times 10^4$。

对于 $47\%$ 的数据，满足 $1\le m\le 6\times 10^4$。

对于 $55\%$ 的数据，满足 $1\le m\le 8\times 10^4$。

对于另外 $15\%$ 的数据，满足对任意询问操作，不存在一个修改操作，该修改操作在该询问操作之后。

对于另外 $10\%$ 的数据，满足 $x_2-x_1\le 5$，$y_2-y_1\le 5$，$d\le 5$。

对于另外 $10\%$ 的数据，满足 $d\le 5$。

对于 $100\%$ 的数据，满足 $1\le m\le 10^5$，$1\le x_1\le x_2\le {10}^8$，$1\le y_1\le y_2\le {10}^8$，$1\le x,y,d,w\le {10}^8$。

每类数据构成子任务。


title: [CTS2022] 燃烧的呐球

background: **警告：滥用本题卡评测者将被封号。**

description:
已知 $n$ 个顶点的有根树，以及 $m$ 个二元组 $(x_i,y_i)$，其中 $x_i,y_i$ 是树的顶点。

对于树的顶点 $a,b$，定义 $D(a,b)$ 为：在以 $a$ 为根的子树中，但不在以 $b$ 为根的子树中的顶点个数。

你需要求出以这些二元组为顶点的完全图的最小生成树，其中 $(x_i,y_i)$ 和 $(x_j,y_j)$ 之间的边权是 $D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i)$。

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

之后一行 $n-1$ 个数，其中第 $i$ 个数表示编号为 $i+1$ 的节点的父亲 $f_{i+1}$，保证 $f_{i+1}< i+1$。

之后 $m$ 行，第 $i$ 行两个数 $x_i,y_i$，表示一个给定的二元组。

outputFormat: 输出一个整数，表示最小生成树的边权和。

hint:
样例解释：

最小生成树包含边 $(1,4,1),(2,3,3),(2,4,3)$，三元组表示第一个二元组的编号，第二个二元组的编号，边权。边权和为 $7$。

数据范围：

对于 $10\%$ 的数据，满足 $1\le n,m\le 1000$。

对于另外 $10\%$ 的数据，满足 $1\le m\le 2\times 10^4$。

对于另外 $10\%$ 的数据，满足 $1\le m\le 5\times 10^4$。

对于另外 $20\%$ 的数据，满足 $m=n^2$，且每个二元组互不相同。

对于另外 $10\%$ 的数据，满足对任意 $i=2\cdots n$，$f_i=i-1$。

对于另外 $10\%$ 的数据，满足对任意 $i=2\cdots n$，$f_i=1$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^6,1\le m\le 10^5$。对任意 $i=1,2,\dots n-1$，满足 $1\le f_{i+1}<i+1$。对任意 $i=1,2,\dots m$，满足 $1\le x_i,y_i\le n$。


title: [CTS2022] 袜子

description: 给定 $n$ 个点 $(x_i,y_i,c_i)$，$i=1,2,\dots,n$，共有 $m$ 次查询操作，每次查询给定 $A,B,C$，问满足 $Ax_i+By_i+C<0$，$Ax_j+By_j+C<0$，$c_i=c_j$ 的二元组 $(i,j)$ 的个数。

inputFormat:
第一行两个整数 $n\ m$；

接下来 $n$ 行，每行三个整数 $x_i\ y_i\ c_i$，$i=1,2,\dots,n$；

接下来 $m$ 行，每行三个整数 $A\ B\ C$。

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

hint:
样例解释：

第一个查询对应 $(2,2)(3,3)$；

第二个查询对应 $(1,1)(2,2)(2,4)(3,3)(3,5)(4,2)(4,4)(5,3)(5,5)$。

数据范围：

对 $5\%$ 的数据，$n,m\le 10^3$；

对另外 $10\%$ 的数据，$c_i\le 2$；

对另外 $15\%$ 的数据，$c_i\le 100$；

对另外 $15\%$ 的数据，$\max(|x_i|,|y_i|)=10^6$；

对另外 $15\%$ 的数据，$|A|=|B|=1$；

对另外 $10\%$ 的数据，$n\le 20000,\;m\le 200000$；

对于其余数据，无特殊约束。

每部分数据构成子任务，无依赖关系。

所有数据满足：

$1\le n\le 50000$；

$1\le m\le 500000$；

$A^2+B^2>0$；

$-10^9\le x_i,y_i,A,B,C\le 10^9$；

$1\le c_i\le n$；

所有数值为整数；

当 $i\ne j$ 时，$x_i\ne x_j$ 或 $y_i\ne y_j$。

对于除了子任务 4 以外的数据，满足 $n$ 个点的 $x,y$ 坐标分别在某个预设的区间内均匀随机选取，并保证没有重复的点，且对于第 $i$ 个点，$c_i$ 和 $x_i,y_i$ 是分别独立地随机选取的，但 $c_i$ 的分布没有特殊限制。


title: [CTS2022] WBTT

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

#### 本地测试需 #include <long.h>
#### 提交时请采用以下模板，而不 include long.h，具体方法就是直接把这个模板放在自己代码里面，然后需要完善题目中要求的函数。

```cpp
struct sethash{
	int val;
	void encode();
	void decode();
	void operator=(int x);
};
struct infoset{
	sethash sum;
	int sz;
	int size()const{
		return sz;
	}
};
extern const infoset emptyset;
infoset merge(const infoset&a,const infoset&b);
void report(infoset p);
void init(int id,int n,int q,vector<int>dad,vector<infoset>ve);
void modify(int x,int y);
void ask(int x,int y);
```
***

伟大的科学家欣准备建造强人工智能隆统治世界。在输入一些越南的算法竞赛题作为训练集后，她发现隆自动生成了一个新的问题，并给出了一份解答。同时隆还将测试集中30%的输入数据归约到了这个问题。
欣连忙将这个问题抄录如下：
给定一棵有根树，你需要支持两种操作

* 查询树链元素和
* 将一个点的父亲改成另一个点

“这个问题并不强啊，为什么能解决测试集中30%的问题呢？”欣心里想。
在关闭训练结果页面前，欣突然发现，隆给出的这个问题中，信息合并的代价并不是 $O(1)$ 的。
欣陷入了沉思，发现自己并不会这道题。
为了知道这题有多难，欣将这题放到了您的面前。

description:
你需要维护一棵以 $1$ 为根的有根树。这棵树有 $n$ 个点。初始时对于所有 $2 \le i \le n$，点 $i$ 有个父亲 $p_i$，保证 $p_i \lt i$。

一开始你有 $n$ 个集合 $\{1\},\{2\},\cdots,\{n\}  $。对于任意两个集合 $A$ 和 $B$，如果 $A \cap B=\empty$，那么你可以通过一次操作，消耗 $|A|+|B|$ 的代价，获得集合 $A \cup B$。

之后有 $q$ 次操作。每次操作有两种类型

* `0 a b` 记树上 $a$ 到 $b$ 之间的路径上的点构成的点集为 $S$。你需要将 $S$ 表示为 $\cup_{i=1}^{k}A_i$，需要满足 $A_i$ 是你已经获得的集合，且 $\forall i \neq j,A_i \cap A_j=\empty$。用 $(A_1,A_2,\cdots,A_k) $ 回答一次询问的代价为 $k$。
* `1 a b` 表示将点 $a$ 的父亲改为 $b$，保证 $a \gt 1$，且修改后这 $n$ 个点仍构成一棵树，但**不保证 $a \gt b$ ** 。你可以在这次操作中新生成一些集合用以应对之后的询问。

记你整个程序运行过程中消耗的总代价为 $C_1$，单次操作消耗代价最大值为 $C_2$。每个子任务会根据 $C_1,C_2$ 的大小按照一定方式给分。

inputFormat:
### 实现细节

头文件中定义了数据类型 `infoset`，用于存储你获得的集合。

该类型包括成员函数 `size()`，表示集合大小。**头文件还为你提供了表示空集的常量 `emptyset`**。

此外你还可以调用如下函数：

`infoset merge(const infoset&A,const infoset&B);`

* 以一定代价生成一个新集合 $A \cup B$
* 注意你可以多次重复生成同一个集合，并且需要多次计入代价

`void report(infoset A);`

* 你仅可以在查询操作过程中调用该函数，表示你需要消耗 $1$ 的代价在最终的并中添加一个集合 $A$

你不需要，也不应该实现主函数。你需要实现如下几个函数：

`void init(int id,int n,int q,vector<int>dad,vector<infoset>ve);`

* 你可以在 $q$ 次操作开始前预处理一些信息
* 在该函数中消耗的代价不会计入**单次操作消耗代价最大值**，但会计入**整个程序运行过程中消耗的总代价**
* `id` 表示子任务编号，`n` 表示总点数，`q`表示总操作数
* `dad` 的大小为  $n-1$，`dad[i]` 表示初始时刻点 $i+2$ 的父亲
* `ve` 的大小为 $n$，`ve[i]` 表示初始集合 $\{i+1\}$

`void modify(int x,int y);`

* 执行一次修改操作，将点 $x$ 的父亲置为点 $y$

`void ask(int x,int y);`

* 执行一次查询操作，询问 $x$ 到 $y$ 的树链信息
* 你需要调用若干次 `report` 来回答询问，本次询问结束时交互库会检查你汇报的所有集合 $A$ 是否满足条件

评测时，交互库会先调用 `init` 一次，然后调用 `modify` 和 `ask` 总共 $q$ 次。

本题保证树的形态与执行的操作在交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。

评测时交互库会使用特殊的实现方式，单个 `infoset` 类型的变量会恒定消耗 $8$ 字节内存，请保证你的程序运行过程中没有过多的 `infoset` 类型变量同时存在。

保证在调用次数限制下，交互库运行所需的时间不超过 2s；交互库本身所消耗的内存不超过16MB。

outputFormat:
### 测试程序方式

下发文件中的 `grader.cpp` 是我们提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

你需要使用如下命令编译得到可执行程序：
`g++ grader.cpp long.cpp -o long -static -O2 -std=c++14`

对于编译得到的可执行程序：

- 可执行文件将从标准输入读入以下格式的数据：
  - 第一行包含一个整数 $id$ ，表示子任务编号
  - 第二行包含两个整数 $n,q$，表示总点数和总操作数
  - 第三行包含 $n-1$ 个整数，分别表示第 $2$ 至$n$ 个点的父亲节点编号
  - 接下来 $q$ 行，每行三个整数 $op,x,y$，描述一次操作。$op=0$ 表示这是一次询问操作，$op=1$ 表示这是一次修改操作
- 读入完成之后，交互库将调用恰好一次函数 `init` 和 $q$ 次 `modify` 或 `ask` ，用输入的数据测试你的函数。程序正常运行后会输出若干行，每行若干个数表示你对每次询问操作给出的回答；最后一行会包括两个整数 $W_1,W_2$，分别表示你程序运行消耗的总代价和单次操作消耗代价的最大值。

**下发文件中包括四组样例文件，其中第四组样例满足子任务二的特殊性质**。测试样例时请忽略输出文件最后一行的比较情况，因为交互库输出的最后一行为程序运行代价而不是询问操作的查询结果。

hint:
### 评分方式

**本题首先会受到和传统题相同的限制**。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

在上述条件基础上，在一个测试点中，若程序执行了非法的函数调用、没有正常结束运行或询问操作给出了错误回答，该测试点将会获得 $0$ 分。否则，将根据你程序消耗的代价，有两种评分方式：

* 评测方式一：若 $W_1 \gt 6 \cdot 10^8$，则该测试点得 $0$ 分；否则该测试点得分为 $\frac{\frac{1.5 \cdot 10^8}{max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10} \times 该测试点所属子任务分值 $
* 评测方式二：若 $W_2 \gt 2 \cdot 10^4$，则该测试点得 $0$ 分；否则该测试点得分为 $\frac{5000}{max(W_2,5000)} \times 该测试点所属子任务分值$

不同的子任务会使用不同的评测方式。一个子任务的得分为其中所有测试点得分的最小值。

### 限制与约定

保证对于所有测试点均有 $1 \le n,q \le 10^5$。

| 子任务编号 | $n,q \le$ | 特殊性质 | 评测方式 | 分值 |
| ---------- | --------- | -------- | -------- | ---- |
| $1$        | $100$     | 无       | 一       | $10$ |
| $2$        | $10^5$    | 有       | 一       | $20$ |
| $3$        | $10^5$    | 有       | 二       | $20$ |
| $4$        | $10^5$    | 无       | 一       | $30$ |
| $5$        | $10^5$    | 无       | 二       | $20$ |

特殊性质：保证每个时刻除了 $1$ 号节点外每个节点至多只有一个儿子。

### 后记

欣发现您五个小时还是没有做出本题，对隆的能力感到非常满意。然而第二天早上起来后，欣突然发现隆做法的复杂度证明是错的。


title: [Ynoi Easy Round 2020] TEST_100

description: 给定一个长为 $n$ 的序列 $a$，每个位置是一个线性变换 $x=|x-a_i|$，每次查询给出一个区间 $[l,r]$ 和一个值 $v$，依次令 $i$ 从 $l$ 到 $r$ ，访问每个元素 $a_i$，将 $v$ 变为 $|v-a_i|$，求结束后的 $v$ 的值。

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

第二行 $n$ 个用空格隔开的数表示序列 $a$。

之后 $m$ 行，每行三个用空格隔开的数 $l,r,v$ 表示一次询问。

本题强制在线，所有输入的 $l,r,v$ 均需要异或上次询问的答案，若之前没有询问操作，则为 $0$。

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

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

样例解释：

第一次询问中，$3$ 依次经过值为 $2,5,3$ 的变化，变为 $1,4,1$，答案为 $1$。

经过解密，第二次询问为区间 $[2,2]$，值为 $1$。

第二次询问中，$1$ 依次经过值为 $5$ 的变化，变为 $4$，答案为 $4$。

经过解密，第三次询问为区间 $[1,4]$，值为 $2$。

第三次询问中，$2$ 依次经过值为 $4,5,2,5$ 的变化，变为 $2,3,1,4$，答案为 $4$。

经过解密，第四次询问为区间 $[1,4]$，值为 $1$。

第四次询问中，$1$ 依次经过值为 $4,5,2,5$ 的变化，变为 $3,2,0,5$，答案为 $5$。

经过解密，第五次询问为区间 $[3,5]$，值为 $1$。

第五次询问中，$1$ 依次经过值为 $2,5,3$ 的变化，变为 $1,4,1$，答案为 $1$。

数据范围：

对于 $100\%$ 的数据 $1\le n,m,a_i,v \le10^5$，$1\le l,r\le n$。


title: 「MCOI-08 / AC6-M12」Weapons of Mass Destruction

background:
Garuda Team, I've got some good news.

The chemical agent used as a catalyst for their WMD is being transported to our shores from the Estovakian mainland.

This catalyst has already been carried into the outskirts of Gracemeria.

As a measure of caution against any attempts to destroy it, it has been concealed at Fort Norton in Gracemeria's north.

If we start advancing again, the enemy will most likely bring the catalyst into Gracemeria at a faster pace.

If in fact weapons of mass destruction are used on the population of Gracemeria, the resulting devastation can't be expressed in enough words.

It will lead to unspeakable tragedies.

We've used this intelligence to come up with a solid proposal on how to prevent this scorched earth policy from being executed in our capital.

Just a minute ago, we received a letter of approval for our prevention plan from the Joint Chiefs of Staff.

The proposal we put on the table for our scorched earth prevention policy is really quite simple.

While the enemy transport unit is stationed at Fort Norton, **we'll ambush them.**

We like to call it our tactic for pre-emptive victory.

The enemy has loaded this catalyst into their transport vehicles and is able to send them into Gracemeria at any time.

This plan will be carried out by a handful of our top pilots under absolute secrecy.

**Fly through Fort Norton's canyon at an extremely low altitude to avoid radar detection, and take out those transport vehicles.**

We've determined that a high-risk mission of this magnitude could not be executed by anyone other than Garuda Team.

We're counting on a flawless execution here.

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 12} \\\Large\text{Weapons of Mass Destruction}\\\tiny -\textit{ Boiling Point }-$$

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

description:
为了摧毁敌方装载有 WMD 催化剂的车队，你需要在超低空穿过 Fort Norton 的峡谷以接近他们。

Fort Norton 抽象为**平面上两个关于 $y$（$y\in[0,10^7]$）的线性分段函数** $A(y):y\mapsto x$ 以及 $B(y):y\mapsto x$，其中对于任意实数 $y\in [0,10^7]$，**满足 $A(y) \le B(y)$**。

你和你的 F-15E 抽象为一质点，**初始位置是 $(X_1,0)$**，保证 $A(0)\leq X_1\leq B(0)$；**同时具有初速度 $(v_0,\theta_0)$，表示初速的大小和方向**。

为了避免敌方发现，你不能大功率开动发动机。你的动力刚好足够在保持平飞的时候保持匀速。

当然你可以转向。由于你是 Ace Combat 的主角，你的转向全部用 PSM 完成。具体来说，你的飞行轨迹应为一条由若干线段组成的折线。但是在转向中会受到阻力。**如果方向改变后的角与改变前的角的差的绝对值为 $\alpha$，则速度大小会减小 $\alpha$**。如果你不改变方向，那么你会一直做匀速直线运动。

由于 Ghost Eye 很着急完成任务，所以**你的 $y$ 坐标必须随时间递增**。

同时，你需要保证在任意时刻，你所在的位置 $(x,y)$ 满足 $A(y)\le x\le B(y)$。

PSM 转向的过载很大，因此你需要保证**转向次数不超过 $\bf 3\times 10^6$**。~~否则你就会像 Prez 一样 g-LOC 并一头栽在仪表盘上。~~

求任何一个转向方案，使得你运动到 $(X_2,10^7)$ 上（**即，速度不能在运动过程中变为 $\bf0$ 或负数**），同时转向次数不超过 $3\times 10^6$。类似的，保证 $A(10^7)\leq X_2\leq B(10^7)$。

inputFormat:
第一行四个整数 $n,m,X_1,X_2$ 和两个实数 $v_0,\theta_0$。

**保证 $v_0\pm 10^{-6}$ 范围内解存在性不变。**

接下来 $n$ 行，每行两个整数 $x,y$，保证 $y$ 递增，第一个 $y$ 是 $0$，最后一个 $y$ 是 $10^7$。把这些点依次用线段连接起来即得到函数 $A$。

接下来 $m$ 行，每行两个整数 $p,q$ 表示函数 $B$，与 $A$ 的输入方式同理。

outputFormat:
先输出一行 `1`。

然后由于这个点的运动轨迹一定是一条折线，所以你需要在下一行输出端点数 $K$；接下来输出 $K$ 行，每行两个实数表示这个端点的坐标。假设你给出的点列是 $C:\{(s_1,t_1),(s_2,t_2),\cdots,(s_K,t_K)\}$，那么表示 $\forall i\in [1,K)$，$C_iC_{i+1}$ 之间连线，得到的折线就是你给出的运动轨迹。

你需要保证：

- $C_1$ 与 $X_1$ 重合，$C_K$ 与 $X_2$ 重合；
- **$C$ 中 $y$ 坐标单调；**
- 对于任意 $1\leq i<K$，有 $t_i<t_{i+1}$；
- 对于任意折线上的点 $(x,y)$，满足 $A(y)-10^{-6}\leq x\leq B(y)+10^{-6}$；
- 运动过程中速度大于 $0$；
- $K\leq 3\times10^6$。

如果你正确输出了一种符合上述要求的方案，即被判为 Accepted。否则判为 Wrong Answer。如果有不止一种方案，输出任意一种皆可。

**本题开启 Special Judge。**

hint:
样例解释（缩小 $10^6$ 倍）：

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

**注意质点在运动过程中可以碰到边界，也可以沿着边界运动一段。**

---

对于 $100\%$ 的数据，保证 $2\leq n,m\leq 10^6$，$0\leq x,y,p,q\leq 10^7$，$x_1\leq X_1\leq p_1$，$x_n\leq X_2\leq p_m$，$0\leq \theta_0<\pi$，$0\leq v_0\leq 10^9$。

对于 $100\%$ 的数据，实数精度不超过 $12$ 位。

对于 $100\%$ 的数据，**保 证 有 解**。

- Subtask 1（3 pts）：$n,m\leq 6$；$v_0\ge 50$。
- Subtask 2（8 pts）：$n,m\leq 6$。
- Subtask 3（17 pts）：$n,m\leq 200$。
- Subtask 4（13 pts）：$n,m\leq 1500$。
- Subtask 5（17 pts）：$n,m\leq 5000$。
- Subtask 6（19 pts）：$n,m\leq 10^5$。
- Subtask 7（23 pts）：无特殊限制。

**请注意浮点数输出效率。**

---

idea：Sol1，solution：Sol1 & w33z8kqrqk8zzzx33，code：Sol1，data：w33z8kqrqk8zzzx33


title: 『JROI-8』颅脑损伤 2.0

description:
给定 $n$ 条线段，第 $i$ 条是 $[l_i,r_i]$。将每一条线段染成红色或黑色，要求：

1. 任意两条红色线段不相交。
2. 任意一条黑色线段**至少**和一条红色线段相交。

请最小化红色线段的长度和，并输出这个长度和。

一条线段 $[l_i,r_i]$ 的长度定义为 $r_i-l_i$，两条线段 $[l_i,r_i],[l_j,r_j]$ 交**当且仅当** $l_i\le r_j$ 且 $l_j\le r_i$。

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

接下来 $n$ 行，每行两个整数，代表 $l_i,r_i$，用空格隔开。

outputFormat: 一行一个非负整数，代表红色线段的长度和的最小值。


title: 「WHOI-1」数列计数

background: > 不再拥有，数列陪伴我。

description:
这种数列满足下面这一条神奇的性质：

- $a_0=0$。
- $\forall i\in[1,n]$ 均有 $a_i=a_{i-1}+x$ 或者 $a_i=a_{i-1}+y$。
- $\forall i\in[1,n],p \nmid a_i$。

求这样的 $\{a\}_0^{n}$ 的数量。答案对 $10^9+7$ 取模。

两个数列不同，当且仅当他们有一个下标存储的元素不同。

inputFormat:
**一个输入文件包含多组数据。**

第一行一个正整数 $T$ 表示测试点数目。

接下来 $T$ 行表示测试点。对于每组测试点，一行四个正整数，表示 $n,p,x,y$。

outputFormat: $T$ 行，每行一个自然数表示该测试点的答案。

hint:
样例 #1：

这样的 $a$ 有 $[0,1,2,4],[0,2,4,5]$。

样例 #2、#3：

本来可爱的 Otm 已经写好了上万页的样例解释了，但是更可爱的 miku 把它删掉了所以 Otm 不想再写一遍了。

---

**本题采用 $\texttt{Subtask}$ 计分方式，只有通过该 $\texttt{Subtask}$ 的所有测试点才能得到该点的分数。**

| $\texttt{Subtask}$ 编号 | 特殊限制 | 分值 |
| :----------: | :----------: | :----------: |
| 1 | $\sum n\leq20$ | 10 |
| 2 | $p\leq10^3$ | 30 |
| 3 | $xy,p$ 互质 | 10 |
| 4 | 无 | 50 |

对于所有测试数据，$1\leq T\leq10^3,1\leq\sum n\leq10^4, 1\leq x,y,p\leq10^9$，输入均为正整数。


title: [USACO22OPEN] Photoshoot B

description:
迫切希望在郡县集市上赢得最佳奶牛摄影师的 Farmer John 正在尝试为他的 $N$ 头奶牛拍摄一张完美的照片（$2 \leq N \leq 2\cdot 10^5$，$N$ 为偶数）。

Farmer John 拥有两种品种的奶牛：更赛牛（Guernsey）和荷斯坦牛（Holstein）。为了使他的照片尽可能地艺术，他想把他的奶牛排成一排，使得尽可能多的更赛牛处于队列中的偶数位置（队列中的第一个位置是奇数位置，下一个是偶数位置，以此类推）。由于他与他的奶牛缺乏有效的沟通，他可以达到目的的唯一方法是让他的奶牛的偶数长的「前缀」进行反转（一个前缀指的是对于某个位置 $j$，从第一头奶牛到第 $j$ 头奶牛范围内的所有奶牛）。

请计算 Farmer John 达到目的所需要的最小反转次数。

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

第二行包含一个长为 $N$ 的字符串，给出初始时所有奶牛从左到右的排列方式。每个 'H' 代表一头荷斯坦牛，每个 'G' 代表一头更赛牛。

outputFormat: 输出一行，包含达到目的所需要的最小反转次数。

hint:
【样例解释】

在这个例子中，只需反转由前六头奶牛组成的前缀即可。
```
   GGGHGHHGHHHGHG （反转前）
-> HGHGGGHGHHHGHG （反转后）
```
在反转之前，四头更赛牛处于偶数位置。反转后，六头更赛牛处于偶数位置。不可能使得超过六头更赛牛处于偶数位置。

【测试点性质】

- 测试点 2-6 满足 $N\le 1000$。
- 测试点 7-11 没有额外限制。


title: [USACO22OPEN] Counting Liars B

description:
奶牛 Bessie 躲在数轴上的某处。Farmer John 的 $N$ 头奶牛（$1\le N\le 1000$）中的每头奶牛都有一条信息要分享：第 $i$ 头奶牛说 Bessie 躲在小于或等于 $p_i$ 的某个位置，或者说 Bessie 躲在大于或等于 $p_i$ 的某个位置（$0\le p_i\le 10^9$）。

不幸的是，可能不存在躲藏位置与所有奶牛的回答均一致，这意味着并非所有奶牛都在说真话。计算在撒谎的奶牛的最小数量。

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

以下 $N$ 行每行包含字符 L 或 G，之后是一个整数 $p_i$。L 表示第 $i$ 头奶牛说 Bessie 的躲藏位置小于或等于 $p_i$，而 G 表示第 $i$ 头奶牛说 Bessie 的躲藏位置大于或等于 $p_i$。

outputFormat: 输出在撒谎的奶牛的最小数量。

hint:
【样例解释 1】

有可能没有奶牛在撒谎。

【样例解释 2】

至少一头奶牛在撒谎。


title: [USACO22OPEN] Alchemy B

description:
总是热衷于培养新的爱好的奶牛 Bessie 正在学习如何转化金属。对于 $1 \le i \le N \le 100$，她有 $a_i$（$0 \le a_i \le 10^4$）单位的金属 $i$。此外，她知道 $K$（$1\le K< N$）个配方，她可以融合若干种金属各一单位，制造一单位编号大于所有被融合金属的金属。另外保证，对于每种金属，Bessie 最多知道一种制造该金属的配方。

计算经过一系列转化后，Bessie 可能拥有的金属 $N$ 的最大单位数。

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

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

第三行包含 $K$。

以下 $K$ 行每行包含两个整数 $L$ 和 $M$（$M\ge 1$），随后是 $M$ 个整数。后 $M$ 个整数表示配方中用于制造一单位金属 $L$ 所需要被融合的金属。输入保证 $L$ 大于这 $M$ 个数。

outputFormat: 输出在应用一系列零次或多次转化后，Bessie 可能拥有的金属 $N$ 的最大单位数。

hint:
【样例解释】

在这个例子中，以下是一种最优的转化方式：

- 将一单位金属 1 转化为金属 2。
- 将一单位金属 2 转化为金属 3。
- 将一单位金属 3 和金属 4 转化为金属 5。

现在 Bessie 还有一单位金属 1 和一单位金属 5。她无法再制造更多的金属 5。

【测试点性质】

- 测试点 2 中，对于 $1\le i< N$，一单位金属 $i$ 可以被转化为一单位金属 $i+1$；

- 测试点 3-4 中，每个配方均将一单位的一种金属转化为另一种金属；

- 测试点 5-11 没有额外限制。


title: [USACO22OPEN] Visits S

description:
Bessie 的 $N$（$2\le N\le 10^5$）个奶牛伙伴（编号为 $1\cdots N$）每一个都拥有自己的农场。对于每个 $1\le i\le N$，伙伴 i 想要访问伙伴 $a_i$（$a_i\neq i$）。

给定 $1\ldots N$ 的一个排列 $(p_1,p_2,\ldots, p_N)$，访问按以下方式发生。

对于 $1$ 到 $N$ 的每一个 $i$：

- 如果伙伴 $a_{p_i}$ 已经离开了她的农场，则伙伴 $p_i$ 仍然留在她的农场。
- 否则，伙伴 $p_i$ 离开她的农场去访问伙伴 $a_{p_i}$ 的农场。这次访问会产生快乐的哞叫 $v_{p_i}$ 次（$0\le v_{p_i}\le 10^9$）。

对于所有可能的排列 $p$，计算所有访问结束后可能得到的最大哞叫次数。

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

对于每一个 $1\le i\le N$，第 $i+1$ 行包含两个空格分隔的整数 $a_i$ 和 $v_i$。

outputFormat:
输出一个整数，为所求的答案。

**注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。**

hint:
【样例解释】

如果 $p=(1,4,3,2)$，则

- 伙伴 $1$ 访问伙伴 $2$ 的农场，产生 $10$ 次哞叫。
- 伙伴 $4$ 看到伙伴 $1$ 已经离开了农场，所以无事发生。
- 伙伴 $3$ 访问伙伴 $4$ 的农场，又产生 $30$ 次哞叫。
- 伙伴 $2$ 看到伙伴 $3$ 已经离开了农场，所以无事发生。

这样总计得到了 $10+30=40$ 次哞叫。

另一方面，如果 $p=(2,3,4,1)$，则

- 伙伴 $2$ 访问伙伴 $3$ 的农场，产生 $20$ 次哞叫。
- 伙伴 $3$ 访问伙伴 $4$ 的农场，产生 $30$ 次哞叫。
- 伙伴 $4$ 访问伙伴 $1$ 的农场，产生 $40$ 次哞叫。
- 伙伴 $1$ 看到伙伴 $2$ 已经离开了农场，所以无事发生。

这样总计得到了 $20+30+40=90$ 次哞叫。可以证明这是所有可能的排列 $p$ 中访问结束后得到的最大可能的哞叫次数。


title: [USACO22OPEN] Subset Equality S

description:
奶牛们正在尝试一种相互交换编码信息的新方法，她们在相关的字母中混入不相关的字母，使信息难以解码。

奶牛们传输两个字符串 $s$ 和 $t$，每个字符串的长度不超过 $10^5$，仅由小写字母 'a' 到 'r' 组成。为了尝试理解这条编码消息，你将被给定 $Q$ 个询问（$1 \leq Q \leq 10^5$）。

每个询问给定小写字母 'a' 到 'r' 的一个子集。你需要对每个询问判断 $s$ 和 $t$ 在仅包含询问中给定的字母时是否相等。

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

第二行包含 $t$。

第三行包含 $Q$。

以下 $Q$ 行每行包含一个询问字符串。在一个询问字符串中，所有字母均不相同。此外，所有询问字符串均已排序，且没有一个询问字符串出现超过一次。

outputFormat: 对每个询问，如果 $s$ 和 $t$ 在仅包含询问中给定的字母时相等则输出 'Y'，否则输出 'N'。

hint:
【样例解释】

对于第一个询问，当仅包含字符 'a' 时，两个字符串均变为 "aa"。

对于第二个询问，第一个字符串变为 "aac" 而第二个字符串变为 "caa"。

【测试点性质】

- 测试点 2 满足 $|s|,|t|,Q\le 1000$。
- 测试点 3-11 没有额外限制。


title: [USACO22OPEN] COW Operations S

description:
Bessie 找到了一个长度不超过 $2 \cdot 10^5$ 且仅包含字符 'C'，'O' 和 'W' 的字符串 $s$。她想知道是否可以使用以下操作将该字符串变为单个字母 'C'（她最喜欢的字母）：

1. 选择两个相邻相等的字母并将其删除。

2. 选择一个字母，将其替换为另外两个字母的任一排列。

求出这个字符串本身的答案对 Bessie 而言并不足够，所以她想要知道 $s$ 的 $Q$（$1\le Q\le 2\cdot 10^5$）个子串的答案。

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

第二行包含 $Q$。

以下 $Q$ 行每行包含两个整数 $l$ 和 $r$（$1\le l\le r\le |s|$，其中 $|s|$ 表示 $s$ 的长度）。

outputFormat: 输出一个长为 $Q$ 的字符串，如果第 $i$ 个子串可以被转变则第 $i$ 个字符为 'Y'，否则为 'N'。

hint:
【样例解释】

第一个询问的答案是「是」，因为 s 的第一个字符已经等于 'C'。

第五个询问的答案是「是」，因为 s 的第二到第三个字符组成的子串 OW 可以通过两步操作变为 'C'：

```
   OW
-> CWW
-> C
```

这个样例字符串 COW 的其他子串均不能被转变为 'C'。

【测试点性质】

- 测试点 2-4 满足 $|s|\le 5000$ 以及 $Q\le 5000$。
- 测试点 5-11 没有额外限制。


title: [USACO22OPEN] Apple Catching G

description:
天上下苹果了！在某些时刻，一定数量的苹果会落到数轴上。在某些时刻，Farmer John 的一些奶牛将到达数轴并开始接苹果。

如果一个苹果在没有奶牛接住的情况下落到数轴上，它就会永远消失。如果一头奶牛和一个苹果同时到达，奶牛就会接住苹果。每头奶牛每秒可以移动一单位距离。一旦一头奶牛接住了一个苹果，她就会离开数轴。

如果 FJ 的奶牛以最优方式合作，她们总共能接住多少个苹果？

inputFormat:
输入的第一行包含 $N$（$1\le N\le 2\cdot 10^5$），为苹果落到数轴上的次数或 FJ 的奶牛出现的次数。

以下 $N$ 行每行包含四个整数 $q_i$，$t_i$，$x_i$ 和 $n_i$（$q_i\in \{1,2\}, 0\le t_i\le 10^9, 0\le x_i\le 10^9, 1\le n_i\le 10^3$）。

- 如果 $q_i=1$，意味着 FJ 的 $n_i$ 头奶牛在 $t_i$ 时刻来到数轴上的 $x_i$ 位置。
- 如果 $q_i=2$，意味着 $n_i$ 个苹果在 $t_i$ 时刻落到了数轴上的 $x_i$ 位置。

输入保证所有有序对 $(t_i,x_i)$ 各不相同。

outputFormat: 输出 FJ 的奶牛总计能接住的苹果的最大数量。

hint:
【样例解释 1】

在这个例子中，在 $t=5$ 时刻落地的 $100$ 个苹果均不能被接住。以下是一种接住 $10$ 个苹果的方式：

- FJ 的所有六头 $t=4$ 时刻到达的奶牛各接一个 $t=8$ 时刻落地的苹果。
- FJ 的一头 $t=2$ 时刻到达的奶牛接一个 $t=8$ 时刻落地的苹果。
- 余下三头 $t=2$ 时刻到达的奶牛各接一个 $t=6$ 时刻落地的苹果。

【样例解释 2】

再一次地，在 $t=5$ 时刻落地的苹果均不能被接住。除此之外，在 $t=2$ 时刻到达的奶牛均不能接住 $t=8$ 时刻落地的苹果。以下是一种接住 $9$ 个苹果的方式：

- FJ 的所有六头 $t=4$ 时刻到达的奶牛各接一个 $t=8$ 时刻落地的苹果。
- 余下三头 $t=2$ 时刻到达的奶牛各接一个 $t=6$ 时刻落地的苹果。


title: [USACO22OPEN] Pair Programming G

background: 由于题目数据问题，在本题中，你**无需考虑**非平凡的（都有 0 或者只差若干个 1 或者仅顺序不同时称为平凡的）、两组不同的数乘积一样的情况，例如 $t\times2\times3=t\times6$；或者，你应当把题面中的 $\times 2,3,4,5,6,7,8,9$ 分别视为 $\times 2,3,5,7,11,13,17,19$ 处理。

description:
一个程序由一系列指令组成，每条指令都具有以下形式之一：

- $\times d$，其中 $d$ 是一个 $[0,9]$ 范围内的一位数；
- $+s$，其中 $s$ 是一个表示变量名称的字符串。一个程序中出现的所有的变量名均不相同。

程序执行的结果定义对表达式 $0$ 依次应用每条指令后得到的表达式。例如，执行程序 $[\times 3,+x,+y,\times 2,+z]$ 得到的结果是表达式 $(0\times 3+x+y)\times 2+z=2 \times x+2\times y+z$。不同的程序执行后可能会得到相同的表达式；例如，执行 $[+w,\times 0,+y,+x,\times 2,+z,\times 1]$ 也会得到表达式 $2\times x+2\times y+z$。

Bessie 和 Elsie 各有一个 $N$（$1\le N\le 2000$）条指令的程序。他们将交错这些程序的指令以制造一个 $2N$ 条指令的新程序。注意有 $\frac{(2N)!}{N!\times N!}$ 种方法可以做到这一点，但并非所有这样的程序在执行后都会得到不同的表达式。

计算执行 Bessie 和 Elsie 的交错程序可能得到的不同表达式的数量，对 $10^9+7$ 取模。

每个测试用例包含 $T$（$1\le T\le 10$）个需要独立求解的子测试用例。输入保证所有子测试用例中的 $N$ 之和不超过 $2000$。

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

每个子测试用例的第一行包含 $N$。

每个子测试用例的第二行包含 Bessie 的程序，用一个长为 $N$ 的字符串表示。每个字符是一个一位数 $d\in [0,9]$，表示类型 1 的一条指令，或字符 $+$，表示类型 2 的一条指令。

每个子测试用例的第三行包含 Elsie 的程序，格式与 Bessie 的程序相同。

在一个子测试用例中，所有指令内的变量名均不相同。注意在这里没有给出它们的实际名称，这是由于它们并不会影响答案。

outputFormat: 输出通过执行 Bessie 和 Elsie 的交错程序可能得到的不同表达式的数量，对 $10^9+7$ 取模。

hint:
【样例解释】

对于第一个子测试用例，两个可以制造的交错程序为 $[\times 1, \times 0]$ 和 $[\times 0,\times 1]$。它们执行后均会得到表达式 $0$。

对于第二个子测试用例，执行 $[\times 1,\times 2, +x]$ 和 $[+y, \times 0,\times 2]$ 的交错程序可以得到表达式 $0$，$x$ 和 $2\times x$ 之一。

【测试点性质】

- 测试点 2 满足 $N\le 6$。
- 测试点 3-5 中，所有 $N$ 之和不超过 $100$。
- 测试点 6-8 中，所有 $N$ 之和不超过 $500$。
- 测试点 9-16 没有额外限制。


title: [USACO22OPEN] Balancing a Tree G

background: 感谢 @tiger2005 配置 SPJ。

description:
Farmer John 对不同奶牛品种的进化进行了广泛的研究。所得到的结果形成一棵 $N$（$2\le N\le 10^5$）个结点的有根树，编号为 $1\ldots N$，每个结点对应一个奶牛品种。对于每一个 $i\in [2,N]$，结点 $i$ 的父结点是结点 $p_i$（$1\le p_i< i$），意味着品种 $i$ 是由品种 $p_i$ 进化而来的。称结点 $j$ 为结点 $i$ 的祖先，如果 $j=p_i$ 或者 $j$ 是 $p_i$ 的祖先。

树中的结点 $i$ 所关联的品种具有整数 $s_i$ 数量的斑点。定义树的「不平衡度」为所有结点对 $(i,j)$ 中 $|s_i-s_j|$ 的最大值，其中 $j$ 是 $i$ 的祖先。

Farmer John 不知道每个品种的 $s_i$ 的确切数值，但他知道这些值的下界和上界。你的任务是为每个结点分配一个整数值 $s_i \in [l_i,r_i]$（$0\le l_i\le r_i\le 10^9$），以最小化树的不平衡度。

inputFormat:
输入的第一行包含 $T$（$1\le T\le 10$），为需要独立求解的子测试用例的数量，以及一个整数 $B\in \{0,1\}$。

每个子测试用例的第一行包含 $N$，第二行包含 $N-1$ 个整数 $p_2,p_3,\ldots,p_N$。

以下 $N$ 行每行包含两个整数 $l_i$ 和 $r_i$。

输入保证所有子测试用例的 $N$ 之和不超过 $10^5$。

outputFormat:
对每个子测试用例，根据 $B$ 的值输出一行或两行。

每个子测试用例的第一行包含最小不平衡度。

如果 $B=1$，则再输出一行，包含 $N$ 个空格分隔的整数 $s_1,s_2,\ldots, s_N$，为达到以上不平衡度的一种斑点数量的分配方式。任何合法的分配方式均正确。

hint:
【样例解释 1】

对于第一个子测试用例，最小不平衡度为 $3$。一种达到不平衡度 $3$ 的方式是令 $[s_1,s_2,s_3]=[4,1,7]$。

【样例解释 2】

这个测试用例除了 $B$ 的值之外与第一个测试用例完全相同。另一种达到不平衡度 $3$ 的方式是令 $[s_1,s_2,s_3]=[3,1,6]$。

【数据范围】

- 测试点 3-4 对于所有的 $i$ 满足 $l_i=r_i$。
- 测试点 5-6 对于所有的 $i$ 满足 $p_i=i-1$。
- 测试点 7-16 没有额外限制。

在每一部分子任务中，前一半的测试点满足 $B=0$，后一半测试点满足 $B=1$。


title: [USACO22OPEN] 262144 Revisited P

description:
Bessie 喜欢在她的手机上下载游戏玩，尽管她确实发现对于她的大蹄子来说使用小触摸屏相当麻烦。

她对目前正在玩的游戏特别着迷。游戏从 $N$ 个 $1\ldots 10^6$ 范围内的正整数组成的序列 $a_1,a_2,\ldots,a_N$（$2\le N\le 262,144$）开始。在一次行动中，Bessie 可以取两个相邻的数字并将它们替换为一个大于两数最大值的数字（例如，她可以将相邻的一对数 $(5,7)$ 替换为 $8$）。游戏在 $N-1$ 次行动后结束，此时只剩下一个数字。游戏目标是**最小化**这个最终的数字。

Bessie 知道这个游戏对你来说太容易了。所以你的任务不仅仅是在 $a$ 上以最优方式玩游戏，而是在 $a$ 的每个连续子段上玩游戏。

输出 $a$ 的所有 $\frac{N(N+1)}{2}$ 个连续子段的最小最终数字之和。

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

第二行包含 $N$ 个空格分隔的整数，表示输入的序列。

outputFormat: 输出一行，包含所求的和。


title: [USACO22OPEN] Hoof and Brain P

description:
给定一个包含 $N$ 个结点和 $M$ 条边的有向图（$2 \leq N \leq 10^5$, $1 \leq M \leq 2 \cdot 10^5$），Farmer John 的奶牛们喜欢玩以下的双人游戏。

在图中的不同结点上放置两个指示物（可以用一些与奶牛相关的物品代替指示物）。每一回合，一名玩家，脑，选择一个需要沿某一条出边移动的指示物。另一名玩家，蹄，选择沿着哪条出边移动该指示物。两个指示物在任何时刻不允许处于同一个结点上。如果在某些时刻蹄不能做出合法的行动，则脑获胜。如果游戏可以无限进行下去，则蹄获胜。

给定 $Q$ 个询问（$1 \leq Q \leq 10^5$），包含两个指示物所在的初始结点。对于每个询问，输出哪名玩家获胜。

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

以下 $M$ 行每行包含两个整数 $a$ 和 $b$，表示一条从 $a$ 连向 $b$ 的边。

图中不包含自环或重边。

下一行包含 $Q$。

最后 $Q$ 行每行包含两个整数 $x$ 和 $y$，满足 $1\le x,y\le N$ 以及 $x\neq y$，表示指示物所在的初始结点。

outputFormat:
输出一个长为 $Q$ 的字符串，其中字符 B 表示脑获胜，H 表示蹄获胜。

**注意：本题的时间限制为 4 秒，通常限制的两倍。**

hint:
【数据范围】

脑可以通过选择结点 $5$ 赢得第一局游戏；此时蹄将没有合法的行动。

脑可以通过选择结点 $4$ 然后选择结点 $7$ 赢得最后一局游戏；此时蹄没有合法的行动。

蹄赢得其他局游戏。

【测试点性质】

- 测试点 2-3 满足 $N\le 100$，$M\le 200$。
- 测试点 4-9 满足 $N\le 5000$。
- 测试点 10-21 没有额外限制。


title: [USACO22OPEN] Up Down Subsequence P

description: Farmer John 的 $N$ 头奶牛（$2 \leq N \leq 3\cdot 10^5$），编号为 $1 \ldots N$，排列成 $1\ldots N$ 的一个排列 $p_1,p_2,\ldots,p_N$。另外给定一个长为 $N-1$ 的字符串，由字母 U 和 D 组成。请求出最大的 $K\le N-1$，使得存在 $p$ 的一个子序列 $a_0,a_1,\ldots,a_{K}$，满足对于所有 $1\le j\le K$，当字符串中第 $j$ 个字母是 U 时 $a_{j - 1} < a_j$，当字符串中的第 $j$ 个字母是 D 时 $a_{j - 1} > a_j$。

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

第二行包含 $p_1,p_2,\ldots,p_N$。

最后一行包含给定的字符串。

outputFormat: 输出 $K$ 的最大可能值。

hint:
【样例解释 1】

我们可以选择 $[a_0,a_1,a_2,a_3,a_4]=[p_1,p_2,p_3,p_4,p_5]$；整个排列与给定的字符串相一致。

【样例解释 2】

我们可以选择 $[a_0,a_1,a_2,a_3]=[p_1,p_3,p_4,p_5]$。

【测试点性质】

- 测试点 3-4 满足 $N\le 500$。
- 测试点 5-8 满足 $N\le 5000$。
- 测试点 9-12 中，字符串中的 U 均在 D 之前。
- 测试点 13-22 没有额外限制。


title: 「HGOI-1」Number

background: $\text{bh1234666}$ 正在学习乘法！

description:
$\text{bh1234666}$ 有一定数量的数字 $0 \sim 9$，现在他想让你寻找一种分配方案，将它们分成两个整数，使得他们的乘积 $p$ 最大。

由于 $\text{bh1234666}$ 不喜欢太大的数，所以你只需要输出**两个非负整数**，使它们的乘积**等于**最大乘积 $p$，但是这两个整数 $0 \sim 9$ 的数量不能等于给定的数量（任意一个数字数量不相等即可，**不考虑前导零**）。

$\text{bh1234666}$ 是很善良的，如果 $0 \sim 9$ 的数量等于给定的数量了，你依旧可以得到的一半的分。

inputFormat: 第一行十个整数 $c_0,c_1,\cdots c_9$，分别表示 $0 \sim 9$ 的个数。

outputFormat: 共两行每行一个非负整数，分别表示你给出的两个非负整数。

hint:
#### 样例解释
最大可能乘积为 $97643210 \times 88653221=13949030 \times 620572547=8656385075279410$。

若输出 $97643210 \times 88653221$ 则只能得到一半的分，因为 $0\sim 9$ 出现的次数与给定的相同。

#### 数据范围及约定
本题采用**捆绑测试**，共有 $5$ 个 $\text{subtask}$，最终分数为所有 $\text{subtask}$ 分数之和。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{Task} & \textbf{Score} & \sum c_i\le \cr\hline
1 & 10 & 20 \cr\hline
2 & 20 & 100 \cr\hline
3 & 20 & 5000 \cr\hline
4 & 20 & 10^6 \cr\hline
5 & 30 & 10^7 \cr\hline
\end{array}
$$

对于 $100\%$ 的数据，保证 $1 \le c_i$，$\sum c_i \le 10^7$。

#### 说明

本题有 $\text{spj}$，两数乘积正确得一半的分，数量与给出的不同且乘积正确得全部分数。故每一 $\text{subtask}$ 的得分为其中所有数据点得分的**最小值**。


title: 「HGOI-1」Mole

background: $\text{brealid}$ 觉得普通的打地鼠游戏太过于 $\text{simple}$ 了。所以，她设计了一款全新的打地鼠游戏。

description:
在长度为 $l$ 的游戏窗口上，有一个长为 $t$ 的地鼠序列 $(l \le t)$，初始序列左端与窗口左端对齐，接下来序列每秒移动一个单位长度，（即最左端的地鼠离开窗口，最右端的地鼠进入窗口），向左滚动直至玩家结束游戏或者序列最右端与窗口最右端重合（即任何时刻窗口内均应有 $l$ 只地鼠）。

游戏开始的第一秒序列不会移动，不难发现游戏最多会进行 $(t-l+1)$ 秒。

序列 $T$ 中的每一只地鼠都有自己的高度 $h_i$，玩家每次可以选择击打一只地鼠，玩家可以获得与地鼠高度 $h_i$ 数值相同的金币奖励，同时地鼠 $i$ 的高度 $h_i$ 会减一。

经过调研，$\text{brealid}$ 控制了游戏运行速度，使得玩家在地鼠序列移动一个单位长度的同时**最多只能打击一次**（也可以不打）。

现在 $\text{brealid}$ 告诉了你某一次游戏的窗口长度 $l$、序列长度 $t$ 以及某一局游戏中生成的地鼠高度序列 $T$。我们可爱的 $\text{brealid}$ 想要知道，她在**任意时刻**结束游戏所能得到的**最多金币**，即在第 $1,2,\cdots (t-l+1)$ 秒时停止游戏分别可以获得的最多金币。

inputFormat:
第一行两个整数 $l$，$t$，表示窗口长度 $l$ 和序列长度 $t$。

第二行 $t$ 个整数，表示某一局中的地鼠高度序列。

outputFormat: 一行 $t-l+1$ 个整数 $a_1,a_2,\cdots a_{t-l+1}$，$a_i$ 表示第 $i$ 秒时结束游戏可以获得的最多的金币数。

hint:
#### 样例解释

第一秒：锤 $2$，答案加 $3$。

第二秒：锤 $2$，答案加 $2$。

第三秒：随便锤一个，答案加 $1$。

第四秒：再随便锤一个（非 $0$ 的），答案加 $1$。

第五秒：锤 $9$，答案加 $5$。

第六秒：锤 $9$，答案加 $4$。

#### 数据范围

本题采用**捆绑测试**，共有 $4$ 个 $\text{subtask}$，最终分数为所有 $\text{subtask}$ 分数之和。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{Task} & \textbf{Score} & l\le t\le  \cr\hline
1 & 10 & 10 \cr\hline
2 & 20 & 500 \cr\hline
3 & 30 & 5000 \cr\hline
4 & 40 & 10^6 \cr\hline
\end{array}
$$

对于 $100\%$ 的数据，$1\le l\le t\le 10^6$，$|h_i|\le 10^9$。


title: 「HGOI-1」Water

background: $\text{uuku}$ 每天都给他的线段树浇水。但由于线段树是平面的，所以 $\text{uuku}$ 用一个二维的水桶给它浇水。

description:
水桶可以描述为一个 $h\times w$ 的竖直平面，其中 `.` 表示空格，`#` 表示挡板，保证除顶面外所有边界均有 `#`。

$\text{uuku}$ 给水桶装水的方式很奇特：他希望在装水完成的瞬间水不流动。即对于任意一格存在水的位置，其左右和下方均有水或者挡板。并且如果一格水的上方是空格，则称之为水平面，如果上方是挡板或者水桶外部，则称之为上界面。水形成的四连通块内的所有水平面都要一样高且所有上界面都应该不高于水平面（该条件即为在真空环境且存在重力时水不流动）。

从装水完成后开始计时，每秒都会进行一次扩展。每次扩展所有水平面都会向上方的空格**扩展一层**，并填充**高度小于等于新扩展层的**所有可达的空格（可以理解为仍满足 $\text{uuku}$ 的上述要求），这一切可以看作是瞬间完成的。

神奇的水会一直扩展，直到**所有可达的空格**均被水填满后停止扩展，即不存在水平面。

现在 $\text{uuku}$ 想知道，对于所有符合他要求的装水方案，所有水停止扩展所需时间的**平均值**是多少。

inputFormat:
第一行两个整数 $h$，$w$，表示水桶的高度和宽度。

接下来 $h$ 行，每行 $w$ 个字符，其中 `.` 表示空格，`#` 表示挡板。

outputFormat: 一行一个整数，表示 $\text{uuku}$ 给水桶装水需要的时间的平均值，由于答案可能很大，所以你只需要给出对 $998244353$ 取模以后的结果。


title: 「HGOI-1」Competition

background:
$\text{HGOI}$ 举办了一场模拟赛。

为了增加选手们的积极性，$\text{HGOI}$ 的出题人根据题目难度划定了一个分数线。$\text{bh1234666}$ 会给超过这个分数线的选手发奖品。

description:
众所周知，$\text{OI}$ 赛制的比赛有很大的运气成分。选手们往往不能发挥出真实水平。所以对于参赛的 $n$ 位选手，第 $i$ 位选手会有一个达到分数线的概率 $p_i$。

在模拟赛结束后就是最激动人心颁奖环节。

组委会的委员们设置了若干种类的奖品，并且每种奖品都有对应的价值。而他们对自己设置的奖品的发放有各自的要求：

- $\text{uuku}$ 喜欢成双成对，所以对于他设置的**每种**奖品必须向**偶数个获奖选手**发放。

- $\text{rechinist}$ 喜欢跟 $\text{uuku}$ 对着干，所以对于他设置的**每种**奖品必须向**奇数个获奖选手**发放。

委员 $\text{uuku}$ 设置了 $A$ 种奖品，$a_i$ 表示他设置的第 $i$ 种奖品的价值。

委员 $\text{rechinist}$ 准备了 $B$ 种奖品，$b_i$ 表示他设置的第 $i$ 种奖品的价值。

当然**每个获奖选手**都将被发给**恰好**一份奖励。

选手们不关心每种奖品被发放了几次，但是他们关心有多少种奖品被发放了，因此选手们的积极性被定义为所有被发放的奖品的价值的乘积（每种奖品只会被乘一次）。

假如获奖人数使得委员会无法发放奖品， $\text{bh1234666}$ 会十分生气，拒绝提供资金购买奖品，使得选手积极性为 $0$ 。

现在，委员会已经知道了每个选手能达到分数线的概率 $p_i$，他们想知道选手们积极性的期望值为多少。

由于答案可能很大，所以你只需要给出对 $998244353$ 取模以后的结果。

inputFormat:
第一行四个整数 $n$，$A$，$B$ 表示参赛人数和两位委员提出的金额序列的长度。

第二行 $n$ 个整数，表示 $n$ 选手达到分数线的概率 $p_i$（为了方便我们给出模 $998244353$ 意义下的概率）。

第三行 $A$ 个整数，表示 $\text{uuku}$ 提出的金额序列 $a$。

第四行 $B$ 个整数，表示 $\text{rechinist}$ 提出的金额序列 $b$。

outputFormat: 一行一个整数，表示**选手们积极性的期望值**。

hint:
#### 样例1解释

$0\sim n$ 人达到分数线的概率依次为$\dfrac{1}{16}$，$\dfrac{1}{4}$，$\dfrac{3}{8}$，$\dfrac{1}{4}$，$\dfrac{1}{16}$。

对于 $0$ 人达到分数线无发放方案。

对于 $1$ 人达到分数线无发放方案。

对于 $2$ 人达到分数线有如下 $2$ 种发放方案。

$4$，$5$ 价值为 $20$ 对期望贡献为 $20\times \dfrac{3}{8}\times \dfrac{1}{2}=\dfrac{15}{4}$。

$5$，$4$ 价值为 $20$ 对期望贡献为 $20\times \dfrac{3}{8}\times \dfrac{1}{2}=\dfrac{15}{4}$。

对于 $3$ 人达到分数线无发放方案。

对于 $4$ 人达到分数线有如下 $32$ 种发放方案。

对于发放 $4$，$5$ 两种奖品一共有 $8$ 种方式。

每种价值均为 $20$ 对期望总贡献为 $20\times 8\times \dfrac{1}{16}\times \dfrac{1}{32}=\dfrac{5}{16}$。

对于发放 $1$，$4$，$5$ 三种奖品一共有 $12$ 种方式。

每种价值均为 $20$ 对期望总贡献为 $20\times 12\times \dfrac{1}{16}\times \dfrac{1}{32}=\dfrac{15}{32}$。

对于发放 $2$，$4$，$5$ 三种奖品一共有 $12$ 种方式。

价值均为 $40$ 对期望贡献为 $40\times 12\times \dfrac{1}{16}\times \dfrac{1}{32}=\dfrac{15}{16}$。

则总期望 $E=\dfrac{15}{4}+\dfrac{15}{4}+\dfrac{5}{16}+\dfrac{15}{32}+\dfrac{15}{16}=\dfrac{295}{32}\equiv 779878410 (\bmod\ 998244353)$。

#### 数据范围

本题采用**捆绑测试**，共有 $6$ 个 $\text{subtask}$，最终分数为所有 $\text{subtask}$ 分数之和。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{Task} & \textbf{Score} & \textbf{特殊限制} \cr\hline
1 & 5 & n \le 5 \text{且} A \text{，}B \le 5 \cr\hline
2 & 10 & n \le 500 \text{且} A+B \le 500 \cr\hline
3 & 15 & n \le 2000 \text{且} A+B\le 2000  \cr\hline
4 & 20 & n\text{，}A\text{，}B \le 5000  \cr\hline
5 & 20 & n \le 2\times 10^5 \text{，} A \text{，} B \le 10^5\cr\hline
6 & 30 &  \cr\hline
\end{array}
$$

对于 $100\%$ 的数据，$1 \le A$，$B \le 2 \times 10^5$，$1 \le n \le 4 \times 10^5$，$1 \le a_i$，$b_i$，$p_i \le 998244352$。


title: 「OICon-02」Great Segments

background: upd：时间限制改为 400ms

description:
给定一个长度为 $n$ 的无重复元素序列 $a$。

对于一个区间 $[l,r]$，我们定义它是好的，有以下条件：

1. 定义一个序列 $b=\{ a_l,\max(a_l,a_{l+1}),\max(a_l,a_{l+1},a_{l+2}),\ ...\ ,\max(a_l,a_{l+1},\ ... \ ,a_r)\}$，将该序列进行去重操作后，该序列的长度不超过 $k$ 且大于 $1$；
2. $\max(a_l,a_{l+1},\ ... \ ,a_r)=a_r$。

请你解决这样一个问题：对于每一个 $i \ (1 \le i \le n)$，有多少个好的区间 $[l,r]$ 满足 $l \le i \le r$。

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

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

outputFormat: $n$ 行，每行一个整数，第 $i$ 行的数表示序列中有多少个好的区间 $[l,r]$ 满足 $l \le i \le r$。


title: [JRKSJ R6] Nothing

background: 【此处应有图】

description:
我们定义 $f(x)$ 表示 $x$ 在 $2$ 进制下最低的 $1$ 的位置（你需要注意，二进制下的最低位是第 $0 $ 位）。以下是其在 `C++` 语言中的代码（未考虑数据类型造成的问题）：

```c++
int f(int x){
	int ans = 0;
	while (x % 2 == 0){
		x /= 2;
		ans += 1;
	}
	return ans;
}
```

共有 $T$ 组询问，每组询问给定区间 $[l,r]$，求有多少个 $i\in [l,r]$ 使得 $f(i)< f(i+1)$。

inputFormat:
第一行一个正整数 $T$。\
接下来 $T$ 行每行两个正整数 $l,r$ 表示一次询问。

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


title: 「Wdoi-2」纯粹的复仇女神

background:
>「因为，人类的历史与成长，就是战争的历史与成长。没有纷争，就没有成长。满足于现状，就等于人类放弃了生存。月之民每天都为地上人考虑着。地上人的历史，就是月之民创造的。」

「我对月之民还是很了解的。这么说吧，她们在各式各样的异世界的居民中，属于最恶劣的那一类。超级排他，超级没自由，虚构的乐园，虽然擅长鄙视别人，但无法容忍自己被当成笨蛋。她们甚至认为其他世界的居民连杂菌都不如。」

「最重要的问题是，月之民敌视着幻想乡，就是这样的。」

「没想到竟然会把地上人送到月面上来，之前丝毫没有过这种想法呢。那些眼里容不下一点沙子的月之民，竟然会使用这种不入流的手段。」

「幻想乡被作为人质绑架了，可以这么认为吧？要是想拯救幻想乡的话，就不许对月之都动手，就是这种不人道的策略。」

遥遥 $38$ 万公里航程之外，于此故乡之星倒映之海，打败不共戴天之敌，击碎永久不得醒之梦。

> 不倶戴天の敵、$\stackrel{じょうが}{嫦娥}$よ。見てるか！？
> 不共戴天之敌，嫦娥啊。你在看着吗！？

description:
### 简要题意

给定一个长度为 $n$ 的序列，序列中每个元素是一个二元组 $(c_i,a_i)$，分别表示颜色与权值。

现在有 $q$ 次询问，每次给出一个区间 $[l,r]$，求：

$$\max\limits_{k=1}^n \left\{\min\limits_{l\le i \le r,c_i=k} a_i\right\}$$

特别地，如果 $[l,r]$ 内没有颜色为 $k$ 的值，后面的部分定义为 $0$。
### 原始题意
纯狐的能力是纯化，一旦灵梦身上的污秽被纯化，则必死无疑。

灵梦携带了 $n$ 张一字排开的灵符用于转嫁污秽，但纯狐依旧可以纯化附着在上面的污秽，置灵梦于死地。

具体地，每次纯狐命中一个区间 $[l_i,r_i]$ 中的所有灵符，灵梦需要在此之前净化这些灵符上面的污秽。
每张灵符有固定的颜色 $c_i$，经过激烈的战斗，每张灵符上沾染了 $a_i$ 单位的污秽。
同种颜色的灵符之间相互作用，净化区间内一批相同颜色的灵符，其灵力花费为这些灵符上污秽的最小值。
由于逸散的灵力可以为其他灵符所吸收，灵梦只需知道该区间内所有颜色的灵符净化花费的最大值，此为她净化一次的灵力花费。

给定 $\{c_i\}$ 和 $\{a_i\}$，每次给出纯狐的一种可能的攻击 $l_i,r_i$，问灵梦净化一次的灵力花费。注意只是计算，每次给出答案后并不改变 $\{c_i\}$ 和 $\{a_i\}$。

inputFormat:
第一行两个整数 $n,q$，表示序列长度与询问次数。

第二行 $n$ 个整数，依次为 $c_1,c_2,\cdots,c_n$。

第三行 $n$ 个整数，依次为 $a_1,a_2,\cdots,a_n$。

接下来 $q$ 行，每行两个整数 $l,r$，表示每次询问给出的区间。

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

hint:
### 样例 1 解释

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

如图，数字代表权值，背景色代表颜色。

- 对于区间 $[3,4]$，出现的两种颜色对应的权值最小值为 $10$ 和 $4$，取最大值答案为 $10$。
- 对于区间 $[3,9]$，出现的三种颜色对应的权值最小值为 $1,4$ 和 $4$，取最大值答案为 $4$。
- 对于区间 $[4,8]$，出现的三种颜色对应的权值最小值为 $1,4$ 和 $4$，取最大值答案为 $4$。
- 对于区间 $[3,6]$，出现的两种颜色对应的权值最小值为 $9$ 和 $4$，取最大值答案为 $9$。
- 对于区间 $[3,3]$，出现的一种颜色对应的权值最小值为 $10$。
其余同理。

### 数据范围及约定

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le } & \bm{q\le} & \textbf{特殊性质} & \textbf{Subtask 依赖} & \textbf{分值}\\\hline
1 & 100 & 100 & - & - & 10\\\hline
2 & 2 \times 10^5 & 2\times 10^5 & \textbf A & - & 20\\\hline
3 & 2 \times 10^5 & 2\times 10^5 & - & 2 & 30\\\hline
4 & 2 \times 10^5 & 10^6 & - & 1,3 & 40\\\hline
\end{array}
$$

特殊性质 $\textbf A$：所有的 $c_i \leq 10$。

对于全部数据，保证 $1 \leq n \leq 2\times10^5$，$1 \leq q \leq 10^6$，$1 \le c_i,a_i \le n$，$l \leq r$。


title: [COCI2021-2022#5] Kemija

description:
给定 $n$ 个化学方程式。

每个参与反应的分子由若干个原子组成，每个原子由一个字母和一个数字表示，分别代表元素名称和分子中该原子的数量。如果多个分子参与反应，则分子前添加一个数字表示化学计量数。本题中只需考虑每一原子的数量，而不必考虑方程式的合理性。例如，$\texttt{3AC4B}$ 可以直接视为 $3$ 个 $\texttt A$、$3$ 个 $\texttt B$ 和 $12$ 个 $\texttt C$ 参与反应。当有不同分子位于方程式同一边时，用 $\texttt +$ 连接。

你的任务是分别检查每个方程式是否已经配平（只需考虑左右原子数量是否都对应相等）。

inputFormat:
第一行一个正整数 $n$，表示方程式的个数。

接下来的 $n$ 行，每行一个方程式。数据保证每个方程式字符串长度不超过 $1000$，且每个元素都只包含一个大写字母。

outputFormat: 对于每个方程式，如果已经配平则输出 $\texttt{DA}$，否则输出 $\texttt{NE}$。

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

|序号|左侧原子|右侧原子|结果|
| :----------: | :----------: | :----------: | :----------: |
|$1$|$4 \times \texttt H, 6 \times \texttt O, 2 \times \texttt C$|$4 \times \texttt H, 6 \times \texttt O, 2 \times \texttt C$|$\green{\texttt{DA}}$|
|$2$|$2 \times \texttt H, \red{1 \times \texttt S}, 4 \times \texttt O$|$2 \times \texttt H, 4 \times \texttt O$|$\red{\texttt{NE}}$|
|$3$|$1 \times \texttt N, \red{5 \times \texttt H}, 1 \times \texttt S, 4 \times \texttt O$|$1 \times \texttt N, \red{4 \times \texttt H}, 1 \times \texttt S, 4 \times \texttt O$|$\red{\texttt{NE}}$|
|$4$|$1 \times \texttt C, 4 \times \texttt H, 4 \times \texttt O$|$1 \times \texttt C, 4 \times \texttt H, 4 \times \texttt O$|$\green{\texttt{DA}}$|

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

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

- Subtask 1（10 pts）：方程式中均不含数字。
- Subtask 2（10 pts）：分子式中均不含数字。
- Subtask 3（30 pts）：无特殊限制。

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

**【来源】[COCI 2021-2022#5](https://hsin.hr/coci/contest5_tasks.pdf) Task 1 Kemija。**


title: [COCI2021-2022#5] Dijamant

description:
桌上摆放有若干颗『钻石』。

当一个正方形旋转 $45^\circ$ 时，它就形成了『菱形』的形状。规定外形形如『菱形』且外边框均为 $\texttt \#$ 但内部均为 $\texttt .$ 的图形为一颗『钻石』。

给定一个 $n \times m$ 大小的桌面，统计桌上摆放有多少颗『钻石』。

inputFormat:
第一行两个正整数 $n,m$，表示桌面的大小。

接下来的 $n$ 行，每行 $m$ 个字符 $\texttt \#$ 或 $\texttt .$，表示桌面。

outputFormat: 『钻石』的数量。

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

看起来好像有 $3$ 颗，但实际上有两个『菱形』互相包含，因此不符合『外边框均为 $\texttt \#$ 但内部均为 $\texttt .$』的定义。故只有 $1$ 颗『钻石』。

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

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

- Subtask 1（20 pts）：$1 \le n,m \le 100$。
- Subtask 2（50 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,m \le 2000$。

**【来源】[COCI 2021-2022#5](https://hsin.hr/coci/contest5_tasks.pdf) Task 2 Dijamant。**


title: 枚举元组

description:
$n$ 元组是指由 $n$ 个元素组成的序列。例如 $(1,1,2)$ 是一个三元组、$(233,254,277,123)$ 是一个四元组。

给定 $n$ 和 $k$，请按字典序输出全体 $n$ 元组，其中元组内的元素是在 $[1, k]$ 之间的整数。

「字典序」是指：优先按照第一个元素从小到大的顺序，若第一个元素相同，则按第二个元素从小到大……依此类推。详情参考样例数据。

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

outputFormat: 若干行，每行表示一个元组。元组内的元素用空格隔开。

hint: 对于 $100\%$ 的数据，有 $n\leq 5, k\leq 4$。