title: [NOI2022] 挑战 NPC Ⅱ

description:
诸由杨是一名咸鱼大学生，虽然他每天仍然幻想着在多项式时间内解决 NPC 问题。

诸由杨上课的时候了解到子图同构问题是一个 NPC 问题。他打算给出一个子图同构问题的多项式判定算法，间接地去证明 P = NP，这样他一定可以凭借这个伟大的工作荣获图灵奖！只可惜诸由杨才疏学浅，连子图同构问题属于 NPC 的证明都没有想出来。因而他退而求其次，准备判定一个更加简单的问题：

给定两棵有根树 $G, H$。设 $\lvert G \rvert$ 代表树 $G$ 中的节点个数，则这两棵树满足如下限制：$1 \leq \lvert H \rvert \leq \lvert G \rvert \leq \lvert H \rvert + k$。这里诸由杨保证 $k$ 是一个小常数。

诸由杨可以删除 $G$ 中的若干个节点，假定删除节点后后得到的子图为 $G'$。他想要知道是否存在一种删除节点的方式，使得删除后得到的子图 $G'$ 满足如下条件：

- $G'$ 连通。
- $G'$ 包含 $G$ 中的根节点（也就是说 $G$ 根节点在删除过程中没有被删除）。
- $G'$ 和 $H$ 同构（也就是说存在一种让 $G'$ 中点重标号的方式，使得重标号得到的图和 $H$ 完全相同，且 $G$ 中的根节点经过重标号后恰好为 $H$ 的根节点）。

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

输入的第一行依次包含两个正整数 $C,T$ 和一个非负整数 $k$，三个数字分别表示当前测试点编号，测试数据组数和题目中给定的常数。如果当前测试数据为样例则 $C = 0$。保证 $T \leq 500$、$k \leq 5$。

对于每一组测试数据：

输入的第一行包含一个正整数 $n_1$，表示树 $G$ 中的节点个数，保证 $1 \leq n_1 \leq {10}^5$，且 $\sum n_1 \leq 5 \times {10}^5$。

输入的第二行包含 $n_1$ 个整数，描述了树 $G$ 的结构。具体地，第 $i$（$1 \leq i \leq n_1$）个整数 $a_i$ 表示在树 $G$ 中节点 $i$ 的父节点，如果其为根节点则 $a_i = -1$。保证按照上述规则得到的树为连通有根树。

输入的第三行包含一个正整数 $n_2$，表示 $H$ 中的节点个数，保证对于所有测试数据，满足 $\max(1, n_1 - k) \leq n_2 \leq n_1$。

输入的第四行包含 $n_2$ 个整数，描述了树 $H$ 的结构。具体地，第 $i$（$1 \leq i \leq n_2$）个整数 $b_i$ 表示在树 $H$ 中节点 $i$ 的父节点，如果其为根节点则 $b_i = -1$。保证按照上述规则得到的树为连通有根树。

outputFormat:
对于每一组测试数据：

输出一行一个字符串。如果存在删除 $G$ 中节点的方式，使得其能够同时满足上述三个条件，则输出 `Yes`；否则输出 `No`。

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

对于第一个测试点，我们删除第一棵树的 $1$ 号节点。此时剩余的树和输入第二棵树均为包含两个节点的有根树，因而输出为 `Yes`。

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

对于第二个测试点，输入第一颗树深度为 $1$，但是输入第二颗树深度为 $2$。因而不论如何删除第一颗树的节点不会导致其树高增加到 $2$，因而输出为 `No`。

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

对于第三个测试点，其输入两颗树均同构于下图的树，因而因而输出为 `Yes`。

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

----

**【样例 \#2】**

见附件中的 `iso/iso2.in` 与 `iso/iso2.ans`。

该样例数据范围满足测试点 $7 \sim 8$。

----

**【样例 \#3】**

见附件中的 `iso/iso3.in` 与 `iso/iso3.ans`。

该样例数据范围满足测试点 $9 \sim 10$。

----

**【样例 \#4】**

见附件中的 `iso/iso4.in` 与 `iso/iso4.ans`。

该样例数据范围满足测试点 $13$。

----

**【数据范围】**

对于所有测试数据，满足 $1 \leq T \leq 500$，$1 \le n_2 \leq n_1 \le {10}^5$，$\sum n_1 \leq 5 \times {10}^5$，$0 \leq k \leq 5$。各测试点的附加限制如下表所示：

| $n_1,n_2$   | $\sum n_1$           | 测试点           | $k$      | 特殊性质         |
|:-----------:|:--------------------:|:-------------:|:--------:|:------------:|
| $\leq 8$    | $\leq 500$           | $1 \sim 3$       | $\leq 0$ | 无            |
| $\leq 8$    | $\leq 500$           | $4 \sim 6$       | $\leq 5$ | 无            |
| $\leq 16$   | $\leq 10^3$          | $7 \sim 8$         | $\leq 0$ | 无            |
| $\leq 16$   | $\leq 10^3$          | $9 \sim 10$        | $\leq 5$ | 无            |
| $\leq 150$  | $\leq 10^4$          | $11$          | $\leq 0$ | 无            |
| $\leq 150$  | $\leq 10^4$          | $12$          | $\leq 1$ | 无            |
| $\leq 150$  | $\leq 10^4$          | $13$          | $\leq 5$ | 无            |
| $\leq 10^5$ | $\leq 5 \times 10^5$ | $14 \sim 16$    | $\leq 0$ | A |
| $\leq 10^5$ | $\leq 5 \times 10^5$ | $17 \sim 20$ | $\leq 0$ | B  |
| $\leq 10^5$ | $\leq 5 \times 10^5$ | $21$          | $\leq 1$ | 无            |
| $\leq 10^5$ | $\leq 5 \times 10^5$ | $22 \sim 23$       | $\leq 3$ | 无            |
| $\leq 10^5$ | $\leq 5 \times 10^5$ | $24 \sim 25$       | $\leq 5$ | 无            |

其中附加限制中的特殊性质如下所示：

- 特殊性质 A：保证有根树 $G$ 每个节点要么是叶节点，要么有恰好 $1$ 个儿子结点；另一种等价的表述是有根树 $G$ 构成了一条链，且根节点为链的一个端点。
- 特殊性质 B：保证有根树 $G$ 每个节点要么是叶节点，要么有恰好 $2$ 个儿子结点，同时保证 $G$ 的每一个叶节点深度均相同；另一种等价的表述是有根树 $G$ 构成一棵完全二叉树，且根节点为完全二叉树的根节点。

**【提示】**

数据没有**针对任何合理的哈希算法做任何针对性的构造**，所以在合理范围内不需要过度担心因为哈希碰撞而产生的失分问题。


title: [NOI2022] 冒泡排序

type: P

background:
最近，小 Z 对冒泡排序产生了浓厚的兴趣。

下面是冒泡排序的伪代码：

```
输入: 一个长度为 n 的序列 a[1...n]
输出: a 从小到大排序后的结果
for i = 1 to n do:
    for j = 1 to n - 1 do
        if (a[j] > a[j + 1])
            交换 a[j] 与 a[j + 1] 的值
```

冒泡排序的交换次数被定义为在排序时**进行交换的次数**，也就是上面冒泡排序伪代码**第六行**的执行次数。他希望找到一个交换次数尽量少的序列。

description:
小 Z 所研究的序列均由非负整数构成。它的长度为 $n$，且必须满足 $m$ 个附加条件。其中第 $i$ 个条件为：下标在 $[L_i, R_i]$ 中的数，即 $a_{L_i}, a_{L_{i+1}},\dots,a_{R_i}$ 这些数，其最小值**恰好为 $\boldsymbol{V_i}$**。

他知道冒泡排序时常会超时。所以，他想要知道，在所有满足附加条件的序列中，进行冒泡排序的交换次数的最少值是多少。

inputFormat:
本题有多组数据。

输入的第一行包含一个正整数 $T$。

对于每组数据，第一行包含两个正整数 $n,m$。数据保证 $1 \leq n,m \leq 10^6$。

接下来 $m$ 行，每行三个非负整数 $L_i, R_i, V_i$，表示一组附加条件。数据保证 $1 \leq L_i \leq R_i \leq n$、$0 \leq V_i \leq 10^9$。

outputFormat:
输出共 $T$ 行，每行一个整数。

对于每组数据，如果存在满足这 $m$ 个附加条件的序列，则输出在所有满足附加条件的序列中，冒泡排序交换次数的最小值。如果不存在满足所有条件的序列，则输出 $-1$。

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

这组数据的约束条件为 $a_1 = 2022, \min\{a_2, a_3\} = 39$。

若 $a_2 = 39$，且 $39 \leq a_3 < 2022$，则冒泡排序只有第一轮有交换操作，这一轮交换了 $a_1, a_2$ 和 $a_2, a_3$，总交换次数为 $2$。

若 $a_2 = 39$，且 $a_3 \geq 2022$，则冒泡排序只有第一轮有交换操作，这一轮仅仅交换 $a_1, a_2$，总交换次数为 $1$。

若 $a_3 = 39$，且 $39 < a_2 < 2022$，则冒泡排序算法第一轮交换 $a_1, a_2$ 和 $a_2, a_3$，第二轮交换 $a_1, a_2$。总交换次数为 $3$。

若 $a_3 = 39$，且 $a_2 \geq 2022$，则冒泡排序算法第一轮交换 $a_2, a_3$，第二轮交换 $a_1, a_2$。总交换次数为 $2$。

因此，交换次数的最小值为 $1$。

----

**【样例 \#2】**

见附件中的 `bubble/bubble2.in` 与 `bubble/bubble2.ans`。

----

**【样例 \#3】**

见附件中的 `bubble/bubble3.in` 与 `bubble/bubble3.ans`。

这个样例满足测试点 $8 \sim 10$ 的条件。

----

**【样例 \#4】**

见附件中的 `bubble/bubble4.in` 与 `bubble/bubble4.ans`。

这个样例满足测试点 $13 \sim 14$ 的条件。

----

**【样例 \#5】**

见附件中的 `bubble/bubble5.in` 与 `bubble/bubble5.ans`。

这个样例满足测试点 $15 \sim 16$ 的条件。

----

**【样例 \#6】**

见附件中的 `bubble/bubble6.in` 与 `bubble/bubble6.ans`。

这个样例满足测试点 $23 \sim 25$ 的条件。

----

**【数据范围】**

本题共 $25$ 个测试点。全部测试点满足：$1 \leq T \leq 1000$，$1 \leq \sum n, \sum m \leq 10^6$，$1 \leq L_i \leq R_i \leq n$，$0 \leq V_i \leq 10^9$。

其中 $\sum n, \sum m$ 分别表示所有测试点的 $n$ 的总和和 $m$ 的总和。$\sum n^2, \sum m^2, \sum n^3, \sum m^3$ 的含义类似。

| 测试点          | 数据范围                                                   | 特殊性质         |
|:------------:|:------------------------------------------------------:|:------------:|
| $1 \sim 4$   | $n,m \leq 7$，且最多 $2$ 组数据不满足 $n, m \leq 5$              |              |
| $5 \sim 7$   | $n,m \leq 17$，且最多 $3$ 组数据不满足 $n, m \leq 9$             | A |
| $8 \sim 10$  | $n,m \leq 100$，$\sum n^3,\sum m^3 \leq 4 \times 10^7$  | A |
| $11 \sim 12$ | $n,m \leq 2000$，$\sum n^2,\sum m^2 \leq 4 \times 10^7$ | A |
| $13 \sim 14$ | $n,m \leq 2000$，$\sum n^2,\sum m^2 \leq 4 \times 10^7$ | B |
| $15 \sim 16$ | $n,m \leq 2000$，$\sum n^2,\sum m^2 \leq 4 \times 10^7$ | C |
| $17 \sim 18$ | $n,m \leq 2000$，$\sum n^2,\sum m^2 \leq 4 \times 10^7$ |              |
| $19$         | $\sum n,\sum m \leq 10^6$                              | A |
| $20$         | $\sum n,\sum m \leq 10^6$                              | B |
| $21 \sim 22$ | $\sum n,\sum m \leq 10^6$                              | C |
| $23 \sim 25$ | $\sum n,\sum m \leq 10^6$                              |              |

特殊性质 A：对于 $1 \leq i \leq m$，$0 \leq V_i \leq 1$。
特殊性质 B：对于 $1 \leq i \leq m$，$L_i = R_i$。
特殊性质 C：输入给出的 $m$ 个区间 $[L_i, R_i]$ 两两不相交。

----

**【提示】**

本题的部分测试点输入量较大。我们建议你使用较为快速的读入方式。


title: [NOI2022] 二次整数规划问题

description:
本题中，你需要解决一个著名的 NP 问题——二次整数规划问题。

二次整数规划问题要有变量：你需要给出一个长度为 $n$ 的**整数**序列 $(x_1, x_2, \ldots, x_n)$，满足下文中的所有条件。

二次整数规划问题要有约束：你给出的整数序列需要满足以下两类约束：

1. 一类约束是单个变量取值的约束：给出正整数 $k$（$3 \leq k \leq 5$）和 $n$ 个区间 $[l_i, r_i]$（$1 \leq i \leq n$），其中 $1 \leq l_i \leq r_i \leq k$，你给出的序列需要满足 $\forall 1 \leq i \leq n$，$l_i \leq x_i \leq r_i$；
2. 另一类约束是变量之间取值的约束：给出 $m$ 个三元组 $(p_i, q_i, b_i)$，你给出的序列需要满足 $\forall 1 \leq j \leq m$，$\lvert x_{p_j} - x_{q_j} \rvert \leq b_j$。

二次整数规划问题要有目标函数：在给出 $k-2$ 个目标参数 $v_2,v_3,\dots,v_{k-1}$（**注意下标范围为 $\boldsymbol{2}$ 至 $\boldsymbol{k-1}$**）的前提下，对于一个值域为 $[1,k]$ 的整数数列 $\{p_1,p_2,\dots,p_n\}$，设 $c_i$ 为该序列中取值为 $i$ 的元素个数，$G$ 为满足 $1 \leq i,j \leq n$ 且 $|p_i-p_j|\leq 1$ 的整数二元组 $(i, j)$ 个数，**注意当 $\boldsymbol{i \neq j}$ 时，$\boldsymbol{(i, j)}$ 与 $\boldsymbol{(j, i)}$ 是不同的二元组**。定义该序列的**权值**为

$$ W(p_1, p_2, \ldots, p_n) = 10^6 G+\sum_{i=2}^{k-1} c_i v_i \text{。} $$

你的序列需要在满足以上两类约束的情况下，最大化其权值。在给出的约束下，保证存在满足约束的序列。

二次整数规划问题不一定要有多组询问，但是我们会给出 $q$ 次询问，每次询问给出不同的权值参数 $v_2, v_3, \ldots, v_{k-1}$，对于每组询问你需要找到满足约束的最大化权值的序列。为了减少输出量，你只需要输出这个序列的权值。

inputFormat:
**本题有多组测试数据。** 第一行一个非负整数和一个正整数 $C, T$，分别表示测试点编号和测试数据数量。$C = 0$ 表示该组数据为样例。

对于每组测试数据，第一行四个整数 $k, n, m, q$，描述序列值域、序列长度、变量之间约束的个数和询问次数。

接下来 $n$ 行每行两个整数 $l_i, r_i$，描述序列中每个元素对应的取值区间。

接下来 $m$ 行每行三个整数 $p_j, q_j, b_j$，描述一个变量之间的约束。

接下来 $q$ 行每行 $k - 2$ 个非负整数 $v_2, v_3, \ldots, v_{k - 1}$ 描述一组询问的权值参数。

outputFormat: 对于每组数据的每组询问输出一行一个整数，表示序列权值的最大值。


title: [语言月赛202210] 应急食品

type: B

background: 派蒙是不是应急食品？不同的旅行者有不同的答案。

description:
派蒙是不是应急食品，是每一个旅行者必须完成的选择题。

选项 A 为 派蒙是应急食品；
选项 B 为 派蒙不是应急食品。

旅行者一定是正确的，现在告诉你某个旅行者的选择，请问派蒙是不是应急食品。

inputFormat: 输入一行一个字符，代表旅行者选择的选项。

outputFormat: 输出一行一个字符串，若为应急食品，则输出 `food`，否则输出 `paimeng`。

samples: A food


title: [语言月赛202210] 购物节

description:
一个商店有两种包装的本子，第一种是单本装，一本 $x$ 元，第二种是十本优惠装，一套 $y$ 元。

现在商店推出“双十一”活动，每种包装的本子都优惠 1 元，优惠后价格为单本装 $x - 1$ 元，十本装为 $y - 1$ 元。

小明想要买**恰好** $n$ 个本子，请问**至少**需要花多少钱？

注：这里的“恰好”的意义为，不能买少于 $n$ 个本子，也不能买超过 $n$ 个本子。

inputFormat: 共一行，包括三个数字 $x,y,n$，分别表示单本装的价格，十本优惠装的价格，小明需要的本子的数量。

outputFormat: 共一个数，表示小明购买 $n$ 个本子至少需要花费的钱的数目。

hint:
**样例解释** ：

单本装原价 $10$ 元，十本装原价 $80$ 元。

优惠后价格为单本装 $9$ 元，十本装 $79$ 元。

此时，如果购买 $10$ 本，则需要 $79$ 元；如果购买 $1$ 本，则需要 $9$ 元；如果购买 $11$ 本，则需要 $88$ 元。

**数据范围**：

对于 $20\%$ 的数据，满足 $n < 10$；

对于 另外 $20\%$ 的数据，满足 $n$ 是 $10$ 的倍数；

对于 $80\%$ 的数据，满足 $0\le n,x,y\le 10^4$

对于 $100\%$ 的数据，满足 $0\le n,x,y\le 10^9$


title: [语言月赛202210] 配餐

description:
午饭时间，喵喵喵幼儿园的 $n$ 位小朋友从左到右排成一列等待领取自己的午餐。我们将这些小朋友从左到右依次标号为 $1, 2, \cdots , n - 1, n$。

负责配餐的老师已经拿到了所有人的午饭餐食，餐食同样也是从左到右排成一排。

老师手里拿到了一份序列 $r _ 1 \cdots r _ n$，代表编号为 $i$ 的小朋友应该拿到从左向右数第 $r _ i$ 份午餐餐食（$1 \leq r _ i \leq n$ 且 $r _ i$ 两两不同）。

按照上面的序列分发完成后，老师又拿到了一个序列 $a _ 1 \cdots a _ n$，其中 $a _ i$ 代表未分发前从左向右数第 $i$ 份餐食的**一个参数**。

老师想要知道，对每个小朋友，他们所拿到的午餐的**这个参数**的值是多少。但是这个任务对于老师来说太难了，所以喵喵喵幼儿园找到了万能的你。

inputFormat:
共三行。

第一行一个整数，代表 $n$。

第二行 $n$ 个整数，代表 $r _ 1 \cdots r _ n$。

第三行 $n$ 个整数，代表 $a _ 1 \cdots a _ n$。

outputFormat: 一行，$n$ 个整数。第 $i$ 个整数代表编号为 $i$ 的小朋友所拿到的午餐的**这个参数**是多少。

hint:
**样例解释**

编号为 $1$ 的小朋友拿到了第四份餐食，参数为 $9$。

编号为 $2$ 的小朋友拿到了第一份餐食，参数为 $7$。

编号为 $3$ 的小朋友拿到了第三份餐食，参数为 $2$。

编号为 $4$ 的小朋友拿到了第二份餐食，参数为 $4$。

**数据规模与约定**

本题共 $10$ 个测试点。

对第一个测试点，保证 $n = 2, r_1 = 1, r_2 = 2$。

对第二个测试点，保证 $n = 2$。

对第三、四个测试点，保证 $n \leq 100$。

对第五、六个测试点，保证对任意的 $1 \leq i \leq n, r _ i = i$。

对全部的测试点，保证 $2 \leq n \leq 1 \times 10 ^ 5, 1 \leq a _ i \leq 10 ^ 9, 1 \leq r _ i \leq n$ 且不存在一对 $(i, j)$ 使得 $r_i = r_j$。


title: [语言月赛202210] 图书新编

description:
图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。 每位借书的读者手中有一个需求码，这个需求码也是一个正整数。

如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。

小 D 刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写一个程序，对于每一位读者，求出有多少本书是他所需要的。

inputFormat:
第一行，包含两个正整数 $n , q$，以一个空格分开，分别代表图书馆里书的数量和读者的数量。

接下来的 $n$ 行，每行包含一个正整数，代表图书馆里某本书的图书编码。

接下来的 $q$ 行，每行包含两个正整数，以一个空格分开，第一个正整数代表图书馆 里读者的需求码的长度，第二个正整数代表读者的需求码。

outputFormat: $ q$ 行，每行包含一个整数，如果存在第 $i$ 个读者所需要的书，则在第 $i$ 行输出有多少书是第 $i$ 个读者所需要的。

hint:
对于 $20\%$的数据，$1 \le n \le 2$；
另有 $20\%$的数据，$q = 1$；
另有 $20\%$的数据，所有读者的需求码的长度均为 $1$；
另有 $20\%$的数据，所有的图书编码按从小到大的顺序给出；
对于 $100\%$的数据，$1 \le n \le 1000,1 \le q \le 1000$，所有的图书编码和需求码均不超过 $10^7$。


title: [语言月赛 202210] 军训

description:
某 E 刚结束军训，军训教官将所有同学排成了 $n$ 行 $m$ 列。

教官组织同学们进行分列式练习，同学们将按行为单位进行练习。第 $i$ 行第 $j$ 名同学摆臂的高度为 $a_{i,j}$，踢腿的高度为 $b_{i,j}$。

教官认为，每一行同学的不整齐度为摆臂高度方差与踢腿高度方差之和。形式化的，第 $i$ 行同学的不整齐度为
$$
\dfrac{1}{m} \times \sum\limits_{j=1}^{m}{\Bigg(a_{i,j}-\dfrac{\sum\limits_{k=1}^{m}{a_{i,k}}}{m}\Bigg)^2} + \dfrac{1}{m} \times \sum\limits_{j=1}^{m}{\Bigg(b_{i,j}-\dfrac{\sum\limits_{k=1}^{m}{b_{i,k}}}{m}\Bigg)^2}
$$

其中，$\sum\limits_{j=1}^m{a_{i,j}}$ 代表 $a_{i,1}+a_{i,2}+a_{i,3}+\cdots+a_{i,m}$。

教官希望对若干行进行位置上的对调，使得最终排出的方阵中，从第 $1$ 行至第 $n$ 行不整齐度依次递增。若有两行不整齐度相同，可以任意安排其顺序。

请你编写程序，给出一种交换方案。请注意，每一步交换是即刻完成的。

例如，给出如下的交换方案：

第一步，交换第 $1$ 行和第 $2$ 行；第二步，交换第 $2$ 行和第 $3$ 行。

初始：

| 当前行数 | 初始行号 |
|:---: | :---: |
| $1$ | $1$ |
| $2$ | $2$ |
| $3$ | $3$ |

第一步完成后：

| 当前行数 | 初始行号 |
|:---: | :---: |
| $1$ | $2$ |
| $2$ | $1$ |
| $3$ | $3$ |

第二步完成后：

| 当前行数 | 初始行号 |
|:---: | :---: |
| $1$ | $2$ |
| $2$ | $3$ |
| $3$ | $1$ |

**提示：例如，将第 $1$ 行与第 $3$ 行交换后，原第 $1$ 行将被叫做第 $3$ 行，而不是仍被叫做第 $1$ 行。**

**具体解释可参照样例 #2 解释。**

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

输入的第一行为两个整数 $m,n$，分别代表列数和行数。

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

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个代表 $b_{i,j}$。

outputFormat:
输出若干行。

输出的第一行为一个整数 $K$，代表你交换方案中交换的次数。

接下来 $K$ 行，每行输出两个整数 $x,y$，代表将第 $x$ 行与第 $y$ 行的同学进行交换。

**注意：$K$ 应当不超过 $n^2$**。

hint:
### 样例 #2 解释

仅考虑摆臂高度，在前两次交换后，阵列变成如下的样子：

$\begin{matrix} 1: & 2 & 4 & 6 \\ 2: & 1 & 2 & 3 \\ 3: & 3 & 6 & 9 \end{matrix}$

此时，原第 $3$ 行现被叫做第 $2$ 行，原第 $2$ 行现被叫做第 $1$ 行。如果我们想要将它们交换，应该输出 `1 2` 而不是 `2 3`。

### 数据规模与约定

对于 $30\%$ 的数据，所有 $a_{i,j}$ 均相同，$b_{i,j}$ 均相同。

