title: 「Wdcfr-1」Alice Wins! (hard version)

description:
**The difference between the versions is the limit of operations.**

Alice is a cute girl who has a lot of dolls.

There are $4\cdot n$ dolls playing *rock-paper-scissors*. They are divided into two teams: Team A and Team B. Each team contains $2\cdot n$ dolls.

A total of $2\cdot n$ rounds of the game will be played. In the $i$-th round, the $i$-th doll in Team A will play against the $i$-th doll in Team B. If the doll in Team A wins, Team A will get $1$ point. If it loses, Team A will lose $1$ point. If it ties, Team A will not get points.

Alice knows all the dolls' choices in this game. To be precise, she uses two arrays $a$ and $b$ to represent the choices of the dolls in the two teams. $a_i$ means the choice of the $i$-th doll in Team A, and $b_i$ means the choice of the $i$-th doll in Team B. In this question, we use $1$ for rock, $2$ for scissors, and $3$ for paper.

Now for **each team**, Alice wants to change the choices of **exact** $n$ dolls to make the score of Team A as high as possible.

Find the maximum score of Team A and its construction method. If there are multiple answers print any of them (you still have to maximize the score of Team A).

outputFormat:
For each test case, output three lines.

The first line contains one integer, which is the maximize the score of Team A.

The second line contains an array $a'$ of length $2\cdot n$, which represents the modified $a$ array. For integers $1$ to $2\cdot n$, if $a_i \ne a'_i$, then it means you have modified the hand shape of one player in Team A.

The third line contains an array $b'$ of length $2\cdot n$, which represents the modified $b$ array. For integers $1$ to $2\cdot n$, if $b_i \ne b'_i$, then it means you have modified the hand shape of one player in Team B.

translation:
AB 每队 $2n$ 人正在玩石头剪刀布。A 队第 $i$ 个人出 $a_i$，B 队第 $i$ 个人出 $b_i$。编号相同的人会对战。若 A 队赢则加一分，平不得分，输扣一分。你必须**恰好**改变**每队** $n$ 个人的出拳方案，使得 A 队的得分最高。输出得分的最大值和任意一组构造方案。

本题中，我们用 $1$ 代表石头，$2$ 代表剪刀，$3$ 代表布。

hint:
### Explanation

For the first test case, we can change $a_2$ to $1$ and $b_1$ to $2$. Then Team A can get $2$ points. It can be proved that this is the maximum score that Team A can get.

### Constraints

$1\le T,n \le 10^5;\ 1\le a_i,b_i \le 3$. The sum of $n$ of all test cases $\le 10^5$.


title: [WFOI - 02] I wanna win the race（比赛）

type: P

background:
> best is yet to come

kid 不小心进入了联机模式，他需要比他的对手更快通关才能取得胜利……

description:
kid 走进了一个场地，若干名选手在进行比赛，场地可以抽象为一个坐标系。

选手们要从 $\left(1,1\right)$ 跑到 $\left(n,n\right)$，若当前选手处在 $\left(x,y\right)$，则他们下一步可以移动到 $\left(x\pm1,y\right)$ 或 $\left(x,y\pm1\right)$，注意，他们**仅可以在第一象限活动**，即任何时候 $x>0,y>0$。

所有点最开始都是 $\texttt{A}$ 类点，主办方选择了一个三元组 $\left(a,b,c\right)$，将所有满足 $a\leq x\leq b$ 且 $y\leq c$ 的点 $\left(x,y\right)$ 变为 $\texttt{B}$ 类点，选手每经过一个 $\texttt{A}$ 类需要耗时 $1$ 秒，每经过一个 $\texttt{B}$ 类需要耗时 $2$ 秒。请注意，**起始点和终点也要纳入计算。**

kid 想要赢得这场比赛，他想知道**最少**需要多少秒能到达终点。

**请注意，在【数据范围】中有重要的约束条件。**

inputFormat: 共两行，第一行一个整数 $n$，第二行三个整数 $a,b,c$。

outputFormat: 输出一个整数表示 kid 通关所需要的的最少秒数。

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

下图是其中一种可行的方案，紫色点为 $\texttt{A}$ 类点，红色点为 $\texttt{B}$ 类点：