对于另外 $20\%$ 的数据，满足 $n\le 100$，$m\le 100$。

对于 $100\%$ 的数据，$1 \le n,m \le 1000$，$1 \le a_{i,j},b_{i,j} \le 100$。

### Special Judge

本题答案不唯一，将有 Special Judge 对你的答案进行检查，所有合法答案均可以得分。

Problem Assigned by 览遍千秋 | 七海


title: [语言月赛202210] 玉桂狗

background: 某 E 非常喜欢玉桂狗。

description:
在商店里共有 $n$ 只玉桂狗玩偶，每只玩偶有可爱度 $k$ 和价格 $p$。$k$ 越大的玉桂狗玩偶越可爱。

某 E 现在有 $R$ 元钱，她想知道自己可以买到的最可爱的玉桂狗玩偶的可爱度为多少。

保证某 E 一定能买到至少一只玉桂狗。

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

输入的第一行为两个个整数 $n,R$。

接下来 $n$ 行，每行两个个整数 $k,p$，用于描述一只玉桂狗。

outputFormat: 输出一行一个整数，代表某 E 能够买到的最可爱的玉桂狗的可爱度。


title: 「KDOI-06-J」翻转与反转

description:
小 W 有一个长度为 $n$ 的 $01$ 序列 $a_1,a_2,\ldots,a_n$，他将对这个序列按顺序进行 $n$ 次操作。

在第 $i$ 次操作中（$1\le i\le n$），小 W 将按顺序执行以下**两种**变换：

1. 将区间 $[1,i]$ 中的数按下标翻转。形式化地说，在这次变换之后，序列 $a$ 将变为 $a_i,a_{i-1},\ldots,a_{1},a_{i+1},a_{i+2},\ldots,a_n$。
2. 将区间 $[1,i]$ 中的数按值翻转。形式化地说，在这次变换之后，对于任意 $1\le j\le i$，若 $a_j=0$，则 $a_j$ 将变为 $1$，否则 $a_j$ 将变为 $0$。

小 W 想要知道，在全部 $n$ 次操作结束后，序列 $a$ 中每个元素的值。

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

输入的第一行包含一个正整数 $n$，表示序列长度。

接下来一行 $n$ 个整数，表示序列 $a_1,a_2,\ldots, a_n$。保证 $a_i=0$ 或 $1$。

outputFormat:
输出到标准输出。

输出包含一行 $n$ 个整数，表示操作结束后序列 $a$ 中每个元素的值。


title: [语言月赛202210] 垃圾分类

description:
2077 年，由于资源几近枯竭，梦之城推行了一套极其严格的垃圾分类制度。具体的，梦之城将垃圾分为 $n$ 类，每一类垃圾只能被放入特定的垃圾桶中。由于梦之城掌握了压缩技术，因此在这里**垃圾只有数量之分，没有体积大小之分。**

你是梦之城的一位居民。在你居住的社区外有 $n + 1$ 个垃圾桶，标号为 $1, 2, \cdots, n, n + 1$。

对前 $n$ 个垃圾桶，它们只能接受**对应标号**的垃圾，并且有一定的容量。具体的，你会得到一个长度为 $n$ 的序列 $r _ 1, \cdots, r _ n$。第 $i$ 个垃圾桶只能接受第 $i$ 类垃圾，且最多只能被放入 $r _ i$ 个。

对最后一个垃圾桶，它可以接受所有种类的垃圾，容量也是几近无限的。但是，每向**这个**垃圾桶放入一个垃圾，居委会会向你收取 $c$ 的费用。

某一天，你的家中堆放满了垃圾。在将这些垃圾分类好后，你得到了一个长度为 $n$ 的序列 $a _ 1, \cdots, a _ n$，代表第 $i$ 类垃圾有 $a _ i$ 个。

你想要知道，如果想要扔掉所有的这些垃圾，你的最小花费是多少。

inputFormat:
共三行。

第一行两个整数 $n, c$，代表垃圾的种类数和向最后一个垃圾桶放入垃圾的费用。

第二行 $n$ 个整数 $r _ 1, \cdots, r _ n$，代表垃圾桶的容量。

第三行 $n$ 个整数 $a _ 1, \cdots, a _ n$，代表每一类垃圾的数量。

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

hint:
**样例解释**

样例组 #1：最优情况下，你需要向最后一个垃圾桶中放入 $9$ 个垃圾，费用为 $7 \times 9 = 63$。

样例组 #2：最优情况下，你不需要向最后一个垃圾桶中放入任何垃圾，费用为 $0$。

**数据规模与约定**

对前 $20\%$ 的数据，保证 $n = 2$。

对前 $60\%$ 的数据，保证 $n, a _ i, c \leq 10 ^ 3$。

对另外 $10\%$ 的数据，保证 $c = 0$。

对另外 $10\%$ 的数据，保证 $r _ i \geq a _ i$。

对 $100\%$ 的数据，保证 $2 \leq n \leq 10 ^ 6, 0 \leq r _ i, a _ i, c \leq 10 ^ 6$。


title: 「Wdoi-2」不败的无尽兵团

background:
畜生界是一个被动物灵所占据的，究极的弱肉强食的空间，也是个被几个组织所支配的世界——劲牙组、鬼杰组、刚欲同盟……

在这些动物灵其中也有一些灵长类动物的灵，也就是人类灵，它们弱小但又手脚灵活，作为完完全全的奴隶苟存在灵长园这一娱乐设施中。

但人类的灵也是有信仰的，它们向神明祈求，神也回应了人类的祈求，向人类给予了信仰的偶像。然而，人类灵原本只是皈依于存在于偶像背后的神性，却逐渐开始信仰起偶像本身来。结果，自然而然地，偶像开始支配人类，使得灵长园变成一个凶恶的失控组织。

畜生界也因为灵长园的暴动变得混乱，为了打倒偶像，鬼杰组希望能够卷入地上的人类，借用人类之手毁灭灵长园。动物灵们也就来到了地上，也就是幻想乡，带领灵梦一行人一同前往地狱。

description:
### 简要题意

对于正整数 $n$（$n$ 为 $529$ 或 $625$），$A=\{1,2,\cdots,n\}$ 的 $m \ge 2$ 个子集 $B_1,B_2,\cdots,B_m(|B_i| \geq 3)$ 为好的，如果对于 $A$ 的每一个三元子集 $C$，都存在 **恰好** 一个 $i$ 使得 $C$ 为 $B_i$ 的子集。构造一个好的子集族使得 $m$ 尽量小（不超过题目给定的评分参数）。

### 原始题意

一路进入畜生界的灵梦，遭遇到了埴轮兵团的首长，杖刀偶磨弓的阻拦。

埴轮兵团由 $n$ 个战士组成，它们编号为 $1,2,\dots,n$。战士数量为 $529$ 或者 $625$。作为一个兵团，要做到最好的进攻与防守，埴轮之间存在 $m$ 组配合关系 $B_1,B_2,\dots,B_m$，每组关系包含若干个不同（但不少于 $3$ 个）的埴轮战士，但不同组的关系中包含的埴轮战士可以重复。

但是灵梦并不事先知道这些配合关系，而且由于埴轮兵团配合默契，灵梦难以强行击败它们。在动物灵的帮助之下，灵梦发现，这些埴轮满足如下特点：从埴轮兵团中任意选出 $3$ 个埴轮，都存在 **恰好** 一个 $i$，使得这三个埴轮是 $B_i$ 的一个子集。在满足这个特点的基础之上，由于磨弓的精力有限，无法同时维护太多组配合关系。因此，$m$ 是一个大于等于 $2$ 的一个正整数，且其小于等于 $m_{ans}$。

现在灵梦告诉了你埴轮兵团的总人数，请你告诉她一种可能的埴轮兵团配合的情况，帮助她打败杖刀偶磨弓，进入灵长园。

inputFormat: 第一行有一个正整数 $n$，含义如题意所示。保证 $n=529$ 或者 $625$。

outputFormat:
第一行输出一个正整数 $m$，表示你构造的方案使用的集合的总个数。应当满足 $m\ge 2$。

接下来 $m$ 行，每行输出若干个整数。第一个整数 $s$ 表示你构造的 $B_i$ 的大小，应当满足 $n\ge s>0$。接下来 $s$ 个整数描述 $B_i$ 内的元素，中间用空格隔开。

hint:
### 样例 1 解释

**样例仅供理解题意参考。实际数据中，$n$ 只会为 $529$ 或 $625$。**

由于 $m>1$，因此结果不能为 $\{\{1,2,3,4\}\}$；又因为 $|B_i|< 3$ 时 $B_i$ 无用，于是唯一的方案就是列出 $\{1,2,3,4\}$ 的所有三元子集 $\{\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\}$。

### 数据范围及约定

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n=} & \bm{m_{\text{ans}}=} & \textbf{分值} \cr\hline
1 & 529 & 1.25\times 10^4 & 75 \cr\hline
2 & 625 & 1.60\times 10^4 & 25 \cr\hline
\end{array}$$

如果你输出的方案不合法，那么你将不能获得该测试点的得分。

当你构造的解符合题设，并且 $m$ 的值不超过 $m_{\text{ans}}$，你才能获得该测试点的分值。


title: 『JROI-8』这是新历的朝阳，也是旧历的残阳