![](https://s1.ax1x.com/2022/03/06/bBvQPJ.png)

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

**本题采用 $\tt Subtask$ 捆绑测试。**

对于 $30\%$ 的数据，$1<a<b<n\leq 10^3，0<c\leq 10^3$。

对于 $100\%$ 的数据，$1<a<b<n\leq 10^9，0<c\leq 10^9$。


title: 「Wdcfr-1」Beautiful Array

description:
In this problem, we define a sequence of `(` and `)` as a "bracket sequence".

The definition of *Regular Bracket Sequence* is as follows:

1. `()` is a Regular Bracket Sequence.
1. If `A` is a Regular Bracket Sequence, then `(A)` is also a Regular Bracket Sequence.
1. If `A` and `B` are Regular Bracket Sequences, then `AB` is also a Regular Bracket Sequence.

For example: `()`, `(())`, and `()()` are all Regular Bracket Sequences, but `)(`, `()(` are not.

In particular, an empty sequence is **not** a Regular Bracket Sequence sequence in this problem.

Now ~~cute~~ Ran gives you a bracket sequence $s$ of length $n$. She wants you to construct $2\cdot m$ **strictly increasing** arrays. Let us denote them as
 $p_1,p_2,\cdots,p_{2 m}$ (you can leave any of them empty). You need to ensure that all integers between $1\sim n$ appear **exactly once** in these arrays.

An array $p_i=\{r_1,r_2,\cdots,r_k\}$ is *Beautiful* if    $\{s_{r_1},s_{r_2},\cdots,s_{r_k}\}$ is a Regular Bracket Sequence.

Ran wonders whether it is possible to construct these arrays so that at least $m$ of the $2\cdot m$ arrays are "beautiful arrays".

inputFormat:
Each test contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains two integers $n$ and $m$, and the second line contains a bracket sequence $s$.

outputFormat:
For each test case, print one line.

If it is possible to construct these arrays, print $1$. Otherwise print $0$.

translation:
定义一个字符串为括号串当且仅当其仅由 `(` 和 `)` 组成。

试将一个长度为 $n$ 的括号串分为 $2m$ 个子序列，子序列可以为空，且每个字符都必须分到恰好一个子序列中，使得至少 $m$ 个子序列为匹配的括号串。**空序列不算匹配的括号序列**。无解请输出 $0$，否则输出 $1$。本题多组数据，其中数据组数为 $T$。

定义 $A$ 为 $B$ 的子序列当且仅当 $A$ 能由 $B$ 在顺序不改变的前提下删除若干元素后得到。

*样例 $1$ 解释：你可以将第一个和第二个字符分入第一个子序列，让第二个子序列为空子序列。此时第一个子序列为 `()`，第二个为空，总计有一个匹配的括号序列，满足要求。

hint:
### Explanation

For the first test case, we can construct $p_1=\{1,2\}$ and $ p_2=\{\}$. So $p_1$ is a "beautiful array".

For the second test case, it is obvious that we cannot use two numbers to construct $99$ beautiful arrays.

### Constraints

$1\le T,n,m\le 200$.


title: 寻宝（Treasure）

description:
铃准备到一个 $2$ 行 $n+1$ 列的方格图上寻宝。
有这样寻宝的机会，她不会放过任何一个可以获取的宝物。

每个方格都有两种状态：**空地** 或 **墙壁**。

**空地** 可以被自由穿过，除了第一列的下面都埋藏有宝物，地图的第一列一定是空地，也是地图的入口。

**墙壁** 不能被穿过。

需要注意的是，她每次只能移动到相邻的方格，且地图的边界也是不能被穿过的。

铃还不知道地图的形态，正在考虑策略时，澪说：「我知道地图中恰好有 $k$ 个墙壁哦，对于所有可能的地图，有多少种情况你能找到恰好 $m$ 个宝物呢？」
「那我不回答又怎样嘛。」铃只想着挖宝，轻浮地答道。
「欸？那还有好几个藏宝点我就不告诉你了～」澪表现出一副认真的样子，「不过我也不难为你，你求出答案对 $998244353$ 取模的结果就可以啦。」

铃没有办法，只能请你帮忙算出答案。

inputFormat: 仅一行三个正整数 $n,k,m$。

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

hint:
【样例一解释】

地图大小为 $2\times(3+1)$，有 $3$ 个障碍。其中有 $4$ 种情况可以找到恰好 $2$ 个宝物，具体如下：

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

图中绿色的部分表示入口，灰色表示墙壁，白色代表**有宝藏的**空地。
可以看出，有且仅有图中 $4$ 种情况可以由入口走到恰好 $2$ 块空地上，即获得 $2$ 个宝物。

故答案为 $4$。

【数据范围】

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

Subtask1（11 pts）：$n\leq 12$；
Subtask2（19 pts）：$n\leq 1000$；
Subtask3（31 pts）：$n \leq 5\times 10^4$；
Subtask4（39 pts）：无特殊限制。

对于 $100\%$ 的数据，$2\le n \le 3\times 10^6$，$m,k\geq 2$，$m+k\leq 2n$。

【提示】
这是一道 OI 题，不是证明题。


title: 【MX-X6-T6】機械生命体

background:
> _許してよ、もう$\\$
分かってよ$\\$
此処の正体を$\\$
僕ですら僕を$\\$
愛せないんだって$\\$
感情を持った代償をくれよ$\\$
狂っている_
>
> _—— [機械生命体 - Nanatsukaze](https://music.163.com/#/song?id=2627128854)_

二进制的运算和记忆，能够在机械生命体中还原出人类的情感吗？

description:
维护一个**可重集** $S$，初始为空。支持如下操作：

- `1 x`，你需要在 $S$ 中加入一个数 $x$。
- `2 x`，你需要在 $S$ 中删除一个数 $x$。保证此时 $S$ 中存在至少一个 $x$。如果存在多个 $x$，则仅删除一个。
- `3 x k v`，你需要对 $S$ 中所有满足 $\operatorname{lowbit}(x\oplus y)\geq 2^k$ 的 $y$ 增加 $v$ 并对 $2^{32}$ 取模。
- `4 x`，你需要求出 $\max\limits_{y\in S} \operatorname{lowbit}(x\oplus y)$。保证此时 $S$ 不为空。

其中 $\operatorname{lowbit}(x)$ 表示最大的整数 $k$，使得 $k$ 是 $2$ 的整数次幂并且整除 $x$。$\oplus$ 代表[按位异或](https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677)。

**特殊的，我们在本题定义 $\boldsymbol{\textbf{lowbit}(0)=2^{32}}$。**

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

接下来 $q$ 行，每行首先输入一个整数 $opt$ 表示操作类型；如果 $opt=3$，则接下来依次输入三个整数 $x,k,v$，否则接下来输入一个整数 $x$。

outputFormat: 对每一次 `4` 操作，输出一个整数代表答案。

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

第 $6$ 次操作时，集合为 $\{1,2,2,3,4\}$，查询 $10$ 时，$\operatorname{lowbit}(10\oplus 2)=\operatorname{lowbit}(8)=8$ 为最大值。

第 $7$ 次操作后，所有 $\operatorname{lowbit}(x\oplus 2)\geq 2^1$ 的数增加 $2$，集合中满足条件的数有 $2,2,4$，于是集合变为 $\{1,3,4,4,6\}$。

第 $8$ 次操作删去一个 $4$，集合变为 $\{1,3,4,6\}$。

第 $9$ 次操作查询 $16$，$\operatorname{lowbit}(16\oplus 4)=\operatorname{lowbit}(20)=4$ 为最大值。

第 $10$ 次操作再次删去一个 $4$，集合变为 $\{1,3,6\}$。

第 $11$ 次操作查询 $16$，$\operatorname{lowbit}(16\oplus 6)=\operatorname{lowbit}(22)=2$ 为最大值。

**【数据范围】**

对于所有数据，$1\leq q\leq 5\times 10^5$，$0\leq x,y,v\leq 2^{32}-1$，$0\leq k\leq 32$。

**捆绑测试**，共 5 个 Subtask，具体限制如下所示：

- Subtask 1（7 pts）：$q\leq 10^3$。
- Subtask 2（16 pts）：不存在 3 操作。
- Subtask 3（21 pts）：对于 3 操作，$k=0$。
- Subtask 4（28 pts）：对于 3 操作，$v=1$。
- Subtask 5（28 pts）：无特殊限制。


title: 「Wdoi-2」花如幻想一般

background:
冬的白色被春日的阳光所点缀，幻想乡完全取回了生机的颜色。但，樱花，向日葵，野菊花，桔梗……明明还是春天，全年的花却全都盛开了。

六十年前（注：现实中的 1945 年）的大战，炮火声中、枪林弹雨中，无数的无辜的亡魂，在六十年后纷纷落于幻想之中，寄托于每一朵花上。

每一朵花寄托着每一朵亡魂的灵魂本质。向日葵寄宿着开朗的人的灵魂。彼岸花寄宿了没有朋友的寂寞灵魂，紫色的樱树下满是持有罪恶的幽灵。由于是从有德的幽灵开始按顺序送往彼岸，留到最后的都将是樱花。

外面的人类所看到的虚幻的彼岸，正回归于幻想的此岸。

description:
### 简要题意

有一个长度为 $n$ 的序列 $a$。可以进行两种操作：
- 将整个序列翻转；
- 将序列中的某个数加上某个**整数**。

问：至少要用多少次操作可以将序列 $a$ 转化为序列 $b$。

### 原始题意

参与解决花之异变的十余位主角都并未年满 60 岁，并没有经历过上一次的花之异变。在万花丛中解决异变的紧迫性逐渐被消弭，取而代之的是用花朵来进行游戏。

灵梦将 $n$ 个花朵排成了一排，第 $i$ 朵花都有其对应的美丽程度 $a_i$。而一旁的魔理沙作为一位魔法使，拥有两种能力。她可以进行若干次操作，每次操作可以**使得这 $\bm n$ 朵花的位置完全翻转**，或者可以**将某一朵花的美丽程度加上或减去一个整数**。

灵梦认为，如果能用魔理沙的操作，使得最后花朵的美丽程度可以变成序列 $b_i$，那么将会是很好的。为了解决异变顺利，魔理沙希望自己的操作次数尽可能少。那么请问魔理沙为了满足灵梦的愿望至少需要操作几次？

---

幻想乡的花儿渐落，新绿开始步向美丽的季节。经过六十年还不会被遗忘的记忆，可能是没有的吧。

inputFormat:
- 第一行一个整数 $n$。
- 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。
- 第三行 $n$ 个整数 $b_1,b_2,\cdots,b_n$。

outputFormat: - 输出一行一个整数，代表至少需要几次操作。

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

$$
\begin{array}{cccl}
\color{red}1&\color{red}2&\color{red}3&\downarrow\text{reverse}\\
3&2&1&
\end{array}
$$

### 样例解释 \#2

$$
\begin{array}{ccl}
\color{red}3&\color{red}1&\downarrow\text{reverse}\\
1&\color{red}3&\downarrow\text{add }-1\\
1&2&
\end{array}
$$

### 数据范围

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值}\\\hline
1 & 10 & - & 10\\\hline
2 & 10^3 & - & 30\\\hline
3 & 5\times 10^5 & \text{A} & 5 \\\hline
4 & 5\times 10^5 & - & 55 \\\hline
\end{array}$$

- 特殊性质 $\textbf{A}$：保证存在一种花费最小的方案，不需要执行第二种操作。

对于全部数据，满足 $1 \leq n \leq 5\times10^5$，
$1 \leq a_i,b_i \leq 10^9$。


title: 「Wdcfr-1」Yet Another Cirno Game (easy version)

description:
**The only difference between the two versions is whether you have to find a way to get the maximum points.**

Cirno drew a graph. This graph contains $4\cdot n$ nodes, numbered $0$ through $4\cdot n - 1$. Also:

- For any $0\le i\le 3$ and $0 \le j, k \lt n$, node $(n\cdot i + j)$ and node $(n\cdot i + k)$ are connected.
- For any $0 \le i < n$ and $0 \le j, k \le 3$, node $(i + n\cdot j)$ and node $(i + n\cdot k)$ are connected.

Cirno called Daiyousei to come and play with her.

The rules for this game are as follows:

- Firstly, Cirno chooses $2\cdot n$ (i.e. half) of the nodes, and she colors them blue. The rest are left red.
- Then there are $2\cdot n$ turns: for each turn Cirno first chooses a blue node, and Daiyousei chooses a red node. If those two nodes are connected, Daiyousei gets a point.

Try to maximize the number of points Daiyousei gets.

inputFormat: The first line contains an integer $n$. Then one line below, $2\cdot n$ numbers follow: they are the nodes that Cirno chose.

outputFormat:
For each test case, output an integer $x$ in a single line, which is the maximum number of points Daiyousei can get.

You don't have to output anything else in this version.

translation:
**两个难度之间的唯一区别为是否需要输出对应的匹配方案**

给定 $4n$ 个点，点的编号从 $0$ 到 $4n-1$，每个点有两种属性 $x$ 和 $y$，编号为 $i$ 的点的属性为 $x_i=\left\lfloor\frac{i}{n}\right\rfloor,y_i=i-n\left\lfloor\frac{i}{n}\right\rfloor$。对于每两个点 $i,j(0\le i <j < 4n)$ 之间，若 $x_i= x_j$ 或 $y_i= y_j$，则这两点有一条无向边相连。现有其中 $2n$ 个不同的点被选择，试给每个被选择的点都匹配上另一个点，使得：

- 被匹配到的点未被选择；
- 每个点都只被匹配一次；
- 若每个点与其匹配的点之间有连边，那么记为一分，需要最大化分值。

请输出最大的分值。

hint:
### Explanation

In the following picture, nodes in matrices are connected to each other. Cirno chose nodes $0,1,2,3,4,5$.

Arrows below show a possible way for Daiyousei to get the maximum number of points she can get.

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

### Constraints

$1\le n\le 2\times 10^6$.


title: 「Wdoi-5」建立与摧毁的结界

background:
八云紫拥有操控境界程度的能力。作为其式神的八云蓝，同样拥有一定程度的操作境界的能力，而作为八云蓝的式神橙，却因为功力尚且不足，而无法对境界进行过多的干预了。

于是八云蓝打算教教橙，境界的用法。境界可以被抽象成一层一层的括号，操作境界本质上就是对括号序列进行修改。由于橙的能力尚且不足，因此只能进行一些简单的境界的建立与摧毁。

尽管如此，通过简单的操作，亦可以把一个境界转换为另外一个境界。为了给橙作为练习，蓝找来了两个境界的范本。将其中一个境界转换为另外一个境界的难度，就是橙需要施用能力的最小次数。但是由于境界实在太长，蓝决定写一个程序（？）来帮帮她计算出境界的难度。

description:
境界可以被抽象为由圆括号组成的括号序列。现做出如下定义：

- 定义 $D_i$ 为**嵌套括号序列**。其中 $D_0$ 为零阶嵌套括号序列，被定义为单组括号 $\verb!()!$；而 $D_k$ 则为 $k$ 阶嵌套括号序列（$k \geq 1$）定义为 $\verb!(!D_{k-1}\verb!)!$，即在 $D_{k-1}$ 的外层增添了一层括号。
- 定义 $F_i$ 为**平铺括号序列**。其中 $F_0$ 为零阶平铺括号序列，被定义为单组括号 $\verb!()!$；而 $F_k$ 则为 $k$ 阶平铺括号序列（$k \geq 1$），定义为 $\verb!()!F_{k-1}$，即在 $F_{k-1}$ 的左侧增添了一对括号。

例如，$\verb!((()))!$ 为 $D_2$，$\verb!()()()()!$ 为 $F_{3}$。

现在蓝给出了两个长度为 $n$ 的**合法**括号序列 $A$ 和 $B$。橙可以用以下操作对序列 $A$ 进行变换：

- 选择任意非负整数 $k$，选择括号序列的一个子串满足其为一个 $k$ 阶嵌套括号序列，然后将其变为 $k$ 阶平铺括号序列。
- 选择任意非负整数 $k$，选择括号序列的一个子串满足其为一个 $k$ 阶平铺括号序列，然后将其变为 $k$ 阶嵌套括号序列。

**提示说明**处有「合法括号序列」与「子串」的定义。

现在需要求出将序列 $A$ 变换为序列 $B$ 所需的最少操作数。可以证明，总存在一种操作方案能将序列 $A$ 变换为序列 $B$。

inputFormat:
- 第一行共有一个整数 $n$，表示 $A$ 与 $B$ 括号序列的长度。
- 接下来一行，共有 $n$ 个字符，描述括号序列 $A$。保证序列 $A$ 合法。
- 接下来一行，共有 $n$ 个字符，描述括号序列 $B$。保证序列 $B$ 合法。

outputFormat: - 共一行，一个整数，表示将 $A$ 转换为 $B$ 需要的最少步数（可能为 $0$，也就是不进行任何操作）。

hint:
样例 $3$ 见下发的附件  $\textbf{\textit{border3.in/border3.ans}}$。
样例 $4$ 见下发的附件  $\textbf{\textit{border4.in/border4.ans}}$。满足特殊性质 $\text{A}$（见下文）。
样例 $5$ 见下发的附件  $\textbf{\textit{border5.in/border5.ans}}$。

#### 样例 1 解释

- 第一步：$\texttt{((\underline{()()})(()()))}\to\texttt{((\underline{(())})(()()))}$。
- 第二步：$\texttt{(((()))(\underline{()()}))}\to\texttt{(((()))(\underline{(())}))}$。
- 第三步：$\texttt{(((()))\underline{((()))})}\to\texttt{(((()))\underline{()()()})}$。
- 第四步：$\texttt{(\underline{((()))}()()())}\to\texttt{(\underline{()()()}()()())}$。
- 第五步：$\texttt{(\underline{()()()()()()})}\to\texttt{(\underline{(((((())))))})}$。
- 第六步：$\texttt{\underline{((((((()))))))}}\to\texttt{\underline{()()()()()()()}}$。

可以证明，不存在更短的方案。

#### 提示

**合法括号序列**通过这样一个形式定义：

- $\verb!()!$ 是合法括号序列。
- 若 $A$ 是合法括号序列，那么 $\verb!(!A\verb!)!$ 是合法括号序列。
- 若 $A,B$ 均为合法括号序列，那么 $AB$ 是合法括号序列。

我们称 $A$ 是 $B$ 的**子串**，当且仅当删除 $B$ 开头若干个字符（可以不删除），再删除 $B$ 末尾若干个字符（可以不删除），剩下来的字符序列与 $A$ 完全相同。

#### 数据范围及约定

本题共有 $20$ 个测试点，每个测试点 $5$ 分。最终分数为所有测试点分数之和。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{Task} & \bm{n\le } & \textbf{特殊性质} \cr\hline
1\sim 4 & 10 & - \cr\hline
5\sim 7 & 2\times 10^3 & \text{A} \cr\hline
8\sim 10 & 2\times 10^3 & - \cr\hline
11\sim 15 & 10^6 & \text{A} \cr\hline
16\sim 20 & 10^6 & - \cr\hline
\end{array}
$$

**特殊性质** $\textbf{A}$：保证 $B$ 是 $(n\div 2-1)$ 阶平铺括号序列。

#### 友情提醒

考虑到选手可能会用不同的方式进行字符串的读入，这里保证输入文件**每行末尾没有多余空格**，并且每行都以 `\n` 结尾（也就是说，不会出现多余的 `\r`）。


title: [Ynoi2006] spxmcq

description:
给定一颗 $n$ 个节点有根树，第 $i$ 节点权值为 $a_i$。

在这个树上支持一种询问：

 - 给定节点 $u$ 和参数 $x$，**假如** 所有节点点权加 $x$，**在这种情况下，求：** 对于所有完全在 $u$ 子树内并包含 $u$ 的连通点集，权值之和最大可能为多少？

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

第二行 $n-1$ 个正整数 $f_2,f_3,\dots,f_n$，依次为 $2,3,\dots,n$ 的父亲节点编号，其中保证 $1\le f_i<i$。

第三行 $n$ 个整数 $a_1,a_2,\dots,a_n$，依次为 $1,2,\dots,n$ 点权。

接下来 $m$ 行，每行一个正整数 $u$ 和一个整数 $x$，代表一组询问，其中保证 $1\le u\le n$。

outputFormat: 输出 $m$ 行，每行一个整数，为对应询问的答案。

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

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^6$，$|a_i|,|x|\le 10^8$，保证 $1\le u\le n$。


title: [Ynoi2006] rprmq2

description:
给定正整数 $m$，你需要维护一个 $m\times m$ 的矩阵 $a_{i,j},\;1\le i,j\le m$，初值为 $0$。

共 $m$ 次操作，每次操作给出 $x,\;y,\;z_{0,0},\;z_{0,1},\;z_{1,0},\;z_{1,1}$，

首先对 $0\le p,q\le 1$ 询问矩阵中满足 $[i\ge x]=p,\;[j\ge y]=q$ 的位置的值 $a_{i,j}$ 的最大值，答案记为 $w_{p,q}$，

然后对矩阵每个位置 $(i,j)$，将其值 $a_{i,j}$ 加上 $z_{[i\ge x],[j\ge y]}$。

记号 $[c]$ 在条件 $c$ 为真时值为 $1$，否则值为 $0$。

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

对于 $100\%$ 的数据，$2 \le x,y\le m\le 2\times 10^5$ ，$1\le z_{i,j}\le 10^9$，所有数值为整数。


title: lgdAKIOI

background:
本题中出现的神犇：[_lgswdn](https://www.luogu.com.cn/user/180652)

AK 完 NOI 后，lgd 一路势不可挡，不久便进入了国家队，来到了 IOI 赛场。

description:
6ms 后，lgd 写对了最后一题的

```plain
可持久化非确定状态AC自动分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫比乌斯反演莫队带花舞蹈链并查集树状数组套主席树预处理动态DP分治FFT求多项式逆元对数函数的指数函数用可持久化并查集合并最小费用循环流上插头DP
```
算法，AK 了 IOI。于是他闲着无聊，开始给自己出题。

有一题是这样的：

$n$ 个同学站成一个圆圈，其中的一个同学手里拿着一个球。每一次，手里有球的同学可以把球传给自己左右的两个同学中的一个（左右任意）。那么有多少种不同的传球方法可以使得从 lgd 手里开始传的球，传了 $m$ 次以后，又回到 lgd 自己手里呢？两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。

你听说这道题之后，希望把它做出来，以不遭到 lgd 的鄙视。由于 lgd 比较仁慈，他允许你只告诉他答案取模 $720000054000001$ 的余数就好了。

inputFormat:
此题有多组数据。

对于每组数据，一行两个正整数 $n,m$，含义如题。

outputFormat: 对于每组数据，一行一个自然数表示答案。

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

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

**请注意常数因子带来的程序效率及空间占用上的影响。**

数据范围如下表所示。

|数据点编号|$n$|$m$|数据组数|分值|特殊性质|子任务编号|
|----|----|----|----|----|----|----|
|$1\sim6$|$=100$|$\le100$|$\le5$|$5$|A|0|
|$7\sim12$|$=10^5$|$\le10^6$|$\le5$|$15$|A|1|
|$13\sim18$|$=10^6$|$\le2\times10^6$|$\le5$|$10$|A|2|
|$19\sim24$|$=2\times10^5$|$\le10^{1000}$|$\le5$|$20$|A|3|
|$25\sim30$|$\le6\times10^6$|$\le10^{30}$|$\le50$|$20$||4|
|$31\sim36$|$\le6\times10^6$|$\le10^{10^4}$|$\le2500$|$30$||5|

特殊性质 A：所有输入的 $n$ 全部相同。

对于 $100\%$ 的数据，$n\in\{10,13,100,10^3,10^4,10^5,2\times10^5,6\times10^5,10^6,6\times10^6\}$。

---

lgd 把这题交给你的时候同时给了你另外一段代码，不过有什么用就不知道了。

```cpp
typedef long long i64;
typedef unsigned long long u64;
typedef __uint128_t u128;
struct Mod64 {
  Mod64() : n(0) {}
  Mod64(u64 n) : n(init(n)) {}
  static u64 modulus() { return mod; }
  static u64 init(u64 w) { return reduce(u128(w) * r2); }
  static void setmod(u64 m) {
    mod = m;
    inv = m;
    for (int i = 0; i < 5; ++i) inv *= 2 - inv * m;
    r2 = -u128(m) % m;
  }
  static u64 reduce(u128 x) {
    u64 y = u64(x >> 64) - u64((u128(u64(x) * inv) * mod) >> 64);
    return i64(y) < 0 ? y + mod : y;
  }
  Mod64& operator+=(Mod64 rhs) {
    n += rhs.n - mod;
    if (i64(n) < 0) n += mod;
    return *this;
  }
  Mod64& operator-=(Mod64 rhs) {
    if (n < rhs.n)
      n += mod - rhs.n;
    else
      n -= rhs.n;
    return *this;
  }
  Mod64& operator*=(Mod64 rhs) {
    n = reduce(u128(n) * rhs.n);
    return *this;
  }
  Mod64 operator*(Mod64 rhs) const { return Mod64(*this) *= rhs; }
  Mod64 operator+(Mod64 rhs) const { return Mod64(*this) += rhs; }
  Mod64 operator-(Mod64 rhs) const { return Mod64(*this) -= rhs; }
  u64 get() const { return reduce(n); }
  static u64 mod, inv, r2;
  u64 n;
  friend ostream& operator<<(ostream& out, Mod64 x) { return out << x.get(); }
};
u64 Mod64::mod, Mod64::inv, Mod64::r2;
```


title: 「Wdcfr-1」CONsecutive and CONcat (hard version)

description:
Lily White is playing with strings. Being a yousei, she is not capable of complex speech. Thus, she likes strings that only contain one kind of letter, she calls such strings of length $x$ a "$x$-CON string". For example, `qqqq` is a "$4$-CON string", while `aaab` is not any type of "CON string".

Lily White composed an array $a$. It contains $n$ strings of length $m$ that she will use to herald spring. For each permutation of $1,2,\ldots, n$, let us denote current permutation as $p=\{p_1,p_2,\cdots,p_n\}$. Lily White concatenates all the string in array $a$ in the order of $a_{p_1},a_{p_2},\cdots,a_{p_n}$ into a string $s$ of length $nm$ .

As she likes $k$-CON strings, she wants to know the sum of the number of "$k$-CON string" in all non-empty substrings of $s$ composed by all $n!$ permutations. Since the answer may be enormous, just print the answer taken modulo $998,244,353$ (a large prime).

inputFormat:
The first line contains three integers $n,m,k$.

Then $n$ lines follow, each line contains a string of length $m$. The string in the$(i+1)$-th line represents $a_i$.

outputFormat: Print a single integer - the answer taken modulo $998,244,353$.

translation: 给定若干长度为 $m$ 的字符串 $a_1,a_2,...,a_n$，给定常数 $k$，试求出对于所有的长度为 $n$ 的排列 $p$，将 $a_{p_1},a_{p_2},...,a_{p_n}$ 依次拼接形成的长字符串 $s$ 中，有多少个位置 $x$ 满足 $s_x,s_{x+1},...,s_{x+k-1}$ 为同一种字符。请输出位置数的和 $\bmod \space998244353$ 的值。

hint:
### Explanation

#### Sample \#1

- For permutation $1,2,3$, the formed $s$ is `aaabaabaa`, none on the non-empty substring in this string are "$5$-CON string".
- For permutation $1,3,2$, the formed $s$ is `aaabaabaa`, none on the non-empty substring in this string are "$5$-CON string".
- For permutation $2,1,3$, the formed $s$ is `baaaaabaa`, this string has one substring `aaaaa` which is a "$5$-CON string".
- For permutation $2,3,1$, the formed $s$ is `baabaaaaa`, this string has one substring `aaaaa` which is a "$5$-CON string".
- For permutation $3,1,2$, the formed $s$ is `baaaaabaa`, this string has one substring `aaaaa` which is a "$5$-CON string".
- For permutation $3,2,1$, the formed $s$ is `baabaaaaa`, this string has one substring `aaaaa` which is a "$5$-CON string".

In summary, the answer is $0+0+1+1+1+1=4$.

#### Sample \#2

In all of the full permutation of length $3$, there will be six different $s$: `xyzqaqaba`, `xyzabaqaq`, `qaqxyzaba`, `qaqabaxyz`, `abaqaqxyz`, and `abaxyzqaq`. None of these has a non-empty substrings which is a "$2$-CON string". So the answer is $0$.

### Constraints

$2\le k \le n\cdot m\le 10^6;\ 1\le m \le 100$. $a_i$ contains only lowercase English letters.


title: [COCI2006-2007#2] SJECIŠTA

description:
考虑一个有 $n$ 个顶点的凸多边形，且这个多边形没有任何三个（或以上）的对角线交于一点。

现在请你求出这样的多边形的对角线交点个数。

inputFormat: 输入一行一个整数表示 $n$。

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

hint:
### 样例 3 解释
![](https://cdn.luogu.com.cn/upload/image_hosting/07pgpeuy.png)

### 数据规模与约定

对于全部的测试点，保证 $3 \leq n \leq 100$。


title: [CoE R5/Stoi2029] 半岛铁盒

background:
> 为什么这样子 你拉着我 说你有些犹豫
> 怎么这样子 雨还没停 你就撑伞要走
> 已经习惯 不去阻止你 过好一阵子 你就会回来
> 印象中的爱情 好像顶不住那时间
> ——《[半岛铁盒](https://www.bilibili.com/video/BV1fx411N7bU?p=26)》

description:
**题意简述**

给定一个 $n$ 个顶点 $m$ 条边的无向图，可能有重边自环，可能不连通。

初始时每个顶点有点权，点权为随机正实数。现在需要重新分配每个顶点的点权，使得：

1. 相邻顶点的点权中较大者与较小者之比不超过 $x$；

2. 点权总和不变；

3. 每个顶点的点权不小于初始时的 $\dfrac{p}{q}$。

求最小的 $x \ge 1$，使得对于给定的图，无论初始点权如何，均存在一种满足上述要求的重新分配方式。

---

**原版题面**

神在半岛铁盒里创建了一个世界。

这个世界由 $n$ 个地域和地域之间的 $m$ 条通道组成，每条通道连接两个地域。创世时每个地域有一定的气压，气压为正数。

由于世界刚刚创建，比较混乱，所以两个地域之间可能有多条通道相连，一个地域也有可能有通道连接到自身，两个地域也可能无法通过若干条通道相互通行。

由于通道连接的两个地域气压之比（大比小，下同）过大时会在通道里形成强风，使得跨地域旅行非常危险，所以造世神决定调整每个地域的气压使得每条通道连接的两个地域气压之比都不超过安全比值 $x$。显然 $x \ge 1$。

由于各种守恒定律被打破会很麻烦，所以神希望调整前后所有地域的气压之和不变。

由于世界中的生物无法在过低的气压中生存但对高气压的适应力强，因此每个地域改变后的气压必须不低于初始的 $\dfrac{p}{q}$。

由于创世时气压不受神控制地随机，所以神希望安全比值 $x$ 满足无论初始气压如何都存在一种合适的调整气压的方法。

由于通道越宽敞，通行越舒适，但是安全比值 $x$ 也越小，因此神想要求出满足要求的最小安全比值 $x$。

由于神忙着处理创世事务，所以他钦定你来解决这个问题。

inputFormat:
第一行四个正整数 $n,m,p,q$，含义如题。

接下来 $m$ 行，每行两个正整数 $u,v$ 表示一条通道连接的两个地域的编号。

outputFormat:
输出一个实数表示 $x$ 的最小值，保留 $7$ 位小数。

本题采用 Special Judge，如果你的答案与参考答案的差值不超过参考答案值的 $10^{-4}$ 倍即为通过。

hint:
**数据范围**

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

对于另外 $20\%$ 的数据，有一个地域和其他所有地域之间有通道相连；

对于另外 $30\%$ 的数据，通道构成一棵树。

对于 $100\%$ 的数据，$1 \le u,v \le n \le 10^3$，$1 \le m \le 3 \times 10^4$，$1 \le p<q \le 10^7$。


title: [Ynoi2005] rpxleqxq

description:
给你一个长度为 $n$ 的正整数序列 $a$，和一个常数 $x$ 。

定义 $x \oplus y$ 表示 $x$ 异或 $y$。

有 $q$ 次询问，每次询问给出一段区间 $[l, r]$，问你这个区间中有多少二元组 $(i, j)$ 满足 $i < j \land (a_i \oplus a_j) \le x$。

inputFormat:
第一行两个正整数 $n, x$ ，分别表示序列长度和给定的常数。

后面一行 $n$ 个整数表示序列 $a$ 。

第三行一个正整数 $q$ 表示询问组数。

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

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

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

对于 $1\%$ 的数据，为样例。

对于另外 $19\%$ 的数据，满足 $n,q\le 100$。

对于另外 $19\%$ 的数据，满足 $n,q\le 1000$。

对于另外 $19\%$ 的数据，满足 $q\le 100$。

对于另外 $19\%$ 的数据，满足 $a_i,x\le 100$。

对于 $100\%$ 的数据，满足 $1 \le n, a_i, x\le 2\times 10^5, 1 \le q \le 10^6$ 。


title: [JRKSJ R4] BBWWBB

description:
数轴上有 $6$ 个棋子。初始，第 $i$ 个棋子摆在 $a_i$，$a$ 单调递增。

其中第 $1,2,5,6$ 个棋子是黑色的，第 $3,4$ 个棋子是白色的。

游戏过程中，同一个位置上可以同时存在任意个同样颜色的棋子。

有两方：黑方和白方。两方轮流进行操作：

* 选择己方颜色的棋子，向左或向右移动一步。
* 若准备移动到的位置上存在另一方的棋子且仅存在 $1$ 个，那么可以移动同时将该棋子移除。
* 若准备移动到的位置上存在多个另一方的棋子，那么不可以移动到这个位置。
* 当一方不存在可以移动的棋子，该方被判输，游戏结束。

两方的目标都是在己方不输的前提下，尽可能的令对方输。两方均采取最优策略。

给定一方作为先手和每个棋子的位置，请判断，游戏是否会无限进行下去。

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

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

下面 $T$ 行，每行一组数据。

每组数据首先一个字符 $c$，为 $\texttt B$ 或者 $\texttt W$。$c=\texttt B$ 表示黑方先手，$c=\texttt W$ 表示白方先手。然后 $6$ 个整数表示 $a_{1\dots 6}$。

outputFormat: 对于每组询问，每行回答一个 `Yes` 或 `No`。`Yes` 表示游戏会无限进行下去，`No` 反之。

hint:
### 数据规模

对于 $15\%$ 的数据，$c=\texttt B$。\
对于 $100\%$ 的数据，$T\le10^5$，$|a_i| \le 10^9$，$c\in\{\texttt B,\texttt W\}$。保证 $a$ 单调递增。

### 样例解释

对于第 $1$ 组数据，其中一种局面变化如下：

```cpp
B:
1 4 6 8 9
B B W B B
W:
1 4 5 8 9
B B W B B
B:
1 5 8 9
B B B B
```
对于第 $2$ 组数据，其中一种局面变化如下：

```cpp
W:
1 3 6 8 9
B W W B B
B:
1 3 6 8 8
B W W B B
W:
1 3 5 8 8
B W W B B
B:
1 3 5 7 8
B W W B B
W:
1 3 4 7 8
B W W B B
B:
1 3 4 7 7
B W W B B
W:
1 3 3 7 7
B W W B B
B:
1 3 3 6 7
B W W B B
W:
1 2 3 6 7
B W W B B
B:
2 3 6 7
B W B B
W:
2 6 7
W B B
```
此后白方每一步均控制 `W` 往左边走一步。无论黑方如何操作，游戏均可以无限进行下去。


title: 「KDOI-02」一个弹的投

background:
- 前置芝士：[平抛运动](https://baike.baidu.com/item/%E5%B9%B3%E6%8A%9B%E8%BF%90%E5%8A%A8/974021?fr=aladdin)
~~（看到这个如果不想做可以直接开下一题）~~

「这群该死的外星人，肯定是来抢夺新矿资源的！」
「这导弹什么鬼啊，研究不明白。」
无数的水滴型武器从苍穹之外落下，猛击着无知的生命。

description:
经研究，该武器的运作方式是这样的。其中设重力方向为 $y$ 轴负半轴，$x$ 轴为地面，速度向右为正向左为负。
- 每颗导弹在 $(x_i,y_i)$ 的地方投放并悬浮，初始速度设置为 $v_i$。
- 所有导弹投放完成后，于同一时刻开始照初始速度做平抛运动。其中 $g=9.8$。
- 每颗导弹与另一颗导弹碰撞时，不会改变原来的路线，并且将爆破威力 $p_i$ 增加 $1$，所有导弹初始时 $p_i=0$，**在接触到 $x$ 轴时碰撞也增加威力**。
- 当武器落到 $x$ 轴时，会对落点造成 $p_i$ 点杀伤力。

地面指挥部提前预测了导弹的落点，并部署了反制武器。第 $i$ 台武器能将第 $i$ 枚导弹在降落至地面后的威力值减少 $a_i$（至多减少到 $0$）。但是，由于技术限制，只能启动其中 $m$ 台反制武器。地面指挥官想知道，导弹造成的爆炸威力值总和最小为多少。

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

输入一共包含 $n+2$ 行。

第 $1$ 行输入两个正整数 $n,m$。

第 $2$ 行到第 $n+1$ 行每行包含三个整数 $x_i,y_i,v_i$，表示第 $i$ 颗导弹的起点坐标和水平速度。

第 $n+2$ 行包含 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$，含义见题目描述。

outputFormat:
输出到标准输出。

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

samples:
见附件中的 missile3.in
见附件中的 missile3.ans

samples:
见附件中的 missile4.in
见附件中的 missile4.ans

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

- **样例 1 解释：**

	每颗导弹的爆炸威力值都是 $0$。
- **样例 2 解释：**

	四枚导弹的爆炸威力值分别是 $0,1,1,0$，启动第 $2$ 或第 $3$ 台反制武器，最后爆炸威力值的和为 $1$。

- **样例 4 说明：**

   该样例满足测试点 $13\sim16$ 的限制。
***
**【数据范围】**

对于 $100\%$ 的数据，$1\le n\le5\times10^5$，$0\le a_i,m\le n$，$0\le |x_i|,y_i\le10^9$，$0\le |v_i|\le10^6$。

**保证所有导弹起始坐标不相等。**

|测试点编号|$n\le$|特殊性质|
|:-:|:-:|:-:|
|$1\sim6$|$5000$|无|
|$7\sim10$|$12000$|无|
|$11\sim12$|$10^5$|有|
|$13\sim16$|$10^5$|无|
|$17\sim20$|$5\times10^5$|无|

特殊性质：保证所有 $y_i$ 均相同。

**【提示】**

本题 I/O 量较大，推荐使用较快的 I/O 方式。

附平抛运动落点公式：
$$x_t=x_i+v_i\sqrt{\dfrac{2y_i}g}$$


title: 「EZEC-11」Unmemorable

description:
Unputdownable 手中有一个长度为 $n$ 的排列 $a$。

他在练习单调栈的时候用程序对于每一个 $i$ 求出了最大的 $l_i$ 使得 $a_{l_i} < a_i$ 且 $l_i<i$，以及最小的 $r_i$ 使得 $a_{r_i}<a_i$ 且 $r_i>i$。

特别的，若这样的 $l_i$ 不存在，则定义为 $0$，不存在的 $r_i$ 则定义为 $n+1$。

某日 Unputdownable 忘记了排列 $a$，而且只剩余**分别重排**后的 $l$ 和 $r$ 数组了，你能帮助他还原原来的排列 $a$ 吗？

随后由于他发现无法还原 $a$，你只要告诉他有多少种可能的原排列 $a$。

答案对于 $998244353$ 取模，数据保证至少存在一种方案。

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

第二行输入 $n$ 个整数，表示重排后的 $l$。

第三行输入 $n$ 个整数，表示重排后的 $r$。

outputFormat: 输出一行，包含一个整数，表示可能的排列数量对 $998244353$ 取模后的值。

hint:
**样例解释 1**

一种可能的排列是 $\{2,5,1,3,4\}$，$l$ 数组是 $\{0,1,0,3,4\}$，$r$ 数组是 $\{3,3,6,6,6\}$。

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

- Subtask 1（5 pts）：$n\leq 8$。
- Subtask 2（15 pts）：$r_i\geq n$。
- Subtask 3（15 pts）：$n\leq 2000$，保证存在一个排列 $a$ 满足排列 $a$ 所求出的 $l,r$ 即为给定的。
- Subtask 4（25 pts）：$n\leq 10^6$，保证存在一个排列 $a$ 满足排列 $a$ 所求出的 $l,r$ 即为给定的。
- Subtask 5（40 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$0 \leq l_i,r_i \leq n+1$，**数据保证至少存在一种方案**。


title: [✗✓OI R1] 后方之水

background: 这个题目没有背景，因为我是圣人的同时还是神之右席。

description:
定义一次石子合并的过程如下：有一排 $n$ 堆石子，每一堆有 $a_i(a_i\ge1)$ 个。每次你可以选择相邻的两堆石子合并，设个数分别为 $x,y$，则你会得到一堆 $(x+y)$ 个石子，同时你要付出 $xy$ 的代价。最后要把所有石子合并成一堆。记 $f(a_1,\ldots,a_n)$ 为合并这些石子的最小代价。

给出石子总数 $S$，求
$$ \sum_{\sum a_i=S}f(a_1,\ldots,a_n) $$
答案对 $998244353$ 取模。

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

第一行一个整数 $T$，表示测试数据的数量。
接下来 $T$ 行，每行两个整数，分别为 $n,S$。

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


title: [Ynoi2005] qwq

description:
定义初始数列为每个数字都为 $0$ 的数列。

定义一次操作为将数列的一个区间中每一个数的值增加 $1$，规定该区间的长度不能超过 $m$。

给定一个长度为 $n$ 的数列 $a$，第 $i$ 个数为 $a_i$。

你需要回答 $q$ 次询问。每次询问给定 $l,r$，你需要回答将一个长度为 $r-l+1$ 的初始数列变为 $a$ 中的 $[l,r]$（即数列 $a_l$, $a_{l+1}$, $\cdots$, $a_r$）至少需要多少次操作。

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

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

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

outputFormat: $q$ 行，每行一个整数，表示至少需要的操作次数。

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

一个长度为 $5$ 的初始数列为 $0$ $0$ $0$ $0$ $0$。

第一次操作为，将区间 $[1,3]$ 中每一个数，即第 $1$、$2$、$3$ 个数的值分别增加 $1$。经过该操作后，数列变为  $1$ $1$ $1$ $0$ $0$。

第二次操作为，将区间 $[3,5]$ 中每一个数，即第 $3$、$4$、$5$ 个数的值分别增加 $1$。经过该操作后，数列变为  $1$ $1$ $2$ $1$ $1$。

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

- Subtask 1（1 point）：$m=1$。
- Subtask 2（4 points）：$m=n$。
- Subtask 3（10 points）：$n,q\le300$。
- Subtask 4（10 points）：$n,q\le5\times10^3$。
- Subtask 5（15 points）：$m\le5$。
- Subtask 6（15 points）：$m\le100$。
- Subtask 7（20 points）：$n,q\le5\times10^4$。
- Subtask 8（25 points）：无特殊限制。

对于 $100\%$ 的数据，保证 $1\le m\le n\le10^5$，$1\le q\le10^5$，$0\le a_i\le10^9$，$1\le l\le r\le n$。


title: Welcome to Lunatic City

description:
M 国由 $n$ 个城市，$n-1$ 条双向高速铁路组成。其中的 $n$ 个城市可经过铁路互相抵达。

由于 M 国有着最顶尖的科技，为了加快交通速度，它可以在铁路上放置若干的互相配对的传送门，但总对数不超过 $L$。当一个列车在一条铁轨上运行时，每当它遇到一个传送门，就会进行传送。每个传送门分为正面与反面，列车从正面进入传送门时就会从与这个传送门配对的传送门的正面出来，从反面进入就从反面出来。传送门可以设立在一条铁路中间的任何地方。（如果对这一段描述有问题可以参考样例解释）

同时由于 M 国有着最高速的列车，列车的行驶时间仅消耗在停靠。于是从城市 $i$ 到城市 $j$ 的距离 $dis(i,j)$ 定义为列车所经过的城市数（包含终点但不包含起点）。

现在 M 国设立了 $m$ 个重要城市 $x_1,x_2,\dots,x_m$，请通过合理放置不超过 $L$ 对传送门使得 M 国的首都 $1$ 号城市到这些城市的距离和最小，即最小化 $\sum_{i=1}^mdis(1,x_i)$，并构造方案。同时放置的传送门必须保证城市间仍互相可达。

（由于 spj 的某些特性，请不要在一条铁路上放超过 $L$ 个传送门，否则会被判断为 WA）

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

接下来对于每一组数据：

第一行三个整数 $n$，$m$ 和 $L$ 表示城市数，$x$ 的长度和最多放置的传送门对数。

接下来 $n-1$ 行，第 $i$ 行两个正整数 $u_i,v_i$ 表示第 $i$ 条铁路连接的两个城市。

接下来一行 $m$ 个整数表示 $x$。

outputFormat:
对于每组数据：

第一行一个整数表示最小距离和。

接下来 $n-1$ 行，第 $i$ 行开头一个整数 $num$ 表示第 $i$ 条铁路上的传送门数。然后 $num$ 对整数 $x,f$ 描述了从 $u_i$ 到 $v_i$ 传送门依次的编号与朝向，$f=0$ 表示正面朝向城市 $u_i$，$f=1$ 表示正面朝向城市 $v_i$。

传送门编号为 $1\sim \frac{\sum num}{2}$ 且每种编号必须恰好出现两次。

对于每组数据，传送门总对数不得超过 $L$，即 $\frac{\sum num}{2}\le L$。

hint:
### 样例解释

对于样例的第二组数据，树的形态及传送门的放置方式如下：

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

其中红色门编号为 $1$，绿色编号为 $2$，蓝色编号为 $3$，紫色编号为 $4$。箭头表示传送门的正面所朝的方向。加粗的点表示重要城市。

其中 $1$ 号城市到 $5$ 号城市的最短路径如下：

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

首先由 $1$ 号城市出发，进入红色传送门的正面到达 $3$ 号城市。

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

随后从 $3$ 号城市出发，从绿色传送门的正面进入，到达 $3-5$ 这条路上绿色与蓝色传送门中间的一段铁路上，再从蓝色传送门正面进入，到达 $2-3$ 这条路中蓝色与红色传送门中间的一段铁路上，再由红色传送门的背面进入，最终到达 $2$ 号城市。

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

最后再从紫色传送门的正面进入，最终到达 $5$ 号城市。中途除去 $1$ 号城市分别经过了 $3,2,5$ 号城市，于是在这种传送门的放置方式下 $dis(1,5)=3$。

同时有 $dis(1,4)=2$，可以证明不存在让 $dis(1,4)+dis(1,5)$ 更小的放置方案。

### 数据范围

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

| 子任务编号 | 分值 | 特殊限制 |
| :----------: | :----------: | :----------: |
| $0$ | $15$ | $n\le 9$，$L=100$ |
| $1$ | $10$ | $m=n-1$，$L=5n$ |
| $2$ | $20$ | $n\le 70$ 且 $n>30$ 的数据不超过五组，$L=n^2$ |
| $3$ | $20$ | $n\le 1000$ 且 $n>100$ 的数据不超过五组，$L=100n$ |
| $4$ | $30$ | $L=5n$ |
| $5$ | $5$ | $L=n$ |

对于所有数据，保证 $1\le T\le 100$，$1\le n\le 10^5$，$1\le \sum n\le 5\times 10^5$，$0\le m<n$，$2\le x_i\le n$，$x_i$ 互不相同。


title: 「LCOI2022」 Cow Function

background:
Bessie 和大家正坐在刚刚合并完成的牛棚里，跟着 Farmer John 在一起学习循环展开。

Farmer John 说，如果一个循环展开的步长为 $8$，会对程序效率有很大的提升。

课后，Farmer John 布置了一道题，要求在 $1$ 秒内算出 $f(x)=\sum\limits_{i=1}^x3^{\omega(i)}$。Bessie 用 $20$ 分钟打了一个 $Θ(n\log_2 n\sqrt n)$ 代码，一交直接 TLE。于是，Bessie 来向你求助。

description:
她想要求出对于 $k\in\{0,1,\dots,7\}$，$f(n)=\sum_{i=1}\limits^n[\omega(i)\equiv k\pmod 8]3^{\omega(i)}$ 的值。

上面的算式中，$\omega(i)$ 表示 $i$ 含有几种质因子，例如 $\omega(12)=\omega(6)=2,\omega(114514)=3$。

inputFormat: 仅一行，包含一个整数 $n$。


title: 「LCOI2022」 Cow Dance

background:
Bessie 带着他的奶牛姐妹们来跳舞了。

她们已经规划好了跳舞的步骤，但是为了更加美观，她们需要知道其中一些头奶牛在某时的平均位置，已达到更完美的表演效果。

不幸的是，由于 Bessie 的姐妹太多了，最多会有 $8\times 10^4$ 只奶牛同时来跳舞。她没有什么方便且快速的方法算这些平均位置，所以向你求助。

description:
Bessie 和她的姐妹们已经排好了位置，第 $i$ 头奶牛的坐标为 $(x_i,y_i)$。其中，$x_i$ 是 $x$ 轴坐标，$y_i$ 是 $y$ 轴坐标。

她们的舞蹈队形会有这几种变换方式：
1. 移动：$x$ 到 $y$ 号奶牛的 $x_i\to x_i+a$，$y_i\to y_i+b$。
1. 旋转：$x$ 到 $y$ 号奶牛以 $(a,b)$ 为旋转中心顺时针旋转 $g°$。
1. 散开: $x$ 到 $y$ 号奶牛以 $(a,b)$ 为中心散开为 $\dfrac{p}{q}$ 倍。即设之前奶牛坐标为 $A$，散开后坐标为 $B$，$(a,b)$ 为 $G$，$\overrightarrow{GB}=\dfrac{p}{q}\overrightarrow{GA}$。

Bessie 想知道：对于 $x$ 到 $y$ 号奶牛，他们的平均位置 $(\frac{\sum\limits^y_{i=x}x_i}{y-x+1},\frac{\sum\limits^y_{i=x}y_i}{y-x+1})$。

舞会就要开始了，所以她只能给你 $\texttt{1s}$ 的时间。

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

接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i(1\le i\le n)$ 个点的坐标

接下来 $m$ 行，每行第一个整数为 $opt$。

若 $opt=1$，则接下来包含四个整数 $x,y,a,b$，进行一次移动操作。

若 $opt=2$，则接下来包含五个整数 $x,y,a,b,g$，进行一次旋转操作。

若 $opt=3$，则接下来包含六个整数 $x,y,a,b,p,q$，进行一次散开操作。

若 $opt=4$，则接下来包含两个整数 $x,y$，表示询问编号为 $x \sim y$ 的奶牛的平均位置。

outputFormat: 即询问结果，以换行隔开，答案误差允许在 $10^{-4}$ 的范围内。

hint:
【样例解释】
![](https://cdn.luogu.com.cn/upload/image_hosting/3jt6apa4.png)

$0$ 为初始情况。$1$ 为进行样例中 `1 1 2 1 -2` 操作后结果。$2$ 为进行样例中 `2 1 3 2 0 270` 操作后结果。$3$ 为进行样例中 `3 1 2 2 2 2 1` 操作后结果。

【数据范围与约定】

保证运算时所有数的绝对值小于或等于 $10^{15}$。

|subtask|特殊限制|分数|
|:-:|:-:|:-:|
|$1$|$1\le n,m\le10^3$|$8$|
|$2$|只有旋转操作且都按奶牛为旋转中心|$18$|
|$3$|只有散开操作且都按奶牛为位似中心|$18$|
|$4$|没有旋转和散开操作|$8$|
|$5$|对于所有操作和询问 $x=y$|$18$|
|$6$|旋转中心和散开中心都是奶牛|$8$|
|$7$|$1\le n,m\le 8\times10^4$|$10$|
|$8$|没有特殊限制|$12$|

对于 $100\%$ 的数据，$1\le n,m\le3\times10^5$，$1\le x\le y\le n$，$-32768\le a,b<32768$，$0< \dfrac{p}{q}\le 233333$，$0\le g\le359$，初始坐标限制同 $a,b$。

### **注：**
- **请注意常数因子优化。**
- **此题输入输出量较大，建议使用 `scanf` 和 `printf`。**


title: [COCI2021-2022#4] Autići

description:
有 $n$ 个好朋友，每人有一辆遥控汽车和一个车库。第 $i$ 个人有若干个长度为 $d_i$ 的玩具道路部件，可以为汽车建造道路。

两个朋友 $a$ 和 $b$ 可以建造一条长度为 $d_a+d_b$ 道路以连接他们的车库。

我们认为，如果从任意一个车库出发能够到达任意的其他车库，我们称这种情况为“连通交通”。

请求出，构成一个“连通交通”所需要的最小总道路长度是多少？

inputFormat:
第一行包含一个整数 $n$，表示朋友的人数。

第二行包含 $n$ 个整数 $d_i$，表示第 $i$ 位朋友手中的道路部件的长度。

outputFormat: 仅一行，输出成一个“连通交通”所需要的最小总道路长度。

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

当只有一位朋友时，已经构成“连通交通”，不必修建道路。故答案为 $0$。

**【样例 3 解释】**

如果在第 $1$ 位和第 $2$ 位朋友、第 $2$ 位和第 $3$ 位朋友、第 $3$ 位和第 $4$ 位朋友之间修建道路可以形成“连通道路”，价格总和为 $(7+3)+(3+3)+(3+5)=24$。

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

**本题采用子任务捆绑测试。**
- Subtask 1（10 pts）：$d_1 = d_2 = \dots = d_n$。
- Subtask 2（20 pts）：$1 ≤ n ≤ 10^3$。
- Subtask 3（20 pts）：没有额外限制。

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

**【提示与说明】**

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

**题目译自 [COCI2021-2022](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) T1 Autići。**


title: [COCI2021-2022#4] Autobus

description:
在一个国家里有 $n$ 座城市。这些城市由 $m$ 条公交线路连接，其中第 $i$ 条线路从城市 $a_i$ 出发，到 $b_i$ 停止，路程中耗时 $t_i$ 分钟。

Ema 喜欢旅行，但她并不喜欢在公交线路之间换乘。在旅行过程中，她希望**最多**只需坐 $k$ 个不同的公交线路。

Ema 想知道，从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间是多少（最多坐 $k$ 个不同的公交线路）。

inputFormat:
第一行包含两个整数 $n,m$，分别表示城市的数量和公交车线路的数量。

接下来 $m$ 行，第 $i+1$ 包含三个整数 $a_i,b_i,t_i$，分别表示第 $i$ 条公交车线路的起点、终点和从起点到终点所需的时间。

接下来一行包含两个整数 $k,q$，最大坐的不同公交线路的个数和问题题的个数。

接下来 $q$ 行，第 $m+j+3$ 行包含两个整数 $c_j,d_j$，表示询问从城市 $c_j$ 到城市 $d_j$ 的最短旅行时间。

outputFormat: 输出包含 $q$ 行，第 $i$ 行包含一个整数，表示从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间。

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

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

每个样例中的答案都已经标记在图中。

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

**本题采用子任务捆绑测试。**

- Subtask 1（15 pts）：$k ≤ n ≤ 7$。
- Subtask 2（15 pts）：$k ≤ 3$。
- Subtask 3（25 pts）：$k ≤ n$。
- Subtask 4（15 pts）：没有额外限制。

对于 $100\%$ 的数据，$2\le n \le 70,1\le m,t_i\le 10^6,1\le a_i,b_i,c_j,d_j\le n,1\le k\le10^9,1\le q \le n^2$。

**【提示与说明】**

**本题分值按 COCI 原题设置，满分 $70$。**

**题目译自 [COCI2021-2022](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) T2  Autobus。**


title: [COCI2021-2022#4] Izbori

description:
Malnar 先生正在竞选县长，这个县一共有 $n$ 栋房屋，每栋房屋里都住着一位居民。Malnar 先生知道，选举的赢家不一定是最好的候选人，而是在选举前举办的宴会最好的候选人。因此，在选举前几天，他将邀请第 $l$ 至 $r(l\le r)$ 栋房屋内居住的居民，为他们准备一顿丰盛的晚餐。

Malnar 先生知道所有居民最喜欢吃的菜。在宴会上，他会准备大多数人喜欢的一道菜。如果一个人吃到了自己最喜欢吃的菜，将会投一票给 Malnar 先生。但是如果没有吃到自己最喜欢吃的菜，他们将会把票投给 Vlado 先生。如果没有来参加晚宴的居民，他们将会忘记选举，不做出任何投票。如果一个候选人获得了投了票的人中一半以上的人的支持，他将会赢得竞选。

Malnar 先生想知道，有多少组的 $(l,r)$ 可以使他赢得竞选。

inputFormat:
第一行包含一个整数 $n$，表示房屋的数量。

第二行包含 $n$ 个整数 $a_i$，表示第 $i$ 栋房屋内居民最喜欢的菜。

outputFormat: 仅一行，输出可以使 Malnar 先生赢得竞选的 $(l,r)$ 的组数。

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

可以使 Malnar 先生赢得竞选的 $(l,r)$ 为：$(1, 1),(2, 2),(3, 3),(1, 3)$。

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

**本题采用子任务捆绑测试。**

- Subtask 1（10 pts）：$1 ≤ n ≤ 300$。
- Subtask 2（15 pts）：$1 ≤ n ≤ 2\times10^3$。
- Subtask 3（15 pts）：$\forall i\in\{1,2,3,\dots,n\},1 ≤ a_i ≤ 2$。
- Subtask 4（70 pts）：没有额外限制。

对于 $100\%$ 的数据，$1 \le l\le r ≤ n ≤ 2\times10^5,1 ≤ a_i ≤ 10^9$。

**【提示与说明】**

**本题分值按 COCI 原题设置，满分 $110$。**

**题目译自 [COCI2021-2022](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) T3 Izbori。**


title: [COCI2021-2022#4] Šarenlist

background: 温暖的夏夜，Vito 和他的好朋友 Karlo 躺在森林的空地上看星星。突然，Vito 大喊：“Karlo，你看！我们周围的树都在变色！”“哇，真是五彩缤纷！”Karlo 惊讶地说。的确，森林中的树枝开始变色。

description:
Vito 和 Karlo 被这些彩色的树迷住了，他们同时也注意到了一些事物。他们正在看的每棵树都可以看做是一个树图，即任意两点之间仅存在一条路径的无向图。他们正在看的每棵树都有这样的特点：每条边上的颜色都是 $k$ 种颜色中的一种。如果树上的一个路径是彩色的，意味着这条路径上至少包含两种不同颜色的边。

早上树的魔力全部消失了。Vito 和 Karlo 还记得 $m$ 条彩色路径的起点和终点。他们想知道：满足条件的树的有多少种可能？由于答案可能很大，所以请将答案对 $10^9+7$ 取模。

inputFormat:
第一行包含三个整数 $n,m,k$，分别表示树上的节点数、Vito 和 Karlo 所记得的彩色路径的个数和树枝的颜色总数。

接下来 $n-1$ 行，第 $i+1$ 行包含两个整数 $a_i,b_i$，表示点 $a_i$ 和点 $b_i$ 之间有一条树边。

接下来 $m$ 行，第 $n+j$ 行包含两个整数 $c_j,d_j$，表示从点 $c_j$ 到点 $d_j$ 之间有一条彩色路径。保证 $c_j$ 和 $d_j$ **不相邻**。

outputFormat: 仅一行，输出满足条件的树的可能数，答案需对 $10^9+7$ 取模。

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

第一种情况是点 $1$ 和点 $2$ 之间的边涂颜色 $1$，点 $2$ 和点 $3$ 之间的边涂颜色 $2$。

第二种情况是点 $1$ 和点 $2$ 之间的边涂颜色 $2$，点 $2$ 和点 $3$ 之间的边涂颜色 $1$。

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

**本题采用子任务捆绑测试。**

- Subtask 1（10 pts）：$m = 1$。
- Subtask 2（15 pts）：$m = 2$。
- Subtask 3（10 pts）：每个树边最多属于 $m$ 条彩色路径中的一条。
- Subtask 4（10 pts）：$1 ≤ n ≤ 15, k = 2$。
- Subtask 5（65 pts）：没有额外限制。

对于 $100\%$ 的数据，$3 ≤a_i,b_i, c_j , d_j ≤ n ≤ 60, 1 ≤ m ≤ 15, 2 ≤ k ≤ 10^9$。

**【提示与说明】**

**本题分值按 COCI 原题设置，满分 $110$。**

**题目译自 [COCI2021-2022](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) T5  Šarenlist。**


title: [COCI2021-2022#4] Parkovi

background: 市政府决定修建公园来美化景观。为了让公园不仅好看，而且有用。市政府为了市民的幸福，希望公园里居民们更近一些。

description:
这个城市由 $n$ 个社区组成，社区间由 $n-1$ 条道路连接。并且从任意一个社区出发，可以到任意一个社区去。一共会建造 $k$ 座公园，同一个社区内只会存在一座公园。市政府希望尽可能减小从每个社区到最近公园的距离的最大值。

帮助政府应该在那些社区建造公园，可以使每个社区到最近公园的距离的最大值最小。

inputFormat:
第一行包含两个整数 $n,k$，分别表示社区数目和需要建造的公园数目。

接下来 $n-1$ 行，第 $i$ 行包含三个数 $a_i,b_i,w_i$，分别表示有一条长度为 $w_i$ 道路连接着社区 $a_i,b_i$。

outputFormat:
第一行包含一个整数，即每个社区到最近公园的距离的最大值的最小值。

第二行包含 $k$ 个整数，可以使每个社区到最近公园的距离的最大值最小所需要修建的公园所在的社区编号。

**如果有多组解输出一组解。**

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

如果只在 $3,4$ 号社区建公园，最大距离不会改变。但是市政府想建 $k$ 个公园，所以需要在其他地方再建两个。

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

**本题采用子任务捆绑测试。**

- Subtask 1（10 pts）：$1 ≤ n ≤ 20$。
- Subtask 2（10 pts）：$k=1$。
- Subtask 3（30 pts）：$\forall i\in\{1,2,3,\dots,n-1\},a_i=i,b_i=i+1$。
- Subtask 4（60 pts）：没有额外限制。

对于 $100\%$ 的数据，$1\le k\le n\le2\times10^5,1\le a_i,b_i\le n,1\le w_i \le 1e9$。

**【提示与说明】**

**本题分值按 COCI 原题设置，满分 $110$。**

**题目译自 [COCI2021-2022](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) T4 Parkovi。**


title: [COCI2021-2022#1] Logičari

description: 给定一个 $n$ 个点的基环树，现在对基环树上的点染色，使得每个点都有且仅有一个与他相连的点（不包括它自身）被染色，求最少的染色点数，或者返回无解。

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

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

outputFormat: 输出最小的染色点数，或者返回无解，无解输出 `-1`。

hint:
#### 样例解释
#### 样例 1 解释
可以在 $1,2$ 号点染色。

#### 样例 2 解释
如果有一个点被染色，则被染色的点不会有被染色的相邻的点。

如果有两个点被染色，则不被染色的点会有两个被染色的相邻的点。

#### 数据范围

对于全部数据，$3\le n\le 10^5$，$1\le u_i,v_i\le n$。

| Subtask |      特殊限制      | 分数 |
| :-----: | :----------------: | :--: |
|   $1$   | 每个点的点度为 $2$ | $10$ |
|   $2$   |     $n\le 20$      | $10$ |
|   $3$   |    $n\le 10^3$     | $40$ |
|   $4$   |     无特殊限制     | $50$ |

#### 说明
**本题总分 $110$ 分。**

本题译自 [Croatian Open Competition in Informatics 2021/2022](https://hsin.hr/coci/archive/2021_2012) [Contest #1](https://hsin.hr/coci/archive/2021_2022/contest1_tasks.pdf) T3 Logičari。


title: [COCI2021-2022#1] Set

background: 在知名游戏 SET 中，存在着一些数字、形状、颜色等不同的卡片，玩家的目标是确定一个存在的 triplet of cards（即卡片的三元组，也就是三张卡片构成的组合），使其符合特定的要求。Marin 和 Josip 很快就对这个游戏感到无趣，并对其进行了加强。

description:
在本题中，定义每张卡片代表着一个仅由 $ 1, 2, 3 $ 构成的长度为 $ k $ 的序列，共有 $ n $ 张卡片，卡片之间是无序的。

定义一个 SET 表示，当且仅当一个无序的 triplet of cards 其中的三个序列的每一位均相同或各不相同，用原文中的话就是 same 或 pairwise different，更严谨地表示，我们令这三个序列为 $ S_i, S_j, S_k $，则一定满足如下条件：

* $ i \lt j \lt k $
* $ \forall x \in \left[1, k\right] $，满足 $ S_i(x) = S_j(x) = S_k(x) $ 或 $ S_i(x) \neq S_j(x) \neq S_k(x) $

例如 $ (1123, 1322, 1221) $ 便满足 $ 1, 3 $ 位均相同，$ 2,4 $ 位各不相同。

给你这些序列，求可以组成多少种本质不同的 SET。

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

接下来 $ n $ 行中每一行包含一个仅由 $ 1, 2, 3 $ 构成的长度为 $ k $ 的序列，代表着一张卡片。

保证每张卡片上的序列不同。

outputFormat: 仅一行一个整数，表示可以组成的本质不同的 SET 的数量。

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

可以组成的两个 SET 分别为 $ (S_1, S_2, S_3) $ 和  $ (S_1, S_4, S_5) $。

**【数据范围】**

对于全部数据，$1\le k\le 12$，$1\le n\le 3^k$，$S_i$ 互不相同，$1\le S_i(x) \le 3$。

| Subtask |  特殊限制  | 分数 |
| :-----: | :--------: | :--: |
|   $1$   |  $k\le 5$  | $10$ |
|   $2$   |  $k\le 7$  | $30$ |
|   $3$   | 无特殊限制 | $70$ |

#### 说明
**本题总分 $110$ 分。**

本题译自 [Croatian Open Competition in Informatics 2021/2022](https://hsin.hr/coci/archive/2021_2012) [Contest #1](https://hsin.hr/coci/archive/2021_2022/contest1_tasks.pdf) T4 Set。


title: [COCI2021-2022#1] Volontiranje

description: 给定一个 $1\sim n$ 的排列 $p$，请从这里面取出尽可能多的不交的上升子序列，且他们的长度为原排列的 LIS 的长度，并构造一组方案。

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

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

outputFormat:
第一行请输出您选择的上升子序列个数与他们的长度。

接下来若干行，一行若干个整数，表示某个上升子序列的每个元素的下标。

您可以以任意顺序输出您选择的上升子序列。

hint:
#### 数据范围

对于全部数据，$1\le n\le 10^6$，$1\le p_i\le n$。

| Subtask |  数据范围   | 分值 |
| :-----: | :---------: | :--: |
|   $1$   |  $n\le 15$  | $10$ |
|   $2$   | $n\le 10^3$ | $40$ |
|   $3$   | 无特殊限制  | $60$ |

#### 说明
**本题总分 $110$ 分。**

本题译自 [Croatian Open Competition in Informatics 2021/2022](https://hsin.hr/coci/archive/2021_2022) [Contest #1](https://hsin.hr/coci/archive/2021_2022/contest1_tasks.pdf) T5 Volontiranje。

在附加文件中下发了一份 checker.cpp。


title: A 质因数

description:
定义 $f(x)$ 表示 $x$ 分解质因数后得到的质数个数，例如 $f(6)=2,f(12)=3$。

具体的，令 $x=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，其中 $p_1,p_2,\ldots,p_k$ 是两两不同的质数，则 $f(x)=a_1+a_2+\cdots + a_k$。

给定一个数 $n$，判断是否存在 $1<m<n$，满足 $f(m)>f(n)$。

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

接下来 $T$ 行，每行一个正整数 $n$。

outputFormat: 输出 $T$ 行，若对于第 $i$ 组数据给定的 $n$ 存在 $1<m<n,f(m)>f(n)$ 输出一行一个数 $1$，否则输出一行一个数 $0$。


title: 「Wdsr-3」迷途竹林

background:
迷途竹林是生长着高耸入云的、无边无际的竹子的竹林。由于特殊地势的缘故，所有竹子都向着一侧倾斜生长。由于竹子顶部的叶片交错在一起，因此即使竹子的下端已经被砍掉，仍然会因为其他竹子的相互作用而无法掉落。

作为白玉楼的亭师，白玉楼的实际管家，魂魄妖梦时常需要收集一些竹子用于维修竹制家具以及竹楼。因为她拥有精湛的剑术，因此可以在瞬间砍伐一大片的竹子作为材料。当然，妖梦并不希望拥有过多的竹子。因此她会选择一个多边形区域进行采集。在那一瞬间，妖梦会用楼观剑顺着多边形的边进行砍伐。

不过，由于掉落下来的竹子数量实在太多，因此妖梦无暇统计砍下来的竹子。你能帮帮她吗？

description:
妖梦在迷途竹林里选定的竹子，可以看作在同一平面上。竹子可以看作有 $+\infty$ 根，每相邻两根竹子间距相等，并且每根竹子的倾斜程度相同。竹子的高度可以看作是无限高。

妖梦选定了一块多边形区域进行竹子的砍伐。**只有在多边形内的部分**才会被收集到。多边形共有 $n$ 条边，为了防止出现歧义，保证任意一条边都不和竹子平行；保证多边形是[简单多边形](https://baike.baidu.com/item/%E7%AE%80%E5%8D%95%E5%A4%9A%E8%BE%B9%E5%BD%A2/18891697)。

我们会使用两个实数 $\theta$ 和 $a$ 来描述这些竹子。这两个字母表示的含义可以参考下图：

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

现在妖梦需要知道她砍下来的竹子的总长度，也就是求出这些竹子（图中橙色的这些线段）的长度之和。

inputFormat:
- 第一行有一个正整数 $n$，表示多边形的边数。
- 接下来 $n$ 行，将会**按照顺时针顺序**给出多边形的 $n$ 个顶点的坐标，第 $i$ 个点与第 $i+1$ 个点连接 $(1\le i<n)$，第 $n$ 个点与第 $1$ 个点连接。
- 接着给出描述线段的参数 $\theta$ 和 $a$。

outputFormat: - 共一行，一个实数，表示所求得的竹子的总长。你的答案 $\mathit{ans}$ 被认为是正确的，当且仅当与标准答案 $\mathit{std}$ 满足 $\dfrac{|\mathit{ans}-\mathit{std}\ |}{\max(1.0,\mathit{std}\ )}\le 10^{-6}$。

hint:
#### 样例 1 解释

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

容易发现，竹子总长（即橘红色线段的总长度）为 $16\sqrt 2$。

#### 样例 2 解释

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

我有一个精妙绝伦的方法解释样例 $2$，可惜这里空白太小写不下。

#### 数据范围及约定

$$
\def{\arraystretch}{1.5}
\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值}\cr\hline
1 & 10 & \text{A} & 30 \cr\hline
2 & 10^3 & - & 20 \cr\hline
3 & 10^5 & \text{B} & 20 \cr\hline
4 & 10^5 & - & 30 \cr\hline
\end{array}
$$

**特殊性质** $\textbf{A}$：保证 $\theta\in[80,100);|x_i|,|y_i|\le 10$。
**特殊性质** $\textbf{B}$：保证 $\theta=90$。

- 对于 $100\%$ 的数据，保证 $3\le n\le 10^5;|x_i|,|y_i|\le 10^4;\theta\in[1,179);\alpha\in[0.1,100]$。输入数据当中出现的浮点数均保留四位小数。


title: [✗✓OI R1] 铝锤制作

background:
DPair 打算用米德拉什给大家带来笑容。

因为 Lillia 不知道什么是米德拉什，所以打算阻止 Ta。

为了阻止 DPair，你需要制作一个小铝锤。

如果你不知道如何制作小铝锤，你可以参考题目下方给出的视频。

或者，你也可以选择做这场月赛的签到题。

description: 构造一个正整数数列 $a$，使 $a$ 中所有元素之积为 $n$，所有元素之和为 $k$。如果不存在这样的数列，输出 `-1`。

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

outputFormat:
第一行一个整数 $m$，代表这个数列的长度。
接下来一行 $m$ 个正整数 $a_i$，代表这个数列。要求 $1\leq m \leq 1000$，$1\leq a_i \leq 1000$。
特别的，如果没有符合要求的数列，直接输出 `-1`。

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

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

对于样例一，显然有 $1\times67=67,1+67=68$。
对于样例二，可以证明没有合法的解。

**【数据范围】**

对于 $10\%$ 的数据，$1\leq n,k \leq 3$；
对于 $30\%$ 的数据，$1\leq n,k \leq 10$；
另有 $10\%$ 的数据，$n=k$；
对于 $100\%$ 的数据，$1\leq n,k \leq 100$。

![](bilibili:av498389435)


title: Hard Brackets Inserting

description:
小 S 有一个长度为 $n$ 的**合法**括号序列。

现在小 K 看到了，想在其中插入若干括号，使之成为一个长度为 $m$ 的括号序列（不一定合法）。但是她不想完全破坏这个序列，于是她希望对于她这种添加括号的方式，仅存在一种合法的且长度为 $n$ 的括号序可以通过插入若干括号来得到小 K 改后的序列，这样小 S 就可以轻松还原出原来的括号序列了（也就是说在保证删完后的括号序列长度为 $n$ 且合法的情况下，无论小 S 如何删除括号，都只能得到她初始的括号序列）。

求小 K 插入括号的方案数模 $998244353$。两种插入括号的方案不同当且仅当我们将最终的括号序列按照是小 K 所插入的还是原有的两类分别染成红色和黑色，得到的带颜色的括号序列不同。

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

接下来对于每一组数据：

第一行两个整数 $n$ 和 $m$ 表示小 S 的括号序列的长度和小 K 插入括号后的长度。

第二行一个**合法**的括号序列表示小 S 的括号序列。

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


title: [CSP-J 2021] 插入排序

description:
插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为 $\mathcal O(1)$，则插入排序可以以 $\mathcal O(n^2)$ 的时间复杂度完成长度为 $n$ 的数组的排序。不妨假设这 $n$ 个数字分别存储在 $a_1, a_2, \ldots, a_n$ 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：

这下面是 C/C++ 的示范代码：

```cpp
for (int i = 1; i <= n; i++)
	for (int j = i; j >= 2; j--)
		if (a[j] < a[j-1]) {
			int t = a[j-1];
			a[j-1] = a[j];
			a[j] = t;
		}
```

这下面是 Pascal 的示范代码：

```pascal
for i:=1 to n do
	for j:=i downto 2 do
		if a[j]<a[j-1] then
			begin
				t:=a[i];
				a[i]:=a[j];
				a[j]:=t;
			end;
```

为了帮助小 Z 更好的理解插入排序，小 Z 的老师 H 老师留下了这么一道家庭作业：

H 老师给了一个长度为 $n$ 的数组 $a$，数组下标从 $1$ 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 $a$ 上的 $Q$ 次操作，操作共两种，参数分别如下：

$1~x~v$：这是第一种操作，会将 $a$ 的第 $x$ 个元素，也就是 $a_x$ 的值，修改为 $v$。保证 $1 \le x \le n$，$1 \le v \le 10^9$。**注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作**。

$2~x$：这是第二种操作，假设 H 老师按照**上面的伪代码**对 $a$ 数组进行排序，你需要告诉 H 老师原来 $a$ 的第 $x$ 个元素，也就是 $a_x$，在排序后的新数组所处的位置。保证 $1 \le x \le n$。**注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作**。

H 老师不喜欢过多的修改，所以他保证类型 $1$ 的操作次数不超过 $5000$。

小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。

inputFormat:
第一行，包含两个正整数 $n, Q$，表示数组长度和操作次数。

第二行，包含 $n$ 个空格分隔的非负整数，其中第 $i$ 个非负整数表示 $a_i$。

接下来 $Q$ 行，每行 $2 \sim 3$ 个正整数，表示一次操作，操作格式见【**题目描述**】。

outputFormat: 对于每一次类型为 $2$ 的询问，输出一行一个正整数表示答案。

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

在修改操作之前，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3, 2, 1$。

在修改操作之后，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3, 1, 2$。

注意虽然此时 $a_2 = a_3$，但是我们**不能将其视为相同的元素**。

**【样例 #2】**

见附件中的 `sort/sort2.in` 与 `sort/sort2.ans`。

该测试点数据范围同测试点 $1 \sim 2$。

**【样例 #3】**

见附件中的 `sort/sort3.in` 与 `sort/sort3.ans`。

该测试点数据范围同测试点 $3 \sim 7$。

**【样例 #4】**

见附件中的 `sort/sort4.in` 与 `sort/sort4.ans`。

该测试点数据范围同测试点 $12 \sim 14$。

**【数据范围】**

对于所有测试数据，满足 $1 \le n \le 8000$，$1 \le Q \le 2 \times {10}^5$，$1 \le x \le n$，$1 \le v,a_i \le 10^9$。

对于所有测试数据，保证在所有 $Q$ 次操作中，至多有 $5000$ 次操作属于类型一。

各测试点的附加限制及分值如下表所示。

| 测试点 | $n \le$ | $Q \le$ | 特殊性质 |
|:-:|:-:|:-:|:-:|
| $1 \sim 4$ | $10$ | $10$ | 无 |
| $5 \sim 9$ | $300$ | $300$ | 无 |
| $10 \sim 13$ | $1500$ | $1500$ | 无 |
| $14 \sim 16$ | $8000$ | $8000$| 保证所有输入的 $a_i,v$ 互不相同 |
| $17 \sim 19$ | $8000$ | $8000$ | 无 |
| $20 \sim 22$ | $8000$ | $2 \times 10^5$ | 保证所有输入的 $a_i,v$ 互不相同 |
| $23 \sim 25$ | $8000$ | $2 \times 10^5$ | 无 |


title: [CSP-J 2021] 小熊的果篮

description: 小熊的水果店里摆放着一排 $n$ 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 $1, 2, \ldots, n$ 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。

inputFormat:
第一行，包含一个正整数 $n$，表示水果的数量。

第二行，包含 $n$ 个空格分隔的整数，其中第 $i$ 个数表示编号为 $i$ 的水果的种类，$1$ 代表苹果，$0$ 代表桔子。

outputFormat:
输出若干行。

第 $i$ 行表示第 $i$ 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号，每两个编号之间用一个空格分隔。

samples:
见附件中的 fruit/fruit3.in。
见附件中的 fruit/fruit3.ans。

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

这是第一组数据的样例说明。

所有水果一开始的情况是 $[1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0]$，一共有 $6$ 个块。

在第一次挑水果组成果篮的过程中，编号为 $1, 3, 5, 8, 9, 11$ 的水果被挑了出来。

之后剩下的水果是 $[1, 0, 1, 1, 1, 0]$，一共 $4$ 个块。

在第二次挑水果组成果篮的过程中，编号为 $2, 4, 6, 12$ 的水果被挑了出来。

之后剩下的水果是 $[1, 1]$，只有 $1$ 个块。

在第三次挑水果组成果篮的过程中，编号为 $7$ 的水果被挑了出来。

最后剩下的水果是 $[1]$，只有 $1$ 个块。

在第四次挑水果组成果篮的过程中，编号为 $10$ 的水果被挑了出来。

**【数据范围】**

对于 $10 \%$ 的数据，$n \le 5$。
对于 $30 \%$ 的数据，$n \le 1000$。
对于 $70 \%$ 的数据，$n \le 50000$。
对于 $100 \%$ 的数据，$1 \le n \le 2 \times {10}^5$。

**【提示】**

由于数据规模较大，建议 C/C++ 选手使用 `scanf` 和 `printf` 语句输入、输出。


title: [CSP-J 2021] 分糖果

background: 红太阳幼儿园的小朋友们开始分糖果啦！

description:
红太阳幼儿园有 $n$ 个小朋友，你是其中之一。保证 $n \ge 2$。

有一天你在幼儿园的后花园里发现无穷多颗糖果，你打算拿一些糖果回去分给幼儿园的小朋友们。

由于你只是个平平无奇的幼儿园小朋友，所以你的体力有限，至多只能拿 $R$ 块糖回去。

但是拿的太少不够分的，所以你至少要拿 $L$ 块糖回去。保证 $n \le L \le R$。

也就是说，如果你拿了 $k$ 块糖，那么你需要保证 $L \le k \le R$。

如果你拿了 $k$ 块糖，你将把这 $k$ 块糖放到篮子里，并要求大家按照如下方案分糖果：只要篮子里有**不少于** $n$ 块糖果，幼儿园的所有 $n$ 个小朋友（包括你自己）都从篮子中拿走**恰好**一块糖，直到篮子里的糖数量**少于** $n$ 块。此时篮子里剩余的糖果均归你所有——这些糖果是**作为你搬糖果的奖励**。

作为幼儿园高质量小朋友，你希望让**作为你搬糖果的奖励**的糖果数量（**而不是你最后获得的总糖果数量**！）尽可能多；因此你需要写一个程序，依次输入 $n, L, R$，并输出你最多能获得多少**作为你搬糖果的奖励**的糖果数量。

inputFormat: 输入一行，包含三个正整数 $n, L, R$，分别表示小朋友的个数、糖果数量的下界和上界。

outputFormat: 输出一行一个整数，表示你最多能获得的**作为你搬糖果的奖励**的糖果数量。

samples:
见附件中的 candy/candy3.in。
见附件中的 candy/candy3.ans。


title: [CSP-J 2021] 网络连接

description:
TCP/IP 协议是网络通信领域的一项重要协议。今天你的任务，就是尝试利用这个协议，还原一个简化后的网络连接场景。

在本问题中，计算机分为两大类：服务机（`Server`）和客户机（`Client`）。服务机负责建立连接，客户机负责加入连接。

需要进行网络连接的计算机共有 $n$ 台，编号为 $1 \sim n$，这些机器将按编号递增的顺序，依次发起一条建立连接或加入连接的操作。

每台机器在尝试建立或加入连接时需要提供一个地址串。服务机提供的地址串表示它尝试建立连接的地址，客户机提供的地址串表示它尝试加入连接的地址。

一个符合规范的地址串应当具有以下特征：

1. 必须形如 `a.b.c.d:e` 的格式，其中 $a, b, c, d, e$ 均为非负整数；
2. $0 \le a, b, c, d \le 255$，$0 \le e \le 65535$；
3. $a, b, c, d, e$ 均不能含有多余的前导 $0$。

相应地，不符合规范的地址串可能具有以下特征：

1. 不是形如 `a.b.c.d:e` 格式的字符串，例如含有多于 $3$ 个字符 `.` 或多于 $1$ 个字符 `:` 等情况；
2. 整数 $a, b, c, d, e$ 中某一个或多个超出上述范围；
3. 整数 $a, b, c, d, e$ 中某一个或多个含有多余的前导 $0$。

例如，地址串 `192.168.0.255:80` 是符合规范的，但 `192.168.0.999:80`、`192.168.00.1:10`、`192.168.0.1:088`、`192:168:0:1.233` 均是不符合规范的。

如果服务机或客户机在发起操作时提供的地址串不符合规范，这条操作将被直接忽略。

在本问题中，我们假定凡是符合上述规范的地址串均可参与正常的连接，你无需考虑每个地址串的实际意义。

由于网络阻塞等原因，不允许两台服务机使用相同的地址串，如果此类现象发生，后一台尝试建立连接的服务机将会无法成功建立连接；除此之外，凡是提供符合规范的地址串的服务机均可成功建立连接。

如果某台提供符合规范的地址的客户机在尝试加入连接时，与先前某台已经成功建立连接的服务机提供的地址串相同，这台客户机就可以成功加入连接，并称其连接到这台服务机；如果找不到这样的服务机，则认为这台客户机无法成功加入连接。

请注意，尽管不允许两台不同的服务机使用相同的地址串，但多台客户机使用同样的地址串，以及同一台服务机同时被多台客户机连接的情况是被允许的。

你的任务很简单：在给出每台计算机的类型以及地址串之后，判断这台计算机的连接情况。

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

接下来 $n$ 行，每行两个字符串 $\mathit{op}, \mathit{ad}$，按照编号从小到大给出每台计算机的类型及地址串。

其中 $\mathit{op}$ 保证为字符串 `Server` 或 `Client` 之一，$\mathit{ad}$ 为一个长度不超过 $25$ 的，仅由数字、字符 `.` 和字符 `:` 组成的非空字符串。

每行的两个字符串之间用恰好一个空格分隔开，每行的末尾没有多余的空格。

outputFormat:
输出共 $n$ 行，每行一个正整数或字符串表示第 $i$ 台计算机的连接状态。其中：

如果第 $i$ 台计算机为服务机，则：

1. 如果其提供符合规范的地址串且成功建立连接，输出字符串 `OK`。
2. 如果其提供符合规范的地址串，但由于先前有相同地址串的服务机而无法成功建立连接，输出字符串 `FAIL`。
3. 如果其提供的地址串不是符合规范的地址串，输出字符串 `ERR`。

如果第 $i$ 台计算机为客户机，则：

1. 如果其提供符合规范的地址串且成功加入连接，输出一个正整数表示这台客户机连接到的服务机的编号。
2. 如果其提供符合规范的地址串，但无法成功加入连接时，输出字符串 `FAIL`。
3. 如果其提供的地址串不是符合规范的地址串，输出字符串 `ERR`。

samples:
见附件中的 network/network3.in。
见附件中的 network/network3.ans。

samples:
见附件中的 network/network4.in。
见附件中的 network/network4.ans。

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

计算机 $1$ 为服务机，提供符合规范的地址串 `192.168.1.1:8080`，成功建立连接；

计算机 $2$ 为服务机，提供与计算机 $1$ 相同的地址串，未能成功建立连接；

计算机 $3$ 为客户机，提供符合规范的地址串 `192.168.1.1:8080`，成功加入连接，并连接到服务机 $1$；

计算机 $4$ 为客户机，提供符合规范的地址串 `192.168.1.1:80`，找不到服务机与其连接；

计算机 $5$ 为客户机，提供的地址串 `192.168.1.1:99999` 不符合规范。

**【数据范围】**

| 测试点编号 | $n \le$ | 特殊性质 |
|:-:|:-:|:-:|
| $1$ | $10$ | 性质 1 2 3 |
| $2 \sim 3$ | $100$ | 性质 1 2 3 |
| $4 \sim 5$ | $1000$ | 性质 1 2 3 |
| $6 \sim 8$ | $1000$ | 性质 1 2 |
| $9 \sim 11$ | $1000$ | 性质 1 |
| $12 \sim 13$ | $1000$ | 性质 2 |
| $14 \sim 15$ | $1000$ | 性质 4 |
| $16 \sim 17$ | $1000$ | 性质 5 |
| $18 \sim 20$ | $1000$ | 无特殊性质 |

“性质 1”为：保证所有的地址串均符合规范；
“性质 2”为：保证对于任意两台不同的计算机，如果它们同为服务机或者同为客户机，则它们提供的地址串一定不同；
“性质 3”为：保证任意一台服务机的编号都小于所有的客户机；
“性质 4”为：保证所有的地址串均形如 `a.b.c.d:e` 的格式，其中 $a, b, c, d, e$ 均为不超过 ${10}^9$ 且不含有多余前导 $0$ 的非负整数；
“性质 5”为：保证所有的地址串均形如 `a.b.c.d:e` 的格式，其中 $a, b, c, d, e$ 均为只含有数字的非空字符串。

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

**【提供 hack 数据感谢】**

- [xyf007](/user/68273)。


title: [CSP-S 2021] 廊桥分配

description:
当一架飞机抵达机场时，可以停靠在航站楼旁的廊桥，也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥，因为这样省去了坐摆渡车前往航站楼的周折。然而，因为廊桥的数量有限，所以这样的愿望不总是能实现。

机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。

L 市新建了一座机场，一共有 $n$ 个廊桥。该机场决定，廊桥的使用遵循“先到先得”的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊桥，否则停靠在远机位（假设远机位的数量充足）。该机场只有一条跑道，因此不存在两架飞机同时抵达的情况。

现给定未来一段时间飞机的抵达、离开时刻，请你负责将 $n$ 个廊桥分配给国内区和国际区，使停靠廊桥的飞机数量最多。

inputFormat:
输入的第一行，包含三个正整数 $n, m_1, m_2$，分别表示廊桥的个数、国内航班飞机的数量、国际航班飞机的数量。

接下来 $m_1$ 行，是国内航班的信息，第 $i$ 行包含两个正整数 $a_{1, i}, b_{1, i}$，分别表示一架国内航班飞机的抵达、离开时刻。

接下来 $m_2$ 行，是国际航班的信息，第 $i$ 行包含两个正整数 $a_{2, i}, b_{2, i}$，分别表示一架国际航班飞机的抵达、离开时刻。

每行的多个整数由空格分隔。

outputFormat: 输出一个正整数，表示能够停靠廊桥的飞机数量的最大值。

samples:
见附件中的 airport/airport3.in
见附件中的 airport/airport3.ans

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

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

在图中，我们用抵达、离开时刻的数对来代表一架飞机，如 $(1, 5)$ 表示时刻 $1$ 抵达、时刻 $5$ 离开的飞机；用 $\surd$ 表示该飞机停靠在廊桥，用 $\times$ 表示该飞机停靠在远机位。

我们以表格中阴影部分的计算方式为例，说明该表的含义。在这一部分中，国际区有 $2$ 个廊桥，$4$ 架国际航班飞机依如下次序抵达：

1. 首先 $(2, 11)$ 在时刻 $2$ 抵达，停靠在廊桥。
2. 然后 $(4, 15)$ 在时刻 $4$ 抵达，停靠在另一个廊桥。
3. 接着 $(7, 17)$ 在时刻 $7$ 抵达，这时前 $2$ 架飞机都还没离开、都还占用着廊桥，而国际区只有 $2$ 个廊桥，所以只能停靠远机位。
4. 最后 $(12, 16)$ 在时刻 $12$ 抵达，这时 $(2, 11)$ 这架飞机已经离开，所以有 $1$ 个空闲的廊桥，该飞机可以停靠在廊桥。

根据表格中的计算结果，当国内区分配 $2$ 个廊桥、国际区分配 $1$ 个廊桥时，停靠廊桥的飞机数量最多，一共 $7$ 架。

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

当国内区分配 $2$ 个廊桥、国际区分配 $0$ 个廊桥时，停靠廊桥的飞机数量最多，一共 $4$ 架，即所有的国内航班飞机都能停靠在廊桥。

需要注意的是，本题中廊桥的使用遵循“先到先得”的原则，如果国际区只有 $1$ 个廊桥，那么将被飞机 $(1, 19)$ 占用，而不会被 $(3, 4)$、$(5, 6)$、$(7, 8)$、$(9, 10)$ 这 $4$ 架飞机先后使用。

**【数据范围】**

对于 $20 \%$ 的数据，$n \le 100$，$m_1 + m_2 \le 100$。
对于 $40 \%$ 的数据，$n \le 5000$，$m_1 + m_2 \le 5000$。
对于 $100 \%$ 的数据，$1 \le n \le {10}^5$，$m_1, m_2 \ge 1$，$m_1 + m_2 \le {10}^5$，所有 $a_{1, i}, b_{1, i}, a_{2, i}, b_{2, i}$ 为数值不超过 ${10}^8$ 的互不相同的正整数，且保证对于每个 $i \in [1, m_1]$，都有 $a_{1, i} < b_{1, i}$，以及对于每个 $i \in [1, m_2]$，都有 $a_{2, i} < b_{2, i}$。

【感谢 hack 数据提供】

- [xingxuxin](/user/393378)。
- [cyslngsul](/user/126765)。


title: [CSP-S 2021] 括号序列

description:
小 w 在赛场上遇到了这样一个题：一个长度为 $n$ 且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。

身经百战的小 w 当然一眼就秒了这题，不仅如此，他还觉得一场正式比赛出这么简单的模板题也太小儿科了，于是他把这题进行了加强之后顺手扔给了小 c。

具体而言，小 w 定义“超级括号序列”是由字符 `(`、`)`、`*` 组成的字符串，并且对于某个给定的常数 $k$，给出了“符合规范的超级括号序列”的定义如下：

1. `()`、`(S)` 均是符合规范的超级括号序列，其中 `S` 表示任意一个仅由**不超过** $\bm{k}$ **个**字符 `*` 组成的非空字符串（以下两条规则中的 `S` 均为此含义）；
2. 如果字符串 `A` 和 `B` 均为符合规范的超级括号序列，那么字符串 `AB`、`ASB` 均为符合规范的超级括号序列，其中 `AB` 表示把字符串 `A` 和字符串 `B` 拼接在一起形成的字符串；
3. 如果字符串 `A` 为符合规范的超级括号序列，那么字符串 `(A)`、`(SA)`、`(AS)` 均为符合规范的超级括号序列。
4. 所有符合规范的超级括号序列均可通过上述 3 条规则得到。

例如，若 $k = 3$，则字符串 `((**()*(*))*)(***)` 是符合规范的超级括号序列，但字符串 `*()`、`(*()*)`、`((**))*)`、`(****(*))` 均不是。特别地，空字符串也不被视为符合规范的超级括号序列。

现在给出一个长度为 $n$ 的超级括号序列，其中有一些位置的字符已经确定，另外一些位置的字符尚未确定（用 `?` 表示）。小 w 希望能计算出：有多少种将所有尚未确定的字符一一确定的方法，使得得到的字符串是一个符合规范的超级括号序列？

可怜的小 c 并不会做这道题，于是只好请求你来帮忙。

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

第二行，一个长度为 $n$ 且仅由 `(`、`)`、`*`、`?` 构成的字符串 $S$。

outputFormat: 输出一个非负整数表示答案对 ${10}^9 + 7$ 取模的结果。

samples:
见附件中的 bracket/bracket3.in
见附件中的 bracket/bracket3.ans

samples:
见附件中的 bracket/bracket4.in
见附件中的 bracket/bracket4.ans


title: [CSP-S 2021] 回文

description:
给定正整数 $n$ 和整数序列 $a_1, a_2, \ldots, a_{2 n}$，在这 $2 n$ 个数中，$1, 2, \ldots, n$ 分别各出现恰好 $2$ 次。现在进行 $2 n$ 次操作，目标是创建一个长度同样为 $2 n$ 的序列 $b_1, b_2, \ldots, b_{2 n}$，初始时 $b$ 为空序列，每次可以进行以下两种操作之一：

1. 将序列 $a$ 的开头元素加到 $b$ 的末尾，并从 $a$ 中移除。
2. 将序列 $a$ 的末尾元素加到 $b$ 的末尾，并从 $a$ 中移除。

我们的目的是让 $b$ 成为一个**回文数列**，即令其满足对所有 $1 \le i \le n$，有 $b_i = b_{2 n + 1 - i}$。请你判断该目的是否能达成，如果可以，请输出字典序最小的操作方案，具体在【**输出格式**】中说明。

inputFormat:
每个测试点包含多组测试数据。

输入的第一行，包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行，包含一个正整数 $n$。
第二行，包含 $2 n$ 个用空格隔开的整数 $a_1, a_2, \ldots, a_{2 n}$。

outputFormat:
对每组测试数据输出一行答案。

如果无法生成出回文数列，输出一行 `-1`，否则输出一行一个长度为 $2 n$ 的、由字符 `L` 或 `R` 构成的字符串（不含空格），其中 `L` 表示移除开头元素的操作 1，`R` 表示操作 2。

你需要输出所有方案对应的字符串中字典序最小的一个。

字典序的比较规则如下：长度均为 $2 n$ 的字符串 $s_{1 \sim 2 n}$ 比 $t_{1 \sim 2 n}$ 字典序小，当且仅当存在下标 $1 \le k \le 2 n$ 使得对于每个 $1 \le i < k$ 有 $s_i = t_i$ 且 $s_k < t_k$。

samples:
见附件中的 palin/palin2.in
见附件中的 palin/palin2.ans


title: [CSP-S 2021] 交通规划

description:
给定一个平面上 $n$ 条水平直线和 $m$ 条垂直直线，它们相交形成 $n$ 行 $m$ 列的网格，从上到下第 $r$ 条水平直线和从左到右第 $c$ 条垂直直线之间的交点称为格点 $(r, c)$。网格中任意两个水平或垂直相邻的格点之间的线段称为一条边，每条边有一个非负整数边权。

进行 $T$ 次询问，每次询问形式如下：

给出 $k$（$T$ 次询问的 $k$ 可能不同）个附加点，每个附加点位于一条从网格边缘向外出发的射线上。所有从网格边缘向外出发的射线按左上-右上-右下-左下-左上的顺序依次编号为 $1$ 到 $2 n + 2 m$，如下图：

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

对于每次询问，不同附加点所在的射线互不相同。每个附加点和最近的格点之间的线段也称为一条边，也有非负整数边权（注意，在角上的格点有可能和两个附加点同时相连）。

给定每个附加点的颜色（黑色或者白色），请你将网格内每个格点的颜色染成黑白二者之一，并使得所有两端颜色不同的边的边权和最小。请输出这个最小的边权和。

inputFormat:
第一行，三个正整数 $n, m, T$，分别表示水平、垂直直线的数量，以及询问次数。

接下来 $n - 1$ 行，每行 $m$ 个非负整数。其中第 $i$ 行的第 $j$ 个非负整数 ${x 1}_{i, j}$ 表示 $(i, j)$ 和 $(i + 1, j)$ 间的边权。

接下来 $n$ 行，每行 $m - 1$ 个非负整数。其中第 $i$ 行的第 $j$ 个非负整数 ${x 2}_{i, j}$ 表示 $(i, j)$ 和 $(i, j + 1)$ 间的边权。

接下来依次输入 $T$ 组询问。第 $i$ 组询问开头为一行一个正整数 $k_i$ 表示这次询问附加点的总数。接下来 $k_i$ 行每行三个非负整数。其中第 $j$ 行依次为 ${x 3}_{i, j}, p_{i, j}, t_{i, j}$ 表示第 $j$ 个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色（$0$ 为白色，$1$ 为黑色）。保证同一组询问内 $p_{i, j}$ 互不相同。

每行的多个整数由空格分隔。

outputFormat: 输出 $T$ 行，第 $i$ 行输出一个非负整数，表示第 $i$ 次询问染色之后两端颜色不同的边权和的最小值。

samples:
见附件中的 traffic/traffic2.in
见附件中的 traffic/traffic2.ans

samples:
见附件中的 traffic/traffic3.in
见附件中的 traffic/traffic3.ans

samples:
见附件中的 traffic/traffic4.in
见附件中的 traffic/traffic4.ans

samples:
见附件中的 traffic/traffic5.in
见附件中的 traffic/traffic5.ans


title: 「RdOI R3.5」Mystery

description:
给出一个长度为 $n$ 的单调不降整数数列 $\{a_i\}$ 和一个整数 $k$。

我们定义两个长度均为 $p$ 的序列 $\{x_i\},\{y_i\}$ 的「差异度」$F(x,y,p)=\sum_{i=1}^p |x_i-y_i|$。

现在对于每个整数 $l \in [1,n]$，你都需要构造一个长度为 $l$ 的序列 $\{b_{l,i}\}$。满足对于任意 $1\le i <l$，$b_{l,i+1}\ge b_{l,i}+k$；且 $F(a_{[1\cdots l]},b_l,l)$ 最小。其中 $a_{[1\cdots l]}$ 表示 $\{a_i\}$ 的长度为 $l$ 的前缀，即 $\{a_1,a_2,\cdots,a_l\}$。注意，$b_{l,i}$ 没必要是整数。

inputFormat:
第一行输入两个整数 $n,k$。
第二行输入 $n$ 个整数，代表 $\{a_i\}$。
第三行输入一个整数 $T$，代表答案输出方式。具体解释请参考「输出格式」。

outputFormat:
- 若 $T=0$，则输出 $n$ 个整数，每个整数单独占一行。第 $l$ 行的整数代表 $F(a_{[1\cdots l]},b_l,l)$。
- 若 $T=1$，则你仅需输出一行一个整数，表示 $F(a,b_n,n)$。


title: [JRKSJ R4] risrqnis

background:
![114514](https://cdn.luogu.com.cn/upload/image_hosting/0rezlv6r.png?x-oss-process=image/resize,m_lfit,h_510,w_675)

**本题时间限制较长，请勿滥用评测资源。**

description:
给你一个长度为 $n$ 的序列 $a$，有 $q$ 次操作，初始有 $m$ 个空集 $S$，共有两种操作，如下：

- `1 l r k`，将 $l\sim r$ 加入集合 $S_k$，即 $S_k\gets S_k\cup\{x|l\le x\le r\}$；
- `2 l r k`，查询对于所有 $l\le i\le r$ 的 $a_i$ 中有多少个在集合 $S_k$ 中，即查询 $\displaystyle\sum_{i=l}^r[a_i\in S_k]$。

inputFormat:
输入均为非负整数。

第一行 $3$ 个数 $n,q,m$。\
第二行 $n$ 个数，其中第 $i$ 个数表示 $a_i$。\
接下来 $q$ 行，每行 $4$ 个数表示一次操作。

outputFormat:
输出均为非负整数。

对于每个 `2` 操作，输出一行表示答案。

hint:
### 数据规模
| $\text{Subtask}$ | $n,q\le$ | $m\le$ | 分值 | $\text{Time Limit}$ |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $10^6$ | $1$ | $30$ | $1500\text{ ms}$ |
| $2$ | $5\times 10^3$ | $3\times 10^5$ | $15$ | $1000\text{ ms}$ |
| $3$ | $10^5$ | $10^5$ | $15$ | $1500\text{ ms}$ |
| $4$ | $3\times 10^5$ | $10^9$ | $40$ | $3000\text{ ms}$ |

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

操作 $1$ 中 $1\le l\le r\le 10^9$，操作 $2$ 中 $1\le l\le r\le n$。所有操作中 $1\le k\le m$。

**没有一个 $\text{Subtask}$ 取到所有数据范围的最大值，各个 $\text{Subtask}$ 都有自己的限制。请阅读数据范围表。**

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

深夜，上条当麻的手机响起了收信声。随即，他来到了邮件所写的地方。第七学区的铁桥。

上条到达的时候，发信人早已经等在那了。

「御坂吗……？」

「你忘记的东西。」

她说着丢了什么过来。上条单手接住，发现那是个青娃的手机挂件。他沉入北水洋的时候这东西就应该不见了啊。它用来系到手机上的挂绳当初都粉碎了，现在却换成了其他颜色的绳子。

「好不容易找回来的，别再弄丢了哦。」

「不好意思。」

上条道了声谢，将它再次系到了手机上。

见状，美琴微微一笑。

那是似乎终于把什么东西回归原状而松了一口气的表情。

「我想你这个家伙应该不会一直呆在一个地方的吧…接下来该不会你又要去哪？」

「算是吧。」

上条叹了口气。

「老实说虽然我一副淡定的表情，但实际上我也对究竟发生了什么一头雾水，只知道元凶的名字而已。不过这场骚动已经波及到了学园都市，而正在追查学园都市的我也被卷入其中，被我追查的学园都市同样被卷入……所以我也没办法置之不理了。」

美琴找他似乎就只是为了送挂饰而已。上条将手机放进了口袋。

既然没有了话题，那也只能分别了。

「再见了。」上条说道。

转身背对着美琴，准备离开铁桥，

准备离开这个由科学常识构筑的学园都市，大步迈向外面的领域，而少年的手，却被美琴抓住了。

确确实实地，紧紧拉住想要飘然离开的少年。

在静止的上条耳边，传来了美琴的声音。

「但，这次你不会是一个人了。」

tags: 珂朵莉树,颜色段均摊,ODT


title: [JRKSJ R3] 琴琴的树

description:
琴琴有一棵二叉树，满足：

* 该树有无穷多个结点。
* 每个结点都有编号和权值。初始所有结点的权值为 $0$。
* 树根的编号为 $1$。
* 若一个结点的编号为 $i$，则该结点的左右儿子的编号分别是 $2i,2i+1$。

琴琴要对树进行共 $m$ 次操作，每次操作是二者之一：

1. 将编号为 $x$ 的结点为根的子树中的每个结点的权值都加 $v$。
2. 求树上编号为 $x$ 的结点到编号为 $y$ 的结点的路径上每个结点的权值和。答案对 $2^{32}$ 取模。

不过琴琴不会直接给出 $x,y$。她再给出一个长度为 $n$ 的 $01$ 序列 $a$，每次给出 $x$ 或 $y$ 时给出一个区间 $[l_x,r_x]$ 或 $[l_y,r_y]$，这个数就是将这个区间视作二进制数的值。

inputFormat:
第一行两个整数 $n,m$。\
第二行一个长度为 $n$ 的字符串表示 $a$。保证字符串中只包含 `0` 和 `1`。\
下面 $m$ 行，每行一个操作编号，然后是操作。操作的格式为：
1. $\ l_x\ r_x\ v$
2. $\ l_x\ r_x\ l_y\ r_y$

outputFormat: 对于每个操作 $2$，每行一个整数表示答案。

hint:
### 样例解释

该树的前四层如图所示：

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

第一个操作：将以 $2$ 为根的子树中的结点权值加上 $5$。\
第二个操作：求 $2\rightarrow 10$ 的路径上的点的权值和。\
第三个操作：将以 $2$ 为根的子树中的结点权值加上 $3$。\
第四个操作：求 $10\rightarrow 1$ 的路径上的点的权值和。\
第五个操作：求 $1\rightarrow 2$ 的路径上的点的权值和。

### 数据规模与约定

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

| $\text{Subtask}$ | $n\le$ | $m\le $ | 分值 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $10$ | $10^3$ | $5$ |
| $2$ | $20$ | $10^5$ | $5$ |
| $3$ | $10^4$ | $10^4$ | $20$ |
| $4$ | $4\times 10^5$ | $4\times 10^5$ | $70$ |

对于 $100\%$ 的数据，$1\le n,m\le 4\times 10^5$，$1\le v \le 10^9$，$1\le l_x\le r_x\le n$，$1\le l_y\le r_y\le n$，保证 $x,y\ne 0$。


title: [JRKSJ R6] Dedicatus545

description:
对于字符串 $x,y$，定义 $w(x,y)$ 为 $x$ 在 $y$ 中的出现次数。

Index 给了你 $n$ 个字符串 $s_{1\dots n}$，$m$ 次询问，每次询问给定 $l,r,k$，求 $\max_{i=l}^r w(s_i,s_k)$。

inputFormat:
第一行两个整数 $n,m$。\
下面 $n$ 行，每行一个只包含小写字母的字符串表示 $s_{1\dots n}$\
下面 $m$ 行，每行三个整数 $l,r,k$ 表示询问。

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

samples:
6 3
dedicatus
a
misaka
mikoto
mi
aaa
1 5 6
1 2 4
1 5 4


title: [UESTCPC 2024] 饮料

description:
有一个果汁机，每分钟可以制作一杯任意体积的果汁。

有 $n$ 个人排成一队。第 $i$ 个人将在第 $t_i$ 分钟走到果汁机前，并拿走当前已经制作的果汁中体积最大的一杯。第 $i$ 个人拿到体积大于等于 $a_i$ 的果汁就会满意。如果此时没有果汁，则第 $i$ 个人也会不满意。

问是否能够让所有人满意。如果是，输出让所有人满意所需的果汁体积之和的最小值。

inputFormat:
第一行一个整数 $n$ $(1\leq n\leq 2 \times 10^5)$，表示队伍中人的数量。

接下来一行 $n$ 个整数 $t_1,t_2,\ldots,t_n$ $(1\leq t_1\leq t_2\leq\ldots\leq t_n\leq 10^9)$，其中 $t_i$ 表示第 $i$ 个人到果汁机前的时间。如果两个人的到达时间相同，则按题目给出的顺序从左到右决定先后。

接下来一行 $n$ 个整数 $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq 10^9)$，其中 $a_i$ 表示第 $i$ 个人对果汁的体积要求。

outputFormat:
如果不能令所有人满意，输出 $-1$。

否则输出一行一个整数，表示所需的最小体积和。


title: [COCI2021-2022#1] Ljeto

description:
有两支四人队伍，菠萝和蓝莓，在玩水枪。

我们将会给定游戏的具体信息，共 $n$ 条，信息形如在 $t_i$ 秒，玩家 $a_i$ 打到了玩家 $b_i$，对于一个玩家 $i$，如果 $1\le i\le 4$，那么他在菠萝队，否则他在蓝莓队，每打到一下加 $100$ 分。

定义一次双喷为，在 $10$ 秒之内，一名队员**连续**打到对面队伍的队员，设这名队员第一次命中是在第 $t_f$ 秒，则第二次命中需要在第 $[t_f+1,t_f+10]$ 秒内，一次双喷可以为队伍增加 $50$ 分，可以连续触发双喷。

试求出两支队伍的得分。

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

接下来 $n$ 行，一行三个整数 $t_i,a_i,b_i$。
保证所有 $t_i$ 互不相同，并且按升序输入。

outputFormat: 输出一行两个整数，分别表示两支队伍的得分。

hint:
#### 数据范围
对于全部数据，$1\le n\le 100$，$0\le t_i\le 10^3$，$\forall 1\le i< n,t_i<t_{i+1}$，$1\le a_i,b_i\le 8$，玩家 $a_i$ 与玩家 $b_i$ 不属于同一支队伍。

| Subtask | 特殊限制 | 分值 |
| :---------: | :---------: | :----------: |
| $1$ | $n\le 3$ | $10$ |
| $2$ | 不存在双喷 | $15$ |
| $3$ | 无特殊限制 | $25$ |

#### 说明
**本题总分 $50$ 分。**

本题译自 [Croatian Open Competition in Informatics 2021/2022](https://hsin.hr/coci/archive/2021_2022) [Contest #1](https://hsin.hr/coci/archive/2021_2022/contest1_tasks.pdf) T1 Ljeto。


title: [COCI2021-2022#1] Kamenčići

description:
Alice 和 Bob 又在玩游戏。

在他们面前有 $n$ 块石头排成一行，石头有红和蓝两种颜色。

Alice 先手，每次每人从两端选择一端取出一块石头，谁先取出 $k$ 块红色石头谁输掉。

假设 Alice 和 Bob 都是绝顶聪明的，求出最后谁获胜。

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

接下来一行一个长度为 $n$ 的字符串，仅由 `C` 和 `P` 组成，`C` 表示红色石头，`P` 表示蓝色石头。

outputFormat: 如果 Alice 必胜，输出 `DA`，否则输出 `NE`。

hint:
#### 数据范围
对于全部数据，$1\le k<n\le 350$，红色石头至少出现 $2k-1$ 次。

| Subtask | 特殊限制 | 分值 |
| :----------: | :--------: | :-------: |
| $1$ | $n\le 20$ | $10$ |
| $2$ | $n\le 50$ | $20$ |
| $3$ | 无特殊限制 | $40$ |

#### 说明
**本题总分 $70$ 分。**

本题译自 [Croatian Open Competition in Informatics 2021/2022](https://hsin.hr/coci/archive/2021_2012) [Contest #1](https://hsin.hr/coci/archive/2021_2022/contest1_tasks.pdf) T2 Kamenčići。


title: 『JROI-4』Sunset

background:
写不出优美的文字，索性不放背景了。【背景待填充】

> 由于这只是个 C，出题人打算良心点，于是加了几个 $0$（指交互次数）（确信）——验题人注。

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

落日可以抽象成一个序列 $\{a_n\}$.

$\{a_n\}$ 是一个 $1\sim n$ 的排列。

你还有一个数列 $\{d_n\}$，为**当前** $a$ 数列的前缀最大值。

换言之，
$$d_i=\max_{j=1}^i \{a_j\}$$

注意：根据前文的定义，$\{d_n\}$ 可能随着 $\{a_n\}$ 数列的改变而改变。

您可以进行两种不同的操作：

- 指定一个 $i$，询问对于当前的 $a$ 数列， $d_{1\sim i}$ 中有几个不同的值。
- 指定一个 $i$，使得 $a_i\leftarrow 0$.

请使用不超过 $5500$ 次操作求出**原排列**。

**保证交互库是静态的，即交互库不会在交互过程中改变 $a$ 数列。**

inputFormat:
本题多测，第一行一个整数 $T$，表示测试组数，接下来 $T$ 行每行一个整数 $n$，表示本组数据下数列的长度。

本题使用 IO 交互模式。
### 交互格式
- `? 1 i` 询问 $d_{1\sim i}$ 中有几个不同的值，交互库会返回一个正整数 $x$ 表示答案。

- `? 2 i` 使 $a_i=0$。

- `! a1 a2 a3 ... an` 输出答案。

请注意：在每组数据中，请保证前两种操作的次数总和不超过 $5500$。

需要注意的是，在每一次操作后，需要调用以下函数刷新缓存：

- 对于 C/C++：`fflush(stdout);`
- 对于 C++：`std::cout << std::flush;`
- 对于 Java：`System.out.flush();`
- 对于 Python：`stdout.flush();`
- 对于 Pascal：`flush(output);`

对于其他语言，请自行查阅对应语言的帮助文档。

outputFormat: 见「交互格式」。

hint:
**样例仅供理解交互过程，可能不符合逻辑。**

【样例解释】

初始的序列 $a$ 为 `1 2 3`，$d$ 为 `1 2 3`.

在对交互库输出了形如 `? 2 2` 的命令后，序列 $a$ 变为 `1 0 3`，$d$ 变为 `1 1 3`，此时 $d_1\sim d_3$ 中有 $2$ 种不同的值，分别是 $1,3$.

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

可供选手参考的资料：[OI Wiki-交互题](https://oi-wiki.org/contest/interaction/) **|** [猜数（IO交互版）
](https://www.luogu.com.cn/problem/P1733)

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

## 数据范围
- 对于 $10\%$ 的数据，$T=1$；
- 对于 $30\%$ 的数据，$n\le 70$；
- 对于另外 $20\%$ 的数据，保证数列 $a$ 随机生成；
- 对于全部数据：$T \leq 10,1\leq n\leq 500$。


title: Easy Strings Merging

description: 给定 $n$ 个 01 串，每次你可以从某个串开头移除一个字符并把它加入一个新串 $S$ 的末尾。最大化 $S$ 中相邻两个字符相同的对数。

inputFormat:
第一行一个正整数 $n$ 表示串的个数。

接下来 $n$ 行，每行一个 01 字符串。

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


title: [COCI2014-2015#6] PAPRIKA

description:
厨师 Marin 准备用 $n$ 个辣椒制作菜品。

他决定用所有年龄不超过 $x$ 天的辣椒来制作菜品 A，用其他的所有辣椒制作菜品 B。

每个辣椒都有自己的梦想，它们知道自己想要成为 A 还是 B。

但它们不知道 $x$ 的值。为了最大化实现梦想的辣椒数量，它们会采取如下策略进行交换：

- 第 1 个辣椒与第 2 个辣椒比较年龄，然后第 2 个辣椒与第 3 个辣椒比较年龄，依此类推，直到第 $n-1$ 和第 $n$ 个辣椒比较年龄。
- 若当前比较二者的编号为 $i,j$，其中**当前年龄**较大的辣椒想成为菜品 A，**当前年龄**较小的辣椒想成为菜品 B，则它们会交换年龄。$^{[1]}$

求出这样操作后实现梦想的辣椒数量。

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

接下来 $n$ 行，每行两个整数 $a_i,b_i$，分别表示第 $i$ 个辣椒的年龄与梦想。

- 若 $b_i=1$，则表示第 $i$ 个辣椒想成为菜品 A。
- 若 $b_i=0$，则表示第 $i$ 个辣椒想成为菜品 B。

**根据这种定义，「题目描述」中 $^\textbf{[1]}$ 更加严谨的表述为：**\
两个辣椒 $i,j$ 会交换年龄当且仅当 $a_i>a_j$ 且 $b_i=1$ 且 $b_j=0$。

outputFormat: 仅一行一个整数，即实现梦想的辣椒数量。

hint:
#### 样例 1 说明

没有辣椒想成为菜品 A。

#### 样例 2 说明

每对辣椒都交换了年龄。

#### 数据规模与约定

对于 $100\%$ 的数据，有 $1\le n,x,a_i\le 10^3$，$b_i\in\{0,1\}$。

#### 说明

按原题配置，满分 50 分。

译自 **[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/)** [Contest #6](https://hsin.hr/coci/archive/2014_2015/contest6_tasks.pdf) Task A _**PAPRIKA**_。


title: [COCI2014-2015#6] NIKO

background: 2018 年，俄罗斯，第 21 届世界杯。

description:
为了方便，记 $\tt O$ 表示防守球员，$\tt V$ 表示中场球员，$\tt N$ 表示进攻球员。

教练有几个排阵方案 $O-V-N$，其中 $O,V,N$ 分别表示 $\tt O,V,N$ 的数量。当然一定有 $O+V+N=10$。

现在 $m$ 个球员都能担任 $\tt O,V,N$ 中的某几个。教练想知道他的每种排阵方案能否实现。

inputFormat:
第一行一个整数 $n$，表示教练的方案数量。

接下来 $n$ 行，每行三个整数 $O_i,V_i,N_i$，描述每种方案。

接下来一行一个整数 $m$，表示球员数量。

接下来 $m$ 行描述每个球员能担任的角色。

outputFormat:
共 $n$ 行。

- 如果第 $i$ 个方案能被满足，在第 $i$ 行输出 `DA`。
- 否则输出 `NE`。

hint:
#### 样例 1 说明

显然教练只能使用 10-0-0。

#### 样例 2 说明

- 对于 4-4-2，可以派 $1,2,9,10$ 作为 $\tt O$，派 $4,5,6,7$ 作为 $\tt V$，派 $3,8$ 作为 $\tt N$。
- 对于 3-5-2，可以派 $4,9,10$ 作为 $\tt O$，派 $1,2,5,6$ 作为 $\tt V$，派 $3,8$ 作为 $\tt N$。
- 对于 4-3-3，不可能，因为只有 $2$ 个球员能作为 $\tt N$。

#### 数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le 10$，$10\le m\le 22$。

#### 说明

按原题配置，满分 80 分。

译自 **[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/)** [Contest #6](https://hsin.hr/coci/archive/2014_2015/contest6_tasks.pdf) Task B _**NIKO**_。


title: [COCI2014-2015#6] METEOR

description:
你需要复原一幅流星坠落后的照片。

流星坠落前的照片可以被看作是一个 $R\times S$ 的字符矩阵。$\texttt X$ 表示流星的一部分，$\texttt \#$ 表示地面，其他部分是空气，用 $\texttt .$ 表示。所有 $\texttt X$ 是联通的。

注意到流星严格位于地面上方，即存在一行 $\texttt .$ 使得 $\texttt X$ 都在它上方且 $\texttt \#$ 都在它下方。照片最后一行必定都是 $\texttt \#$。

请还原出流星落地后的照片，落地后流星与地面性质都未改变。

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

接下来 $R$ 行每行一个长度为 $S$ 的字符串，表示这个流星坠落前的照片。

outputFormat: 一个 $R\times S$ 的矩阵，表示你还原的流星坠落后的照片。

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

对于 $100\%$ 的数据，有 $3\le R,S\le 3\times 10^3$，字符矩阵中的字符都是 $\texttt{X \# .}$ 中的一种。

#### 说明

按原题配置，满分 100 分。

译自 **[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/)** [Contest #6](https://hsin.hr/coci/archive/2014_2015/contest6_tasks.pdf) Task C _**METEOR**_。


title: [COCI2014-2015#6] KRATKI

background:
我们都非常熟悉「最长单调子序列」问题：

>给定一个长度为 $n$ 的数列，你需要求出它的 LMS（即最长单调子序列）的长度。\
>**请注意**，这里「LMS」是指「递增子序列和递增递减子序列中**更长的一个**」。\
>即需要对 LIS 和 LDS 的长度取最大值。

现在你需要解决一个 LMS 的逆问题。

description:
给定数列的长度 $n$。

你需要构造出一个 $n$ 的排列，使得它的 LMS 长度为 $k$。

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

outputFormat:
如果无解，输出 $\texttt{-1}$。

否则输出一行 $n$ 个整数，即你构造的数列。

**如果存在多组解，输出任意一种。**

hint:
#### 样例 1 说明

$\{1,4,2,3\}$ 的 **LMS** 为 $\{1,2,3\}$，长度为 $3$，符合要求。

#### 数据规模与约定

**本题采用 Special Judge。**

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

#### 说明

按原题配置，满分 120 分。

译自 **[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/)** [Contest #6](https://hsin.hr/coci/archive/2014_2015/contest6_tasks.pdf) Task D _**KRATKI**_。

由于原数据没有一些特殊的数据，本题添加了数据 #11。如果你没通过它，会得到 120 Unaccept。


title: [COCI2014-2015#6] NEO

description:
一个矩阵 $A$ 是「YF 矩阵」当且仅当满足：

- $r,s>1$
- $A_{1,1}+A_{r,s}\le A_{1,s}+A_{r,1}$

$r,s$ 分别表示矩阵 $A$ 的行数和列数。

此外，如果一个矩阵的每个大小至少为 $2\times2$ 的子矩阵都是「YF 矩阵」，我们就说这个矩阵是「Sept 矩阵」。

给定一个矩阵 $A$，你需要求出 $A$ 的含有最多元素的是「Sept 矩阵」的子矩阵所含的元素数量。

inputFormat:
第一行两个整数 $R,S$，分别表示 $A$ 的行数和列数。

接下来 $R$ 行每行 $S$ 个整数，描述矩阵 $A$。

outputFormat:
仅一行，即 $A$ 的最大的是「Sept 矩阵」的子矩阵所含的元素数量。

若这样的子矩阵不存在，输出 $0$。

hint:
#### 样例 3 说明

最大的是「Sept 矩阵」的子矩阵的左上角与右下角坐标分别为 $(3,2),(5,6)$。

#### 数据规模与约定

- 对于 $60\%$ 的数据，有 $R,S\le 350$。
- 对于 $100\%$ 的数据，有 $2\le R,S\le 10^3$，$A_{i,j}\in[-10^6,10^6]$。

#### 说明

按原题配置，满分 140 分。

译自 **[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/)** [Contest #6](https://hsin.hr/coci/archive/2014_2015/contest6_tasks.pdf) Task E _**NEO**_。


title: [COCI2014-2015#6] WTF

description:
你有一个长度为 $n$ 的数组 $\textbf A$，一个值域为 $[1,n-1]$ 的长度为 $n+1$ 的数组 $\textbf{ID}$ 和一个整数 $r$。

我们通过以下伪代码对数组 $\textbf A$ 进行 Warshall-Turing-Fourier 变换 $^\textsf{[1]}$：

```cpp
sum = 0
for i = 1 to n
	index = min{ID[i], ID[i+1]}
	sum = sum + A[index]
	Rorate(A, r)
Change(A)
for i = 1 to n
	index = max{ID[i], ID[i+1]}
	index = index + 1
	sum = sum + A[index]
	Rorate(A, r)
```

其中：
- $\texttt{Change}(\textbf A)$ 表示把数组 $\textbf A$ 中所有元素分别改成它们的相反数。
- $\texttt{Rorate}(\textbf A,r)$ 表示把数组 $\textbf A$ 复制两遍得到数组 $\textbf B$，取 $\textbf B[n-r+1,2n-r]$ 代替数组 $\textbf A$。\
  即**向右旋转** $R$ 个位置。

你已经知道数组 $\textbf A$ 和整数 $r$，但你并不知道数组 $\textbf{ID}$。

你需要求出 WTF 变换后伪代码中 $\text{sum}$ 可能的最大值。

$\textsf{[1]}$：实际上并不存在，当然也可以叫做「Sept 变换」。

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

接下来一行 $n$ 个整数，表示数组 $\textbf A$。

outputFormat:
第一行一个整数，即伪代码中 $\text{sum}$ 可能的最大值。

第二行 $n+1$ 个整数，即使得 $\text{sum}$ 值最大的 $\textbf{ID}$ 数组。

**如果存在多组解，输出任意一种。**

hint:
#### 判分方式

如果输出只有第一行正确，可以得到 $50\%$ 的分数。

**但你必须保证第二行有 $\bm{n+1}$ 个符合要求的数。**

#### 数据规模与约定

**本题采用 Special Judge。**

- 对于 $20\%$ 的数据，有 $n\le 7$。
- 对于 $60\%$ 的数据，有 $n\le 300$。
- 对于 $100\%$ 的数据，有 $2\le n\le 3\times 10^3$，$1\le r\le n$，$\textbf A[i]\in[-10^4,10^4]$。

你需要保证你构造的 $\textbf{ID}[i]\in[1,n-1]$。

#### 说明

按原题配置，满分 160 分。

译自 **[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/)** [Contest #6](https://hsin.hr/coci/archive/2014_2015/contest6_tasks.pdf) Task F _**WTF**_。


title: 故事结局

background:
莲子最终有惊无险的救下了梅莉，虽然梅莉本人似乎对此不以为意，而且还对莲子的观点有很多看法……不过她们很快就和好如初，然后一起度过了一段甜蜜的时光。

但是你既不是莲子也不是梅莉，所以在故事的结尾，你需要做一道数据结构题。

description:
你需要维护一个大小为 $n \times m$ 的矩阵 $A$，初始时其所有元素均为 $0$。题目还给出了一个长度为 $m$ 的序列 $b$。

共有 $q$ 次操作，分为两种：

- `1 l r x v`，对于 $l \le i \le r$，将 $A_{x,i}$ 修改为 $v$。

- `2 l r x y`，查询 $\max\limits_{i=l}^r \max\limits_{j=x}^y (A_{i,j} \times b_j)$。

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

第二行 $m$ 个整数描述序列 $b$。

接下来 $q$ 行，每行描述一次操作，要么格式为 `1 l r x v`，要么格式为 `2 l r x y`。

outputFormat: 对于每次 `2` 操作，输出一行一个整数表示查询的结果。

hint:
### 数据范围

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

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|}\hline
\textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n,q\le } & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\cr\hline
1 & 5 & 100 & - &-\cr\hline
2 & 5 & 5000 & -&- \cr\hline
3 & 20 & 2 \times 10^5 & \mathbf{A}&- \cr\hline
4 & 10 & 2 \times 10^5 & \mathbf{B}&- \cr\hline
5 & 10 & 2\times 10^5 & \mathbf{C}&-  \cr\hline
6 & 10 & 2\times 10^5 & \mathbf{D}&-  \cr\hline
7 & 20 & 2\times 10^5 & -&1,2,3,4,5,6  \cr\hline
8 & 20 & 4\times 10^5 & -&7  \cr\hline
\end{array}
$$

特殊性质 $\mathbf{A}$：保证所有修改在查询之前。\
特殊性质 $\mathbf{B}$：对于修改操作保证 $l=r$。\
特殊性质 $\mathbf{C}$：保证数据随机（随机方法见下）。\
特殊性质 $\mathbf{D}$：保证 $b$ 序列满足所有 $b_i=1$。

对于所有数据满足：$1 \le n,m,q \le 4 \times 10^5$。$1 \le b_i \le 10^9$。

**在所有 $q$ 次操作中，修改操作出现不超过 $\dfrac{q}{4}$ 次。**

对于一操作，$1 \le l \le r \le m,1 \le x \le n,1 \le v \le  10^9$。

对于二操作，$1 \le l \le r \le n,1 \le x \le y \le m$。

数据随机的方式：$n,m,q$ 事先选定，不是随机的。然后均匀随机取 $\left \lfloor \dfrac{q}{4} \right \rfloor$ 次操作为修改操作，剩下的为查询操作。对于操作的所有参数以及 $b$ 序列在其限制范围内等概率随机。


title: [CEOI2021] Diversity

background:
译自 CEOI2021 Day1 T1. [Diversity](https://hsin.hr/ceoi/competition/ceoi2021_day1_tasks.pdf)。

原题时限 7s。由于洛谷时间以及测试点数量限制，这里只选取部分测试点并缩小时限。但保证在标程时限的 1.5 倍。

description:
定义一个序列的 _多样性_ 为其不同的元素个数，一个序列的 _总多样性_ 为其所有子区间的 _多样性_ 的和。

例如，序列 $(1,1,2)$ 的 _多样性_ 为 $2$ ，因为其有两种元素；它的 _总多样性_ 为序列 $(1),(1),(2),(1,1),(1,2),(1,1,2)$ 的 _多样性_ 之和，即 $1+1+1+1+2+2=8$。

给出长为 $N$ 的序列 $\{a _i\}$ 与 $Q$ 个**互相独立**的询问，每个询问给出 $[l,r]$。求将原序列 $[l,r]$ 内的数重排可以得到的该区间最小的 _总多样性_。

inputFormat:
输入第一行包含两个整数 $N$ 和 $Q$，表示序列长度和询问数量。

第二行 $N$ 个整数，表示序列 $\{a_i\}$。

接下来 $Q$ 行，每行两个整数 $l_i,r_i$，表示第 $i$ 次询问的区间。

outputFormat: 输出应包含 $Q$ 行整数，第 $i$ 行的整数表示第 $i$ 个询问的答案。


title: [CEOI2021] L-triominoes

background: 译自 CEOI2021 Day1 T2. [L-triominoes](https://hsin.hr/ceoi/competition/ceoi2021_day1_tasks.pdf)。

description:
给出一个 $H\times W$ 的矩形，我们称其中 $1\times 1$ 的最小矩形为单元格。这个矩形现在有 $K$ 个单元格遗失了。现在请问能否用形如下图的纸片完全覆盖整个矩形。

![捕获3.PNG](https://cdn.luogu.com.cn/upload/image_hosting/ylltjsyr.png)

我们认为一个矩形能被覆盖，当且仅当其所有未遗失的单元格恰好被纸片覆盖一次且没有纸片超出矩形或覆盖在遗失的单元格上。当然，纸片可以垂直或 $90°$ 旋转。

inputFormat:
输入的第一行包含三个非负整数，分别是 $W,H,K$，表示矩形的列数，行数和遗失的单元格数量。

接下来 $K$ 行，每行两个正整数 $x_i,y_i$ 表示一个遗失单元格的坐标。保证给出的单元格坐标互不相同。

outputFormat: 若能刚好覆盖则输出一行一个字符串 `YES`，否则输出一行一个字符串 `NO`。

samples:
2 3 0
YES

hint:
#### 样例解释

对于样例一，如图是一种合法的覆盖：

![捕获4.PNG](https://cdn.luogu.com.cn/upload/image_hosting/xgj9bfbw.png)

对于样例二，你永远无法覆盖 $(1,1)$ 上的单元格。

![捕获5.PNG](https://cdn.luogu.com.cn/upload/image_hosting/hrrzvyjx.png)

对于样例三，如图是一种合法的覆盖：

![捕获6.PNG](https://cdn.luogu.com.cn/upload/image_hosting/p5awynm4.png)

#### 子任务

所有测试点均满足 $1\leq W\leq 13$，$2\leq H\leq 10^9$，$0\leq K\leq 250$，$1\leq x_i\leq W$，$1\leq y_i\leq H$。

| 子任务编号 | 分值 |                    约束                     |
| :--------: | :--: | :-----------------------------------------: |
|    $1$     | $10$ | $2\leq W\leq 13$，$2\leq H\leq 10^3$，$K\leq 250$ |
|    $2$     | $7$  | $2\leq W\leq 13$，$2\leq H\leq 10^9$，$K=0$    |
|    $3$     | $11$ |  $2\leq W\leq3$，$2\leq H\leq 10^9$，$K\leq 250$  |
|    $4$     | $17$ | $4\leq W\leq 6$，$2\leq H\leq 10^9$，$K\leq 250$  |
|    $5$     | $35$ | $7\leq W\leq 13$，$2\leq H\leq 10^9$，$K\leq 250$ |
|    $6$     | $20$ | $2\leq W\leq 13$，$2\leq H\leq 10^9$，$K\leq 250$ |


title: 「Wdsr-3」令人感伤的红雨

background:
秋静叶是在秋季掌管落叶的神明。在秋季即将迎来落幕之时，因她的力量使然，山里会变得火红一片。同时，将红叶变为落叶也是她工作的一环。

秋穰子是在秋季掌管丰收的神明。与秋静叶的职责相反，她掌管着秋天果实的成熟、秋粮的收获。

交织着快乐与忧愁的秋天，怎能让人不有感而发呢？

description:
秋穰子和秋静叶是掌管秋天的神灵，因而控制着田地的收成。具体而言，有 $n$ 块田依次排列，第 $i$ 块田的丰收程度为 $a_i$。秋之姐妹会据此得出一年的年成。

在综合考察了各方面因素后，秋之姐妹得出了收获第 $l$ 块至第 $r$ 块田地可以获得的作物总量 $\Omega(l,r)$。具体定义如下：

$$
\begin{aligned}
\Alpha(l,r)&=\max_{i=l}^r\{i\times[a_i=\max_{j=l}^r\{a_j\}]\}\cr
\Beta(l,r)&=\max_{i=l}^r\{\min_{j=1}^i\{\Alpha(j,i)\}\}-\min_{i=l}^r\{\max_{j=1}^i\{\Alpha(j,i)\}\}\cr
\Omega(l,r)&=\min_{i=l}^r\{\min_{j=i}^r\{|\Beta(i,j)|\}\}
\end{aligned}$$

在**提示说明**部分有相关符号的解释。

---

由于相关因素的影响，田地的丰收程度会发生变化。因此秋之姐妹会对 $a$ 进行 $q$ 次操作：

1. 形如 $\colorbox{f0f0f0}{\verb!1 x y!}$，表示让 $a_1,a_{2},a_{3},\cdots ,a_x$ **分别加上** $y$。
2. 形如 $\colorbox{f0f0f0}{\verb!2 l r!}$，表示询问 $\Omega(l,r)$ 的值。

inputFormat:
- 第一行有两个正整数 $n,q$，分别表示田地总数、操作次数。
- 接下来一行有 $n$ 个整数，表示每块田地的丰收程度。
- 接下来 $q$ 行，第一个数字 $op$ 表示该操作的种类。
  - 如果 $op=1$，那么接下来会有两个整数 $x,y$，含义如题意所示。
  - 如果 $op=2$，那么接下来会有两个正整数 $l,r$，含义如题意所示。

outputFormat: - 输出若干行。对于每一个操作 $2$，输出对应的结果。

hint:
样例 $3$ 见下发的附件 $\textbf{\textit{sequence3.in}}/\textbf{\textit{sequence3.ans}}$。

#### 数据范围及约定

$$
\def{\arraystretch}{1.5}
\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n,q\le} & \textbf{特殊性质} & \textbf{分值}\cr\hline
1 & 100 & - & 10\cr\hline
2 & 5\times 10^3 & - &15\cr\hline
3 & 10^5 & \text{A} &10\cr\hline
4 & 10^5 & \text{B} &5\cr\hline
5 & 10^5 & - &30\cr\hline
6 & 6\times 10^6 & - & 30\cr\hline
\end{array}
$$

**特殊性质** $\textbf{A}$：保证对于任意的 $i\in[1,n-1]$，都有 $a_i<a_{i+1}$。
**特殊性质** $\textbf{B}$：保证没有操作 $1$。

对于全部数据，保证 $1 \leq n,q \leq 6\times10^6$，$a_i,y_i\in[0,10^9]$，$1\le x_i\le n$，$1\le l_i\le r_i \le n$。

#### 符号解释

- $[P]$ 是艾弗森括号，其中 $P$ 是一个条件。如果 $P$ 为真，则该式子的值为 $1$；否则为 $0$。也就是说，
$$[P]=\begin{cases}1 & \text{$P$ 为真}\cr 0 & \text{$P$ 为假}\end{cases}$$
- $\min\limits_{i=l}^r\{P\}$ 表示当 $i$ 取 $l,l+1,l+2,\cdots,r$ 时，表达式 $P$ 的取值的最小值；同理定义了 $\max\limits_{i=l}^r\{P\}$。

#### 提示

本题输入输出量较大，请注意常数因子的影响。


title: 「Wdsr-3」永远与须臾的走廊

background:
永远亭是迷途森林里的不可思议的屋子。

为了躲避月之使者的到来，也是为了防御，永远亭内被布下了一条无尽的长廊。困在其中的对手无法触及到真实，陷入到永远与须臾的陷阱里去。

不过，无尽的长廊 $S$ 毕竟只是单一有限走廊 $S_0$ 的无限循环，其本质是永远亭的主人蓬莱山辉夜及八意永琳设下的圈套。正因该长廊是通过辉夜的能力实现的，因此辉夜可以通过修改该「有限长的」走廊 $S_0$，进而作用于「无限长的」长廊 $S$。这意味着有限的修改可以创造出无限的变动。

光秃秃的长廊显得单调，也难以起到掩人耳目的目的。辉夜决定在长廊上绘制象征着月初的「上弦月」和象征着月末的「下弦月」，以达到图案交错重叠的目的。为了方便起见，「上弦月」可以被近似认为是左括号，而「下弦月」可以被近似认为是右括号。作为优雅的月之都的公主，当然会有不少条条框框——轮到你帮助辉夜满足她的要求了。

description:
辉夜希望创造一个无限长的括号序列 $S$ 作为永远亭长廊的绘制图案，它由一个长度为 $n$ 的括号序列 $S_0$ 不断重复而成。

我们称一个括号序列 $T$ 是合法的，当且仅当它可以由以下方式生成：

- $\verb!()!$ 是一个合法的括号序列。
- 如果 $A$ 是合法括号序列，那么 $\verb!(!A\verb!)!$ 同样是一个合法括号序列。
- 如果 $A,B$ 都是合法括号序列，那么 $AB$（即 $A,B$ 拼接）同样是一个合法括号序列。

例如，$\verb!(()())!,\verb!()()!,\verb!((()())())!$ 都是合法括号序列；而 $\verb!)(!,\verb!(()!,\verb!())(()!$ 均不是合法括号序列。

现在辉夜已经确定了 $S_0$ 当中一部分的符号。你需要求出，「在剩下来的单元上绘制括号，使得这条无限长的长廊上可以找到**无限长的**合法括号序列」的方案数。两种方案不同仅当两种方案中有至少一个位置的 `?` 被替换成了不同的字符。输出它对 $998,244,353$（一个大质数）取模后的结果。

inputFormat:
- 第一行有一个正整数 $n$，表示单元总数。
- 接下来一行有 $n$ 个字符。若第 $i$ 个字符是 $\verb!(!$ 或者 $\verb!)!$，则表示第 $i$ 个单元上绘制的括号已经被辉夜所指定；否则若第 $i$ 个字符是 $\verb!?!$，则表示该位置尚未被确定。

outputFormat: - 共一行一个整数。表示所有方案数对 $998,244,353$ 取模后的结果。

hint:
#### 样例 1 解释

符合条件的方案共有三种：$\verb!(())!$、$\verb!()()!$ 和 $\verb!())(!$。

- 第一种方案，$\overbrace{\text{\tt\textcolor{red}{(())}\textcolor{blue}{(())}\texttt{...}\textcolor{red}{(())}\textcolor{blue}{(())}}}^{\text{无穷个}}$ 可以找到无限长的合法括号序列。
- 第二种方案，$\overbrace{\text{\tt\textcolor{red}{()()}\textcolor{blue}{()()}\texttt{...}\textcolor{red}{()()}\textcolor{blue}{()()}}}^{\text{无穷个}}$ 同样可以找到无限长的合法括号序列。
- 第三种方案，$\text{\tt\textcolor{red}{())}}\overbrace{\text{\tt\textcolor{red}{(}\textcolor{blue}{())(}\texttt{...}\textcolor{red}{())(}\textcolor{blue}{())}}}^{\text{无穷个}}\text{\tt\textcolor{blue}{(}}$ 仍然可以找到无穷长的括号序列。

可以证明，不存在其他方案。

#### 数据范围及约定

$$
\def{\arraystretch}{1.5}
\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le } & \textbf{特殊性质} & \textbf{分值} \cr\hline
1 & 20 & - & 20 \cr\hline
2 & 10^5 & \text{A} & 10 \cr\hline
3 & 10^5 & \text{B} & 10 \cr\hline
4 & 10^5 & - & 60 \cr\hline
\end{array}
$$

**特殊性质** $\textbf{A}$：保证字符串里仅出现 $\verb!(!$ 和 $\verb!)!$。
**特殊性质** $\textbf{B}$：保证字符串里仅出现 $\verb!?!$。

对于全部数据，满足 $1\le n\le 10^5$，且字符串里仅出现 $\verb!(!,\verb!)!,\verb!?!$ 三种字符。


title: 「Wdsr-3」船往低处流

background:
村纱水密是控制着圣辇船的船长。因为是一生和船相伴的船幽灵，因此对船只非常感兴趣。正因为这样的爱好，村纱有一大堆船模。

由于间歇泉的喷发，间歇泉的周围出现了一个汇聚了多方水流的大水坑。不同的水流交错，形成了大大小小的水道。只需要把船模放在某个位置，它就会顺着水流流动。根据物理原理，船自然会从高处流向低处。由于水坑由四处的水汇集而成，因此水坑的中央地势最低；随着到中央距离的增加，地势不断增加。

村纱发现，当她选定了两个位置放下船模后，它们会在某个水流的交汇处发生碰撞。村纱关心碰撞发生的位置。容易发现，第一个可能会产生碰撞的位置，就是在树形结构上这两个选定的点的最近公共祖先。

当然了，由于间歇泉并不稳定，因此水池中央的位置可能会不断变化，地势也不断变化，但是水道并不会发生任何改变。村纱给每个交汇处标上了一个数值「危险程度」，表示两个船模在此处碰撞可能会发生的危险的大小。村纱放置船模的位置也是随机的。

不过由于水坑实在是太大，水坑中央又不断变化，因此只关心船模的村纱被绕晕了。她迫切地想知道在水坑处玩船模产生的威胁，因此希望你帮她计算。

description:
这些水道形成了一棵以 $1$ 为根的节点数为 $n$ 的树形结构 $T$。每个节点上有一个点权 $w_i$，表示它的危险程度。现做出如下定义：

- **最近公共祖先**：在一棵以 $r$ 为根的有根树上，两个节点 $u,v$ 的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个，记作 $\operatorname{lca}(r,u,v)$。
- **子树**：树 $T$ 上，删掉节点 $u$ 与父亲相连的边后，该结点所在的子图记为子树 $T_u$。特别地，$T$ 本身可以认为是以 $1$ 为根节点的子树 $T_1$。
- **危险值**：对于 $T_u$ 而言，它的危险值被定义为：

$$\mathrm{LCAS}(u)=\sum_{i\in T_u}\sum_{j\in T_u}\sum_{k\in T_u,k<j} w_{\operatorname{lca}(i,j,k)}$$

现在给出 $T$，希望你对于 $i=1,2,\cdots n$，求出 $\mathrm{LCAS}(i)$。

inputFormat:
- 第一行有一个正整数 $n$，表示节点的个数。
- 第二行有 $n$ 个整数 $w_i$，表示每个结点的危险程度。
- 接下来 $n-1$ 行，每行有两个正整数 $u,v$，描述 $T$ 中的一条边。

outputFormat: - 共 $n$ 行 $n$ 个整数，第 $i$ 个整数表示 $\mathrm{LCAS}(i)$ 的值对 $998,244,353$（一个大质数）取模后的结果。

hint:
#### 样例 1 解释

样例一当中的树如下。红色的是节点，蓝色的是点权。

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

容易发现 $\mathrm{LCAS}(2)=\mathrm{LCAS}(4)=\mathrm{LCAS}(5)=0$。这里说明如何计算 $\mathrm{LCAS}(1)$ 和 $\mathrm{LCAS}(3)$。首先说明 $\mathrm{LCAS}(3)$：

- 以 $3$ 为根，那么有 $\mathrm{lca}(3,3,4)=\mathrm{lca}(3,3,5)=\mathrm{lca}(3,4,5)=3$，这部分的贡献是 $3\times w_3=6$。
- 以 $4$ 为根，那么有 $\mathrm{lca}(4,3,4)=\mathrm{lca}(4,4,5)=4,\mathrm{lca}(4,3,5)=3$，这部分的贡献是 $2\times w_4+1\times w_3=4$。
- 以 $5$ 为根，那么有 $\mathrm{lca}(5,3,5)=\mathrm{lca}(5,4,5)=5,\mathrm{lca}(5,3,4)=3$，这部分的贡献是 $2\times w_5+1\times w_3=8$。

因此，$\mathrm{LCAS}(3)=6+4+8=18$。下面计算 $\mathrm{LCAS}(1)$。

$$
\def\arraystretch{1.2}
\begin{matrix}
\textbf{以 1 为根 }\bm{\mathbf{lca}(1,i,j)} & \textbf{以 2 为根 }\bm{\mathbf{lca}(2,i,j)}\cr
\begin{array}{c||c|c|c|c|c}\hline
& 1 & 2 & 3 & 4 & 5 \cr\hline\hline
1 & - & - & - & - &- \cr\hline
2 & 1 & - & - & - &- \cr\hline
3 & 1 & 1 & - & - &- \cr\hline
4 & 1 & 1 & 3 & - &- \cr\hline
5 & 1 & 1 & 3 & 3 &- \cr\hline
\end{array} &
\begin{array}{c||c|c|c|c|c}\hline
& 1 & 2 & 3 & 4 & 5 \cr\hline\hline
1 & - & - & - & - &- \cr\hline
2 & 2 & - & - & - &- \cr\hline
3 & 1 & 2 & - & - &- \cr\hline
4 & 1 & 2 & 3 & - &- \cr\hline
5 & 1 & 2 & 3 & 3 &- \cr\hline
\end{array} \cr[50pt]
\textbf{以 3 为根 }\bm{\mathbf{lca}(3,i,j)} & \textbf{以 4 为根 }\bm{\mathbf{lca}(4,i,j)}\cr
\begin{array}{c||c|c|c|c|c}\hline
& 1 & 2 & 3 & 4 & 5 \cr\hline\hline
1 & - & - & - & - &- \cr\hline
2 & 1 & - & - & - &- \cr\hline
3 & 3 & 3 & - & - &- \cr\hline
4 & 3 & 3 & 3 & - &- \cr\hline
5 & 3 & 3 & 3 & 3 &- \cr\hline
\end{array} &
\begin{array}{c||c|c|c|c|c}\hline
& 1 & 2 & 3 & 4 & 5 \cr\hline\hline
1 & - & - & - & - &- \cr\hline
2 & 1 & - & - & - &- \cr\hline
3 & 3 & 3 & - & - &- \cr\hline
4 & 4 & 4 & 4 & - &- \cr\hline
5 & 3 & 3 & 3 & 4 &- \cr\hline
\end{array}
\end{matrix}\\[10pt]
\textbf{以 5 为根 }\bm{\mathbf{lca}(5,i,j)}\\
\begin{array}{c||c|c|c|c|c}\hline
& 1 & 2 & 3 & 4 & 5 \cr\hline\hline
1 & - & - & - & - &- \cr\hline
2 & 1 & - & - & - &- \cr\hline
3 & 3 & 3 & - & - &- \cr\hline
4 & 3 & 3 & 3 & - &- \cr\hline
5 & 5 & 5 & 5 & 5 &- \cr\hline
\end{array}
$$

容易发现，在上图中，$1$ 出现了 $13$ 次，$2$ 出现了 $4$ 次，$3$ 出现了 $25$ 次，$4$ 出现了 $4$ 次，$5$ 出现了 $4$ 次。因此，$\mathrm{LCAS}(1)=3\times 13+1\times 4+2\times 25+1\times 4+3\times 4=109$。

#### 样例 2 解释

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

我有一个精妙绝伦的方法解释样例 $2$，可惜这里空白太小写不下。

**本题输入量较大。请采用较快的读入方式。**

#### 数据范围及约定

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值}\cr\hline
1 & 100 & - & 20 \cr\hline
2 & 10^3 & - & 25 \cr\hline
3 & 10^5 & \text{A} & 10\cr\hline
4 & 10^5 & \text{B} & 10\cr\hline
5 & 10^6 & - & 35\cr\hline
\end{array}
$$

**特殊性质** $\textbf{A}$：保证第 $i$ 条边为 $u=i$，$v=i+1$。
**特殊性质** $\textbf{B}$：保证第 $i$ 条边为 $u=1$，$v=i+1$。

对于全部数据，保证 $1\le n\le 10^6$，$0\le w_i<998,244,353$。


title: 「Wdoi-2」禁断之门对面，是此世还是彼世

background:
或许是后户之国轻易不与外界联系，或许是神职所限，又或许是性格喜好的原因，摩多罗作为最初建立幻想乡的几位贤者之一，和其他贤者之间的联系并不频繁。其他如八云紫、茨木华扇等贤者均亲身走在幻想乡之中，而摩多罗却置身之外。

耗费神力发动全幻想乡级别的异变，看似规模宏大，其实并未对幻想乡造成真正的伤害，只是让一群笨蛋妖精狂躁了些而已。

谁也不知道门后的秘神心中真正的想法。

description:
给定一场长度为 $n$ 的正整数序列 $a$ 和一个长度为 $m$ 的正整数序列 $b$。

现在蓝根据序列 $a$ 与序列 $b$ 构造了一个 $n$ 行 $m$ 列的正整数矩阵 $A$ 满足 $A_{i,j}=a_ib_j$，你需要构造 $n+1$ 行 $t$ 列的正整数矩阵 $B$ 满足以下条件：

- 矩阵的每个元素取值在 $[1,m]$ 间；
- 矩阵同一行的元素**两两**不相同；
- 矩阵的每列**相邻元素**不同；
- 在所有满足上面三项要求的矩阵中**最小化**下式：
$$f(B)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{t}\sum\limits_{k=\min(B_{i,j},B_{i+1,j})}^{\max(B_{i,j},B_{i+1,j})}A_{i,k}$$

请输出构造出的 $B$ 矩阵的 $f(B)$ 的值模 $10^9+7$ 的结果。

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

接下来一行 $n$ 个整数 $a_1,a_2,\cdots a_n$，含义如题面中所述。

接下来一行 $m$ 个整数 $b_1,b_2,\cdots b_m$，含义如题面中所述。

outputFormat: 输出一行，表示构造出的 $B$ 矩阵的 $f(B)$ 的值模 $10^9+7$ 的结果。

hint:
### 样例解释 1

根据题意，可以构造出矩阵 $A=\begin{bmatrix}54 & 9 \\ 54 & 9 \end{bmatrix}$。

你需要构造出的 $3$ 行 $2$ 列的矩阵 $B=\begin{bmatrix}1 & 2 \\ 2 & 1 \\ 1 & 2 \end{bmatrix}$，此时 $f(B)=252$ 为最小值

可以证明 $f(B)=252$ 为所有情况中，$f(B)$ 的最小值。

### 数据范围及约定

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n \le } & \bm{m \le } & \bm{t \le } & \textbf{特殊性质} & \textbf{分值}\\\hline
1 & 10 & 10 & 10 & - & 5 \\\hline
2 & 100 & 100 & 100 & - & 5 \\\hline
3 & 10^3 & 10^3 & 10^3 & - & 15 \\\hline
4 & 5\times 10^4 & 5\times 10^4 & 5\times 10^4 & - & 30 \\\hline
5 & 5\times 10^5 & 5\times 10^5 & 5\times 10^5 & \textbf{A} & 10 \\\hline
6 & 5\times 10^5 & 5\times 10^5 & 5\times 10^5 & \textbf{B} & 10 \\\hline
7 & 5\times 10^5 & 5\times 10^5 & 5\times 10^5 & - & 25 \\\hline
\end{array}$$

- **特殊性质** $\textbf{A}$：保证 $a_i=1$；
- **特殊性质** $\textbf{B}$：保证 $m=t$。

对于全部数据，保证 $1\le a_i, b_i\le 10^9$，$1\le n, m, t\le 5\times 10^5 $，$t\le m$。保证数据有解。

tags: 凸完全单调性, wqs 二分


title: [CEOI2021] Newspapers

background: 译自 CEOI2021 Day1 T3. [Newspapers](https://hsin.hr/ceoi/competition/ceoi2021_day1_tasks.pdf)。

description:
Ankica 和 Branko 在一张无向连通图上玩追逐游戏，游戏分为若干个回合，每一回合有如下两步：

- **Ankica 猜测 Branko 现在在哪个结点**。具体地，她将猜测 Branko 在某个特定的结点，如果正确，Branko 被抓住，游戏将会结束，否则：
- **Branko 穿过一条边**。换句话说，Branko将移动到一个相邻的结点，注意他**不能**不移动。

给出这张图，请求出 Ankica 是否总能在有限步内抓到 Branko 且不论 Branko 初始位置在哪以及如何移动。

更形式化地，我们把 Ankica 猜测的策略用 $A=(a_1,a_2,\dots,a_k)$ 表示，其中 $a_i$ 代表她第 $i$ 次猜测 Branko 在 $a_i$ 结点。

相似地，我们把 Branko 的移动也用 $B=(b_1,b_2,\dots,b_k)$ 表示，其中 $b_i$ 代表他在第 $i$ 回合前的位置。此外，对于 $B$ 中任意两个相邻的元素 $b_i$ 和 $b_{i+1}$（$1\leq i<k$），$b_i$ 和 $b_{i+1}$ 之间必定有一条边。注意对于 $A$ 没有这样的限制。

我们认为 Ankica 的猜测策略 $A$ 是成功的，当且仅当对于任意合法的 $B$ ，都存在 $i\in[1,k]$ 使得 $a_i=b_i$。

如果存在这样的策略，请输出使得 $k$ 最小的一组策略。

inputFormat:
输入第一行包含两个整数 $N$ 和 $M$，代表这张图的点数和边数。

接下来 $M$ 行两个整数 $u_i$，$v_i$，表示图上有一条连接 $u_i$，$v_i$ 的边。

输入保证图上无重边。

outputFormat:
如果不存在成功的策略 $A$，仅输出一行一个字符串 `NO`。

否则，第一行应输出一个字符串 `YES`。

第二行应输出该策略最小的 $k$。

第三行应包含 $k$ 个整数，其中第 $i$ 个整数表示 $a_i$。

hint:
#### 样例解释1

![捕获1.PNG](https://cdn.luogu.com.cn/upload/image_hosting/kajahhgy.png)

如果 Branko 初始位于 $1$ 号结点，则他会被抓住，否则他必定会移动到 $1$ 号结点，然后被抓住。

#### 样例解释2

![捕获2.PNG](https://cdn.luogu.com.cn/upload/image_hosting/rtcfz96j.png)

若 Branko 初始在环 $(1,2,3)$ 上且不与 $a_1$ 相同，则根据之后的 $a$ 必定能构造出使 $A$ 不合法的 $B$。

#### 子任务

所有测试点均满足 $1\leq N\leq 1000$，$N-1\leq M\leq \frac{N\times (N-1)}{2}$。

各子任务的约束条件如下：

| 子任务编号 | 分值 |                             限制                             |
| :--------: | :--: | :----------------------------------------------------------: |
|     $1$      |  $12$  |                       $1\leq N\leq 20$                       |
|     $2$      |  $8$   | $1\leq N\leq 1000$，$M=N-1$，且每个结点 $u\in[1，N-1]$ 都与 $u+1$ 有边 |
|     $3$      |  $80$  |                      $1\leq N\leq 1000$                      |

#### 评分细则

如果你仅能正确回答第一行，则你将得到该测试点 $50\%$ 的分数。

如果对于所有回答 `YES` 的测试点，你能提供一组 $k$ 非最小但正确的策略，你将得到该测试点 $75\%$ 的分数。注意，你提供的策略不能超过 $5N$ 轮，可以证明，任何一组最优策略都不会超出这个限制。

每个子任务的得分等于该子任务内得分最小的测试点得分。


title: [RC-07] Game Theory

description:
给出长度为 $n$ 的 `01` 序列 $a_{1\sim n}$，**序列中有偶数个 `1`**。NIT 和 TIN 轮流做以下操作，NIT 先手：

- 选择位置 $i\ (1\le i\le n)$，满足区间 $[1,i]$ 中有奇数个 `1`。再选择位置 $j\ (i<j\le n)$。将 $a_i,a_j$ 都取反（即，`0` 变 `1`，`1` 变 `0`）

当整个序列中的所有元素都变为 `0` 时，当前轮到的人就无法操作，他就输了。假设 NIT 和 TIN 都*绝顶*聪明，谁会赢？可以证明，游戏总会结束。

$n$ 可能很大，但序列中 $1$ 的个数不超过 $2\times 10^5$。

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

输入的第一行是数据组数 $T$。

接下来是每组数据的描述。每组数据的第一行是两个正整数 $n,m$，$m$ 为序列中 `1` 的个数，保证 $m$ 是偶数。

接下来一行 $m$ 个**递增**的正整数，描述这些 `1` 的下标，下标从 $1$ 开始。

outputFormat: 对每组数据，输出一行一个字符串 `NIT` 或 `TIN`，表示赢家的名字。

hint:
**样例解释**

第一组数据中，NIT 选择 $i=1,j=3$ 就能把全部位置都变成 0，使得 TIN 无法操作。

第二组数据中，无论 NIT 先手怎么操作，都会剩下恰好两个 1 的位置。TIN 只需要选择这两个剩下的位置，就可以把全部位置都变成 0。

第三组数据中，一种可能的游戏进程如下（注意该进程里，每一步不一定是最优的）：

- NIT 选择 $i=2,j=3$ 并将这两个位置取反。现在
`1` 的位置在 $1,2,7,8$。
- TIN 选择 $i=7,j=9$ 并将这两个位置取反。现在
`1` 的位置在 $1,2,8,9$。
- NIT 选择 $i=1,j=5$ 并将这两个位置取反。现在
`1` 的位置在 $2,5,8,9$。
- TIN 选择 $i=3,j=4$ 并将这两个位置取反。现在
`1` 的位置在 $2,3,4,5,8,9$。
- NIT 选择 $i=4,j=5$ 并将这两个位置取反。现在
`1` 的位置在 $2,3,8,9$。
- TIN 选择 $i=2,j=9$ 并将这两个位置取反。现在
`1` 的位置在 $3,8$。
- NIT 选择 $i=3,j=8$ 并将这两个位置取反。现在序列里没有 `1` 了。
- TIN 无法操作，NIT 获胜。

**数据范围**

对于所有数据，$1\le T\le 10^4$，$1\le n\le 10^{18}$，$2\le m\le 2\times 10^5$，$\sum m\le 10^6$。保证 $m$ 是偶数，保证为 `1` 的下标是递增顺序给出的。

- 子任务 1（$1$ 分）$T\le 10^3$，$n\le 10$。
- 子任务 2（$9$ 分）序列中全是 `1`。
- 子任务 3（$40$ 分）$T\le 100$，$n\le 100$。
- 子任务 4（$10$ 分）$\sum n\le 10^6$。
- 子任务 5（$40$ 分）没有任何附加限制。


title: [COCI2015-2016#4] YODA

background: 很久很久以前，在一个遥远的星系里，一个巨大的整数碰撞正在发生。

description:
当两个整数碰撞时会发生什么？先将数位较少的数前不断添加前导 $0$ 直到和数位较高的数的数位数量相同为止。然后，从两个数的最低位开始，每次将两个数的对应数位进行比较，并删去较小的那个数位（如果这两个数位相等则**不执行任何操作**），不断向高数位执行上述操作，直到最高位为止。此时，将这两个数中没有删去的数位按顺序依次拼接，可以得到两个新数。

例如，对于 $456328$ 和 $284315$ 这两个数，这两个的碰撞过程如下所示：

| $4$ | $\sout{~5~}$ | $6$ | $3$ | $2$ | $8$ |
| :-: | :-: | :-: | :-: | :-: | :-: |
| $\sout{~2~}$ | $8$ | $\sout{~4~}$ | $3$ | $\sout{~1~}$ | $\sout{~5~}$ |

不难看出，碰撞之后得到的两个新数为 $46328$ 和 $83$。

现在给定两个数 $n,m$，请求出这两个数进行碰撞之后分别得到的新数。如果某个数在进行碰撞之后，其数位都已经被删空了，则在输出中输出一行字符串 `YODA`。具体见『输出格式』部分。

inputFormat:
第一行输入一个整数 $n$，表示要进行碰撞的第一个数。
第二行输入一个整数 $m$，表示要进行碰撞的第二个数。

outputFormat:
输出共两行。

第一行中，如果 $n$ 的数位已经删空，则输出一个字符串 `YODA`，否则输出一个整数，表示 $n$ 进行碰撞后得到的新数。
第二行中，如果 $m$ 的数位已经删空，则输出一个字符串 `YODA`，否则输出一个整数，表示 $m$ 进行碰撞后得到的新数。


title: [CoE R5] X 细胞

description:
**题意简述**

**有根树**为一个有向图，该有向图有一个特殊的顶点，称之为**根**，从根出发，存在唯一的有向路径到达图中的任意其他顶点。按照习惯，一般将有根树中的顶点称为**结点**。**子树**为有根树 $T$ 的一个子图且该子图是一棵以 $T$ 中某个结点为根的有根树。在有根树中，如果有一条边从结点 $i$ 出发，到达结点 $j$，则将结点 $i$ 称为结点 $j$ 的**父结点**，将结点 $j$ 称为结点 $i$ 的**子结点**。将有根树中不存在子结点的结点称为**叶结点**。

给定有根树 $T$，第 $i$ 个结点具有权值 $a_i \in \mathbb{Z^+}$ 和 $b_i \in \mathbb{Z^+}$。

令 $T'$ 为 $T$ 的一棵子树，$F_i$ 为 $T$ 中所有以结点 $i$ 为根的子树的集合。

- 定义 $r(T') = \frac {a(T')}{b(T')}$，其中 $a(T') = \sum \limits_{j \in T'}{a_j}$，$b(T') = \sum \limits_{j \in T'}{b_j}$。

- 定义 $T_i$ 为一棵以结点 $i$ 为根的子树，$T_i$ 满足 $r(T_i) = \min \limits_{T' \in F_i}r(T')$ 且具有最多的结点数量。

- 定义 $S(T')$：对于 $T$ 中的某个结点 $j$，令其父结点为 $i$，则 $j \in S(T')$ 当且仅当 $i \in T'$ 但 $j \notin T'$ 。

给定一棵具有 $n$ 个结点的有根树 $T$，令根结点为 $i$，对其执行以下操作：

（$1$）将根结点 $i$ 放入结点集合 $Q$，即初始时置 $Q \leftarrow \{i\}$；

（$2$）任取 $Q$ 中的一个元素，令其为 $j$，确定 $T_j$，对于结点 $k \in S(T_j)$，置 $a_k \leftarrow a_k + \lceil r(T_j) \rceil$；

（$3$）从集合 $Q$ 中删除元素 $j$，并置 $Q \leftarrow Q \cup S(T_j)$；

（$4$）若集合 $Q = \varnothing $，结束操作，否则转步骤（$2$）。

每执行一次步骤（$2$）就会确定一棵 $T$ 的子树，假设在结束操作时一共执行了  $m$ 次步骤（$2$）,令第 $i$ 次执行步骤（$2$）所确定的子树为 $K_i$，最小化以下 $W$ 值：

$$W = 1 \times \lceil r(K_1) \rceil + 2 \times \lceil r(K_2) \rceil + \cdots + m \times \lceil r(K_m) \rceil = \sum_{i = 1}^{m}i \times \lceil r(K_i) \rceil$$

$\mathbb{Z^+}$ 表示全体正整数，$\lceil x \rceil$ 表示不小于 $x$ 的最小整数。

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

**原版题面**

$\text{X}$ 细胞是来自于仙女座星系 $\text{Gamma}$ 行星的一种古老生命形式。

初始时，只有 $1$ 个 $\text{X}$ 细胞，而 $\text{X}$ 细胞可以通过直接分裂来产生后代 $\text{X}$ 细胞。对于某个 $\text{X}$ 细胞 $i$ 来说，如果它产生了一个直接后代 $\text{X}$ 细胞 $j$，则将细胞 $i$ 称为细胞 $j$ 的**母细胞**，将细胞 $j$ 称为 $i$ 的**子细胞**。

注意，母细胞、子细胞的定义不具有传递性。假设细胞 $i$ 产生了一个直接后代细胞 $j$，细胞 $j$ 又产生了一个直接后代细胞 $k$，则将 $j$ 称为 $i$ 的子细胞，$k$ 称为 $j$ 的子细胞，但 $k$ 不是 $i$ 的子细胞。

每个 $\text{X}$ 细胞具有活力值 $h_x$ 和体积 $v_x$，为了研究的方便，人们为 $\text{X}$ 细胞定义了**变异指数**

$$d_x = \frac{h_x}{v_x}$$

该指数用于衡量 $\text{X}$ 细胞对环境的适应性，变异指数越低，细胞存活的概率越高。

人们发现，当 $\text{X}$ 细胞受到特定的外界刺激后，它会激活并开始一种被人们称为**同化**的过程来转变为一个 $\text{Z}$ 细胞。在同化过程开始前，激活的 $\text{X}$ 细胞会改变自身状态成为一个 $\text{Y}$ 细胞，$\text{Y}$ 细胞会不断吸收它的子细胞并进行融合，使得该子细胞成为 $\text{Y}$ 细胞的一部分。

在融合后，$\text{Y}$ 细胞的活力值和体积为融合前的细胞活力值和体积的加和。也就是说，假设有 $n$ 个细胞经过融合成为一个 $\text{Y}$ 细胞，这 $n$ 个细胞的活力值和体积分别为 $h_1$，$h_2$，…，$h_n$ 和 $v_1$，$v_2$，…，$v_n$，则融合完成后，该 $\text{Y}$ 细胞的活力值 $h_y = \sum_{i=1}^{n}h_i$，体积 $v_y = \sum_{i=1}^{n}v_i$，变异指数 $d_y = \frac{h_y}{v_y}$。

在同化过程中，$\text{Y}$ 细胞会遵循以下原则：

- 如果某个子细胞 $j$ 的母细胞 $i$ 尚未被同化，则该子细胞 $j$ 不会被同化。
- 能够使得 $\text{Y}$ 细胞变异指数尽可能地小且同化尽可能多的细胞。

当 $\text{Y}$ 细胞无法再同化更多的细胞时，它会停止同化过程，转变为一个 $\text{Z}$ 细胞并释放信息素（状态转变前后，细胞的活力值和体积不变）。该信息素会产生以下作用：令生成的 $\text{Z}$ 细胞的变异指数为 $d_z = \frac{h_z}{v_z}$，如果某个尚未被同化的子细胞 $j$ 的母细胞 $i$ 被该 $\text{Z}$ 细胞同化，则该子细胞 $j$ 的活力值 $h_j$ 增加 $\lceil d_z \rceil$（$\lceil x \rceil$ 表示不小于 $x$ 的最小整数）。

需要注意，在同化过程结束时，$\text{Y}$ 细胞的变异指数要求尽可能地小，但在同化过程中，$\text{Y}$ 细胞的变异指数并不要求时刻保持最小（参见输入 $\#1$）。

研究人员需要通过一种专用设备来产生激活 $\text{X}$ 细胞的特定外界刺激，每次使用该设备都会消耗一定数量的激活剂，消耗的激活剂数量 $c_t$ 使用以下公式进行计算：

$$c_t = t \times \lceil d_z \rceil $$

其中 $t$ 表示使用该设备的次数序号（初始时从 $1$ 开始计数），$d_z$ 表示该次激活最终生成的 $\text{Z}$ 细胞的变异指数。

由于母细胞会分泌信息素使得子细胞无法被激活，只能选择不存在母细胞或者母细胞已经被同化的 $\text{X}$ 细胞作为特定外界刺激的对象，以使其激活并开始同化过程。

给定所有 $\text{X}$ 细胞之间的相互关系及其活力值和体积，鉴于激活剂非常难以制造，现在需要你制定一个最优的 $\text{X}$ 细胞激活顺序方案，使得所有的 $\text{X}$ 细胞均转变为 $\text{Z}$ 细胞且消耗的激活剂数量最少。

你只需要输出该最少值即可。

inputFormat:
输入的第一行是一个整数 $n$，表示 $\text{X}$ 细胞的数量。

接下来的一行，包含 $n - 1$ 个整数，依次表示编号为 $2 \sim n$ 的 $\text{X}$ 细胞的母细胞的编号。

接下来的一行，包含 $n$ 个整数，依次表示编号为 $i$ 的 $\text{X}$ 细胞的活力值 $h_i$。

再接下来的一行，包含 $n$ 个整数，依次表示编号为 $i$ 的 $\text{X}$ 细胞的体积 $v_i$。

初始的 $\text{X}$ 细胞的编号为 $1$。

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

**题意简述所对应的输入格式**：

输入的第一行是一个整数 $n$，表示有根树结点的数量。

接下来的一行，包含 $n - 1$ 个整数，依次表示编号为 $2 \sim n$ 的结点的父结点的编号。

接下来的一行，包含 $n$ 个整数，依次表示编号为 $i$ 的结点的权值 $a_i$。

再接下来的一行，包含 $n$ 个整数，依次表示编号为 $i$ 的结点的权值 $b_i$。

根结点的编号为 $1$。

outputFormat:
输出一个整数，表示使得所有 $\text{X}$ 细胞均转变为 $\text{Z}$ 细胞所需消耗的激活剂数量的最少值。

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

**题意简述所对应的输出格式**：

输出一个整数，表示 $W$ 的最小值。

hint:
**样例说明**

输入 $\#1$：

- 激活细胞 $1$，同化细胞 $2、3$，产生的 $\text{Z}$ 细胞活力值 $h_z = 24$，体积 $v_z = 12$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {24}{12} = 2$。

- $1$ 次激活总共最少需要消耗的激活剂数量为 $c_1 = t \times \lceil d_z \rceil = 1 \times \lceil \frac {24}{12} \rceil = 1 \times 2 = 2$。

- 初始时 $\text{Y}$ 细胞的变异指数为 $5$，当同化细胞 $2$ 后，变异指数为 $6$，当同化细胞 $3$ 后，变异指数变为 $2$。由此可见，在同化过程中，$\text{Y}$ 细胞的变异指数并不是时刻都保持最小，只需在最后停止同化转变为 $\text{Z}$ 细胞时为最小值即可。

输入 $\#2$：

- 激活细胞 $1$，同化细胞 $2$，产生的 $\text{Z}$ 细胞活力值 $h_z = 2 + 2 = 4$，体积 $v_z = 2 + 3 = 5$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {4}{5}$，该次激活消耗的激活剂数量 $c_1 = t \times \lceil d_z \rceil= 1 \times \lceil \frac {4}{5} \rceil = 1 \times 1 = 1$，该 $\text{Z}$ 细胞释放信息素使得细胞 $3$ 的活力值增加 $1$，则细胞 $3$ 的活力值变为 $13$；

- 激活细胞 $3$，未同化其他细胞，产生的 $\text{Z}$ 细胞活力值 $h_z = 13$，体积 $v_z = 4$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {13}{4}$，该次激活消耗的激活剂数量 $c_2 = t \times \lceil d_z \rceil = 2 \times \lceil \frac {13}{4} \rceil= 2 \times 4 = 8$。

- $2$ 次激活总共最少需要消耗的激活剂数量为 $c_1 + c_2 = 1 + 8 = 9$。

输入 $\#3$：

- 激活细胞 $1$，未同化其他细胞，产生的 $\text{Z}$ 细胞活力值 $h_z = 1$，体积 $v_z = 1$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {1}{1} = 1$。总共消耗的激活剂数量 $c_1 = t \times \lceil d_z \rceil = 1 \times \lceil 1 \rceil = 1$。$\text{Z}$ 细胞释放信息素，使得细胞 $2$、$5$ 的活力值各增加 $1$，细胞 $2$、$5$ 的活力值当前为 $8$、$10$。

- 激活细胞 $2$，未同化其他细胞，产生的 $\text{Z}$ 细胞活力值 $h_z = 8$，体积 $v_z = 1$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {8}{1} = 8$。总共消耗的激活剂数量 $c_2 = t \times \lceil d_z \rceil = 2 \times \lceil 8 \rceil = 16$。$\text{Z}$ 细胞释放信息素，使得细胞 $3$、$4$ 的活力值各增加 $8$，细胞 $3$、$4$ 的活力值当前为 $18$、$28$。

- 激活细胞 $4$，未同化其他细胞，产生的 $\text{Z}$ 细胞活力值 $h_z = 28$，体积 $v_z = 1$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {28}{1} = 28$。总共消耗的激活剂数量 $c_3 = t \times \lceil d_z \rceil = 3 \times \lceil 28 \rceil = 84$。

- 激活细胞 $3$，未同化其他细胞，产生的 $\text{Z}$ 细胞活力值 $h_z = 18$，体积 $v_z = 1$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {18}{1} = 18$。总共消耗的激活剂数量 $c_4 = t \times \lceil d_z \rceil = 4 \times \lceil 18 \rceil = 72$。

- 激活细胞 $5$，未同化其他细胞，产生的 $\text{Z}$ 细胞活力值 $h_z = 10$，体积 $v_z = 1$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {10}{1} = 10$。总共消耗的激活剂数量 $c_5 = t \times \lceil d_z \rceil = 5 \times \lceil 10 \rceil = 50$。

- $5$ 次激活总共最少需要消耗的激活剂数量为 $c_1 + c_2 + c_3 + c_4 + c_5 = 1 + 16 + 84 + 72 + 50 = 223$。

输入 $\#4$：

- 激活细胞 $1$，未同化其他细胞，产生的 $\text{Z}$ 细胞变异指数 $d_z = \frac {h_z}{v_z} = \frac {4}{1}$，释放信息素使得细胞 $2、5、9$ 的活力值增加 $4$，消耗激活剂 $c_1 = 1 \times \lceil \frac {4}{1} \rceil = 1 \times 4 = 4$。

- 激活细胞 $5$，同化细胞 $6、7、8$，产生的 $\text{Z}$ 细胞变异指数 $d_z = \frac {h_z}{v_z} = \frac {84}{4}$，消耗激活剂 $c_2 = 2 \times \lceil \frac {84}{4} \rceil = 2 \times 21 = 42$。

- 激活细胞 $9$，同化细胞 $10、11、12$，产生的 $\text{Z}$ 细胞变异指数 $d_z = \frac {h_z}{v_z} = \frac {71}{4}$，消耗激活剂 $c_3 = 3 \times \lceil \frac {71}{4} \rceil = 3 \times 18 = 54$。

- 激活细胞 $2$，同化细胞 $3、4$，产生的 $\text{Z}$ 细胞变异指数 $d_z = \frac {h_z}{v_z} = \frac {17}{3}$，消耗激活剂 $c_4 = 4 \times \lceil \frac {17}{3} \rceil = 4 \times 6 = 24$。

- $4$ 次激活总共最少需要消耗的激活剂数量为 $c_1 + c_2 + c_3 + c_4 = 4 + 42 + 54 + 24 = 124$。

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

**数据范围**

**本题采用捆绑测试。某些子任务的输入文件较大，请使用合适的输入读取方式。**

| 子任务 | 分值 | $n \leq$ | 特殊性质 | 时间限制 | 内存限制 | 子任务依赖 |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| $1$ | $10$ | $20$ |   | $1 \text{ s}$ |  $256 \text{ MB}$ | |
| $2$ | $30$ | $10^3$ |   | $1 \text{ s}$ | $256 \text{ MB}$ | $1$ |
| $3$ | $10$ | $10^5$ |   | $1 \text{ s}$ | $256 \text{ MB}$ | $1 \sim 2$ |
| $4$ | $10$ | $10^6$ | $\text{A}$ | $3 \text{ s}$ | $256 \text{ MB}$ |  |
| $5$ | $20$ | $10^6$ | $\text{B}$ | $1 \text{ s}$ | $320 \text{ MB}$ |  |
| $6$ | $10$ | $10^6$ | $\text{C}$ | $1 \text{ s}$ | $256 \text{ MB}$ |  |
| $7$ | $10$ | $10^6$ |   | $3 \text{ s}$ | $320 \text{ MB}$ | $1 \sim 6$ |

- 特殊性质 $\text{A}$：即给定的有根树所对应的图是星形图。$\forall \  2 \leq i \leq n$，$f_i = 1$。
- 特殊性质 $\text{B}$：给定的有根树所对应的图是有向链。$\forall \ 2 \leq i \leq n$，$f_i = i - 1$。
- 特殊性质 $\text{C}$：数据随机生成。$\forall \ 2 \leq i \leq n$，$f_i$ 是 $[1, i - 1]$ 中随机选取的整数。$h_i, v_i$ 是 $[1, 10^6]$ 中随机选取的整数。

对于 $100 \%$ 的数据，$1 \leq n \leq 10^6$，$1 \leq h_i \leq 10^6$，$1 \leq v_i \leq 10^6$，答案不超过 $10^{18}$。


title: [COCI2015-2016#4] HAN

background:
Han 不想单独学习，所以他邀请他的朋友 Dominik 过来。他们一起学习了一个晚上之后，Dominik 回家了。令他吃惊的是，一名警察拦住了他，认为他**喝醉了**。众所周知，在这种情况下，通过解决一系列精心设计的任务，测试一个人的认知能力，可以证明他是否清醒。如果我们能相信 Dominik，对话将会是这样的——

> 警察：从简单点的问题开始吧……冒泡排序的复杂度是多少？
Dominik：太简单了，$\mathcal O(n^2)$。
警察：很好，下一题。请倒着念英文字母表。
Dominik：太无聊了，$\texttt{zyxwvutsrqponmlkjihgfedcba}$。
警察：你这显然是背的，不算数。再来考你一题吧。想象一下，英文字母表中的从 $\texttt{a}$ 到 $\texttt{z}$ 的所有字母以顺时针顺次排列成一个环。初始时，你从字母 $\texttt{a}$ 开始，顺时针念字母。每念完一个字母，我可以告诉你按照相反方向念字母，或者询问你到目前为止某个字母你念了多少次。准备好了吗？开始！
Dominik：唔……$\texttt{a}$、$\texttt{b}$、$\texttt{c}$……

警察的最后一个问题显然难倒了 Dominik。现在，请你帮助 Dominik 回答这些问题。

description:
具体地，警察在接下来将会发出 $q$ 次命令，每次命令为以下两种命令中的一种：

- $\bf SMJER~n$：在 Dominik 说完第 $n$ 个字母之后，他必须开始按照与当前方向相反的方向念字母。
- $\bf UPIT~n~x$：Dominik 需要回答在他念的前 $n$ 个字母中，字母 $x$ 出现了多少次。

你需要对于每次 $\bf UPIT~n~x$ 命令输出答案。

inputFormat:
第一行一个整数 $q$，表示警察发出的命令数。
随后 $q$ 行，描述 $q$ 次命令。每行先输入一个字符串 $s$ 和一个整数 $n$。如果 $s$ 是 $\bf UPIT$，则在输入完一个整数 $n$ 之后还需要输入一个字符 $x$。

数据保证对于所有 $q$ 次命令，$n$ 严格递增。形式化地说，$\forall i\in [1,q)$，$n_i<n_{i+1}$。

outputFormat: 对于每次 $\bf UPIT~n~x$ 命令，输出一行一个整数，表示在 Dominik 说的前 $n$ 个字母中，字符 $x$ 出现的次数。

samples:
5
UPIT 1 b
UPIT 3 b
SMJER 4
UPIT 7 a
UPIT 10 z

samples:
5
SMJER 1
SMJER 2
SMJER 3
UPIT 5 a
UPIT 7 w

samples:
4
UPIT 100 a
UPIT 200 c
UPIT 300 a
UPIT 400 b

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

Dominik 说的前 $10$ 个字母依次是：$\texttt{a}$，$\texttt{b}$，$\texttt{c}$，$\texttt{d}$，$\texttt{c}$，$\texttt{b}$，$\texttt{a}$，$\texttt{z}$，$\texttt{y}$，$\texttt{x}$。

**【样例 2 解释】**

Dominik 说的前 $7$ 个字母依次是：$\texttt{a}$，$\texttt{z}$，$\texttt{a}$，$\texttt{z}$，$\texttt{y}$，$\texttt{x}$，$\texttt{w}$。

**【数据范围】**

对于 $40\%$ 的数据，保证 $n\leqslant 1000$。
对于 $60\%$ 的数据，保证 $n\leqslant 10^5$。
对于所有数据，$1\leqslant q\leqslant 10^5$，$1\leqslant n\leqslant 10^9$，$x$ 仅包含小写字母。

**【题目来源】**

本题来源自 **_[COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST 4](https://hsin.hr/coci/archive/2015_2016/contest4_tasks.pdf) T2 HAN_**，按照原题数据配置，满分 $80$ 分。

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