background:
![1663764375173.png](https://img-kysic-1258722770.file.myqcloud.com/8c10be566f21cceb653f209300936b97/68a6764e14651.png)

>少女于海边伫立，凝视着落日最后的余晖\
“已然过去了呢，旧历的一年......”

**已获得转载授权。**

description:
给定序列 $\{a_n\}$，满足每一项都不小于前一项。对于所有不超过 $k$ 的正整数 $m$，询问如果将 $a$ 分成 $m$ 段（可以有空段），并给从前往后第 $i$ 段内的每个数都加上 $i$，增加后的 $\sum\limits_{j=1}^n a_j^2$ 最大是多少。询问相互独立，即每次询问时给每个数加的值不保留到下一次询问。

例如，对于序列 $\{-3,1,2,2\}$，若 $m=5$，则一种分段方式是 $[-3][][1,2][][2]$，增加后的序列是 $-2,4,5,7$，此时 $\sum\limits_{j=1}^n a_j^2=94$。

记 $m=i$ 时的答案（即此时最大的 $\sum\limits_{j=1}^n a_j^2$）为 $q_i$，出于良心考虑，你只需要输出 $\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353$ 即可。标准程序不基于特殊的输出方式，即能独立求出每一个 $q_i$。

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

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

outputFormat: 一行一个整数，表示 $\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353$。


title: 『JROI-8』雷雨天特别行动科

background:
![1663764044201.png](https://img-kysic-1258722770.file.myqcloud.com/639b5f084b6aa779f0a90253f9eef153/b2f5e91db29b9.png)

>“天使可没有假期”\
“啊，又来了……还是不要勉强自己会比较好哦”

**已获得转载授权。**

description:
对于**非负整数**变量 $x$，记以下为一轮操作：

1. 将 $x$ 增加 $1$；
2. 如果 $x$ 是 $3$ 的倍数，则将 $x$ 除以 $3$。

给定初始的 $x,k$，试求 $k$ 轮操作后 $x$ 的值。

**请注意，大样例不以文件附加形式给出，而直接放在题目的 输入输出样例 中的 样例 #3**

inputFormat: 一行两个非负整数 $x,k$。

outputFormat: 一行一个正整数，表示 $k$ 轮操作后 $x$ 的值。


title: 『MdOI R5』Message

description:
小 A 有一个群。这个群正在玩一个小游戏：给出一个函数 $f$，从某一个时间点起，发送第 $x$ 条消息，而 $f(x)=1$ 的群友会受到一个小惩罚。当群内消息总数达到 $m$ 时游戏结束。

但小 A 是个话痨，这段时间他在这个群发了 $n$ 条消息，他发的第 $i$ 条消息在整个消息记录里是第 $a_i$ 条消息。

但是小 A 不想受到惩罚，而小 A 恰好是管理员，他可以撤回**任何时刻、任何群成员发的任何消息**，注意这会导致这条消息之后的消息排名改变。

但是撤回消息太多容易被当成暴政，因此他要尽可能减少撤回信息次数，不管是自己的还是别人的。

接下来你也猜到你要干什么了：假如其他群成员不操作，给出 $n$、函数 $f$ 和 $a_i$，求出他至少要撤回几条消息。

inputFormat:
输入的第一行有两个正整数 $n,m$，表示他的消息数量以及群内消息数量总数。

第二行是一个长为 $m$ 的 **01 串** $f$，其第 $i$ 项 $f(i)$ 表示发第 $i$ 条消息的群成员是否要受到惩罚。

第三行有 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示每条消息的初始排名。保证数列 $a$ 严格递增，且 $1\le a_i\le m$。

outputFormat: 输出一行一个整数 $ans$ 表示至少撤回几条消息才能让小 A 不被惩罚。


title: [CoE R5] So What Do We Do Now?

background:
![396ac9d3c58dbf329d6ead206944a5a495930006.jpg](https://img-kysic-1258722770.file.myqcloud.com/f2a3112865eea75d3c27aae713e1a8a8/ae2c3e0c34910.jpg)

>$\texttt{I'm getting tired of hiding.}$

声明：上述图片取自网络，`pid:6544352`，如有侵权，告知即删。

description:
给定一棵 $n$ 个结点的有根树，根结点编号为 $1$。设以 $i$ 为根的子树为 $T_i$。你需要给每个结点赋一个正整数点权 $v_i$，使得所有点的点权恰为 $1,2,\dots,n$ 各一个。记
$$f=\sum_{i=1}^{n}R_i,$$
其中 $R_i$ 是以 $i$ 为根的子树中点权的极差，即
$$R_i=\max_{j \in T_i}\{v_j\}-\min_{j \in T_i}\{v_j\}.$$
对于所有的赋点权的方式，请求出一组使 $f$ 取到最小值的点权。

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

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

outputFormat: 第一行一个 $1,2,\dots,n$ 的排列，表示结点 $1,2,\dots,n$ 的点权。由于赋点权的方式可能有很多种，你只需要输出其中任意一种即可。

hint:
**样例说明**

输入 $\#1$

![graph.png](https://img-kysic-1258722770.file.myqcloud.com/4a372f1ae46e27a31fae60c4db5e439e/af9581fa182de.png)

$R_1=3-1=2,R_2=2-2=0,R_3=3-3=0,f=R_1+R_2+R_3=2$，可以证明，不存在使得 $f$ 更小的构造。

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

**数据范围**

对于 $10\%$ 的数据，$n \le 10$；

对于另外 $10\%$ 的数据，树是一条链；

对于另外 $20\%$ 的数据，有一个结点与其他 $n-1$ 个结点都相连；

对于另外 $20\%$ 的数据，树是一棵完全二叉树，即除了叶子结点外每个结点都恰有两个子结点；

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


title: [PA2021] Zbalansowane słowa

description:
定义一个字符串 $s$ 是好的，当且仅当它包含的所有字符出现次数相同。

好的字符串例如：`mama`、`aabbcbcccbaa`。

不好的字符串例如：`ovo`。

给定一个字符串 $s$，求出 $s$ 好的**子串**数量。

inputFormat: 一行，一个字符串 $s$。

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

hint: 对于 $100\%$ 的数据，$1 \leq |s| \leq 3 \times 10^5$，$s$ 中只含 `a`、`b`、`c` 三个小写字母。


title: [PA2021] Koszulki

description:
$n$ 个人参加一场比赛，其中第 $i$ 个人的得分为 $a_i$。

主办方决定至少颁发 $k$ 件礼物。

但是，若 $\exist 1 \leq x, y \leq n, a_x \geq a_y$ 且 $x$ 未拿到礼物但 $y$ 拿到礼物，$x$ 会不满意。

主办方希望每个人都满意，求颁发的礼物数量的最小值。

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

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

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

hint:
#### 样例 #1 解释
最优方案为除了最后一人以外全部送礼物。
#### 数据范围
对于 $100\%$ 的数据，$1 \leq k \leq n \leq 2 \times 10^3$，$1 \leq a_i \leq 120$。


title: 「UOI-R1」求和

description:
给定 $n$ 个区间 $p_i, q_i$。

求$\sum\limits_{s_1={p_1}}^{q_1}\sum\limits_{s_2={p_2}}^{q_2}\sum\limits_{s_3={p_3}}^{q_3} \cdots\sum\limits_{s_n={p_n}}^{q_n}\max\limits_{i=1}^ns_i$ 对 $998244353$ 取余的值。

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

第 $2$ 至 $(n+1)$ 行，每行两个整数 $p_i,q_i$。

outputFormat: 一个整数，表示答案。你需要将答案取余 $998244353$ 后输出。

samples:
见文件附件的 sum2.in
见文件附件的 sum2.ans


title: [PA2021] Oranżada

description:
有一排共 $n$ 瓶橙汁，其中第 $i$ 瓶的品牌为 $a_i$。

你可以花费 $1$ 个单位的的代价交换两瓶相邻的橙汁。

求最小代价使得最左边 $k$ 瓶橙汁品牌两两不同。

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

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

outputFormat: 一行，一个整数，若有解，输出最小代价；否则，输出 $-1$。

hint:
#### 样例 #1 解释
最优方案为先交换位置 $3$ 和 $4$ 的瓶子、再交换位置 $4$ 和 $5$ 的瓶子，接着交换位置 $2$ 和 $3$ 的瓶子，最后交换位置 $3$ 和 $4$ 的瓶子，共 $4$ 次操作。
#### 样例 #2 解释
显然无解。
#### 数据范围
对于 $100\%$ 的数据，$1 \leq k, a_i \leq n \leq 5 \times 10^5$。


title: [PA2021] Pandemia

description:
某国有 $n$ 座城市，其中 $\forall 1 \leq i < n$，城市 $i$ 与城市 $i + 1$ 有**双向**道路相连。

该国发生了疫情，一个城市要么无人感染，要么全体感染。具体地，一个城市初始时被感染当且仅当 $s_i = 1$。

疫情会扩散，每一天上午，你可以为一个未感染的城市的居民接种疫苗，下午，每个被感染的城市会向相邻的城市扩散，如果相邻的城市未接种疫苗，它将立即全员感染。

你作为城市管理者，想要知道执行最优策略的情况下，最少会有几个城市的所有人都被感染。

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

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

对于每组数据：

第一行，一个整数 $n$；

第二行，一个长度为 $n$ 的字符串 $s$。

outputFormat:
对于每组数据：

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

hint:
#### 样例 #1 解释
测试点一：第一天接种城市 $7$，第二天接种城市 $1$。

测试点二：第一天接种城市 $5$，第二天接种城市 $7$。

测试点三：初始不存在疫情，因此不需要接种。
#### 数据范围
对于 $100\%$ 的数据，$1 \leq n, T \leq 10^5$，$1 \leq \sum n \leq 10^6$。


title: [PA2021] Poborcy podatkowi

description:
给定一棵 $n$ 个点的树，你可以选择若干条长度为 $4$ 的不相交链（**可以不选**）。

每个选链的方案的收益为所选链的并集的边权和，求最大收益。

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

接下来 $n - 1$ 行，每行三个整数 $u, v, w$，表示树上的一条边 $(u, v)$，其边权为 $w$。

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

hint:
#### 样例 #1 解释
给出一种最优方案：选择链 $2 \to 6$，$6 \to 10$，$11 \to 15$，$16 \to 19$。
#### 样例 #2 解释
由于每一条长度为 $4$ 的链权值均为负数，所以不选最优。
#### 数据范围
对于 $100\%$ 的数据，$2 \leq n \leq 2 \times 10^5$，$-10^9 \leq a_i \leq 10^9$。


title: [PA2021] Zakłócenia

description:
定义一种小写字母到 $8$ 位 01 串的映射：

- 将小写字符的 ASCII 码转为 $8$ 位二进制数，如：$a \rightarrow 97 \rightarrow 01100001$。

现在小 A 有一个长度为 $n$ 的只含小写字母的字符串 $s$，他将这个字符串映射到了一个长为 $8n$ 的 01 字符串 $t$。

他打乱了 01 串 $t$ 得到 01 串 $t'$，请你根据打乱后的结果还原出一个 $s$。

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

第二行，一个长为 $8n$ 的 01 串 $t'$。

outputFormat:
如果有解，输出一行，一个长度为 $n$ 的只含小写字母的字符串 $s$；否则，输出 `NIE`。

**如有多解，输出任意一组均可。**


title: [PA2021] Mopadulo

description:
给定一个长度为 $n$ 的序列 $a$，求有多少种方案可以将 $a$ 划分成若干个区间，使得每段区间所有数的和模 $10^9 + 7$ 的结果为偶数。

由于结果可能很大，你只需要求出结果对 $10^9 + 7$ 取模的值。

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

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

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


title: [PA2021] Sumy

description:
有 $n$ 条鱼，其中第 $i$ 条的质量为 $a_i$ 克。

$x$ 能吃掉 $y$ 当且仅当 $a_x > a_y$。

若 $x$ 吃了 $y$，$y$ 会消失，$a_x$ 会变为 $a_x + a_y$。

你可以随意指定吃鱼的顺序，直至留下一条鱼为止。

求每一条鱼是否可能被作为最后**唯一**的鱼留下。**若最终无法只剩下一条鱼，则每条鱼均不满足此条件。**

outputFormat: 一行，一个长度为 $n$ 的字符串 $s$，其中 $s_i = \text{T}$ 表示第 $i$ 条鱼满足上述条件，$s_i = \text{N}$ 表示第 $i$ 条鱼不满足上述条件。

hint:
#### 样例 #1 解释
下面用 $x \rightarrow y$ 表示 $x$ 吃 $y$。

留下 $2$ 号鱼的一种方案如下：$2 \rightarrow 1, 2 \rightarrow 3, 2 \rightarrow 4, 2 \rightarrow 5, 2 \rightarrow 6$。
#### 数据范围
对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$1 \leq a_i \leq 10^9$。


title: [PA2021] Wystawa

description:
给定长度为 $n$ 的序列 $a, b$。

你需要构造一个序列 $c$，构造方法为：

- 选择 $k$ 个 $i$，令 $c_i \leftarrow a_i$。
- 对于其他 $i$，令 $c_i \leftarrow b_i$。

求序列 $c$ 的最大子段和的最小值，并给出一种方案。

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

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

第三行，$n$ 个整数 $b_1, b_2, \cdots, b_n$。

outputFormat:
第一行，一个整数，表示序列 $c$ 的最大子段和的最小值；

第二行，一个长为 $n$ 的字符串 $s$，若令 $c_i \leftarrow a_i$，$s_i = \text{A}$；否则，$s_i = \text{B}$。

**如有多解，输出任意一组均可。**


title: [PA2021] Areny

description:
给定一张有向图，每个点至少有一条出边，每个点只可能被染成黑色或白色。

你需要对于所有 $1 \leq k \leq n$ 求出以下问题的答案：

- 初始状态下所有点均为白色。
- 每一次操作，Alice 先选择一个黑点 $1 \leq u \leq k$，Bob 必须从 $u$ 出边指向的点中选择一个将其染黑。
- Alice 和 Bob 在这张图上玩游戏，定义一个有序二元组 $(A, B)$ 是好的，如果 $A \neq B$ 且 Alice 从只有 $A$ 点为黑色的状态开始，无论 Bob 如何操作，$B$ 点均可以变成黑色。
- 求好的有序二元组的个数。

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

接下来 $n$ 行，其中第 $i$ 行先是一个整数 $l$，接下来 $l$ 个整数 $p_1, p_2, \cdots, p_l$，表示 $i$ 的出边指向的点。

outputFormat: 一行，$n$ 个整数，其中第 $i$ 个整数表示 $k = i$ 时的答案。

hint: 对于 $100\%$ 的数据，$2 \leq n \leq 2 \times 10^5$，$1 \leq l \leq 5 \times 10^5$，$n \leq \sum l \leq 5 \times 10^5$，**不保证无重边，但保证无自环**。


title: [PA2021] Ranking sklepów internetowych

description:
给定长为 $n$ 的**排列** $a$。

定义区间 $[l, r]$ 的权值如下：将区间内的数从小到大排序，设 $x$ 为区间长度（即 $r - l + 1$），$y$ 为区间中位数，则该区间的权值为 $x + 2y$。

求所有 $\frac{n(n + 1)}{2}$ 个区间中权值的最大值和最大值的个数。

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

中位数的定义：

以一个长为 $n$ 的**单调递增**的序列 $a$ 为例。

- 当 $n$ 为奇数，中位数为 $a_{\frac{n + 1}{2}}$。
- 当 $n$ 为偶数，中位数为 $\frac{a_{\frac{n}{2}} + a_{\frac{n}{2} + 1}}{2}$。

outputFormat: 一行，两个整数，表示权值的最大值和最大值的个数。

hint: 对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$1 \leq a_i \leq n$。


title: [yLOI2023] 分解只因数

description:
给定一个正整数 $n$，对 $n$ 分解质因数。

设 $n = p_1 \times p_2 \times p_3 \times \dots \times p_x$，其中 $p_i$ 均为质数。

如果 $p_i$ 均为奇数，则称 $n$ 为『只因数』。

现在，给出若干个 $n$，请你判断 $n$ 是不是『只因数』。

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

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

接下来 $T$ 行，每行一个整数，表示一组数据的 $n$。

outputFormat: 对每组数据，输出一行一个字符串。如果 $n$ 是『只因数』，请输出 `Yes`，否则输出 `No`。

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

本题共有 $10$ 个测试点。对第 $i$ 个测试点，$T = \max(1, i - 1)$。

- 对 $30\%$ 的数据，$n \leq 3$。
- 对 $50\%$ 的数据，$n \leq 10$。
- 另有 $10\%$ 的数据，$n$ 为奇数。
- 另有 $10\%$ 的数据，$n$ 为偶数。
- 对 $90\%$ 的数据，$n \leq 10^9$。
- 对 $100\%$ 的数据，$1 \leq T \leq 9$，$2 \leq n \leq 10^{18}$。

### 说明

本题共有两个附加样例文件，见题目附件中的 `ibvl.zip`。


title: 扔骰子问题 2

description:
有 $n$ 个六面骰子，投掷时，每个面朝上的概率均相同，且每个骰子的投掷结果相互独立。

现在投掷出这些骰子，请问所有骰子朝上的面的点数之和恰好为 $m$ 的概率是多少？

请你求出这个概率对 $998,244,353$ 取模的结果。

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

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

接下来 $T$ 行，每行两个整数，分别表示一组数据的 $n$ 和 $m$。

outputFormat: 输出一行一个整数，表示所有询问的答案的**按位异或和**。

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

对 $100\%$ 的测试点，保证 $1 \leq T \leq 6 \times 10^6$，$1 \leq n \leq 10^3$，$1 \leq m \leq 6 \times 10^3$。


title: 扔骰子问题 1

description:
有 $n$ 个六面骰子，投掷时，每个面朝上的概率均相同，且每个骰子的投掷结果相互独立。

现在投掷出这些骰子，请问恰好有 $m$ 个骰子的朝上面为一号面（仅有一个点的面）的概率是多少？

请你求出这个概率对 $998,244,353$ 取模的结果。

outputFormat:
共输出两行。

第一行输出一个仅含小写字母的字符串，表示『骰』这个字的汉语拼音（不含声调）。
第二行输出一行一个整数， 表示所有询问答案的**按位异或和**。

hint:
### 样例 1 解释

样例输出的第一行被抹去了，你应该用一个仅含小写字母的字符串替换它。

### 数据规模与约定

对 $100\%$ 的测试点，保证 $1 \leq T \leq 5 \times 10^6$，$m \leq n \leq 5 \times 10^6$，$n \geq 1$，$m \geq 0$。

### 评分说明

本题共两行输出，第二行输出错误得 $0$ 分，第二行输出正确但第一行输出错误的，得 $50$ 分。


title: 「GLR-R4」芒种

background:
  「晴云轻漾，熏风无浪，开樽避暑争相向」

---

  “高考周啊……”

  今天倒是没有抢场的压力，不过甚至没人敢出训练室，毕竟对面教学楼就是正在进行高考的考场。

  “我们明年说不定就在对面了。”虽然下午的训练结束，但今天食堂安排特殊，天依和阿绫还得在休息室里腻歪好一会儿。

  “阿绫，饿……”像是听不见食物以外的话题，天依躺在沙发上，手指绕着头发——绕着阿绫的头发，抱怨着。

  “来玩个游戏吧。”

---

  **芒种** 「冰苏打烦躁气泡都融化
　慵懒的风快趁虚而入吧」

description:
  *双重神经衰弱* 是一个极其考验记忆力的卡牌游戏，其规则如下。

  有 $n$ 种不同类型的卡牌，每种两张，初始时这 $2n$ 张牌全部倒扣在桌面上。两位玩家轮流操作，每次操作选择两张**不同的**牌**同时**翻起，这两张牌将对双方展示，此后：

- 若两张牌类型相同，则操作者得 $1$ 分，将这两张牌拿走。下一次操作由**当前操作者**继续进行。

- 否则，操作者将这两张牌扣回。下一次操作轮到**对方**进行。

  当所有牌全部被拿走时，游戏结束。

  两位玩家的目标都是最大化自己的最终得分。此外，在**双方同意**的情况下，两人可以选择和局。设和局时还剩下 $2n'$ 张牌，则双方各获得 $n'/2$ 分，游戏结束。为避免游戏无法结束的情况，我们认为：当选择和局同时是双方的最优选择**之一**时，双方会立即和局。

---

  现在，阿绫和天依想来玩玩这个游戏。因为太饿，负责摆牌的天依不小心把 $2n$ 张牌中的 $m$ 张牌牌面朝上地摆放了，**这 $m$ 张牌的的类型恰好两两不同**，双方悄悄记住了它们的类型和位置，并将它们扣回，然后开始游戏。我们假定天依和阿绫过目不忘且聪明绝顶，能够记住所有被展示过的牌（包括最初 $m$ 张牌）的类型和位置，也都会采取最优策略最大化自己的期望得分。作为先手方的阿绫想要知道自己的期望得分，你可以帮帮她吗？

  由于她们真的要在休息室腻歪好一会儿，所以你需要对 $T$ 组的 $(n,m)$ 分别求出答案。

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

接下来 $T$ 行，每行两个整数 $n,m$，分别表示该轮游戏中卡牌的类型数和双方预先翻起并扣回的卡牌张数。

outputFormat: 输出 $T$ 行，每行一个实数，表示该组数据的答案。当且仅当你的输出与标准答案的相对误差或绝对误差不超过 $10^{-6}$ 时，被视为正确。


title: 「DTOI-4」白的 Fibonacci

description:
定义 $F(k, n)$ 如下：

$$
F(k,n) =
\left \{
\begin{aligned}
&st_0\ && k = 1\ \land\ n = 0 \\
&st_1\ && k = 1\ \land\ n = 1 \\
&0\ && k > 1 \ \land \ n < 0 \\
&a \times F(k, n - 1) + b \times F(k, n - 2)\ && k = 1 \ \land\ n > 1 \\
&t_k \times F(k, n - 1) + s^n \times F(k - 1, n)\ && \text{otherwise}
\end{aligned}
\right.
$$

给定 $F$ 递推式的各项系数和 $k, n$，请你求出 $F(k, n) \bmod 998244353$ 的值。

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

第二行，五个整数 $st_0, st_1, a, b, s$；

第三行，$k - 1$ 个整数 $t_2, t_3, \cdots, t_k$。

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


title: [DMOI-R2] 风神瞳（Anemoculus）

description:
风起地有一颗大树，它有 $n$ 个节点，以 $1$ 号节点为根。

树上有 $m$ 个风神瞳，第 $i$ 个风神瞳位于节点 $a_i$ 上。

你想要收集这些风神瞳。于是请来了~~在大树旁边摸鱼的~~温迪帮忙。

一开始，你在树的根部的节点，也就是 $1$ 号节点上，每一秒钟，你可以从当前节点走到相邻的节点。或者，你可以请温迪帮忙，他会生成一个风场，你可以通过这个风场直接一次性向上走正好 $k$ 步（我们定义根节点到叶子结点的方向为『上』，即从深度较小的节点到深度较大的节点，换句话说，你可以从当前节点朝着深度更大的节点连续走 $k$ 步）。当你到达某个有风神瞳的节点上时，你就可以收集那个节点的风神瞳，收集不耗费时间。由于从树上跳下来会摔伤，你最后必须回到根节点。现在你有 $q$ 个问题，第 $i$ 个问题是你在 $t_i$ 秒内你最多可以收集到几个风神瞳。

inputFormat:
第一行四个正整数 $n,m,k,q$，含义如题目描述中所述。

接下来 $n - 1$ 行，每行两个正整数 $u,v$，表示结点 $u$ 和结点 $v$ 是相邻的。

接下来一行 $m$ 个互不相同的正整数，第 $i$ 个数表示 $a_i$，含义如题目描述中所述。

接下来 $q$ 行，其中第 $i$ 行有一个正整数 $t_i$，含义如题目描述中所述。

outputFormat: 对于 $q$ 次询问，每次询问输出一行，表示最多可以收集到几个风神瞳。

hint:
---
### 样例解释
#### 样例一
![](https://cdn.luogu.com.cn/upload/image_hosting/mz5mcnuo.png)

如图，其中加粗的点是有风神瞳的点。温迪~~很懒~~有事所以不准备帮你。
#### 样例二
这个样例除了温迪能让你一次性向上走两步和样例一没有区别。

---
### 数据范围

本题采用捆绑测试。

对于 $5\%$ 的数据，$m = 10$。

对于另外 $15\%$ 的数据，$m = 17$。

对于另外 $20\%$ 的数据，$k=1$。

对于 $100\%$ 的数据，$n \leq 2000$，$m \leq 500$，$q \le 1000$，$1\leq t_i \leq 2\times n$，$1\le a_i,u,v \le n$，$1 \leq k\le \min(dep-1,100)$，其中 $dep$ 表示树的深度，定义根节点的深度为 $1$。


title: [JRKSJ R7] Clock Paradox

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

一分钟后的出题人阻止了这个时刻的出题人写一个有趣的题目背景。

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

description:
给你一个字符串 $S$，设 $S=\overline{s_1s_2\dots s_n}$。

有一个字符串 $T$，初始时 $T=S$，你可以进行若干次操作，每次操作可以选取 $S$ 一个子串并插入到 $T$ 的任意位置。

你希望经过若干次操作后，$T=\overline{s_1s_1s_2s_2\dots s_ns_n}$，定义 $f(S)$ 为满足此条件所需的最少的操作次数。

此外，字符串 $S$ 还会发生一些改变。具体地，有 $q$ 次修改操作，每次修改操作会给出 $p$ 和 $\texttt{c}$，表示令 $s_p\gets \texttt{c}$。$\texttt{c}$ 表示任意一个小写字母，而并非 ASCII 为 $99$ 的字符。

你需要在最开始和每次修改后求出 $f(S)$ 的值。

inputFormat:
第一行一个整数 $q$ 表示修改次数。\
第二行仅由小写字母构成的字符串 $S$。\
接下来 $q$ 行，每行一个整数 $p$ 和一个小写字母 $\texttt{c}$ 表示一次修改。

outputFormat: 共有 $q+1$ 行，每行一个整数表示答案。

hint:
Idea：cyffff，Solution：cyffff，Code：cyffff，Data：cyffff

**Clock Paradox - WyvernP (Insane12.6)**

**本题输入输出文件较大，请使用恰当的输入输出方式。**

### 提示

称字符串 $A$ 是字符串 $S$ 的子串当且仅当存在 $1\le l\le r\le |S|$ 使得 $A=\overline{s_ls_{l+1}\dots s_{r}}$。

### 样例解释
所有修改前，$f(S)$ 的计算方法如下：

初始时，$S=T=\texttt{aabc}$。

第一次操作，选取 $S$ 的子串 $\texttt{aa}$，插入到 $T$ 的最前端，操作后 $T=\texttt{aaaabc}$。

第二次操作，选取 $S$ 的子串 $\texttt{bc}$，插入到 $T$ 的第 $5$ 个字符后，操作后 $T=\texttt{aaaabbcc}$，符合要求。

经过一次修改、两次修改后的 $S$ 分别等于 $\texttt{abbc}$ 和 $\texttt{abbb}$，这两次修改后 $f(S)$ 分别是 $2$ 和 $1$。
### 数据规模

本题采用捆绑测试。
| $\text{Subtask}$ | $\vert S\vert\le$ | $q\le$ | $\text{Score}$ |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $5$ | $0$ | $10$ |
| $2$ | $10^4$ | $10^4$ | $20$ |
| $3$ | $5\times10^5$ | $0$ | $20$ |
| $4$ | $5\times10^5$ | $5\times 10^5$ | $20$ |
| $5$ | $3\times10^6$ | $3\times 10^6$ | $30$ |

对于 $100\%$ 的数据，$1\le|S|\le3\times10^6$，$0\le q\le 3\times10^6$，保证 $S$ 仅由小写字母构成，保证 $\texttt{c}$ 为单个小写字母。


title: 【模板】双端队列 1

background: Aya 衷心祝愿大家不再因为 `std::deque()` 重蹈覆辙。

description:
请你实现 $m$ 个双端队列，支持如下的 $q$ 次操作：

- `push_back(a,x)`：在第 $a$ 个双端队列中从尾部插入一个元素 $x$；
- `pop_back(a)`：在第 $a$ 个双端队列中从尾部弹出一个元素。
- `push_front(a,x)`：在第 $a$ 个双端队列中从头部插入一个元素 $x$；
- `pop_front(a)`：在第 $a$ 个双端队列中从头部弹出一个元素。
- `size(a)`：查询第 $a$ 个双端队列的元素个数；
- `front(a)`：查询第 $a$ 个双端队列的队首元素；
- `back(a)`：查询第 $a$ 个双端队列的队尾元素；

对于 `pop_back`，`pop_front`，`front` 和 `back` 操作，若当前双端队列为空则不进行，直接跳过该次操作。

inputFormat:
输入的第一行是一个正整数 $q$，表示操作次数。

接下来 $q$ 行，每行先是一个字符串，保证为 `push_back` 或者 `pop_back` 或者 `push_front` 或者 `pop_front` 或者 `size` 或者 `front` 或者 `back` 之一。接下来是 $1$ 或 $2$ 个正整数，分别表示 $a$ 和 $x$。

outputFormat: 对于每个 `size` 或者 `front` 或者 `back` 操作，输出一行表示答案。

samples:
10
pop_back 2
push_back 1 1
push_front 1 3
push_front 2 2
push_front 2 3
pop_back 1
size 1
push_back 2 3
back 1
front 1


title: [IOI2021] 钥匙

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

### 由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。

description:
建筑师 Timothy 设计了一个新的密室逃脱游戏。

这个游戏里有 $n$ 个房间，房间从 $0$ 到 $n - 1$ 编号。最开始的时候，每个房间里都恰好有一把钥匙。每把钥匙都有一个类型，钥匙的类型是一个 $0$ 到 $n - 1$ 区间内的整数。第 $i$ 个房间里的钥匙类型是 $r[i]$。注意多个房间里可能会包含相同类型的钥匙，即$r[i]$ 的值不一定是两两不同的。

游戏里还有 $m$ 条**双向**的通道，通道从 $0$ 到 $m - 1$ 编号。第 $j$ 条通道连接了一对编号不同的房间 $u[j]$ 和 $v[j]$。同一对房间之间可能存在多条通道。

参与游戏的玩家需要收集钥匙和在不同的房间之间通过通道进行移动。 当玩家使用通道 $j$ 从房间 $u[j]$ 移动到 $v[j]$ ，或者反过来从 $v[j]$ 移动到 $u[j]$ 时，我们说玩家**通过**了通道 $j$。 只有当玩家收集到类型为 $c[j]$ 的钥匙时，玩家才可以通过通道 $j$。

在游戏的任意时刻，玩家可以在某个房间 $x$ 里执行以下两种操作：

- 收集房间 $x$ 里面的钥匙，钥匙的类型是 $r[x]$（除⾮对应类型的钥匙已经被收集过）。
- 通过通道 $j$，需要满足 $u[j] = x$ 或 $v[j] = x$，且玩家已经获得 $c[j]$ 类型的钥匙。

注意玩家收集过的钥匙可以一直使用，**永远不会被丢弃**。

最初玩家会在某个房间 $s$ **开始**游戏，不带任何钥匙。 如果玩家从房间 $s$ 开始，通过一系列上述描述的两种操作，能够到达房间 $t$，那么称房间 $t$ 是**从房间 $s$ 开始可以到达的**。

对于每一个房间 $i ~ ( 0 \le i \le n − 1)$，定义从房间 $i$ 出发能够到达的房间数为 $p[i]$。Timothy 想要知道满⾜ $p[i]$ 值最小的下标 $i$ 的集合。

inputFormat:
你要实现以下函数：

```cpp
std::vector<int> find_reachable(
	std::vector<int> r, std::vector<int> u,
	std::vector<int> v, std::vector<int> c
)
```

- $r$：⼀个⻓度为 $n$ 的序列。对于每⼀个 $i ~ ( 0 \leq i \leq n − 1)$，第 $i$ 个房间⾥的钥匙类型是 $r[i]$。
- $u, v$：两个⻓度为 $m$ 的序列。 对于每⼀个 $j ~ ( 0 \leq j \leq m − 1)$，第 $j$ 条通道连接了房间 $u[j]$ 和 $v[j]$。
- $c$：⼀个⻓度为 $m$ 的序列。对于每⼀个 $j ~ ( 0 \leq j \leq m − 1)$，通过通道 $j$ 需要⽤到的钥匙类型是 $c[j]$.

outputFormat: - 这个函数应该返回⼀个⻓度为 $n$ 的序列 $a$。对于 $0 \leq i \leq n − 1$ 中的 $i$，如果满⾜ $p[i] \leq p[j] ~ (0 \leq j \leq n − 1)$ 那么 $a[i]$ 的值为 $1$，否则 $a[i]$ 的值为 $0$。


title: [Ynoi2012] NOIP2015 充满了希望

description:
给一个长为 $n$ 的序列，有 $m$ 个操作，操作编号从 $1$ 到 $m$，每个操作为：

`1 x y`：将序列位置为 $x,y$ 的两个元素交换。

`2 l r x`：将序列区间 $[l,r]$ 内所有元素修改为 $x$。

`3 x`：查询序列 $x$ 位置的值。

现在有 $q$ 次查询，每次查询给出一个操作的区间 $[l,r]$：

先将序列中的元素全部置为 $0$，之后依次进行从 $l$ 到 $r$ 的所有操作，求出所有这些操作中所有 $3$ 操作的答案的和。

查询之间独立。

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

之后 $m$ 行，每行 $2$ 到 $4$ 个数，依次表示每个操作。

之后 $q$ 行，每行两个数 $l,r$，查询依次进行 $[l,r]$ 的所有操作，所有 $3$ 操作的答案的和。

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

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

对于 $10\%$ 的数据，满足 $1\le n,m,q\le 1000$。

对于 $40\%$ 的数据，满足 $1\le n,m,q\le 10^5$。

对于另外 $20\%$ 的数据，没有 $1$ 操作。

对于另外 $20\%$ 的数据，没有 $2$ 操作。

对于 $100\%$ 的数据，满足 $1\le n,m,q\le 10^6$，$1\le x\le 10^9$。


title: [Ynoi Easy Round 2021] TEST_68

description:
给定一棵 $n$ 个节点的树，第 $i$ 个点有一个权值 $a_i$。

对每个点 $x$，其的答案为其所在子树外的所有点中，选两个可以相同的点 $i,j$，$a_i$ 异或 $a_j$ 的最大值，如果选不出两个点，则认为 $x$ 的答案是 $0$。

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

之后一行 $n-1$ 个数，第 $i$ 个数表示 $i+1$ 节点的父亲节点 $j$，保证 $j<i+1$。

之后一行 $n$ 个元素，第 $i$ 个元素表示第 $i$ 个点的权值 $a_i$。

outputFormat: $n$ 行，每行一个数，其中第 $i$ 行的数表示第 $i$ 个节点对应的答案。

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

对于 $10\%$ 的数据，满足 $1 \le n \le 10^2$。

对于另外 $20\%$ 的数据，满足 $1 \le n \le 10^4$。

对于另外 $30\%$ 的数据，树构成一条链。

对于另外 $20\%$ 的数据，满足 $0 \le a_i \le 10^2$。

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


title: [Ynoi Easy Round 2021] TEST_152

description:
转转有一个操作序列$(l_i,r_i,v_i)$。

现在，有 $q$ 个询问 $l$,$r$。

每次询问，你初始有一个长度为 $m$ 的序列 $c$，初值全是 $0$。

现在我们从 $l$ 到 $r$ 执行这 $r-l+1$ 个操作。

每个操作是将 $c[l_i]$~$c[r_i]$ 赋值为 $v_i$。

询问所有操作结束后整个 $c$ 的序列所有数的和。

询问之间互相独立。

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

第 $2$~$n+1$ 行,每行 $3$ 个正整数，第 $i+1$ 行表示 $l_i$,$r_i$,$v_i$。

后面 $q$ 行，每行两个正整数，表示一次询问 $l$,$r$。

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

hint:
Idea：Ynoi，Solution：Ynoi，Code：Ynoi，Data：Ynoi

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

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

$ 1 \le l_i \le r_i \le m$

$0 \le v_i \le 2 \times 10^9$

$1 \le x_i \le y_i \le n$。


title: [Ynoi Easy Round 2021] TEST_136

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:
Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

样例解释：

第一个查询对应 $(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: [IOI2021] 喷泉公园

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

### 由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。但是你的代码需要声明 `void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b)` 函数。

具体的，以下是一种模板：
```cpp
#include <vector>

void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b);

int construct_roads(std::vector<int> x, std::vector<int> y) {
    // Code here...
}
```

由于洛谷技术限制，本题仅包含 IOI 官方数据的部分测试点。

description:
在附近的一个公园里，有 $n$ 座**喷泉**，编号为从 $0$ 到 $n - 1$。我们把喷泉看成是二维平面上的点。也就是说，喷泉 $i ~ (0 \leq i \leq n - 1)$ 是一个点 $(x _ i, y _ i)$，这里 $x _ i$ 和 $y _ i$ 是**偶数**。喷泉的位置各不相同。

建筑师 Timothy 受雇来规划一些**道路**的建设，以及每条道路对应的长椅的摆放。每条道路都是一个长度为 $2$ 的**横向**或**纵向**的线段，其端点是两座不同的喷泉。游客应该能够沿着它们即可在任意两座喷泉之间互相抵达。在最开始时，公园里没有任何道路。

对于每条道路，都要在公园里摆放恰好一个长椅，并将其**分配给**（也就是面朝）这条道路。每个长椅必须摆放在某个点 $(a, ~ b)$ 上，这里 $a$ 和 $b$ 都是**奇数**。所有长椅的位置必须都是**不同的**。在 $(a, ~ b)$ 处的长椅，只能分配给两个断电均为 $(a - 1, ~ b - 1), (a - 1, ~ b + 1), (a + 1, ~ b - 1)$ 和 $(a + 1, ~ b + 1)$ 其中之一的道路。举例来说，在 $(3, ~ 3)$ 处的长椅只能分配给下面四条线段所表示的道路之一：$(2, ~ 2), - (2, ~ 4), ~ (2 , ~ 4) - (4, ~ 4), ~ (4, ~ 4) - (4, ~ 2), ~ (4, ~ 2) - (2, ~ 2)$。

请帮助 Timothy 判断一下，能否在满足上述所有要求的前提下，造出所有道路，并摆放和分配长椅。如果这能做到，请给他一个可行的解决方案。如果有多个满足所有要求的方案，你可以报告其中的任意方案。

inputFormat:
你要实现以下函数：

```cpp
int construct_roads(std::vector<int> x, std::vector<int> y)
```
- $x, ~ y$: 长度为 $n$ 的两个数组。对所有 $i ~ (0 \leq i \leq n - 1)$，喷泉 $i$ 是一个点 $(x[i], y[i]$，这里 $(x[i], y[i])$ 都是偶数。
- 如果存在某个建设方案，函数应当调用 `build`（参见下文）恰好一次来报告建设方案，并紧接着返回 $1$。
- 否则，函数应当返回 $0$，并且不做 `build` 的任何调用。
- 该函数将被调用恰好一次。

你实现的函数可以调用下面的函数，以提供一个可行的道路建设与长椅摆放方案。
```cpp
void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b)
```

- 设 $m$ 为建设方案中道路的个数。
- $u, v$: 长度为 $m$ 的两个数组，表示要建设的道路。这些道路的编号为从 $0$ 到 $m - 1$。对所有的 $j ~ (0 \leq j \leq m - 1)$，道路 $j$ 要连接喷泉 $u[j]$ 和 $v[j]$。每条道路必须是长度为 $2$ 的横向或纵向线段。任意两条不同的道路，最多只能有一个公共端点（某个喷泉）。这些道路在建成之后，必须能够沿着它们就可以在任意两个喷泉之间相互抵达。
- $a, b$: 长度为 $m$ 的两个数组，表示长椅。对所有的 $j ~ (0 \leq j \leq m - 1)$，将在 $(a[j], b[j])$ 处摆放一个长椅，并且分配给道路 $j$。不同的长椅不能摆放在同一位置。

hint:
**例 1**

考虑如下调用：
```cpp
construct_roads([4, 4, 6, 4, 2], [4, 6, 4, 2, 4])
```

这意味着总共有 $5$ 座喷泉：

- 喷泉 $0$ 坐落在 $(4, 4)$ 处。
- 喷泉 $1$ 坐落在 $(4, 6)$ 处。
- 喷泉 $2$ 坐落在 $(6, 4)$ 处。
- 喷泉 $3$ 坐落在 $(4, 2)$ 处。
- 喷泉 $4$ 坐落在 $(2, 4)$ 处。

可以建造下面这样 $4$ 条道路，其中每条道路连接两座喷泉，并且摆放着对应的长椅。

| 道路编号 | 道路所连接的喷泉编号 | 所分配的长椅的位置 |
| :----------: | :----------: | :----------: |
| $0$ | $0, 2$ | $(5, 5)$ |
| $1$ | $0, 1$ | $(3, 5)$ |
| $2$ | $3, 0$ | $(5, 3)$ |
| $3$ | $4, 0$ | $(3, 3)$ |

该方案对应下图：

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

为报告此方案，`construct_roads` 应做如下调用：

```cpp
build([0, 0, 3, 4], [2, 1, 0, 0], [5, 3, 5, 3], [5, 5, 3, 3])
```

随后它应当返回 $1$，

注意，在这个例子中，有多个满足要求的方案，它们都被视为正确。

**例 2**

考虑如下调用：

```cpp
construct_roads([2, 4], [2, 6])
```

喷泉 $0$ 坐落在 $(2, 2)$ 处，而喷泉 $1$ 坐落在 $(4, 6)$ 处。由于不可能建造出满⾜要求的道路，
`construct_roads` 应当返回 $0$，并且不做 `build` 的任何调⽤。

**约束条件**

- $1 \leq n \leq 2 \times 10 ^ 5$
- $2 \leq x[i], y[i] \leq 2 \times 10 ^ 5$
- $x[i], y[i]$ 都是偶数。
- 任意两座喷泉的位置都不相同。

**子任务**

1. （$5$ 分）$x[i] = 2$
2. （$10$ 分）$2 \leq x[i] \leq 4$
3. （$15$ 分）$2 \leq x[i] \leq 6$
4. （$20$ 分）至多只有一种道路建设方案，能够让游客在任意两座喷泉之间沿着这些道路即可抵达。
5. （$20$ 分）任意四座喷泉都不会构成某一个 $2 \times 2$ 正方形的四个顶点。
6. （$30$ 分）没有额外的约束条件。


title: [洛谷 202406GESP 模拟 一级] 小洛的幸运数字

description:
小洛得到了 $n$ 个整数，他认为，“个位数是 $3$，或者是 $3$ 的倍数的整数”是不好的，应当被排除。

请编写一个程序，将不好的数字排除掉后，计算剩余数字的总和，以及剩下的数字数量。

inputFormat:
- 第一行包含一个整数 $n$（$1 \leq n \leq 1000$）。
- 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（每个整数 $0 \leq a_i \leq 10^4$）。

outputFormat: 输出两个整数，用空格隔开。第一个整数表示这些数字中个位数不是 $3$ ，且不是 $3$ 的倍数的数字的总和，第二个整数表示这些数字的个数。

hint:
输入的 $5$ 个数字分别是 $12, 23, 35, 47, 50$ 。

其中 $23$ 的个位数是 $3$，$12$ 是 $3$ 的倍数，所以这两个数不符合条件。


title: [洛谷 202406GESP 模拟 一级] 明日复明日

description:
给定一个日期，要求输出它的后一天的日期。假设今年不是闰年。

输入包括两个整数，分别表示月份和日期。你需要编写一个程序来计算并输出这个日期的后一天。如果输入的日期是年末的最后一天（12 月 31 日），则需要输出下一年的 1 月 1 日。

inputFormat:
输入只有一行，包括两个整数，分别表示月份 $M$ 和日期 $D$ 。

- $ M $ 是一个整数，表示月份（$1 \leq M \leq 12$）。
- $ D $ 是一个整数，表示日期（$1 \leq D \leq 31$，且不大于当月的最大天数）。

outputFormat: 输出一行，包含两个整数，分别表示后一天的月份和日期。

hint:
## 提示

- 每个月份的天数如下：
  - 1 月：31 天
  - 2 月：28 天（不考虑闰年）
  - 3 月：31 天
  - 4 月：30 天
  - 5 月：31 天
  - 6 月：30 天
  - 7 月：31 天
  - 8 月：31 天
  - 9 月：30 天
  - 10 月：31 天
  - 11 月：30 天
  - 12 月：31 天

- 输入保证为有效的日期，不需要进行日期有效性的验证。

## 例子解释

对于输入样例 1，3 月 14 日的后一天是 3 月 15 日。

对于输入样例 2，4 月 30 日的后一天是 5 月 1 日。

对于输入样例 3，12 月 31 日的后一天是下一年的 1 月 1 日。


title: [Ynoi2078] 《How to represent part-whole hierarchies in a neural network》阅读报告（更新中...）

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:
Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $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: [Ynoi2003] 赫露艾斯塔

description:
给定 $n$ 个互不相同的点 $(x_i,y_i),\;1\le i\le n$，$m$ 个集合 $S_j=\{(x_i,y_i)\mid A_jx_i+B_jy_i+C_j>0\},\;1\le j\le m$。

你需要找出一个 $1,2,\dots,m$ 的排列 $p_1,\dots,p_m$，使得 $|S_{p_1}|+\sum\limits_{i=2}^m |S_{p_i}\oplus S_{p_{i-1}}|\le M$。

$M$ 是给定的常数，$A\oplus B$ 表示 $(A\cup B)-(A\cap B)$。

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

接下来 $n$ 行每行两个整数表示 $x_i,y_i$；

接下来 $m$ 行每行三个整数表示 $A_j,B_j,C_j$。

outputFormat: 输出 $m$ 行，依次表示 $p_1,\dots,p_m$。


title: [Ynoi2079] riapq

description:
给出排列 $a_1,\dots,a_n$，你需要维护序列 $b_1,\dots,b_n$，初值为 $0$。

共 $m$ 次操作：

修改操作：给出 $l,r$，对每个 $(i,j)$ 满足 $l\le i\le j\le r,\;a_i\le a_j$，将 $b_j$ 增加 $1$；

查询操作：给出 $x$，查 $b_x$。

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

第二行 $n$ 个整数依次表示 $a_1,\dots,a_n$；

接下来 $m$ 行，每行 $1,l,r$ 或 $2,x$ 表示修改操作或查询操作。

输入的所有数值为整数。

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

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

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

$1\le n,m\le 2\times 10^5$；

$1\le a_i\le n$，$a_i$ 互不相同；

$1\le l\le r\le n$；

$1\le x\le n$。


title: [蓝桥杯 2022 国 C] 填空问题(缺少prime.txt)

description:
## 试题 A: 斐波那契与 7

### 【问题描述】

斐波那契数列的递推公式为 ： $F_n = F_{n−1} + F_{n−2}$，其中 $F_1 = F_2 = 1$。

请问，斐波那契数列的第 $1$ 至 $202202011200$ 项（含）中，有多少项的个位是 $7$。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

## 试题 B: 小蓝做实验

### 【问题描述】

小蓝很喜欢科研，他最近做了一个实验得到了一批实验数据，一共是两百万个正整数。如果按照预期，所有的实验数据 $x$ 都应该满足 $10^7 ≤ x ≤ 10^8$。但是做实验都会有一些误差，会导致出现一些预期外的数据，这种误差数据 $y$ 的范围是 $10^3 ≤ y ≤ 10^{12}$。由于小蓝做实验很可靠，所以他所有的实验数据中 $99.99\%$ 以上都是符合预期的。小蓝的所有实验数据都在 primes.txt 中，现 在他想统计这两百万个正整数中有多少个是质数，你能告诉他吗？

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat:
您可以通过提交答案文件的方式进行提交。你需要将你的答案放在 `1.out` 和 `2.out` 中，其中 `1.out` 对应 A 题的答案，`2.out` 对应 B 题的答案。

输入文件包含一个字符，代表题目编号（`A` 或 `B`），你需要输出对应的答案。

以下模板供参考：

```cpp
#include<bits/stdc++.h>
using namespace std;

char pid;
int main() {
    cin >> pid;
    if(pid == 'A')
        puts("Answer for Problem A");
    else
        puts("Answer for Problem B");
    return 0;
}
```

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [Ynoi2003] 戌亥彗星

description:
定义一个图为海胆， 如果它满足以下条件：

1. 是一个连通图
2. 包含恰好一个简单环
3. 除了环以外的点每个点度数不超过 $2$

有一张图，有 $n$ 个点，$n$ 条边，第 $i$ 条边连接 $u_i$ 和 $v_i$（不保证联通）。

定义一张图的区间子图 $[l,r]$ 为 $(V',E'),E'=\{(u_i,v_i)|l\leq i\leq r\},V'=\{u_i|l\leq i\leq r\} \cup \{v_i|l\leq i\leq r\}$，也就是说，这个区间子图包含且仅包含区间中的边和所有在区间中一条边上的点。

现在有 $q$ 次询问，每次给定一个区间 $l,r$，求 $l,r$ 有多少个子区间 $[l',r'](l\leq l'\leq r'\leq r)$ 满足原图的 $[l',r']$ 区间子图是个海胆。

**对于条件 2 的补充说明：**

1. 简单环的定义是 可以从任一点开始经过一些不重复的边回到起点，途中经过了至少一条边，且除了起点和终点相同以外不经过重复点，例如 $1-2-3-1$ 是简单环，两条 $1-2$ 的边是简单环，但只有一个点的时候不是, $1-2-3-4-5-3-1$ 也不是，（这里的环用某一个点开始的路径表示）。
2. 条件 $2$ 要求除了环边以外不存在边两端都在这个环上。

inputFormat:
第一行一个整数 $n$，表示点数和边数。

接下来 $n$ 行，每行两个整数 $u_i,v_i$ 表示一条边。

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

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

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


title: [Ynoi2003] 雾雨魔理沙

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

**在提交本题前请务必仔细阅读以下内容。**

本题只支持 C++ 语言提交（建议使用 C++14，请不要使用 C++14 (GCC9)）。

由于洛谷特殊的交互机制，在提交本题时，请去掉代码中的 ```#include "count.h"``` 语句，并将下发文件 **`count_.h`** （注意并不是 `count.zip` 里的 `count.h`）中的内容粘贴到代码最开头，然后提交。

如果您无法打开 `count_.h`，那么可以复制下面的内容。

```cpp
#ifndef CIRCLE_H
#define CIRCLE_H
#include<vector>
struct info{
  unsigned val;
  unsigned poi[2];
};
const info emptyinfo=info{0,(unsigned)-1,(unsigned)-1};
info MR(info a,info b);
info MC(info a,info b);
void init(int T,int n,int q,std::vector<int>dad,std::vector<info>ve,int M);
bool isempty(info a);
info ask(int x,int d);

#endif
```

如果您在提交本题时出现了任何意外的情况，请咨询管理员。

description:
给出五元组 $(T, I, S_V, S_E, \iota)$，其中：

- $T$ 是一棵 $n$ 个点的有根树 $T = (V, E)$，其中 $V$ 为 $T$ 的点集，$E$ 为 $T$ 的边集。树的节点被编号为 $1, 2, \ldots, n$，其中根节点编号为 $1$。
- $I$ 是一个集合，集合中的元素称作**信息**。其中有两个不同的特殊元素：单位元 $\epsilon$ 和不合法信息 $\bot$。

对于一般的信息，其都具有**点集合**和**边集合**两个属性。特别的，对于单位元，其只有边集合的属性，而对于不合法信息，其没有以上两种属性。

- 对于信息 $o \in I \setminus \{ \epsilon, \bot \}$，$o$ 的**点集合**是 $V$ 的一个二元子集，记作 $S_V(o)$，满足 $S_V(o) \subseteq V$ 且 $\lvert S_V(o) \rvert = 2$。其中，两个集合 $A, B$ 的差 $A \setminus B$ 被定义为 $A \setminus B = \{ x \in A \hspace{3mu}\vert\hspace{3mu} x \notin B \}$。
- 对于信息 $o \in I \setminus \{ \bot \}$，$o$ 的**边集合**是 $E$ 的一个子集，记作 $S_E(o)$，满足 $S_E(o) \subseteq E$。规定单位元的边集合为空，也即 $S_E(\epsilon) = \varnothing$。
- 对于树上的任何一条边 $e \in E$，记 $e = (u, v)$，存在一个关于 $e$ 的信息 $\iota(e) \in I$，它以其端点为点集合、自身为边集合，即 $S_V(\iota(e)) = \{ u, v \}$、$S_E(\iota(e)) = \{ e \}$。

信息有两种合并的方式，分别记作 $R$ 和 $C$。对于 $\forall a, b \in I$，记 $r = R(a, b), c = C(a, b)$，满足 $r, c \in I$，则：

- 单位元和任何信息合并都得到对方。也即，如果 $a = \epsilon$，那么 $r = c = b$；如果 $b = \epsilon$，那么 $r = c = a$。
- 不合法信息和任何信息合并都得到不合法信息。也即，如果 $a = \bot$ 或者 $b = \bot$，那么 $r = c = \bot$。
- 对于剩下的情况，如果两个信息的**边集合**的交集非空，或者**点集合**的交集的大小不为 $1$，则合并得到不合法信息。也即，如果 $S_E(a) \cap S_E(b) \ne \varnothing$ 或 $\lvert S_V(a) \cap S_V(b) \rvert \ne 1$，则 $r = c = \bot$。
- 否则，有
  $$ S_E(r) = S_E(c) = S_E(a) \cup S_E(b) \text{,} $$
  $$ S_V(r) = S_V(a) \text{,} $$
  $$ S_V(c) = S_V(a) \oplus S_V(b) \text{,} $$
  其中 $\oplus$ 表示集合的对称差运算，也即 $A \oplus B = (A \cup B) \setminus (A \cap B)$。

定义 $T$ 中两个点的树上距离为树上以两个点为端点的唯一简单路径经过的边数。

给出评分参数 $M$ 和 $q$ 次询问，每次询问给出树上的一个点 $u$ 和一个非负整数 $d$。记点集 $X$ 为 $T$ 中所有与 $u$ 的树上距离不超过 $d$ 的点构成的集合，又记边集 $Y = \{ (a, b) \in E \hspace{3mu}\vert\hspace{3mu} a, b \in X \}$ 为 $X$ 内部的边集。可以证明，从 $\epsilon$ 和所有 $\iota(e)$（$e \in E$）出发，总是能通过有限次 $R, C$ 的调用得到信息 $o \ne \bot$ 满足 $S_E(o) = Y$。

每组询问中，你需要在 $R$ 和 $C$ 的调用次数总和不超过 $M$ 的限制下构造出一个满足这样的要求的信息 $o$。特别地，如果 $d = 0$，则直接返回单位元 $\epsilon$ 即可。

----

**【实现细节】**

请确保你的程序开头有 `#include "count.h"`。

头文件 `count.h` 中实现了如下内容：

1. 定义了信息对应的数据类型 `info`；
2. 定义了 $\epsilon$ 所对应的 `info` 类型常量 `emptyinfo`，你可以在程序中直接使用。
3. 定义并实现了以下两个信息合并函数，你可以在程序中直接调用：

   ```cpp
   info MR(info a,info b);
   info MC(info a,info b);
   ```

   - 两个函数分别返回 $R(a, b)$ 与 $C(a, b)$ 对应的信息。

   **你需要保证调用 $\boldsymbol{R(a, b)}$ 与 $\boldsymbol{C(a, b)}$ 时结果不为 $\boldsymbol{\bot}$，否则程序可能会出现异常行为。**
4. 定义并实现了判定一个信息是否为单位元的函数，你可以在程序中直接调用：
   ```cpp
   bool isempty(info a);
   ```
   - 这个函数返回真当且仅当 $a$ 为单位元。

可以查看参考交互库了解更多实现细节。

**你不需要，也不应该实现主函数。** 你需要实现如下几个函数：

```cpp
void init(int T, int n, int q, vector<int> fa, vector<info> e, int M);
```

- `T` 表示测试点编号，`n` 表示树的点数，`q` 表示询问数，`M` 表示该测试点的评分参数。
- `fa` 和 `e` 的长度均为 $n - 1$。对于 $0 \le i < n - 1$，$fa[i]$ 和 $i + 2$ 为第 $i$ 条边 $e_i$ 的两个端点，$e[i]$ 为题目描述中提到的 $\iota(e_i)$ 所对应的 `info` 类型元素。数据保证 $fa[i]$ 小于 $i + 2$。

```cpp
info ask(int u, int d);
```

给出一个询问，参数的意义见题目描述。你需要在函数结束时返回一个满足题设条件的信息。

最终测试时，在每个测试点，交互库会**恰好**调用一次 `init` 函数，随后调用 $q$ 次 `ask`函数。交互库会使用特殊的实现方式，单个 `info` 类型的变量会恒定消耗 $12$ 字节内存，**这与下发的参考交互库不同**。为保证程序运行时内存使用在题目限制内，你需要保证运行过程中没有过多的 `info` 类型变量同时存在。

保证在满足调用次数限制且不进行 `isempty` 函数调用的情况下，最终测试的交互库运行所需的时间不超过 0.6 秒，交互库本身所消耗的内存不超过 16 MiB。保证在只执行 ${10}^8$ 次 `isempty` 函数调用的情况下，最终测试的交互库运行的时间不超过 0.25 秒。

在下发文件中包含一个名为 `count.cpp` 的文件，作为示例程序，选手可以在此基础上继续实现本题。在下发文件中还额外包含一个名为 `count_backup.h` 的备份文件，我们保证其与 `count.h` 文件完全相同。

----

**【测试程序方式】**

本题目录下提供了两个交互库的参考实现 `grader.o`、`checker.o`，其为两个不同的交互库编译产生的可链接文件。最终测试时所用的交互库实现与该实现有不同，因此选手的解法**不应依赖交互库的具体实现**，同时也不应该依赖 `count.h` 中 `info` 类型的具体实现。

你需要修改下发的 `count.h` 来帮助进行链接。具体的，在将源代码 `count.cpp` 和程序 `grader.o` 进行链接的时候，你需要注释掉 `count.h` 代码的第 5 行，并保留第 4 行的代码。链接 `checker.o` 方法类似，需要注释掉 `count.h` 代码的第 4 行，并保留第 5 行的代码。选手可以对 `count.h` 的实现自行修改来实现不同程序的编译。

修改后，选手可以在本题目录下使用如下命令编译得到可执行程序：

```bash
g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o grader.o -o count
g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o checker.o -o count
```

其中第一行命令会编译当前 `count.cpp` 后与 `grader.o` 链接起来，生成可执行文件 `count`，第二行命令则会编译当前 `count.cpp` 后与 `checker.o` 链接起来，生成可执行文件 `count`。

按上述方法编译得到的可执行文件 `count`，其运行方式如下：

- 可执行文件将从标准输入读入以下格式的数据：
  - 第一行四个整数 $id, n, q, M$，分别表示测试点编号、树的点数、询问数和评分参数；
  - 第二行 $n - 1$ 个整数 $p_2, p_3, \ldots, p_n$，分别表示 $2$ 至 $n$ 的父亲节点编号，在本地调试时你需要保证 $\forall i \in [2, n]$，$p_i < i$；
  - 接下来 $q$ 行每行两个整数 $u, d$，描述一次询问。
- 读入之后，交互库会进行测试。如果你的程序不满足交互库限制，其会在输出中返回对应的错误信息。否则，对于链接的可执行文件，其输出如下：
  - 总共一行三个整数 $C_1, C_2, C_3$，其中：
    - $C_1$ 表示程序在 `init` 函数中调用交互库函数的总次数；
    - $C_2$ 表示程序在运行过程中调用交互库函数的总次数；
    - $C_3$ 表示程序在 $q$ 次 `ask` 函数中调用交互库函数的次数的最大值。
    - 对于上述三个统计量，我们只会计入 `MR`、`MC` 函数的调用次数，而不会计入 `isempty` 函数的调用次数。
- 在链接不同文件的时候，其能够进行的检查也不同，具体地：
  - `grader.o`：其在运行时不会检查 `ask` 函数返回的信息是否正确，但可以帮助选手判断交互操作是否符合要求。这份程序运行时间最接近评测时的交互库，因此选手可以利用该程序测试运行速度，但不保证程序正确性。
  - `checker.o`：其在运行时会检查 `ask` 函数返回的信息是否正确，也可以帮助选手判断交互操作是否符合要求。同时其会检查 `ask` 函数返回的信息是否正确。这份程序可以进行答案正确性的检查。

选手在调试时需要保证输入可执行文件 `count` 的数据满足上述输入格式，否则不保证输出结果正确。

inputFormat: 见【测试程序方式】。

outputFormat: 见【测试程序方式】。

hint:
Idea：zx2003，Solution：zx2003，Code：zx2003，Data：zx2003

**【评分方式】**

最终评测**只会**收取 `count.cpp`，修改选手目录下其他文件不会对评测结果产生影响。**注意：**

- **未初始化的 `info` 类型的变量不保证是 `emptyinfo`。**
- **请不要尝试访问或修改 `info` 类型的成员变量，否则将被视为攻击交互库。**
- **请不要在 `init` 函数调用之前调用 `MR` 和 `MC` 函数，否则可能会发生未定义行为。**
- **你只能访问自己定义的变量和交互库返回的 `info` 类型变量，尝试访问其他空间将可能导致编译错误或运行时错误。**

**本题首先会受到和传统题相同的限制**，例如编译错误会导致整道题目得 0 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 0 分等。

在上述条件以外，在一个测试点中，若程序执行了非法的函数调用或询问操作中给出了错误回答，该测试点将会获得 0 分。否则，记 $C_1, C_3$ 分别表示你的程序在 `init` 函数中调用交互库函数的次数，和你的程序在所有 $q$ 次 `ask` 函数中调用交互库函数的次数的最大值。如果 $C_1 \le 3 \cdot {10}^7$ 且 $C_3$ 不超过该测试点的评分参数 $M$，你将获得该测试点的分数，否则你无法获得该测试点的分数。注意：计算 $C_1, C_3$ 时只会计入 `MR`、`MC` 函数的调用次数，而不会计入 `isempty` 函数的调用次数。

----

**【样例 \#1】**

见附件中的 `count/count1.in` 与 `count/count1.ans`。

----

**【样例 \#2】**

见附件中的 `count/count2.in` 与 `count/count2.ans`。

该组样例满足数据范围中的特殊性质 A。

----

**【样例 \#3】**

见附件中的 `count/count3.in` 与 `count/count3.ans`。

该组样例满足数据范围中的特殊性质 B。

----

**【样例 \#4】**

见附件中的 `count/count4.in` 与 `count/count4.ans`。

----

**【数据范围】**

对于所有测试点，$1 \le n \le 2 \times {10}^5$，$1 \le q \le {10}^6$；每组询问中，有 $1 \le u \le n$，$1 \le d \le n - 1$。

| 测试点   | $n=$              | $q=$            | 特殊性质 | $M=$  |
|:-----:|:-----------------:|:---------------:|:----:|:-----:|
| $1$   | $1000$            | $10^4$          |      | $500$ |
| $2$   | $2000$            | $10^4$          |      | $500$ |
| $3,4$ | $10^5$            | $10^6$          | A    | $5$   |
| $5,6$ | $6 \times 10^4$   | $6\times 10^4$  | B    | $50$  |
| $7$   | $6 \times 10^4$   | $6 \times 10^4$ | B    | $5$   |
| $8$   | $10^5$            | $10^5$          | B    | $5$   |
| $9$   | $7500$            | $5 \times 10^4$ | C    | $500$ |
| $10$  | $10^4$            | $5 \times 10^4$ |      | $500$ |
| $11$  | $1.5 \times 10^4$ | $5 \times 10^4$ |      | $500$ |
| $12$  | $2 \times 10^4$   | $5 \times 10^4$ |      | $50$  |
| $13$  | $2.5 \times 10^4$ | $5 \times 10^4$ |      | $5$   |
| $14$  | $3 \times 10^4$   | $10^5$          |      | $5$   |
| $15$  | $6 \times 10^4$   | $10^6$          | D    | $5$   |
| $16$  | $6 \times 10^4$   | $10^6$          |      | $5$   |
| $17$  | $8 \times 10^4$   | $10^6$          |      | $5$   |
| $18$  | $10^5$            | $10^6$          |      | $5$   |
| $19$  | $1.5 \times 10^5$ | $10^6$          |      | $5$   |
| $20$  | $2 \times 10^5$   | $10^6$          |      | $1$   |

特殊性质 A：保证 $\forall i \in [1, n - 1]$，编号为 $i + 1$ 的点的父节点为 $i$。
特殊性质 B：保证所有询问均满足 $u = 1$。
特殊性质 C：保证所有询问均满足 $d \le 100$。
特殊性质 D：保证所有询问均满足 $d \ge 1000$。


title: 「DTOI-2」星之灵

background: >苍渊一点灿，仙凝一点灵。

description:
星之灵可以对你说 $n$ 句话，你需要对其做记录。

每句话可能是一个不等于 $\texttt{CapsLock}$ 的字符串，也可以是一个命令 $\texttt{CapsLock}$，其作用是控制星之灵说出的所有字母的大小写，当说出一次 $\texttt{CapsLock}$ 时，之后说出的所有小写字母均需变为大写，大写字母均需变为小写，第二次说出 $\texttt{CapsLock}$ 时又变为正常，以此类推。特别地，对于星之灵说出的 $\texttt{CapsLock}$ 命令，你无须记录。

星之灵将会不断重复说出这 $n$ 句话，且不改变顺序，而且他有 $q$ 次询问，每次询问都请你告诉星之灵，你记录的第 $x$ 句话是什么。

### 简要题意

重复在键盘上输入 $n$ 个字符串，若字符串为 $\texttt{CapsLock}$ 则之后所有字符串大写转小写，小写转大写，第二次出现 $\texttt{CapsLock}$ 时变为正常。最开始输入的字母大小写为正常，有 $q$ 次询问，每次问第 $x$ 个打入的字符串是什么（不计算 $\texttt{CapsLock}$）。

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

第一行一个整数 $n$。

接下来一行 $n$ 个字符串，用空格隔开，表示星之灵说的话。

第三行一个整数 $q$，表示星之灵的询问次数。

接下来 $q$ 行，每行一个正整数 $x$。

outputFormat: 对于每组询问，输出一行一个字符串，表示记录的第 $x$ 句话。

samples:
5
CapsLock CapsLock a CapsLock B
4
1
2
3
4

samples:
YOhAwuwWhu
YxhXpGFXTU
cVhkBOcFnh
YOhAwuwWhu
YOhAwuwWhu
cVhkBOcFnh
EhuqjPYhNY
AceSmixHlR
qWJgtStfNy
YOhAwuwWhu

hint:
### 样例 #1 解释

明显地，两次 $\texttt{CapsLock}$ 可以抵消，第三次 $\texttt{CapsLock}$ 对后面的字母起效果。则 $1,2,3,4$ 次分别为 $a,b,A,B$。

### 数据范围

| $\textbf{Subtask}$ | $n,q \le$ | $x\le $ | $\textbf{特殊性质}$ | 分值 |
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
| $1$ | $10$ | $100$ | $\texttt{A}$ | $30$ |
| $2$ | $10^4$ | $10^5$ | / | $30$ |
| $3$ | $10^5$ | $10^{18}$ | / | $40$ |

对于所有数据，$1 \leq n,q \leq 10^5,1 \leq x \leq 10^{18}$

性质 $\texttt{A}$：星之灵说的话中不存在 $\texttt{CapsLock}$。

数据保证星之灵说的话中至少存在一个非 $\texttt{CapsLock}$ 的字符串，任意字符串的长度 $\le 10$，且星之灵的话中只有字符串和 $\texttt{CapsLock}$。

所有字符串不为空且仅包含大小写字母。


title: [Ynoi2078] 《A theory of consciousness from a theoretical computer scienceperspective: Insights from the Conscious Turing Machine》阅读报告（更新中...）

background: ## 警告：滥用本题将被封号。

description:
给定一个长度 $n$ 的序列 $a_1,\dots,a_n$，需要进行 $m$ 次操作，操作共有三种类型：

操作 1：给定 $l,r,x$，先新建一个数组 $b$ 满足 $b_i=a_i$，之后将 $a_x,\dots,a_{x+r-l}$ 同时修改为 $b_l,\dots,b_r$；

操作 2：给定 $l,r$，将 $a_l,\dots,a_r$ 同时修改为除以 $2$ 下取整后的值；

操作 3：给定 $l,r$，求 $a_l,\dots,a_r$ 的和。

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

接下来一行 $n$ 个整数表示序列 $a_1,\dots,a_n$。

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

接下来 $m$ 行，每行表示一个操作：

`1 l r x` 表示操作 1；

`2 l r` 表示操作 2；

`3 l r` 表示操作 3。

outputFormat: 对每个操作 3，输出一行，包含一个整数，表示答案。

hint:
对于 $100\%$ 的数据，满足 $1\le n\le 3\cdot 10^6$，$1\le m\le 3\cdot 10^6$。

序列的初值满足 $1\le a_i\le 10^9。$

对每个操作满足 $1\le l\le r\le n$。

对每个操作 1 满足 $1\le x\le x+r-l+1\le n$。

以上所有数值为整数。


title: 「PEOI Rd1」寻宝（treasure）

description:
有一天 wrzSama 在寻宝，突然他掉到了一个神奇的房间里。这个房间里有 $n$ 个机器，第 $i$ 个机器可以生产 $2^i$ 个钻石。

具体地，wrzSama 可以用 $a_i$ 的时间开动第 $i$ 个机器，让它生产 $2^i$ 个钻石。这些机器有个很特殊的性质，每当他用一次第 $i$ 个机器后，会让它的开动时间 $a_i$ 加上 $b_i$。这意味着当他要第二次得到这 $2^i$ 个钻石时就需要 $a_i + b_i$ 的时间，每次不断累加，第 $x$ 次开动就需要 $a_i+(x-1)b_i$ 的时间。

wrzSama 需要得到至少 $2^n$ 个钻石来得到宝藏，请问他最少需要多长时间。

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

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

第三行 $n$ 个正整数，表示 $b_1,b_2,\dots,b_n$。

outputFormat: 一行一个正整数，即为答案。


title: [JRKSJ R7] 茎

description:
你有一棵 $n$ 个点的根节点为 $1$ 的有根树，现在你要对这棵树进行剪枝，每次你可以选择一个还未被剪掉的节点 $u$ 进行操作，然后剪掉 $u$ 的子树所有点（包括 $u$）。当且仅当你剪掉 $1$ 时，操作停止。

你知道 $1$ 到 $x$ 这条路径是这棵树的茎，需要特殊处理。所以你需要在第 $k$ 次剪枝时对 $x$ 进行操作，而非仅仅将其剪掉，即你不能在第 $k$ 次及以前对其祖先进行操作使其被连带剪掉。

求有多少种不同的操作序列，两个操作序列不同当且仅当长度不同或存在一次操作 $i$ 使得两操作序列在第 $i$ 次时选择的 $u$ 不同。输出答案模 $10^9+7$。

inputFormat:
第一行三个数 $n,k,x$。
接下来 $n-1$ 行每行两个数 $u,v$，代表树上的一条边 $(u,v)$。

outputFormat: 一个数表示答案对 $10^9+7$ 取模的结果。


title: 「GLR-R4」小暑

background:
  「长养薰风拂晓吹，浅开荷芰落蔷薇」

---

  在校内的最后一次试演出！

  从[第一次登台](https://www.luogu.com.cn/problem/P7245)至今，从以往约定的放学后空无一人的操场到如今日夜挥汗的训练室，他们与彼此的约定是否改变呢？

  “肩上的吉他和小小梦想，要为它们长出坚强的翅膀！”

---

  **小暑** 「Can you hear me now?　我会从此成为你的骄傲　现在就要出发　一切刚刚好」

description:
  [还记得吗？](https://www.luogu.com.cn/problem/P8476)你可是天依他们的专业分析师。除了演出者的表现，观众们的情感波动也是重要的分析对象。经过不懈努力，你提出了以下这些指标（出题人已经被你消灭啦，但还是请你耐心读题）：

  「情绪」 我们用强烈度 $v\in\mathbb N^\star$ 来表达一个情绪。

  「心境」 一系列情绪共同组成一个心境，我们将心境描述为一个二元组 $M=(s,f)$，其中 $s,f\in\mathbb N^\star$，其中 $s$ 为所含情绪的强烈度之和，$f$ 为某个特征情绪的强烈度。

  「共鸣」 两个心境可以通过共鸣而融合得到新的心境。我们将 $M_2=(s_2,f_2)$ 融合向 $M_1=(s_1,f_1)$ 的共鸣记作 $M_1+M_2$，共鸣的结果是一个新的心境 $M=M_1+M_2=(s_1+s_2,f_1)$。注意此时**不一定满足** $M_1+M_2=M_2+M_1$。

  「心路」 在一棵有根树上，沿**树形关系**共鸣心境的过程称为心路。对于以 $r$ 为根的子树，其心路历程可以描述如下：

1.  初始时，$A_r\gets M_r$，其中 $A_x$ 表示以 $x$ 为根的子树心路完成后的最终心境，$M_x$ 为 $x$ 结点上的初始心境。

2.  **按编号升序地**枚举 $r$ 的孩子结点 $x$：

    -   递归完成 $x$ 子树的心路，得到 $A_x$。此时，设 $A_r=(s_r,f_r)$，$A_x=(s_x,f_x)$。

    -   若 $s_r\ge s_x$，则令 $A_r\gets A_r+A_x$，否则令 $A_r\gets A_x+A_r$。

  最终的 $A_r$ 即为以 $r$ 为根的子树心路完成后的最终心境。

---

  为研究特定观众的心理变化情况，你需要时刻监控其上述指标。现给定一棵含有 $n$ 个结点，以 $1$ 为根结点的有根树，结点 $x$ 上初始有心境 $M_x=(a_x,a_x)$。此后进行 $q$ 次操作，每次操作有以下两类：

1.  给出结点 $x$，询问 $A_x=(s_x,f_x)$ 中 $f_x$ 的值，其中 $A_x$ 应当在每次询问时，依据当前的信息重新计算。

2.  给出结点 $x$ 和变化量 $d$，令 $a_x\gets a_x+d$，并修改对应的 $M_x$。注意 $d$ **可能为负数**，但保证操作前后都有 $a_x>0$。

  请你对于每个询问操作，计算出相应的答案。

inputFormat:
第一行两个整数 $n,q$，分别表示树的大小和操作次数。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，其中 $a_i$ 表示结点 $i$ 的初始权值。

第三行 $n-1$ 个整数 $p_2,p_3,\cdots,p_n$，其中 $p_i$ 表示以结点 $1$ 为根时，结点 $i$ 的父亲。

接下来 $q$ 行，每行格式形如 `1 x` 或 `2 x d`，分别对应题目描述中的两种操作。

outputFormat: 对于每个类型为 $1$ 的操作，输出一行一个整数，表示所求答案。


title: [PA2021] Autostrada

description:
特工 Karol 正在一条三车道的高速公路上驾驶他的红色汽车。在他前面有一些车，并且他们都在以一个取决于车道的固定速度向前行驶：第 $i$ 条车道的速度为 $v_i$ 且 $v_1 > v_2 > v_3$。其他车都不会变换车道和速度，但是 Karol 可以迅速变换车道，也可以迅速改变自己的车速到不超过 $v_0$ 的任意实数速度。他不能掉头，所以他的车的时速在区间 $[0, v_0]$ 中。

包括 Karol 在内，每辆车的长度都是 $1$。车之间可能会互相碰撞，但是 Karol 不能让这些车相撞。即：有正数长度的相交区间。形式化地，定义一辆车的位置为车头与高速路起点（即，Karol 的车刚开始的位置）之间的距离。相同车道的两辆车的位置差不能小于 $1$。

入口处有一段长为 $L$ 的公路，Karol 目前在第三车道的起点处。高速路无限延伸，并且在描述路段之外高速路上没有车。

请计算 Karol 最快多久后能超过所有车。换句话说，计算所有其他的车在最少多长时间后可以完全落后于 Karol 的车尾。

**注意：Karol 可能会在非整数时间内改变他的车道和速度，汽车的位置也可能是非整数的。**

inputFormat:
第一行，五个整数 $L, v_0, v_1, v_2, v_3$；

接下来三行，其中第 $i$ 行有一个长为 $L$ 的字符串 $s_i$，描述第 $i$ 条车道，如果字符串 $s_i$ 的第 $j$ 个字符为 `#`，则表示那个位置有一辆车；如果为 `.`，则表示那个位置没有车。保证 $s_1$ 和 $s_2$ 的第一个字符都是 `.`，$s_3$ 的第一个字符为 `#`，表示 Karol 的车。输入中至少有两个 `#`。

outputFormat:
一行，一个实数，表示 Karol 超过所有车所用的最短时间。

与标准答案的绝对误差或相对误差在 $10^{-9}$ 之内的输出均可被接受。也就是说，你的答案为 $x$，如果标准答案是 $x_0$，若 $\frac{|x - x_0|}{\max(x_0, 1)} \leq 10^{-9}$ 则你的输出就会被判为正确。


title: [PA2021] Butelki

description:
Byteasar 有三瓶橙汁。他现在想通过把橙汁从一个瓶子倒入另一个瓶子的方式，让其中一个瓶子恰好装有 $k$ 升橙汁。因为他家里没有量筒，所以唯一允许的操作是在两个瓶子之间转移橙汁——要么把一个瓶子倒空，要么把一个瓶子倒满。橙汁不能撒到地上，也不能在这三个瓶子之外添加橙汁。

Byteasar 现在想知道，对于每一个 $k$，最少需要转移多少次橙汁才能让三个瓶子中的一个装有恰好 $k$ 升橙汁。他希望你帮帮他。

inputFormat:
第一行，三个整数 $A, B, C$，表示第一、二、三个瓶子的容积；

第二行，三个整数 $a, b, c$，表示第一、二、三个瓶子中最初装的橙汁体积。

outputFormat: 一行，$C + 1$ 个整数，其中第 $i$ 个整数在存在一种操作方式使得让三个瓶子中的一个装有 $i - 1$ 升橙汁时为最小操作次数，否则为 $-1$。

hint: 对于 $100\%$ 的数据，$1 \leq A \leq B \leq C \leq 10^5$，$0 \leq a \leq A$，$0 \leq b \leq B$，$0 \leq c \leq C$。


title: [PA2021] Drzewo czerwono-czarne

description:
你熟悉红黑树这种数据结构吗？在本题我们将考虑一种节点颜色为红色或黑色的树，但请放心，如果你听说过刚才提到的数据结构的话，最好迅速忘掉它。

给定一棵树（即，一个无环的无向连通图），每个节点被涂成红或黑两种颜色之一。你可以选择被一条边相连的两个节点 $v$ 和 $u$，并把 $v$ 重新涂成和 $u$ 一样的颜色。

你的任务是确定经过一系列操作（**有可能不进行任何操作**）之后，一种最初的涂色情况能否变为最终给定的涂色情况。

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

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

对于每组数据：

第一行，一个整数 $n$，表示树的节点数；

第二行，$n$ 个字符，每个字符是 $0$ 或 $1$，如果第 $i$ 个字符是 $0$，则初始时第 $i$ 个节点被涂成红色。如果第 $i$ 个字符是 $1$，则初始时第 $i$ 个节点被涂成黑色；

第三行，$n$ 个字符，每个字符是 $0$ 或 $1$，如果第 $i$ 个字符是 $0$，则最后第 $i$ 个节点必须被涂成红色。如果第 $i$ 个字符是 $1$，则最后第 $i$ 个节点必须被涂成黑色；

接下来 $n - 1$ 行，其中第 $i$ 行有两个整数 $a_i, b_i$，表示树上的一条边；

outputFormat:
对于每组数据：

一行，一个字符串。如果存在一个操作序列能使涂色情况变为最终给定的情况，输出 `TAK`，否则输出 `NIE`。

hint: 对于 $100\%$ 的数据，$1 \leq T, n \leq 10^5$，$1 \leq \sum n \leq 10^6$，$1 \leq a_i, b_i \leq n$。


title: [PA2021] Desant 2

description:
Byteotia 准备再次袭击 Bitotia！在敌人的领土上登陆是一个真正硬汉的任务，因此，Byteotia 最好的特种部队的士兵——Byteburg——将参与其中。

Bytchak 将军让 $n$ 名士兵集合。他们立即排成一排，并从左到右依次用 $1$ 到 $n$ 的整数编号。将军希望选择一定数量的部队重新部署到 Bitotia 境内。作为一个熟练的战略家，他知道他的部下排队顺序不是随意的，而是与他们之间的友好关系有关，所以他选择的每支部队必须恰好由 $k$ 个连续的士兵组成。通过这种方式，他可以确保组成小队的士兵能够很好地合作。当然，每个士兵最多属于一个小队，将军对小队的数量没有偏好——特别是，他可以不选择任何小队而放弃对 Bitotia 的攻击（至少暂时如此）。

Bytchak 将军知道每一个士兵的技能——他可以用一个整数 $a_i$ 来描述他们每个人。技能值越高，这个士兵在战斗中的效率就越高。这个值也可以是负数，意味着这个士兵可能只会阻碍行动。

将军希望将所有将被派去登陆的士兵的 $a_i$ 值之和最大化。然而，有一个问题。可能他要派一定数量的排头兵去与 Intotia 作战的前线，而派一定数量的排尾兵在 Longlongotia 进行情报行动。那么他将不得不只从位置号在 $[l_i, r_i]$ 范围内的士兵中选择部队。

请你帮助将军考虑不同的情况，并为每一种情况计算派去登陆的士兵的最大可能的 $a_i$ 值之和。

inputFormat:
第一行，三个整数 $n, k, q$，分别表示士兵总数、每支队伍中士兵人数和将军考虑的情况数；

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$，表示每个士兵的技能值；

接下来 $q$ 行，其中第 $i$ 行有两个整数 $l_i, r_i$，表示第 $i$ 种情况，即只有编号在 $[l_i, r_i]$ 范围内的士兵参与对 Bitotia 的作战。

outputFormat: $q$ 行，其中第 $i$ 行一个整数，表示在第 $i$ 种情况下参与作战的士兵最大的技能值之和。

hint: 对于 $100\%$ 的数据，$1 \leq n, q \leq 3 \times 10^5$，$1 \leq k \leq n$，$-10^9 \leq a_i \leq 10^9$，$1 \leq l_i \leq r_i \leq n$。


title: [PA2021] Fiolki 2

description:
Byteasar 是一名化学家。你可能还记得，许多年前他因一项实验而闻名，该实验产生了一种特定的物质 X。由于上述物质根本没有解决人类的所有问题，这次他没有试图生产这种物质或找寻任何其他具体的解决方案——他只是在进行实验和评估其结果。

Byteasar 的实验室里有 $n$ 个样品瓶，用 $1$ 到 $n$ 的整数编号，这些样品瓶用 $m$ 根导管连接，物质可以从导管中流过。所有的样品瓶都处于两两不同的高度，液体只能通过导管往低处流。每根导管都有两端——第 $i$ 根导管的一端与编号为 $a_i$ 的样品瓶相连，另一端与编号为 $b_i$ 的样品瓶相连，我们知道编号 $a_i$ 的样品瓶比 $b_i$ 的样品瓶高。此外，每根导管都被一个导管夹夹住，以阻止物质的流动。Byteasar 可以在任何时候选择任何导管夹并打开它，让物质从样品瓶 $a_i$ 自由地流向样品瓶 $b_i$，在所有物质从一个样品瓶流向另一个样品瓶后，再夹住它。由于导管夹是机械式卡箍，保持其打开需要用力，因此在任何时候都只能打开一个导管夹。

编号为 $1$ 至 $k$ 的样品瓶含有危险化学品。这些样品瓶中的每一个都包含一种不同的物质。编号大于 $k$ 的样品瓶最初都是空的。

化学品是非常危险的，在任何情况下都不允许不同的物质混合在一起——这种混合的后果可能是灾难性的。由于流动的物质会留下微小的沉淀物，所以甚至不能让一种物质倒入以前装有任何其他物质的样品瓶中。

Byteasar 唯一能做的就是在样品瓶之间移动这些物质，确保没有两个物质混合。这并不是毫无意义的——通过以安全的方式运输物质，他可以把这些物质移到其他样品瓶中，这样更方便他研究它们的特性。

Byteasar 现在想选择一个区间 $[l, r]$，满足 $k < l \leq r \leq n$，然后他会将尽可能多的物质转移到该区间的任何编号的样品瓶中并继续测试那些方便放置的化学品。由于他不能决定哪个区间对他来说是最方便的，对于每个可能的区间 $[l, r]$，他想知道他能最多将多少种不同的物质转移到编号在区间 $[l, r]$ 的样品瓶中。我们用 $f(l, r)$ 来表示这个值。

请你帮 Byteasar 写一个程序，根据他的描述，计算对于区间 $[0, k]$ 中的每个 $x$，有多少个区间 $[l, r]$ 满足 $f(l,r) = x$。

inputFormat:
第一行，三个整数 $n, m, k$，表示样品瓶的数量、连接样品瓶的导管数量和最初装有 Byteasar 正在测试的物质的样品瓶数量。

接下来 $m$ 行，每行两个整数 $a_i, b_i$，表示样品瓶 $a_i$ 和 $b_i$ 之间有导管，样品瓶 $a_i$ 中的物质可以转移到样品瓶 $b_i$ 中。

我们保证对实验室的描述是合法的，即如果我们把样品瓶当作一个图的顶点，把导管当作这个图的有向边，那么输入就描述了一个**有向无环图**。

请注意，输入中没有指出样品瓶所处的高度。然而，对于每一对由导管直接连接的样品瓶，可以知道哪一个样品瓶的位置更高。

outputFormat: $k + 1$ 行，其中第 $i$ 行包含一个整数，表示满足 $k < l \leq r \leq n$ 且 $f(l, r) = i - 1$ 的区间 $[l, r]$ 的数量。

hint: 对于 $100\%$ 的数据，$2 \leq n \leq 10^5$，$1 \leq m \leq 10^6$，$1 \leq k \leq \min(n - 1, 50)$，$1 \leq a_i \leq n$，$k < b_i \leq n$。


title: [PA2021] Zbiory niezależne

description:
树 $T = (V, E)$ 是一个无向连通且无环的简单图。在本题中，我们考虑 $c$ 色树，即树上每个节点有 $c$ 种颜色之一的树。

两棵有色树 $T_1 = (V_1, E_1), T_2 = (V_2, E_2)$ 相等，当且仅当：

- 存在双射 $\pi : V_1 \to V_2$，满足对于任意节点对 $(u, v) \in V_1$，满足 $\{u,v\} \in E_1$ 当且仅当 $\{\pi(u), \pi(v)\} \in E_2$。
- 对于任意节点 $v \in V_1$，$T_1$ 中 $v$ 节点的颜色和 $T_2$ 中 $\pi(v)$ 节点的颜色相同。

我们称一棵树 $T = (V, E)$ 的一个独立集为任意节点的子集 $S \subseteq V$，满足 $S$ 中没有两不同节点被一条边相连。独立集 $S$ 的大小等于属于 $S$ 集合的节点个数。

给定三个整数 $l, r, c$，求问有多少不同的 $c$ 色树满足其最大独立集的大小在 $[l, r]$ 中？由于答案可能会非常大，所以请求出它对 $998244353$ 取模后的值。

inputFormat: 一行，三个整数 $l, r, c$。

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


title: 小挖的 X 献身

description:
给定一张 $n\times  n$ 的 $01$ 方阵，请计算其中 X 的数目。

X 定义为用 $1$ 填充且形状为 X 的联通块。具体的，X 由左向斜线 `\` 和右向斜线 `/` 构成，且需要保证左向斜线和右向斜线**长度相等**，而且 X 是中心对称图形，斜线长度大于 1。

例如：

```cpp
101
010
101
```
有一个斜线长度为 $3$ 的 X。

```cpp
1001
0110
0110
1001
````

则有两个斜线长度分别为 $2,4$ 的 X。

```cpp
10001
01010
00100
01010
00001
```

仅有一个斜线长度为 $3$ 的 X 。

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

接下来 $n$ 行每行一个长度为 $n$ 的 $01$ 串，描述了一个 $01$ 矩阵。

outputFormat: 共 $1$ 行，一个非负整数，表示 X 的数目。

hint:
对于 $20\%$ 的数据，$1\leq n\leq 3$。

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

对于 $70\%$ 的数据，$1\leq n\leq 50$。

对于 $100\%$ 的数据，$1\leq n\leq 100$。


title: 小挖的核燃料填充

description:
小挖做 Web 设计的时候，剧情里插入了酷炫的核填充情节！但很可惜，受制于技术，情节对应的游戏竟然是数独……

一开始，会给定你一个有 $n\times n$ 个**宫**，每个宫中有 $n \times n$ 个元素，且**早已全部正确填好**的 $n$ 阶数独。本题中数独游戏的详细表示与玩法见下方 **“补充说明”** 。

但小挖会把其中**一些宫向左或者向右转 90 度/180 度**。比如，若一个宫初始为

```cpp
087
654
321
```

那么它向左旋转 $90$ 度后会变成：

```cpp
741
852
063
```
你在恢复数独时，也**只能将一些宫向左转 $90$ 度**，一次旋转算作一步。现在小挖想考考你：如果把操作后的数独重新恢复成合法的数独，最少需要多少步呢？

如果一开始小挖给出的数独局面不可以通过任意次、任意位置的左旋得到，则输出 $-1$ 。~~为什么呢？因为小挖给出的是“自认为完全正确的”数独，但实际不一定。~~

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

第 $2\sim n^2+1$ 行，每行输入 $n^2$ 个 $16$ 进制整数，表示一个给定的数独局面，表示小挖操作之后的游戏。

outputFormat:
第 $1$ 行输出一个整数，表示最小步数 $s$。

第 $2\sim s+1$ 行，每行输出两个整数 $x_i,y_i$。表示对行号列号为 $x_i,y_i$ 的宫向左旋转了 $90$ 度。

数据保证当存在解时，最优解方案唯一。输出时请按如下规则输出：

设 $i<j$ 表示输出方案时的第 $i,j$ 两步。则：

- $x_i\leq x_j$。
- 若 $x_i= x_j$ ，则 $y_i\leq y_j$。

若不存在合法方案，请输出 $-1$。

hint:
对于 $40\%$ 的数据，$2 \le n\leq 3$。

对于 $100\%$ 的数据，$2 \le n\leq 4$。

## Hint

$n$ 阶数独合法的条件：每一行、每一列、每一个粗线宫 $(n\times n)$ 内的数字均含 $0\sim  n^2-1$，且不重复。

需要注意的是，本题内对于 $4$ 阶数独的表示方式中 $>9$ 的数字采用了十六进制表示法。准确来说 $\mathrm A=10$，$\mathrm B=11$，$\mathrm C=12$，$\mathrm D=13$，$\mathrm E=14$，$\mathrm F=15$。


title: 小挖的买花

background: 小挖喜欢买花，但是 ta 太懒了！所以这个任务全权交给了你。

description:
花店里只有 $n$ 株花，每一株花都有三个属性：价格 $cost_i$、美丽度 $be_i$、新鲜程度 $fr_i$。

小挖每次都有不同的要求。准确来说，对于第 $j$ 次买花，你手里的钱**至多能买下总价为 $c_j$ 的花**。同时，小挖还要求购买花的**新鲜程度总和大于等于 $f_j$**。而小挖希望知道，在满足 ta 给出的条件后，购买**花的美丽度总和**的最大值是多少？

小挖一共要让你买 $q$ 次花，你能否正确回答 ta 的问题呢？询问彼此独立。

inputFormat:
第 $1$ 行，共两个正整数 $n,q$。

第 $2\sim n+1$ 行，每行三个正整数 $cost_i,fr_i,be_i$，分别表示一株花的三个属性。

第 $n+2\sim n+q+1$ 行，每行两个正整数 $c_j,f_j$，表示每次买花时的要求。

outputFormat: 共 $q$ 行，每行一个整数，表示美丽度总和的最大值。

hint:
对于 $20\%$ 的数据，$3\leq n,q\leq 16$。

对于 $40\%$ 的数据，$3\leq n,q\leq 30$，$0\leq c_j,f_j\leq 50$。

对于 $60\%$ 的数据，$3\leq n\leq 100$，$1\leq q\leq 5\times 10^4$，$0\leq cost_i,fr_i,c_j,f_j\leq 100$。

对于另外 $20\%$ 的数据，对于每次买花，都有 $f_j=0$。

对于 $100\%$ 的数据，$3\leq n\leq 500$，$\boldsymbol{1\leq q\leq 10^6}$，$0\leq cost_i,fr_i,c_j,f_j\leq 500$，$1\leq be_i \leq 10^6$。


title: 小挖的时间

description:
小挖有一个电子表，采用只显示小时和分钟的 $12$ 小时制，即只显示 $12:00\sim 11:59$，$12:59$ 后的时刻是 $1:00$。

小时数不会有前导零，但分钟数可以（比如 $7:59$ 不会写成 $07:59$，而 $10:03$ 不会写成 $10:3$）。

小挖从某天**中午**（即 $12:00$）开始盯着这块电子表，一共会持续盯 $T$ 分钟。Ta 现在想知道，一共会看到多少次成**等差数列**的时刻呢？

**等差数列**的定义如下：如果一个数列是等差数列，那么第一个数后面的每一个数，都是前面一个数加上一个固定的差值。比如 $11:11$ 就是一个固定差值为 $0$ 的等差数列时刻，$12:34$ 就是一个固定差值为 $1$ 的等差数列时刻。

如果你稍微留心一点，就会发现我没有给差值明确的大小定义，所以正数负数皆可。

inputFormat:
第 $1$ 行，一个正整数 $D$，表示该测试点有共 $D$ 组测试数据。

第 $2\sim D+1$ 行，每行一个非负整数 $T$，含义见题目描述。

outputFormat: 共 $D$ 行，每行一个整数 $ans$ 表示看到的等差数列时刻数目。


title: ρars/ey

description:
给定一颗有 $n$ 个节点的有根树，其中根节点是 $1$。你可以进行若干次以下操作:

-   选择一个节点，删去其子树内除其以外的点。

此操作的代价为 $f_i$，其中 $i$ 是你选择的节点子树大小。

你希望删掉除了 $1$ 以外的所有点，请问代价的最小值是多少？

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

第二行 $n-1$ 个正整数，第 $i$ 个表示 $f_{i+1}$。

接下来 $n-1$ 行，每行两个正整数，表示一条树边。

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

hint:
【样例解释】

先删除节点 $8$ 的子树内除了它自身的 $5$ 个点，再删除节点 $1$ 的子树内除了它自身的 $2$ 个点，代价为 $f_6+f_3=63744$。可以证明这是最小的代价。

【数据范围】

对于所有数据，保证 $1\le n\le 5000$，$1\le f_i\le 10^9$。
$$
\def{\arraystretch}{1.5}
\begin{array}{c|c|c}\hline
\textbf{测试点编号}&\bm{~~~~~~~~n\le~~~~~~~~}&~~~~\textbf{特殊限制}~~~~\cr\hline
\textsf1\sim \sf2 & 8& \cr\hline
\sf3\sim 6 & 15&  \cr\hline
\sf7\sim 8 & 400&\textsf{A}\cr\hline
\textsf9 & 400 &\sf B\cr\hline
\sf10\sim 12 & 400&\cr\hline
\sf13\sim 14 & &\sf C\cr\hline
\sf15\sim 20 & &\cr\hline
\end{array}
$$

$\textsf A$：保证树上所有点度数均小于等于 $2$，其中 $1$ 号点度数为 $1$。

$\textsf B$：保证树上只有 $1$ 号点度数大于等于 $2$。

$\textsf C$：保证树随机生成，随机生成方式是，对于 $i\ge 2$，从 $[1,i-1]$ 中随机一个整数 $x$，在 $x$ 与 $i$ 之间连边。然后随机打乱所有节点的编号。


title: Sultan Rage

description:
有一个数列 $\{a_n\}$ 满足对 $n > m$ 均有 $a_n=\sum\limits_{j=1}^m a_{n-j}$，并且 $a_1,a_2,\cdots,a_m$ 是输入中给出的正整数。

$q$ 次询问，每一次给出一个正整数 $x$，问有多少个不可重正整数集 $S$ 满足 $\sum\limits_{s\in S}a_s=x$。答案对质数 $998244353$ 取模。

本题有多组数据。

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

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

第一行两个整数 $m,q$。

第二行 $m$ 个整数 $a_1,a_2,\cdots,a_m$。

第三行 $q$ 个整数，每一个整数代表一次询问。

outputFormat: 对于每组询问输出一行表示答案。

hint:
对于所有数据，$T=5$，$2 \le m \le 100$，$1 \le q,a_i \le 100$，$1 \le x \le 10^{18}$。
$$
\def{\arraystretch}{1.5}
\begin{array}{c|c|c|c|c|c}\hline
\textbf{测试点编号}&\bm{m\le}&\bm{q \le }&\bm{a_i \le }& \bm{x \le}&\bm{\textbf{特殊性质}}\cr\hline
\textsf1\sim \sf2 & 8&8  & 8 & 100\cr\hline
\sf3\sim 5 & 15& &15&10^3 \cr\hline
\textsf6 & & & & 1 &\cr\hline
\sf7\sim 11 & & 1& & & \textsf{A}\cr\hline
\sf12\sim 16 & 2& & &\cr\hline
\sf17\sim 20 & &\cr\hline
\end{array}
$$

$\textsf A$：$m=10$，且 $x$ 在所有可能的 $x$ 中随机生成。


title: Magenta Potion

description:
给定一个长为 $n$ 的整数序列 $a$，其中所有数的绝对值均大于等于 $2$。有 $q$ 次操作，格式如下：

$\texttt{1 i k}$，表示将 $a_i$ 修改为 $k$。保证 $k $ 的绝对值大于等于 $2$。

$\texttt{2 l r}$，考虑 $[l,r]$ 的子区间（包括本身）中乘积最大的的区间乘积 $M$。如果 $M>2^{30}$，输出 `Too large`，否则输出 $M$。特别地，空区间的元素乘积定义为 $1$。

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

第二行输入 $n$ 个**整数**表示 $a_i$。

接下来 $q$ 行，每行三个整数表示一次询问，格式见上。

outputFormat: 对于每次 $\tt2$ 操作输出一行表示询问的答案。

hint:
对于所有的数据，$2\le |a_i|,|k| \le 10^9$，$1 \le n,q \le 2\times 10^5$，$1 \le l \le r \le n$。

$$
\def{\arraystretch}{1.5}
\begin{array}{c|c|c}\hline
\textbf{测试点编号}&\bm{~~~~~~~~n,q\le~~~~~~~~}&~~~~\textbf{特殊限制}~~~~\cr\hline
\textsf1\sim \sf2 & 10& \cr\hline
\sf3\sim 6 & 100&  \cr\hline
\sf7\sim 10 & 5 \times 10^3&\cr\hline
\sf 11\sim 13 &  &\sf A\cr\hline
\sf14\sim 16 & & \sf B\cr\hline
\sf17\sim 20 & &\cr\hline
\end{array}
$$

$\textsf A$：保证 $a_i,k \ge 2$。

$\textsf B$：保证对于每一组询问，对应的 $r-l \ge 100$。


title: You are the Miserable

description:
小 A 和小 B 玩游戏。小 A 有一个凸 $n$ 边形以及 $n-3$ 条不交的对角线构成一个三角剖分。每一次，小 B 可以问小 A 某一条对角线 $x-y$ ，小 A 会回答他该对角线是否在他的三角剖分中。小 B 想要对于每一条 **三角剖分中** 的对角线得到至少一次肯定的答复。他希望询问的次数尽量少，而小 A 希望询问次数尽量多，并且有可能会根据小 B 的询问来改变他的三角剖分。但在这个过程中，小 A 的三角剖分不能与他曾做出的回答矛盾。

现在，给出小 A 和小 B 玩的若干步，判断它们的游戏过程是否保持最优。如果是，输出 $0$；如果不是，输出第一次不是最优的操作，形如 `A x` 或者 `B x`，表示小 A 或者小 B 的第 $x$ 次操作不是最优的。

具体地，保持最优的定义如下：假设最优情况下小 B 要询问 $k$ 次，那么每一步过后，双方最优的策略仍然使得总的询问次数为 $k$，第一次使得询问次数不为 $k$ 的步骤就是需要输出的步骤。

他们玩了 $T$ 次独立的游戏，你需要对每一次询问作出回答。

**注意：**

-   数据保证，直到第一次不优的操作被做出，小 A 的回答都是合法的，即总存在一个三角剖分符合小 A 做出的所有回答。
-   数据不保证，在第一次不优的操作被做出以后，小 A 的回答仍然保持合法，即可能不存在一个三角剖分符合小 A 做出的所有回答。

**【提示】**

1. 多边形的对角线指连接不相邻两个顶点的线段。
2. 多边形的三角剖分指 $n-3$ 条仅可以在顶点处相交的对角线构成的集合。

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

对于每一组数据，第一行两个整数 $n,m$。

接下来 $m$ 行，每一行三个整数 $x,y,z$，表示小 B 的询问和小 A 的回答。其中 $z=0$ 表示该对角线不存在，$z=1$ 则表示存在。

outputFormat: 对于每组数据输出一行，若存在不优的操作则输出第一次不是最优的操作，否则输出 $0$。

hint:
【样例解释】

对于 $n=5$，最优的 $k=4$。对于 $n=4$，最优的 $k=2$。对于最后一组数据，B 重复询问同一条边已经不是最优，此时 A 的回答可以不合法。

【数据范围】

$1 \le T\le 10^3$，$4\le n \le 10^5$，$1 \le \sum n \le 2\times 10^5$，$1 \le m \le k$，$1 \le x,y \le n$，$0 \le z \le 1$。保证所有的 $x-y$ 都是合法的对角线，以及直到第一次不是最优的一步所有询问的回答都至少对应一种三角剖分。

$$
\def{\arraystretch}{1.5}
\begin{array}{c|c|c|c|c}\hline
\textbf{~~测试点编号~~}&\bm{~~T\le~~}&\bm{~~n \le ~~}&\bm{~~~~m~~~~}& ~\bm{z}~\cr\hline
\textsf1\sim \sf2 &100 &5  &  \cr\hline
\sf3\sim 4 & 100& 7& &\cr\hline
\sf5 \sim 6 &100 &8 & & \cr\hline
\sf7 \sim \sf9 & & &=1 & \cr\hline
\sf10\sim 12 & & & & =0\cr\hline
\sf13\sim 16 &20 &200\cr\hline
\sf 17 \sim 20
\end{array}
$$


title: 『JROI-8』颅脑损伤 2.0（加强版）

background:
注意到本题特殊的时间限制。

[普通版](https://www.luogu.com.cn/problem/P8591)。

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]$ 交**当且仅当**存在 $k\in[l_i,r_i]$ 且 $k\in[l_j,r_j]$。

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

接下来 $n$ 行，每行两个整数，代表 $l_i,r_i$，用空格隔开。

outputFormat: 一行一个非负整数，代表最小的红色线段的长度和。


title: A Certain Forbidden Index

background:
**这是一道函数式交互题。本题仅支持 C++ 提交。（出于某些原因，请不要使用 GCC 9 提交）**

**本地编译、提交时请在程序里加入以下函数声明语句：**

```cpp
int query(int, int);
```

**任何在赛时攻击交互库而得分的行为均视为作弊。**

description:
有一个长为 $n=2^k$ 的序列，基于这个序列建立了一棵[线段树](https://oi-wiki.org/ds/seg/)。现在线段树上有恰好一个节点被标记了。

你可以进行若干次询问，每次询问给定一个区间 $[l,r]$，交互库会在被修改的线段树上进行一次区间查询，你可以得知在被修改的线段树上这个区间对应的所有节点中，是否有节点被标记。

你需要在尽可能少的询问内找到这个节点。具体而言，若最优策略在最坏情况下需要 $Q$ 次询问，则你最多可以使用 $Q$ 次询问。

### 交互流程

你不需要，也不应该实现主函数，你只需要实现如下函数：

```cpp
std::pair<int, int> solve(int k);
```

该函数需要在得到答案后返回一个数对 $(x,y)$，表示被标记的线段树节点所对应的区间为 $[x,y]$。

你可以调用交互库提供的方法：

```cpp
int query(int l, int r);
```

传入的 `l` 和 `r` 代表询问的区间为 $[l,r]$。交互库会返回对应的结果。你需要保证 $1\le l\le r\le n$。具体而言：

- 当没有节点被标记时，交互库返回 $0$；
- 当有节点被标记时，交互库返回 $1$；
- 当询问的区间不合法时，交互库会返回 $-1$，此时你需要立即结束这组数据的交互（不是整个测试点），否则可能导致不可预知的错误。

本题无询问次数限制，但过多的询问会导致时间超限，详细信息请看“数据规模与约定”。

inputFormat:
下面给出样例交互库的输入输出格式：

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

对于每组数据，第一行输入三个整数 $k,l,r$ 代表 $n=2^k$，且将对应区间为 $[l,r]$ 的线段树节点修改。

注意样例交互库不会检查输入数据的正确性。

outputFormat:
对于每组数据，如果你得到的答案正确，输出一个整数表示你使用的交互次数，否则：

- 若你的询问不合法，输出 `Wrong Answer [1]`；
- 若你返回的区间不正确，输出 `Wrong Answer [2]`。

hint:
#### 样例 1 解释

下面是一种可能的交互流程：

| 交互库 | 选手程序 | 备注 |
| :----------: | :----------: | :----------: |
| 调用 `solve(2)` |  | 开始测试 |
| 返回 $1$ | 调用 `query(1,1)` | $[1,1]$ 就是答案节点 |
|  | 返回 $(1,1)$ | 答案正确 |
| 调用 `solve(2)` |  | 开始下一组数据的评测 |
| 返回 $1$ | 调用 `query(2,4)` | $[2,4]$ 对应的节点是 $[2,2]$ 和 $[3,4]$，包括了答案节点 |
| 返回 $0$ | 调用 `query(1,4)` | $[1,4]$ 对应的节点只有 $[1,4]$，不包括答案节点 |
|  | 返回 $(3,4)$ | 答案正确，评测结束 |

### 计分方式

本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。

如果你找到的节点是错误的，或者你给出的询问不合法，在该测试点将会得到 $0$ 分。

否则，设在一组数据中，答案最坏需要 $x$ 次询问，而你使用了 $y$ 次询问，满分为 $t$，则这组数据的分数是 $t\times \min\left(1,\mathrm{e}^{-\frac{y}{x}+1}\right)$。

每个测试点取所有数据组中得分的最小值，向下保留两位小数。你的得分是所有测试点得分之和。

### 数据规模与约定

对于所有数据，保证 $1\le k\le 14$，$1\le T\le 300$。

本题共 $14$ 个测试点，对于第 $i$ 个测试点，保证 $k=i$。对于 $1\le k\le 4$ 的测试点，满分 $10$ 分。对于 $5\le k\le 14$ 的测试点，满分 $6$ 分。

保证在每组数据进行 $2n$ 次询问时，单个测试点内，交互库使用的时间不超过 0.6s，空间不超过 8MiB。

### 下发文件说明

下发文件中有一个可以通过样例的程序示例 `sample.cpp`，以及一个样例交互库 `grader.cpp`。假设你的答案文件为 `answer.cpp`，则可以使用如下命令将其编译成可执行文件 `answer`：

```shell
g++ grader.cpp answer.cpp -o answer -O2
```

实际评测时的交互库可能是自适应的，即被修改的节点可能不会在交互一开始时确定。


title: 「CROI · R2」公交接驳

background:
H 市是一座特大城市，每天来往于城市各个角落的乘客络绎不绝。该市郊区建筑分散，为方便周边群众出行，该市沿平行于主要公路的方向修建了市郊铁路，与公路上的公交系统形成互补格局。同一方向上的铁路站点与公交站点不完全一致，但设有若干个换乘站，铁路列车与公交车均停靠换乘站。现目前，市郊铁路仅在早高峰、晚高峰时各单向发一趟列车。

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

上图是沿早高峰方向的市郊铁路和公交车的停靠站点示意图。用蓝色箭头连接的为换乘站，市郊铁路的乘客可以在这些车站换乘公交车。

在下面的问题中，我们忽略非换乘站的存在，仅考虑换乘站在运营过程中的影响。

description:
由于城市人口增多，H 市市郊铁路通勤压力增大，为了应对短时大客流，公交集团决定于早高峰时期在某条公交线路上安排若干班次的公交车，其运行方向与早高峰时期列车的开行方向相同，均为自西向东运行，便于乘坐火车的乘客换乘公交到达目的地。

给出一条共有 $n$ 个换乘站的街道，由西向东地将每个换乘站编号为 $1\sim n$。每一个换乘站的调度室对行驶效率的重视程度有所不同，第 $i$ 个换乘站的重视程度为 $v_i$。不同公交车在同一区间内的行驶时间相同，从第 $i$ 个换乘站行驶至第 $i+1$ 个换乘站的**时间**均为 $s_i$，可以忽略车辆停站的时间。市郊铁路列车到达第 $i$ 个换乘站的**时刻**为 $t_i$。保证两个换乘站之间乘坐公交车花费的时间一定不小于乘坐市郊铁路花费的时间。

现在你需要在这条公交线路上安排 $k$ 班公交车。全部的 $n$ 个换乘站都会有乘客从铁路下车。对于每一班车，你都需要安排其发车的时刻和发车的换乘站，且需要保证从任意一个换乘站下车的乘客均能坐上公交车，即最晚到达换乘站 $i$ 的公交车的到达时刻必须不小于 $t_i$。每班公交车发车后，都会以既定速度向东行驶至第 $n$ 个换乘站，并在途中的每个车站停靠并接上所有等候的乘客。你可以任意指定每条公交线路的始发站和发车时刻。

乘客们会登上他们到达车站后，首辆到达该站的公交车。定义换乘站 $i$ 的不满意度为在该站点处，于 $t_i$ 时刻从铁路下车的乘客等待首辆到达该站的公交车所花费的时间与乘客登上的公交车的始发站的重视程度的乘积。如果存在多班公交车同时到站，我们认为乘客登上的是始发站重视程度最小的一班。你需要最小化所有 $n$ 个换乘站的不满意度之和。

铁路时刻表和可供公交公司使用的空闲公交车数量总是在变化，所以你需要处理多组 $t_i$ 和 $k$ 不同的询问。

inputFormat:
第一行包含一个正整数 $n$，表示换乘站的数量。

第二行包含 $n-1$ 个用空格隔开的非负整数 $s_1,s_2,...,s_{n-1}$。

第三行包含 $n$ 个用空格隔开的非负整数 $v_i$。

第四行包含一个正整数 $p$，表示不同市郊铁路时刻表的数量。

接下来共有 $p$ 组数据，每组数据包含三行。

每组第一行包含 $n$ 个用空格隔开的正整数 $t_1,t_2,\cdots,t_n$。

每组第二行包含一个正整数 $q_i$ ，表示在当前时刻表下询问的 $k$ 的数量。

每组第三行包含 $q_i$ 个用空格隔开的正整数 $k_1,k_2,\cdots,k_q$，表示询问的不同的 $k$。

outputFormat: 输出 $p$ 行，每行 $q_i$ 个用空格隔开的正整数，表示在当前询问的 $k$ 的情况下，所有换乘站不满意度之和的最小值。


title: 冬之花

background:
“哭泣并不是因为悲伤，

只是因为活着，眼泪就不自觉跑了出来。”

赫尔德失恋以后，跑到大马路上飙车。因为是飙车，她不愿意一直待在路上，而是跑到路左右的黄沙地上转圈圈。她的便宜车的转向功能出了一些问题，但她真的很想转圈圈。

description:
给定 $n$ 个数 $a_1, a_2, \ldots, a_n$，再给定一个非零数 $x$。

你需要进行 ${10}^{100}$ 次操作，每次操作，你需要选定一个下标 $i$（$1 \le i \le n$），然后给 $x$ 加上 $a_i$。

你需要保证，在每次操作后，新的 $x$ 值都不能为 $0$。

请判断你能否完成这 ${10}^{100}$ 次操作。

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

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

- 第一行，两个整数 $n, x$。
- 第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$。

outputFormat: 对于每组数据，输出一行一个字符串，若可以进行 ${10}^{100}$ 次操作，则输出 `Yes`，否则输出 `No`。

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

对于第一组数据，第一次操作只能选择下标 $1$，$a_1=-1$，但 $1+(-1)=0$，因此无法进行操作。输出 `No`。

对于第二组数据，你可以轮流选择下标 $1$ 和 $2$，这样 $x$ 将一直 $+1$、$-1$，从而一直在 $10$ 和 $9$ 之间变化，这样你可以执行任意多次操作。输出 `Yes`。当然，这只是其中一种方案，你还可以有其他的操作方案。

---

**【数据范围】**

- 测试点 1（50 分）：$n = 1$；
- 测试点 2（50 分）：无特殊限制。

对于所有测试点：$1 \le T \le 30$，$1 \le n \le 5$，$1 \le \lvert x \rvert, \lvert a_i \rvert \le 100$。


title: Bassline

background:
fuwa↑ fuwa↑ fuwa↑ fuwa↑

赫尔德开始使用当下热潮的聊天软件 BassLine，那么第一步自然是加好友了！加好友既需要确认自己和对方有共同兴趣，又需要能加到足够多的好友。赫尔德将其抽象成了下面这个问题，让你来帮她解决。

description:
本题中，区间 $[l,r]$ 指所有大于等于 $l$ 且小于等于 $r$ 的整数组成的集合，如 $[3,3]$ 代表 $\{3\}$，$[3,7]$ 代表 $\{3,4,5,6,7\}$。

给定 $n$ 个区间，第 $i$ 个区间是 $[l_i,r_i]$。

你需要选择两个整数 $x\le y$，满足：

- 对于所有区间 $[l_i,r_i]$（$1\le i \le n$），以下两个条件之一满足：
	1. $[x,y]$ 被 $[l_i,r_i]$ 包含，换言之， $[x,y]\cap[l_i,r_i]=[x,y]$。
    2.  $[x,y]$ 与 $[l_i,r_i]$ 无交集，换言之，$[x,y]\cap[l_i,r_i]=\varnothing$。

若有 $k$ 个区间满足条件 1，则你的得分是 $k(y-x)$。输出你最大的可能的得分。

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

接下来 $n$ 行，每行两个数 $l_i,r_i$，描述一个区间。

outputFormat: 一行一个自然数表示答案。

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

对于样例，$[5,6]$ 是最优的区间之一，其含于 $[4,7],[5,9]$，且与 $[1,3],[7,10]$ 没有交集。此时 $k=2$，因此答案为 $2\times(6-5)=2$。$[1,3]$ 也是一个最优的区间。

$[5,7]$ 并非合法的区间，因为它与 $[7,10]$ 有交集，也并不含于 $[7,10]$。

---

**【数据范围】**

对于所有数据保证 $1 \le n \le 3 \times {10}^5$，$1 \le l_i \le r_i \le 3 \times {10}^5$。

- 子任务 1（20 分）：$n,l_i,r_i \le 10$；
- 子任务 2（20 分）：$n \le {10}^3$；
- 子任务 3（20 分）：$l_i, r_i \le {10}^3$；
- 子任务 4（40 分）：无特殊限制。


title: Rabbit

background:
“说实话，最喜欢你了；因为长得好看，所以最喜欢你了。

你的性格，我最喜欢了；虽然不太清楚，但是最喜欢了。”

赫尔德最近加入了一个奇怪的社区，那里面流行一种“配对追星”的活动。大家在人群中找到那个最耀眼的人，就作为自己的偶像了。

description:
赫尔德不知道这样是否好，为了研究这个活动，她想先从这个活动能持续多久开始研究。于是她抽象了这个问题。

给定一棵树，共 $n$ 个点，分别编号为 $1\sim n$。

每次操作，你需要选出三个点 $a,b,c$ 将他们标记，满足：

- $c$ 是 $a$ 到 $b$ 简单路径上编号最大的点；
- $a,b,c$ 两两不同；
- $a,b,c$ 先前都没有被标记过。

问至多能进行多少次操作。

---

**【提示】**

树上 $p$ 到 $q$ 的简单路径是指一个数列 $a_1,\dots,a_k$，满足：

1. $a_1=p$，$a_k=q$；
2. 其中没有重复元素；
3. 对于所有 $1\le i<k$，$a_{i+1}$ 与 $a_i$ 有边相连。

inputFormat:
本题有多组数据。

第一行是数据组数 $T$，接下来 $T$ 组数据，每组数据格式如下：

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

接下来 $n-1$ 行，每行两个正整数 $x,y$，描述树上的一条连接 $x,y$ 的边。

outputFormat: 对于每组数据输出一行一个非负整数，为答案。

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

对于第一组数据，可以选择 $a=1,b=2,c=3$。

对于第三组数据，可以依次选择 $a=3,b=4,c=7$，$a=1,b=2,c=5$。

---

**【数据范围】**

设 $S$ 为每个测试点所有数据中 $n$ 的和。

对于所有数据：$1\le T\le 3\times 10^4$，$1\le n\le 2\times 10^5$，$S\le 6\times 10^5$。

$$
\def{\arraystretch}{1.5}
\begin{array}{c|c|c|c|c|c}\hline
\textbf{子任务编号}&~~~~~~~n\le ~~~~~~~&~~~~~~~S\le ~~~~~~~&\textbf{特殊性质}&\textbf{子任务依赖}&\textbf{~~~分数~~~}\cr\hline
\textsf1 & 5 &&&&3\cr\hline
\textsf2 & 20&60&&&5\cr\hline
\textsf3 & & &\textsf{B}&&12\cr \hline
\textsf4 & 333&  10^3&\textsf{A}&&9\cr \hline
\textsf5 & 333 &  10^3&&\textsf{2,4}&7\cr\hline
\textsf6 & 3333 &10^4&\textsf{A}&\textsf{4}&15\cr\hline
\textsf7 & 3333 &10^4&&\textsf{5,6}&13\cr\hline
\textsf8 & &&\textsf{A}&\textsf{6}&12\cr\hline
\textsf9 & &&&\textsf{1,3,7,8}&24\cr\hline
\end{array}
$$

特殊限制 $\textsf{A}$：保证树的形态是一条链，即树上不存在度数大于 2 的点。

特殊限制 $\textsf{B}$：保证树随机生成：对于每个整数 $i\in [2,n]$，均匀随机选择整数 $j\in [1,i-1]$ 并在 $i,j$ 间连边，然后随机打乱点的编号。


title: 醒来

background:
“那羡慕的烟火去哪了，那信任的朋友疏远了。

我年幼时坚持过什么，你们还记不记得。”

回想自己儿时的样子，已和现在大不相同了；但想想昨天的自己，却与今天没什么差异。这不经意的改变，让我们已经是另一个样子了。

description:
赫尔德用一个长为 $r-l+1$ 的数列 $a$ 来描述自己性格的变化。但赫尔德记忆不好，她已经记不清 $a$ 了，只记得非负整数 $l,r$，其中 $l<r$。

不过，她还记得：

1.  $l\le a_i\le r$，且 $a_i$ 互不相同。换言之，$a$ 是一个 $l\sim r$ 的排列。
2.  对于所有 $1\le i\le r-l$，有 $\operatorname{popcount}(a_i \mathbin{\mathrm{xor}} a_{i+1})=1$。换言之，$a$ 中相邻的两个数二进制下只相差一位。

请你告诉她一个可能的 $a$，或告诉她其实不存在这样的 $a$。

inputFormat: 仅一行，两个非负整数 $l,r$。

outputFormat:
第一行，若有解输出 `Yes`，若无解则输出 `No`。不区分大小写。

若你输出了 `Yes`，则你可以用以下两种格式之一输出你的构造：

1. 输出一行 $r-l+1$ 个数，表示你构造的排列。
3. 先输出一个数，表示你构造排列的第一个数。接下来输出一个长为 $r-l$ 的字符串，对于第 $i$ 个字符，若你构造排列第 $i$ 与 $i+1$ 个数相差了 $2^k$，则你应该输出第 $k+1$ 个小写英文字母，即 `(char)('a'+k)`。

**注意，若你使用格式 1 输出，你可能无法通过最后两个子任务。若您获得了 UKE 的评测结果，请考虑修改输出答案的格式。**

---

**【评分方法】**

本题采用**自定义校验器**检测你的输出。

若你对解的存在性判断错误，你无法获得任何分数。

若你对解的存在性判断正确，你可以获得 $40\%$ 的分数；若解不存在或你给出了一组正确的构造，则你可以获得剩下 $60\%$ 的分数。

samples:
0 7
yes

samples:
3 5
No

hint:
**【样例解释 \#1、\#2、\#3】**

样例输出 \#1 和 \#2 对应同一个数列，即 $\{ 0, 1, 3, 2, 6, 7, 5, 4 \}$，它们均能获得该测试点 $100 \%$ 的分数。

样例输出 \#3 能获得该测试点 $40 \%$ 的分数。

----

**【数据范围】**

对于所有数据，保证 $0\le l<r\le 10^7$。

设 $n=r-l+1$。

$$
\def{\arraystretch}{1.5}
\begin{array}{c|c|c|c}\hline
\textbf{子任务编号}&\bm{~~~~~~~~n\le~~~~~~~~}&~~~~\textbf{特殊限制}~~~~&\textbf{分数}\cr\hline
\textsf1 & 10& &9\cr\hline
\textsf2 & 20& &9 \cr\hline
\textsf3 & 10^5&\textsf{A, B}&10\cr\hline
\textsf4 & 10^5 &\sf A&10\cr\hline
\textsf5 & 2000& \textsf C&25 \cr\hline
\textsf6 & 5\times 10^5&\textsf D&20\cr\hline
\textsf7 & 3\times 10^6&&10\cr\hline
\textsf8 & &&7\cr\hline
\end{array}
$$

$\textsf A$：保证 $l=0$。

$\textsf B$：保证 $n$ 是 $2$ 的整数次幂。

$\textsf C$：保证 $l$ 是偶数，$r$ 是奇数。

$\textsf D$：本子任务有 5 个测试点，从所有 $n\ge 2\times 10^5$ 且有解的数据中随机生成。

---

即使一直在改变，赫尔德也许仍似儿时的自己。


title: 心跳

background:
“清晰的跳动声传达来的，重叠的声响和流动的思念。

约定再也不要分开吧，希望无论何时都不要让你寂寞。”

恋爱之时，人的心情不会一成不变，可喜悦和悲伤会随着时间流逝而归于平淡。最令人难忘的是那些“心动”的感觉，那些因未曾经历而喜出望外的感觉。因此，有些时候，失去某些特别美好的回忆，反而能让心动的感觉增多。可为此失去那些回忆，真的值得吗？

description:
赫尔德想对上面的问题进行探究，她想先做一些统计，于是她抽象了这个问题。

我们对于一个长为 $l$ 的数列 $p$，定义函数：

-   $f(p)$ 表示有多少 $1\le i\le l$ 满足 $p_i=\max_{j=1}^i p_j$（即前缀最大值的个数）。

现在，给定 $n,m$，请求出有多少满足以下条件的长为 $n$ 的，值域在 $[m,n]$ 数列 $a$：

-   存在一个排列 $p$ 使得：令 $P_i$ 代表 $p$ 去掉 $p_i$ 后的数列（即 $[p_1,p_2,\dots,p_{i-1},p_{i+1},\dots,p_n]$），$f(P_i)=a_i$。

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

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

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


title: 嘘月

background:
“我早已认不出你的眼睛，也没有在想念你的面容；

你还是没有说出再见，就化作黑夜离开了。”

[赫尔德看着潮水](https://baike.baidu.com/item/%E4%B8%A5%E7%95%AF/23345630?fr=aladdin)，忽觉这不断上涨的潮水就像是持续上升的热情，它维持着热恋的时间，而激动的情绪又带给我们更多的热情。但是初识的热情终会逐渐平淡，又有多少人能在冷却的心跳中找到其中不变的节奏，走完这一生呢？

description:
赫尔德想对上面的问题进行探究，她想先做一些统计，于是她抽象了这个问题。

对于一个长为 $n$ 的排列，我们维护一个下标 $t$，初始 $t=m$。

重复以下过程：

- 从下标在 $1\sim t$ 的元素中选一个没标记过的，并将其标记。若标记的数比上一次标记的数大且 $t<n$，则 $t$ 自增 $1$；否则结束此过程。在你进行第一次标记前，上一次标记的数视为 $0$。

我们称这样的排列是好的：

- 存在某种方法，使得在经过若干次操作后，$t=n$。

现在，给定 $m$，求长为 $n$ 的好的排列在所有长为 $n$ 的排列中所占比例，对 $998244353$ 取模。换言之，若长为 $n$ 的好的排列一共有 $x$ 个，你需要输出 $\frac x{n!}$ 取模 $998244353$ 的结果。如果你不理解有理数的取模，可以看[这道题目](/problem/P2613)。

有 $q$ 次询问，每次给出一个 $m$。

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

第二行 $q$ 个正整数，表示每次询问的 $m_i$。保证询问升序且两两不同。

outputFormat: 对于每次询问一行一个整数表示答案对 $998244353$ 取模的值。


title: 冒泡排序

description:
有一个值域下标均为 $1\sim n$ 的排列或圆排列 $A$，定义 $f(A)$ 为将 $A$ 升序排序所需的最小操作次数。

每次操作中，你可以选择一个元素并向前**冒泡**若干次，一次**冒泡**定义为：若这个元素小于前一个元素，则可以交换它与前一个元素。当某次无法**冒泡**时，这次操作立即停止。否则可以连续**冒泡**任意次。

比如有排列 $[3,5,2,1,4]$，一次操作可以选择元素 $1$ ，得到排列 $[3,5,1,2,4],[3,1,5,2,4]$ 或 $[1,3,5,2,4]$ 。

若有圆排列 $[2,1,4,3]$，选择元素 $1$ 后可以得到圆排列 $[1,2,4,3],[3,2,4,1]$ 或 $[3,2,1,4]$ 。注意到圆排列中第 $1$ 个元素的前一个元素为第 $n$ 个元素。

排列或圆排列被升序排序，当且仅当对于所有 $\space 2 \leq i \leq n$，元素 $i$ 的前一个元素为元素 $i-1$。

给定 $n,k,type$，你需要：
- 在 $type=1$ 时求有多少长为 $n$ 的排列 $A$ 满足 $f(A)=k$ 。
- 在 $type=2$ 时求有多少长为 $n$ 的圆排列 $A$ 满足 $f(A)=k$ 。

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

inputFormat: 输入一行三个正整数 $n,k,type$，具体含义见题目描述。

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


title: 动态图连通性

description:
给定一张 $n$ 点 $m$ 边的**有向图**，初始时存在一条从 $1$ 到 $n$ 的路径。

你需要处理 $q$ 组询问，每组询问给定一个 $[1,m]$ 中的正整数 $x$，如果原图中的第 $x$ 条边仍存在且当前的图中删去原图中的第 $x$ 条边后仍有一条从 $1$ 到 $n$ 的路径，则删除原图中的第 $x$ 条边。

你需要报告每组询问中是否删去了第 $x$ 条边。

**请注意：一组询问中删除某条边后，这条边会被永远删除。也就是询问之间会相互影响。**

inputFormat:
输入第一行三个正整数 $n,m,q$，分别表示有向图的点数，边数以及询问个数。

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

接下来 $q$ 行，每行一个正整数 $x$，具体含义同题目描述。

outputFormat:
输出共 $q$ 行，每行一个正整数 $0$ 或 $1$。

如果在这组询问中删去了第 $x$ 条边，输出 $1$，否则输出 $0$。


title: 『MdOI R5』Variance

background: Subtask 1~5 为原数据，Subtask 6 为 hack 数据。

description:
给定两个长度为 $n$ 的整数序列 $a,b$，满足：
- $\forall i\in [1,n),a_i\le a_{i+1},b_i\le b_{i+1}$。

- $\forall i\in [1,n],a_i\le b_i$。

有一个长度为 $n$ 的实数序列 $c$，满足 $c_i\in [a_i,b_i]$，求 $c$ 的方差的最大值。

你只需要输出答案乘上 $n^2$ 之后的结果。容易证明这是一个整数。

### 提示

一个长度为 $n$ 的序列 $a$ 的方差为：$\dfrac{1}{n}\sum\limits_{i=1}^n (a_i-\overline{a})^2$。其中 $\overline{a}=\dfrac{1}{n}\sum\limits_{i=1}^n a_i$。

本题的计算过程中可能会涉及到超过 `long long` 范围的数，此时可能需要用到 `__int128` 进行处理。

我们提供了以下代码，它可以用于输出一个 `__int128` 类型的数：

``` cpp
void print(__int128 x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x<10)
	{
		putchar(x+48);
		return;
	}
	print(x/10);
	putchar(x%10+48);
}
```

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

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

第三行，$n$ 个整数，表示 $b_1,b_2,\dots,b_n$。

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

hint:
对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le a_i,b_i\le 10^9$。

$\operatorname{Subtask} 1(10\%)$：$n\le 2\times 10^3$，$a_i=b_i\le 10^5$。

$\operatorname{Subtask} 2(20\%)$：$n\le 10$，$a_i,b_i\le 5$。

$\operatorname{Subtask} 3(20\%)$：$n\le 2\times 10^3$，$a_i,b_i\le 10^5$。

$\operatorname{Subtask} 4(20\%)$：$n\le 10^5$，$a_i,b_i\le 2\times 10^3$。

$\operatorname{Subtask} 5(30\%)$：无特殊限制。

#### 样例说明 1

$c$ 只可能为 $(1,10)$。

#### 样例说明 2

一种最优的 $c$ 为 $(1,2,5)$。


title: [ZSHOI-R1] 巡城

background: 在 X 国国王多年的建设之下，她的国家发生了质的蜕变，从众多 $n$ 座城市却只有 $n-1$ 条道路的国家中脱颖而出。也就是说，X 国不再是一棵树了，而是一张图。

description:
国王为了能够集中自己的权力，稳固城邦，她对国家道路设计要求十分严苛，**任何两个城市之间的路径至多只有一条不经过首都**，虽然但是，没有人知道为什么这样能够更好地稳固 X 国。

有一天，X 国国王决定巡视所有的城市，她通过无线电在巡城前一天向所有的城市通知了这个好消息。热情的群众们也积极地做出了响应，准备迎接国王的到来。

国王一天只能造访一座城市，而且第一天她会从首都开始。

在之后的每一天，她会随机从与她所在城市直接相连的城市中**等概率**地选择一个她**没有前往过的城市**前往。如果不存在这样的城市，她会立即**原路返回**，从她来这个城市的路回去，再重复上述操作，因为有携带宇宙射线的传送门，这个过程**不消耗时间**。

爱戴她的群众们想要知道，他们的国王第一次到达他们所在城市的日期（她造访首都的那一天为 $1$，之后每一天一次加 $1$）的期望是多少，答案对 $998244353$ 取模。

保证城市构成的图是连通图，无自环与重边，且首都编号为 $1$。

inputFormat:
第一行有两个数 $n,m$，代表X国的城市数和路径数。

接下来的 $m$ 行，每行两个数 $u,v$ 表示城市的一条路径。

outputFormat:
共 $1$ 行，$n$ 个数。

第 $i$ 个数代表 $i$ 号城市的期望。


title: 「CGOI-3」残暴圣所

background:
终于打过春二心门的 ac 来到了春三，并决定预测一下残暴圣所（Ferocious Sanctuary）的难度。

[![](https://cdn.luogu.com.cn/upload/image_hosting/xolrra48.png?x-oss-process=image/resize,m_lfit,h_340,w_450)](//www.bilibili.com/video/BV1Cg411v7Ji)

description:
为了通关残暴圣所，ac 需要在接下来的 $2n$ 个时刻进行 $n$ 次操作。第 $i$ 次操作需要在时刻 $l_i$ 按下某个按键，此后一直按住这个按键，直到时刻 $r_i$ 松开它（$l_i<r_i$）。在每个时刻，ac 要么按下一个按键，要么松开一个按键，但是可以同时按住多个按键。

第 $i$ 次操作形成了一个操作区间 $[l_i,r_i]$，满足 $l_i$ 严格递增。并且，由于残暴圣所的关卡设计，任意两个操作形成的操作区间之间，要么不交，要么包含。

ac 设计了 $2n$ 个难度系数 $a_1,a_2,\dots,a_{2n}$。第 $i$ 次操作的难度可以用 $a_{l_i}\times a_{r_i}$ 来评估，而通关残暴圣所的难度即为所有操作的难度之和。

然而，由于 ac 卡在了残暴圣所的第一面，所以他并不知道每个操作的操作区间。在给定 $n$ 和 $\{a\}$ 的前提下，请你计算对于所有可能的情况，通关残暴圣所的难度之和，对 $998244353$ 取模。

#### 形式化题意：

给定一个长为 $2n$ 的数列 $a_1,a_2,\dots,a_{2n}$。

定义“区间组”由 $n$ 个区间组成，第 $i$ 个区间为 $[l_i,r_i]\ (1\le l_i<r_i\le2n)$，求所有满足下列条件的区间组的 $\sum_{i=1}^na_{l_i}\times a_{r_i}$ 之和对 $998244353$ 取模：

1. $l_1,r_1,l_2,r_2,\dots,l_n,r_n$ 是 $1,2,\dots,2n$ 的一个排列。
2. $\forall 1\le i<n$，$l_i<l_{i+1}$。
3. $\forall i,j$，$[l_i,r_i]\cap[l_j,r_j]=\varnothing$ 或 $[l_i,r_i]\sube[l_j,r_j]$ 或 $[l_j,r_j]\sube[l_i,r_i]$。

inputFormat:
第一行一个整数 $n$，表示区间数。

第二行 $2n$ 个整数 $a_i$，含义如上所述。

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


title: 「CGOI-3」灵气

background:
>「地牢中回荡着尖叫声...」

打完世花的 ac 进入地牢刷灵气……

花后地牢十分险恶，ac 想在地牢里搭满单向门。

[![](https://cdn.luogu.com.cn/upload/image_hosting/a1ewte9n.png)](https://www.bilibili.com/video/BV1jf4y1Z7RB)

description:
ac 世界里的地牢有 $n$ 个小房间，恰好存在 $n-1$ 条过道，并且每个小房间连通。第 $i$ 个小房间生成的怪在一个时刻**最多只会存在一个**，且**伤害为 $a_i$**。

为了方便刷灵气，ac 在每个过道上建了一个单向门。

每一秒会发生以下几个事件之一：

1. 第 $x$ 个房间生成了一个怪。怪**不会穿墙**，只会顺着单向门方向移动。

2. 第 $x$ 个房间生成的怪被 ac 的仆从干掉了。

3. ac 想要挂机刷怪，于是他希望知道，如果从时刻 1 开始站在房间 $x$ 一直到当前时刻，受到伤害最多的一个时刻所受伤害是多少。

这里定义一个时刻受到伤害为可以走到 ac 所在房间的怪的伤害值总和，“可以走到”定义为可以穿过若干条单向门到达 ac 的房间（若干可以为 $0$）。ac 非常强大，不会中途被怪打死。

当然，ac 所在的位置**不会改变怪的刷新**和**仆从的行为**。

#### 简化版题面

一棵树，每个点有个点权，每条边有个方向。

有个集合，一开始为空，三个操作：

1. 在集合中加入一个点。
2. 删除集合中的一个点。
3. 给出一个点 $x$，询问集合中满足可以走到 $x$ 的点的点权之和的历史最大值。

inputFormat:
第一行，两个整数 $n,m$，分别表示房间个数和事件个数。

接下来一行，共 $n$ 个整数，第 $i$ 个数表示 $i$ 房间中怪的伤害 $a_i$。

接下来 $n-1$ 行，每行两个整数 $x,y$，表示 $x$ 与 $y$ 有一条过道，单向门方向为 $x\rightarrow y$ 。

接下来 $m$ 行，第 $i$ 行两个整数 $fl,x$，表示第 $x$ 号房间发生了 $fl$ 号事件。

对于 $fl=1$ 的操作，保证 $x$ 号房间没有怪。

对于 $fl=2$ 的操作，保证 $x$ 号房间有怪。

outputFormat: 对每一个 $fl=3$ 的事件，输出一个整数表示答案，并用换行隔开。

hint:
#### 样例一说明
第一个询问中，时刻 $1$ 存在怪的房间为 $\{4\}$，$4$ 号房间的怪可以走到 $1$ 号房间，因此答案为 $a_4=4$。

第二个询问中，受到伤害最大的时刻为时刻 $1$，答案为 $a_4=4$。其中时刻 $5$ 存在怪的房间为 $\{3,5\}$，而 $5$ 号房间的怪走不到 $1$ 号房间，因此此时刻受到伤害为 $a_3=3<4$，不是最大值。

第三个询问中，受到伤害最大的时刻为时刻 $5$，$3,5$ 号房间的怪均可走到 $5$，因此答案为 $a_3+a_5=8$。

---

#### 数据范围
**「本题采用捆绑测试」**

对于 $10\%$ 的数据，$n,m \leq 2000$。

对于另 $10\%$ 的数据，过道 $(x,y)$ 单向门满足 $x<y$。

对于另 $30\%$ 的数据，不存在 2 事件。

对于 $100\%$ 的数据，$1\leq n,m \leq 2\times 10^5$，$1\leq a_i\leq10^4$。

~~但是地牢幽魂就是穿墙怪（）（）（）~~

~~不会真的有人会在地牢里搭满单向门吧。~~


title: 小清新数据结构题

description:
给定 $n$ 条数据，第 $i$ 条数据有 $s_i$ 个数，依次记为 $a_{i, 1}, a_{i, 2}, \dots a_{i, s_i}$。

现在有 $q$ 次询问，每次询问第 $x$ 条数据的第 $y$ 个数，即 $a_{x,y}$ 是多少。

为了避免输出过大，你只需要输出所有询问的答案的**按位异或**和。

按位异或指的是 C++ 中的「^」运算符。你可以参考「说明/提示」中的代码求出若干个数的按位异或和。

inputFormat:
第一行是两个整数，表示数据条数 $n$ 和询问次数 $q$。

接下来 $n$ 行，每行依次表示一条数据，每行首先是一个整数，表示本条数据的数字个数 $s_i$，接下来 $s_i$ 个整数，依次表示本条数据的每个数字。

接下来 $q$ 行，每行两个整数 $x, y$，表示一次查询。

outputFormat: 输出一行一个整数表示所有询问的答案的按位异或之和。

hint:
### 样例 1 解释

第一次询问的结果为 $5$，第二次询问的结果为 $2$。他们做按位异或的结果为 $7$。

### 数据规模与约定

对于全部的测试点，保证 $1 \leq n, q, s_i \leq 3 \times 10^6$，$0 \leq a_i \lt 2^{32}$，$1 \leq x \leq n$，$1 \leq y \leq s_x$，且 $\sum\limits_{i = 1}^n s_i \leq 5 \times 10^6$，即 $s_1 + s_2 + \dots + s_n \leq 5 \times 10^6$。

### 提示

对于使用 C++ 的选手，你可以用如下的函数返回若干个数的按位异或和。
```cpp
#include <vector>
unsigned int getXorSum(const std::vector<unsigned int>& rec) {
  unsigned ret = 0;
  for (int i = 0; i < rec.size(); ++i) ret ^= rec[i];
  return ret;
} // 将需要求按位异或和的数放在 vector 中传参。
```

请注意大量数据读入对程序效率造成的影响。


title: 心跳 加强版

background:
本题为 [洛谷 9 月月赛 II & NR I. E. 心跳](/problem/P8554) 的加强版，唯一的区别在于数据范围改为 $n \le 5 \times {10}^6$。

---

“清晰的跳动声传达来的，重叠的声响和流动的思念。

约定再也不要分开吧，希望无论何时都不要让你寂寞。”

恋爱之时，人的心情不会一成不变，可喜悦和悲伤会随着时间流逝而归于平淡。最令人难忘的是那些“心动”的感觉，那些因未曾经历而喜出望外的感觉。因此，有些时候，失去某些特别美好的回忆，反而能让心动的感觉增多。可为此失去那些回忆，真的值得吗？

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


title: [蓝桥杯 2020 省 A1] 填空问题

description:
## A：跑步训练。

小明要做一个跑步训练。初始时，小明充满体力，体力值计为 $10000$。如果小明跑步，每分钟损耗 $600$ 的体力。如果小明休息，每分钟增加 $300$ 的体力。体力的损耗和增加都是均匀变化的。

小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循环。如果某个时刻小明的体力到达 $0$，他就停止锻炼。请问小明在多久后停止锻炼。

为了使答案为整数，请以秒为单位输出答案。答案中只填写数，不填写单位。

## B：合并检测。

新冠疫情由新冠病毒引起，最近在 $A$ 国蔓延，为了尽快控制疫情，$A$ 国准备给大量民众进病毒核酸检测。

然而，用于检测的试剂盒紧缺。为了解决这一困难，科学家想了一个办法：合并检测。即将从多个人（$k$ 个）采集的标本放到同一个试剂盒中进行检测。如果结果为阴性，则说明这 $k$ 个人都是阴性，用一个试剂盒完成了 $k$ 个人的检测。如果结果为阳性，则说明至少有一个人为阳性，需要将这 $k$ 个人的样本全部重新独立检测（从理论上看，如果检测前 $k-1$ 个人都是阴性可以推断出第 $k$ 个人是阳性，但是在实际操作中不会利用此推断，而是将 $k$ 个人独立检测），加上最开始的合并检测，一共使用了 $k+1$ 个试剂盒完成了 $k$ 个人的检测。$A$ 国估计被测的民众的感染率大概是 $1\%$，呈均匀分布。请问 $k$ 取多少能最节省试剂盒？

## C：分配口罩。

某市市长获得了若干批口罩，给定每批口罩的数量，市长要把口罩分配给市内的 $2$ 所医院。

```
masks=[9090400,8499400,5926800,8547000,4958200,4422600,
5751200,4175600,6309600,5865200,6604400,4635000,
10663400,8087200,4554000]
```

由于物流限制，每一批口罩只能全部分配给其中一家医院。市长希望 $2$ 所医院获得的口罩总数之差越小越好。请你计算这个差最小是多少？

## D：矩阵。

把 $1 \sim 2020$ 放在 $2 \times 1010$ 的矩阵里。要求同一行中右边的比左边大，同一列中下边的比上边的大。一共有多少种方案？

答案很大，你只需要给出方案数除以 $2020$ 的余数即可。

## E：完美平方数。

如果整个整数 $X$ 本身是完全平方数，同时它的每一位数字也都是完全平方数，我们就称 $X$ 是完美平方数。前几个完美平方数是 $0$、$1$、$4$、$9$、$49$、$100$、$144$ …。

请你计算第 $2020$ 个完美平方数是多少？

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。

hint:
答题模板，可供参考。

```cpp
#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "The answer of task A", // 双引号中替换为 A 题的答案
        "The answer of task B", // 双引号中替换为 B 题的答案
        "The answer of task C", // 双引号中替换为 C 题的答案
        "The answer of task D", // 双引号中替换为 D 题的答案
        "The answer of task E", // 双引号中替换为 E 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}
```


title: [蓝桥杯 2020 省 B1] 填空问题

description:
## 试题 A ：跑步训练

### 【问题描述】

小明要做一个跑步训练。

初始时，小明充满体力，体力值计为 $10000$ 。如果小明跑步，每分钟损耗 $600$  的体力。如果小明休息，每分钟增加 $300$ 的体力。体力的损耗和增加都是均匀变化的。

小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循环。如果某个时刻小明的体力到达 $0$，他就停止锻炼。请问小明在多久后停止锻炼。

请问小明在多久后停止锻炼。为了使答案为整数，请以秒为单位输出答案。答案中只填写数，不填写单位。

### 【答案提交】

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：纪念日

### 【问题描述】

$2020$ 年 $7$ 月 $1$ 日是×××××成立 $99$ 周年纪念日。

×××××成立于 $1921$ 年 $7$ 月 $23$ 日。

请问从 $1921$ 年 $7$ 月 $23$ 日中午 $12$ 时到 $2020$ 年 $7$ 月 $1$ 日中午 $12$ 时一共包含多少分钟?

### 【答案提交】

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C ：合并检测

### 【问题描述】

新冠疫情由新冠病毒引起，最近在 $\mathrm{A}$ 国蔓延，为了尽快控制疫情，$\mathrm{A}$ 国准备给大量民众进病毒核酸检测。

然而，用于检测的试剂盒紧缺。

为了解决这一困难，科学家想了一个办法：合并检测。即将从多个人 $(k$ 个) 采集的标本放到同一个试剂盒中进行检测。如果结果为阴性，则说明这 $k$ 个人都是阴性，用一个试剂盒完成了 $k$ 个人的检测。如果结果为阳性，则说明至少有一个人为阳性，需要将这 $k$ 个人的样本全部重新独立检测（从理论上看，如果检测前 $k-1$ 个人都是阴性可以推断出第 $k$ 个人是阳性，但是在实际操作中不会利用此推断，而是将 $k$ 个人独立检测)，加上最开始的合并检测，一共使用了 $k+1$ 个试剂盒完成了 $k$ 个人的检测。

$\mathrm{A}$ 国估计被测的民众的感染率大概是 $1 \%$，呈均匀分布。请问 $k$ 取多少能最节省试剂盒?

### 【答案提交】

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：REPEAT 程序

### 【问题描述】

附件 `prog.txt` 中是一个用某种语言写的程序。

其中 REPEAT $k$ 表示一个次数为 $k$ 的循环。循环控制的范围由缩进表达，从次行开始连续的缩进比该行多的（前面的空白更长的）为循环包含的内容。

例如如下片段:

```
REPEAT 2:
    A=A+4
    REPEAT 5:
        REPEAT 6:
            A=A+5
        A=A+7
    A=A+8
A=A+9

```

该片段中从 $A=A+4$ 所在的行到 $A=A+8$ 所在的行都在第一行的循环两次中。

REPEAT 6：所在的行到 $A=A+7$ 所在的行都在 REPEAT 5：循环中。

$A=A+5$ 实际总共的循环次数是 $2 \times 5 \times 6=60$ 次。

请问该程序执行完毕之后，$\mathrm{A}$ 的值是多少?

### 【答案提交】

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E ：矩阵

### 【问题描述】

把 $1 \sim 2020$ 放在 $2 \times 1010$ 的矩阵里。要求同一行中右边的比左边大，同一列中下边的比上边的大。一共有多少种方案?

答案很大，你只需要给出方案数除以 $2020$  的余数即可。

### 【答案提交】

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。


title: [蓝桥杯 2020 省 AB1] 解码

description:
小明有一串很长的英文字母，可能包含大写和小写。

在这串字母中，有很多连续的是重复的。小明想了一个办法将这串字母表达得更短：将连续的几个相同字母写成字母 + 出现次数的形式。 例如，连续的 $5$ 个 `a`，即 `aaaaa`，小明可以简写成 `a5`（也可能简写成 `a4a`、`aa3a` 等）。

对于这个例子：`HHHellllloo`，小明可以简写成 `H3el5o2`。为了方便表达，小明不会将连续的超过9个相同的字符写成简写的形式。

现在给出简写后的字符串，请帮助小明还原成原来的串。

inputFormat: 输入一行包含一个字符串。

outputFormat: 输出一个字符串，表示还原后的串。

hint:
对于所有评测用例，字符串由大小写英文字母和数字组成，长度不超过 $100$。请注意原来的串长度可能超过 $100$。

蓝桥杯 2020 第一轮省赛 A 组 F 题（B 组 G 题）。


title: [蓝桥杯 2020 省 AB1] 走方格

description:
在平面上有一些二维的点阵。

这些点的编号就像二维数组的编号一样，从上到下依次为第 $1$ 至第 $n$ 行，从左到右依次为第 $1$ 至第 $m$ 列，每一个点可以用行号和列号来表示。

现在有个人站在第 $1$ 行第 $1$ 列，要走到第 $n$ 行第 $m$ 列。只能向右或者向下走。

注意，如果行号和列数都是偶数，不能走入这一格中。

问有多少种方案。

inputFormat: 输入一行包含两个整数 $n$，$m$。

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

hint:
$1\le n,m\le30$。

蓝桥杯 2020 第一轮省赛 A 组 G 题（B 组 H 题）。


title: [蓝桥杯 2020 省 A1] 整数小拼接

description:
给定一个长度为 $n$ 的数组 $A_1,A_2,\cdots,A_n$。你可以从中选出两个数 $A_i$ 和 $A_j$($i\neq j$)，然后将 $A_i$ 和 $A_j$ 一前一后拼成一个新的整数。例如 `12` 和 `345` 可以拼成 `12345` 或 `34512`。注意交换 $A_i$ 和 $A_j$ 的顺序总是被视为 $2$ 种拼法，即便是 $A_i=A_j$ 时。

请你计算有多少种拼法满足拼出的整数小于等于 $K$。

inputFormat:
第一行包含 $2$ 个整数 $n$ 和 $K$。

第二行包含 $n$ 个整数 $A_1,A_2,\cdots,A_n$。

outputFormat: 一个整数代表答案。


title: [蓝桥杯 2020 省 A1] 超级胶水

description:
小明有 $n$ 颗石子，按顺序摆成一排，他准备用胶水将这些石子粘在一起。

每颗石子有自己的重量，如果将两颗石子粘在一起，将合并成一颗新的石子，重量是这两颗石子的重量之和。

为了保证石子粘贴牢固，粘贴两颗石子所需要的胶水与两颗石子的重量乘积成正比，本题不考虑物理单位，认为所需要的胶水在数值上等于两颗石子重量的乘积。

每次合并，小明只能合并位置相邻的两颗石子，并将合并出的新石子放在原来的位置。

现在，小明想用最少的胶水将所有石子粘在一起，请帮助小明计算最少需要多少胶水。

inputFormat:
输入的第一行包含一个整数 $n$，表示初始时的石子数量。

第二行包含 $n$ 个整数 $w_1, w_2, \cdots, w_n$ 依次表示每颗石子的重量。

outputFormat: 输出一行包含一个整数，表示最少需要的胶水数。

hint:
对于 $20\%$ 的评测用例，$1 \le n \le 15$。

对于 $60\%$ 的评测用例，$1\leq n \leq 100$。

对于 $80\%$ 的评测用例，$1\leq n \leq 1000$。

对于所有评测用例，$1\leq n \leq 10^5$，$1 \leq w_i \leq 1000$。

蓝桥杯 2020 第一轮省赛 A 组 I 题。


title: [蓝桥杯 2020 省 AB1] 网络分析

description:
小明正在做一个网络实验。

他设置了 $n$ 台电脑，称为节点，用于收发和存储数据。

初始时，所有节点都是独立的，不存在任何连接。

小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信了。两个节点如果存在网线连接，称为相邻。

小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接或间接相邻的节点都收到了信息。所有发送和接收的节点都会将信息存储下来。一条信息只存储一次。

给出小明连接和测试的过程，请计算出每个节点存储信息的大小。

inputFormat:
输入的第一行包含两个整数 $n$，$m$，分别表示节点数量和操作数量。节点从 $1$ 至 $n$ 编号。

接下来 $m$ 行，每行三个整数，表示一个操作。

如果操作为 `1 a b`，表示将节点 $a$ 和节点 $b$ 通过网线连接起来。当 $a=b$ 时，表示连接了一个自环，对网络没有实质影响。

如果操作为 `2 p t`，表示在节点 $p$ 上发送一条大小为 $t$ 的信息。

outputFormat: 输出一行，包含 $n$ 个整数，相邻整数之间用一个空格分割，依次表示进行完上述操作后节点 $1$ 至节点 $n$ 上存储信息的大小。

hint:
对于 $30\%$ 的评测用例，$1 ≤ n ≤ 20$，$1 ≤ m ≤ 100$。

对于 $50\%$ 的评测用例，$1 ≤ n ≤ 100$，$1 ≤ m ≤ 1000$。

对于 $70\%$ 的评测用例，$1 ≤ n ≤ 1000$，$1 ≤ m ≤ 10000$。

对于所有评测用例，$1 ≤ n ≤ 10000$，$1 ≤ m ≤ 10^5$ ，$1 ≤ t ≤ 100$。

蓝桥杯 2020 第一轮省赛 A 组 J 题（B 组 J 题）。


title: [蓝桥杯 2020 省 B1] 整除序列

description: 有一个序列，序列的第一个数是 $n$，后面的每个数是前一个数整除 $2$，请输出这个序列中值为正数的项。

inputFormat: 输入一行包含一个整数 $n$。

outputFormat: 输出一行，包含多个整数，相邻的整数之间用一个空格分隔，表示答案。

hint:
对于 $80\%$ 的评测用例，$1\le n\le10^9$。

对于所有评测用例，$1\le n\le10^{18}$。

蓝桥杯 2020 第一轮省赛 B 组 F 题。


title: [蓝桥杯 2020 省 B1] 整数拼接

description:
给定一个长度为 $n$ 的数组 $A_1,A_2,\cdots,A_n$。你可以从中选出两个数 $A_i$ 和 $A_j$（$i\neq j$），然后将 $A_i$ 和 $A_j$ 一前一后拼成一个新的整数。例如 `12` 和 `345` 可以拼成 `12345` 或 `34512`。注意交换 $A_i$ 和 $A_j$ 的顺序总是被视为 $2$ 种拼法，即便是 $A_i=A_j$ 时。

请你计算有多少种拼法满足拼出的整数是 $K$ 的倍数。

hint:
对于所有评测用例，$1\le n\le10^5$，$1\le k\le10^5$，$1\le A_i\le10^9$。

蓝桥杯 2020 第一轮省赛 B 组 I 题。


title: [蓝桥杯 2020 省 AB3] 填空问题(缺少 inc.txt, E 题数据)

description:
## 试题 A ：数青蛙

### 【问题描述】

“一只青蛙一张嘴，两只眼睛四条腿。两只青蛙两张嘴，四只眼睛八条腿。

三只青蛙三张嘴，六只眼睛十二条腿。……。二十只青蛙二十张嘴，四十只眼睛八十条腿。

请问上面这段文字，如果完全不省略，全部写出来，从 $1$  到 $20$  只青蛙，总共有多少个汉字。

约定：数字 $2$  单独出现读成 “两”，在其他数里面读成 “二”，例如 “十二”。$10$ 读作 “十”，$11$ 读作 “十一"，$22$ 读作 “二十二”。

请只计算汉字的个数，标点符号不计算。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：互质

### 【问题描述】

今年是 $2020$ 年，今天是 $10$ 月 $18$ 日。

请问在 $1$ 到 $2020$ 中，有多少个数与 $1018$  互质。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 C ：车牌

### 【问题描述】

$\mathrm{A}$ 市的车牌由六位组成，其中前三位可能为数字 `0` 至 `9` ，或者字母 `A` 至 `F`，每位有 $16$  种可能。后三位只能是数字 `0` 至 `9`。为了减少攀比，车牌中不能有连续三位是相同的字符。

例如，`202020` 是合法的车牌，`AAA202` 不是合法的车牌，因为前三个字母相同。

请问，$\mathrm{A}$ 市有多少个合法的车牌?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：Fibonacci 集合

### 【问题描述】

小蓝定义了一个 Fibonacci 集合 $F$，集合的元素如下定义:

1. 最小的 $5$  个 Fibonacci 数 $1,2,3,5,8$ 属于集合 $F$。

2. 如果一个元素 $x$ 属于 $F$，则 $3 x+2 、 5 x+3$ 和 $8 x+5$ 都属于集合 $F$。

3. 其他元素都不属于 $F$。

请问，这个集合中的第 $2020$  小元素的值是多少?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E：上升子串

### 【问题描述】

小蓝有一个字母矩阵，他喜欢和小伙伴们在这个矩阵上玩一些游戏。

今天，他打算玩找上升子串的游戏。游戏是合作性质的。小蓝和小伙伴们首先要在矩阵中指定一个位置，然后从这个位置开始，向上下左右相邻位置移动，移动必须满足所到达位置上的字母比当前位置大。小蓝和小伙伴们可以移动任意多次，也可以随时停下来，这样就找到了一个上升子串。只要子串在矩阵中的位置不同，就认为是不同的子串。

小蓝想知道,一共可以找到多少个上升子串。

小蓝的矩阵很大，已经放在了试题目录下面，叫 inc.txt。为了更清楚的描述问题，他还找了一个很小的矩阵用来解释。

例如，对于矩阵:

$A B$

$\mathrm{BC}$

可以找到 $4$ 个长度为 $1$ 的上升子串、$4$ 个长度为 $2$  的上升子串、$2$ 个长度为 $3$ 的上升子串，共 $10$  个。

现在，请你对于小蓝的大矩阵，找到上升子串的数量。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。


title: [蓝桥杯 2020 省 AB3] 日期识别

description:
小蓝要处理非常多的数据, 其中有一些数据是日期。

在小蓝处理的日期中有两种常用的形式：英文形式和数字形式。

英文形式采用每个月的英文的前三个字母作为月份标识，后面跟两位数字表示日期，月份标识第一个字母大写，后两个字母小写, 日期小于 $10$ 时要补前导 $0$。$1$ 月到 $12$ 月英文的前三个字母分别是 `Jan`、`Feb`、`Mar`、`Apr`、`May`、`Jun`、`Jul`、`Aug`、`Sep`、`Oct`、`Nov`、`Dec`。

数字形式直接用两个整数表达，中间用一个空格分隔，两个整数都不写前 导 `0`。其中月份用 $1$ 至 $12$ 分别表示 $1$ 月到 $12$ 月。

输入一个日期的英文形式, 请输出它的数字形式。

inputFormat: 输入一个日期的英文形式。

outputFormat: 输出一行包含两个整数，分别表示日期的月和日。

hint: 蓝桥杯 2020 第三轮省赛 AB 组 F 题。


title: [蓝桥杯 2020 省 AB3] 乘法表

description:
九九乘法表是学习乘法时必须要掌握的。在不同进制数下，需要不同的乘法表。

例如, 四进制下的乘法表如下所示：

```
1*1=1
2*1=2 2*2=10
3*1=3 3*2=12 3*3=21
```

请注意，乘法表中两个数相乘的顺序必须为样例中所示的顺序，不能随意交换两个乘数。

给定 $P$，请输出 $P$ 进制下的乘法表。

inputFormat: 输入一个整数 $P$。

outputFormat: 输出 $P$ 进制下的乘法表。$P$ 进制中大于等于 $10$ 的数字用大写字母 `A`、`B`、`C`、$\cdots$ 表示。

hint:
对于所有评测数据, $2 \leq P \leq 36$。

蓝桥杯 2020 第三轮省赛 AB 组 G 题。


title: [蓝桥杯 2020 省 AB3] 限高杆

description:
某市有 $n$ 个路口，有 $m$ 段道路连接这些路口，组成了该市的公路系统。其中一段道路两端一定连接两个不同的路口。道路中间不会穿过路口。

由于各种原因，在一部分道路的中间设置了一些限高杆，有限高杆的路段货车无法通过。

在该市有两个重要的市场 $A$ 和 $B$，分别在路口 $1$ 和 $n$ 附近，货车从市场 $A$ 出发，首先走到路口 $1$，然后经过公路系统走到路口 $n$，才能到达市场 $B$。两个市场非常繁华，每天有很多货车往返于两个市场之间。

市长发现，由于限高杆很多，导致货车可能需要绕行才能往返于市场之间，这使得货车在公路系统中的行驶路程变长，增加了对公路系统的损耗，增加了能源的消耗，同时还增加了环境污染。

市长决定要将两段道路中的限高杆拆除，使得市场 $A$ 和市场 $B$ 之间的路程变短。请问最多能减少多长的距离?

inputFormat:
输入的第一行包含两个整数 $n$，$m$，分别表示路口的数量和道路的段数。

接下来 $m$ 行，每行四个整数 $a$，$b$，$c$，$d$，表示路口 $a$ 和路口 $b$ 之间有一段长度为 $c$ 的道路。如果 $d$ 为 $0$，表示这段道路上没有限高杆; 如果 $d$ 为 $1$，表示 这段道路上有限高杆。两个路口之间可能有多段道路。

输入数据保证在不拆除限高杆的情况下，货车能通过公路系统从路口 $1$ 正常行驶到路口 $n$ 。

outputFormat: 输出一行，包含一个整数，表示拆除两段道路的限高杆后，市场 $A$ 和市场 $B$ 之间的路程最大减少多长距离。

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

只有两段道路有限高杆，全部拆除后，$1$ 到 $n$ 的路程由原来的 $17$ 变为了 $11$，减少了 $6$。

**【评测用例规模与约定】**

对于 $30 \%$ 的评测样例，$2 \leq n \leq 10,1 \leq m \leq 20,1 \leq c \leq 100$。

对于 $50 \%$ 的评测样例，$2 \leq n \leq 100,1 \leq m \leq 1000,1 \leq c \leq 1000$。

对于 $70 \%$ 的评测样例，$2 \leq n \leq 1000,1 \leq m \leq 10000,1 \leq c \leq 10000$。

对于所有评测样例，$2 \leq n \leq 10000,2 \leq m \leq 10^5,1 \leq c \leq 10000$，至少 有两段道路有限高杆。

蓝桥杯 2020 第三轮省赛 AB 组 H 题。