title: [SEERC2019] Tree Permutations

description:
有一天，Cool 先生建了一棵 $n$ 个点的树（没有环的无向连通图），他给任一编号 $i > 1$ 的点规定了两个值：$p_i < i$ 代表点 $i$ 的父节点，与 $w_i$ 代表 $i$ 与 $p_i$ 之间的边的边权。点 $1$ 是树根，所以它没有父节点。

你想知道 Cool 先生建的树长啥样，但是 Cool 先生拒绝告诉你，但他给了你一些提示：

他把所有的 $p_i$ 和 $w_i$ 值写成一列，得到了长为 $2 \cdot n - 2$ 的数列 $b$。

$$ b=[p_2, w_2, p_3, w_3, \dots, p_{n-1}, w_{n-1}, p_n, w_n] $$

然后他将其随机打乱，得到了数列 $a$，并将 $a$ 告诉你。

然而只知道数列 $a$ 是无法还原那棵树的，你决定解决一个更难的问题。

定义一个树是 *$k$ 长*的，当且仅当点 $1$ 到点 $n$ 的路径上有恰好 $k$ 条边。

定义一个树是 *$k$ 完美*的，当且仅当这棵树是 *$k$ 长*的且点 $1$ 到点 $n$ 的路径上的边的边权之和是所有 *$k$ 长*的树中最大的。

你的任务是计算出每个 $k$ 值对应的 *$k$ 完美*的树中，点 $1$ 到点 $n$ 的路径上的边的边权之和。如果某个 $k$ 值不存在 *$k$ 完美*的树，则在该位置输出 $-1$。

inputFormat:
第一行包含一个整数 $n \ (2 \leq n \leq 10^5)$，代表树上的节点数。

第二行包含 $2 \cdot n -2$ 个整数 $a_1, a_2, \dots, a_{2n-2} \ (1 \leq a_i \leq n-1)$，代表数列 $a$ 中的数字。

outputFormat: 输出一行，共 $n-1$ 个空格隔开的整数 $w_1, w_2, w_3, \dots, w_{n-1}$，其中 $w_k$ 代表 *$k$ 完美*的树中点 $1$ 到点 $n$ 的路径上的边的边权之和。如果不存在 *$i$ 长*的树，则 $w_i=-1$。

hint:
第一个样例中，*$1$ 完美*的树由数列 $[1, 2, 1, 2]$ 构成（即，$p_2=1, w_2=2, p_3=1, w_3=2$），*$2$ 完美*的树由数列 $[1, 2, 2, 1]$ 构成（即，$p_2=1, w_2=2, p_3=2, w_3=1$）。以下是这两棵树的图形（点 $1$ 到点 $n$ 的路径上的边都为粗线）。

![样例1](https://cdn.luogu.com.cn/upload/image_hosting/lgpg0jne.png)

第二个样例中，不存在能通过重排 $a$ 构造出的 *$k$ 完美*的树。

第三个样例中，只有 *$4$ 完美*的和 *$5$ 完美*的树可以被构造出。它们分别由数列 $[1, 4, 2, 4, 3, 4, 4, 4, 4, 5]$ 和 $[1, 4,2, 4, 3, 4, 4, 4, 5, 4]$ 构成。以下是这两棵树的图形。

![样例3](https://cdn.luogu.com.cn/upload/image_hosting/rz04b4ro.png)


title: [SEERC2019] Absolute Game

type: P

description:
Alice 和 Bob 在玩一个游戏。Alice 有一个包含 $n$ 个整数的数列 $a$，Bob 有一个包含 $n$ 个整数的数列 $b$。每一回合中，玩家需要从他的数列中删去一个数字。玩家轮流进行回合，Alice 先手。

当两个数列中都只剩下一个数字的时候，游戏结束。令 Alice 的数列剩下的数字为 $x$，Bob 的数列剩下的数字为 $y$。Alice 想要最大化 $x$ 与 $y$ 之差的绝对值，而 Bob 想最小化这个值。两个玩家都以最优策略游戏。

请算出游戏结束时的结果。

inputFormat:
第一行包含一个整数 $n \ (1 \leq n \leq 1 \ 000)$，代表每个数列中的数字个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n \ (1 \leq a_i \leq 10^9)$，代表 Alice 的数列中的数字。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n \ (1 \leq b_i \leq 10^9)$，代表 Bob 的数列中的数字。

outputFormat: 输出当两个玩家都以最优策略游戏时，$x$ 与 $y$ 之差的绝对值。

hint:
第一个样例中，$x=14, y=10$，因此两个数之差为 $4$。

第二个样例中，两个数列都只剩下一个数字了，因此 $x=14, y=42$。


title: [SEERC2019] Graph and Cycles

description:
有一个 $n$ 个点的无向有边权的完全图，其中 $n$ 是奇数。

定义一个大小为 $k$ 的*环边组*为一个边构成的数组 $[e_1, e_2, \dots, e_k]$，且具有以下性质：

- $k$ 大于 $1$。
- 对于任意 $[1, k]$ 中的整数 $i$，边 $e_i$ 与 $e_{i-1}$ 和 $e_{i+1}$ 都恰好有一个相同的端点（规定 $e_0=e_k, e_{k+1}=e_1$）。

显然一个环边组中的边构成了图上的一个环。

定义一个参数为两条边 $e_1, e_2$ 的函数 $f(e_1, e_2)$，其函数值为两条边中边权的较大值。

定义一个环边组 $C=[e_1, e_2, \dots, e_k]$ 的*价值*为对于任意 $[1, k]$ 中的整数 $i$，$f(e_i, e_{i+1})$ 的值之和（规定 $e_{k+1}=e_1$）。

定义一个图的*环分割*为一组无交集的环边组，且这些环边组的并包含了图上所有的边。定义一个图的环分割的*价值*为其中所有环边组的价值之和。

一个图可能存在多组环分割。给定一个图，你的任务是找到价值最小的环分割并输出该最小价值。

inputFormat:
第一行包含一个整数 $n \ (3 \leq n \leq 999, n \bmod 2 = 1)$，代表图的点数。

接下来的 $\frac{n\cdot (n-1)}{2}$ 行每行包含三个整数 $u, v$ 和 $w \ (1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^9)$，代表点 $u$ 和点 $v$ 间有一条边权为 $w$ 的边。

outputFormat: 输出一个整数，代表给定图的最小价值环分割的价值。


title: [SEERC2019] Stranded Robot

description:
在废弃宇宙飞船的残骸中，有一个机器人。残骸的某处有一个传送机，可以将这个可怜的机器人送至安全的地方。

宇宙飞船不受控制地在各个方向上翻滚。一个邻近的恒星发出的光可以照到残骸上。飞船配备了人工重力发生器。人工重力总是向远离恒星的方向拉机器人，无论飞船的方向如何。

机器人配备了太阳能电池板，必须依赖太阳能才能在残骸上移动。当残骸的一部分挡住了光照，机器人就无法移动了。然而，机器人总是会在移动后将自己固定住，以免被晃走或者掉入宇宙中。

残骸和残骸周围的区域可以用一个大小为 $m \times n \times p$ 的三维坐标空间表示。每个空间中的小方格都可能是残骸的一部分或真空。飞船残骸可能不是连在一起的。

机器人最开始固定在飞船的某一块上。机器人可以决定什么时候移动或什么时候等光照从合适的方向照过来。

形式化地说，重力可以在六个方向上作用于机器人，包括三个坐标轴上各两个方向。当一个格子在重力的反方向上没有残骸遮挡时，这个格子就有光照。当进行移动时，起点和终点都必须同时有光照。

以下是可用的移动方式：（光照从图片所示空间的上方照下；蓝色格子代表机器人；橙色格子代表可能的移动终点）

1. **在平地移动**
   假如机器人固定在某一块上，它可以移动到相邻的块上，这些块必须与起点同高。
   机器人无法斜向移动。终点必须也有光照。
   ![移动1](https://cdn.luogu.com.cn/upload/image_hosting/sf5pxkhr.png)
2. **从高处跳下**
   机器人可以从高处走出一步，然后落下。落下的高度没有限制。
   机器人不能落入宇宙中，也不能落到没有光照的地方。
   ![移动2](https://cdn.luogu.com.cn/upload/image_hosting/8jwv3v8y.png)
3. **掉落**
   假如机器人有光照且悬在空中，它可以掉落下来。这种情况可能会在重力的方向改变后产生。
   机器人不能掉入宇宙中。
   ![移动3](https://cdn.luogu.com.cn/upload/image_hosting/8ei3yfks.png)

机器人的目标是到达传送机的所在地，如果有多种走法，则使用移动次数最少的走法。传送机工作要求机器人必须固定在飞船上。换句话说，机器人必须在某一次移动之后到达传送机的位置上，但掉落时经过它是无法工作的。传送机不会遮住光照或阻挡机器人的移动。

inputFormat:
第一行包含三个整数 $m, n, p \ (1 \leq m, n, p \leq 500)$。

飞船和飞船周围的空间被描述为 $p$ 块。

第 $k$ 块描述了高度为 $k$ 的格子。每块都包含 $n$ 行。

第 $k$ 块的第 $i$ 行包含 $m$ 个字符，描述该格子的情况。令 $a_{ijk}$ 代表第 $j$ 个字符。

- 如果 $a_{ijk}$ 是 `*`，则这个格子是残骸。
- 如果 $a_{ijk}$ 是 `-`，则这个格子是真空。
- 如果 $a_{ijk}$ 是 `R`，则这个格子是机器人。数据保证只有一个格子是机器人，且机器人被固定在一个残骸格子上。
- 如果 $a_{ijk}$ 是 `T`，则这个格子是传送机。数据保证只有一个格子是传送机。

outputFormat: 输出到达传送机处所需的最少移动数。如果无解，输出 $-1$。


title: 【模板】常系数非齐次线性递推

background:
NaCly\_Fish 一到机房，所有做题的人便都看着她笑。有的叫道，“鱼鱼，你怎么又爆零了！”她不回答，对教练说：“要两道数学题，一道数据结构。”便打开电脑。他们又故意的高声嚷道，“你怎么连 exgcd 都写不对了！”......

NaCly\_Fish 自己知道不能和同机房的神仙们谈天，便只好向隔壁初一的说话。有一回对我说道，“你学过 OI 么？”我略略点一点头。他说，“学过 OI，...... 我便考你一考。常系数线性齐次递推，怎样算的？”我想，机房垫底 AFO 的人，也配考我么？便回过脸去，不再理会。NaCly\_Fish 等了许久，很恳切的说道，“不会算罢？…… 我教给你，记着！这算法应该好好记着，将来比赛的时候，做题要用。”我懒懒的答她道，“谁要你教，不是把递推系数写在矩阵第一列，剩下斜着放 $1$，再快速幂么？”NaCly\_Fish 显出极高兴的样子，将两个指头的长指甲敲着课桌，点头说，“对呀对呀！...... 这还有四样求法，你知道么？”......
****
NaCly\_Fish 看见了这题，她根本不会做。
看在她那么菜的份上，请您做了这题，帮帮她吧。

description:
已知递推式：

$$a_n = P(n) + \sum\limits_{i=1}^k f_i \times a_{n-i}$$

其中 $P(x)$ 是一个 $m$ 次多项式。

给定 $f_1,f_2,\dots,f_k$，$a_0,a_1,\dots,a_{k-1}$，和 $P(x)$ 的各项系数，求 $a_n$。
答案对 $998244353$ 取模。

inputFormat:
第一行三个正整数 $n,m,k$。
第二行 $k$ 个整数，表示 $a_0,a_1,\dots,a_{k-1}$。
第三行 $k$ 个整数，表示 $f_1,f_2,\dots,f_k$。
第四行 $m+1$ 个整数，由低到高的表示 $P(x)$ 的系数。

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

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 10^9$，$1\le m,k \le 30000$。
除第一行外，输入的所有数在 $[0,998244353)$ 范围内。

数据有一定梯度。


title: 【模板】BEST 定理 | Which Dreamed It

description:
有 $n$ 个房间，每个房间有若干把钥匙能够打开特定房间的门。

最初你在房间 $1$。每当你到达一个房间，你可以选择该房间的一把钥匙，前往该钥匙对应的房间，并将该钥匙丢到垃圾桶中。

你希望最终回到房间 $1$，且垃圾桶中有所有的钥匙。

你需要求出方案数，答案对 $10^6 + 3$ 取模。两组方案不同，当且仅当使用钥匙的顺序不同。

注意，每把钥匙都是不同的。

原 BZOJ3659。

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

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

对于每组数据：

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行描述房间 $i$：

首先一个数 $s$，表示这个房间的钥匙数目，接下来 $s$ 个数，分别描述每把钥匙能够打开的房间的门。

outputFormat: 对于每组数据，一行一个整数，表示答案对 $10^6+3$ 取模后的值。

hint:
【样例说明】

在第一组样例中，没有钥匙，则方案数为 $1$。

在第二组样例中，你不可能使用第二个房间的钥匙，所以方案数为 $0$。

【数据范围】

对于 $50\%$ 的数据，$n \le 4$，$\sum s \le 30$。

对于 $100\%$ 的数据，$1 \le T \le 15$，$1 \le n \le 100$，$0 \le \sum s \le 3141592$。

2021/5/14 加强 by [SSerxhs](https://www.luogu.com.cn/user/29826)&[滑大稽](https://www.luogu.com.cn/user/203743)


title: [SCOI2004] 文本的输入

description:
人们在输入文本时，除了逐个输入这种方式外，还可以利用剪贴板进行复制，如果打入一个字母需要 $1$ 的时间，将已输入的部分复制进剪贴板需要 $5$ 的时间（`Ctrl`+`A`，`Ctrl`+`C`，再取消全选状态），将剪贴板的内容粘贴出来需要 $2$ 的时间（`Ctrl`+`V`）。

如果我们不关心输入文本的内容，而只关心输入文本的长度，要输入一个长度**不低于** $n$ 的文本最少需要多少时间？

**请注意，数据范围与原题略有不同。**

inputFormat: 一个正整数 $n$，表示文本的长度。

outputFormat: 一个正整数 $t$，表示需要的最短的时间。

hint:
样例解释：先用 $7$ 时间打出 $7$ 个字符，再复制（用去 $5$ 时间），粘贴两次（用去 $4$ 时间），即可用 $16$ 时间打出 $21$ 个字符。

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

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

对于 $100\%$ 的数据，$n\le 4\times 10^4$。


title: 【模板】多项式复合逆

background: 神鱼姐姐太鸽了 qwq

description:
令 $n-1$ 次多项式 $F(x)=\sum\limits _{i=0}^{n-1} a_ix^i$。

给定 $n$ 和 $F(x)$ 的各项系数，要求一个 $n-1$ 次多项式 $G(x)$ 满足：

$$
G(F(x))\equiv x\pmod{x^n}
$$

求 $G(x)$ 的各项系数对 $998244353$ 取模的结果。

保证 $a_0=0$，$a_1\neq 0$。

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

第二行 $n$ 个非负整数 $a_0,a_1,a_2,\ldots,a_{n-1}$，其中 $a_i$ 表示 $F(x)$ 的第 $i$ 项系数。保证 $a_0=0$，$a_1\neq 0$。

outputFormat: 一行 $n$ 个非负整数，第 $i$ 个非负整数表示 $G(x)$ 的第 $i-1$ 项系数。


title: [IOI2019] 景点划分

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

注：本题按照传统题方式进行评测，即，你的程序**需要包含 `main` 函数**。

description:
巴库有 $n$ 处景点，从 $0$ 到 $n-1$ 编号。另外还有 $m$ 条双向道路，从 $0$ 到 $m-1$ 编号。每条道路连接两个不同的景点。经由这些道路，可以在任意两处景点之间往来。

Fatima 打算在三天之内参观完所有这些景点。她已经决定要在第一天参观 $a$ 处景点，第二天参观 $b$ 处景点，第三天参观 $c$ 处景点。因此，她要将 $n$ 处景点划分为三个集合 $A$、$B$ 和 $C$，其规模分别为 $a$、$b$ 和 $c$。每处景点恰好属于其中一个集合，因此有 $a+b+c=n$。

Fatima 想要找到这样的景点划分 $A$、$B$ 和 $C$，使得这三个集合中的至少两个是联通的。一个景点集合 $S$ 被称为是联通的，如果能够经由这些道路在 $S$ 中的任意两处景点之间往来，且不需要经过不在 $S$ 中的景点。如果满足上述要求，则景点的一个划分 $A$、$B$ 和 $C$ 被称为是合法的。

请帮助 Fatima 找到一个合法的景点划分 （给定 $a$、$b$ 和 $c$），或者判断合法的划分不存在。如果存在多个合法的划分，你可以给出其中的任何一个。

**实现细节**

你需要实现下述函数：
`int [] find_split（int n,int a,int b,int c,int [] p,int [] q）`
- $n$：景点的数量。
- $a$、$b$ 和 $c$：集合$A$、$B$ 和 $C$ 的期望规模。
- $p$ 和 $q$：长度为 $m$ 的数组，包含道路的端点。对每个 $i$ （$ 0 \le i \le m-1 $），$p[i]$ 和 $q[i]$ 是由道路 $i$ 连接的两处景点。
- 该函数需要返回一个长度为 $n$ 的数组。记该数组为 $s$。如果不存在合法的划分，$s$ 应当包含 $n$ 个零。否则，对于 $0 \le i \le n-1$，$s[i]$ 应为 $1$、$2$ 或 $3$ 中的一个。以分别表示景点 $i$ 被归到集合 $A$、$B$ 或 $C$

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

第二行，三个正整数 $a$、$b$ 和 $c$。

第 $3+i$ 行 （对于 $ 0 \le i \le m-1 $） 两个正整数 $p[i]$、$q[i]$。

意义见题目描述

outputFormat: 共一行，内容为 `find_split` 所返回的数组。

hint:
**样例说明**

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

一个可能解为 $[1,1,3,1,2,2,3,1,3]$。这个解刻画了这样的划分：$A=\{0,1,3,7\}$，$B=\{4,5\}$，$C=\{2,6,8\}$。集合 $A$ 和 $B$ 是联通的。

**数据范围**

对于 $100\%$ 的数据，
- $3 \le n \le 10^5$。
- $2 \le m \le 2 \times 10^5$。
- $1 \le a,b,c \le n$。
- $a+b+c=n$。
- 每一对景点之间至多有一条道路。
- 经由这些道路，可以在任何两处景点之间往来。
- 对于 $0 \le i \le m-1$，有 $0 \le p[i],q[i] \le n-1$ 和 $p[i] ≠ q[i] $。

**子任务**
1. （$7$ 分） 每处景点至多可做两条道路的端点。
2. （$11$ 分） $a=1$
3. （$22$ 分） $m=n-1$
4. （$24$ 分） $n \le 2500$，$m \le 5000$。
5. （$36$ 分） 没有任何附加限制。


title: [IOI2019] 天桥

description:
Kenan 为沿着巴库大街某一侧的建筑和天桥绘制了一张规划图。规划图中有 $n$ 栋建筑，从 $0$ 到 $n-1$ 编号。还有 $m$ 座天桥，从 $0$ 到 $m-1$ 编号。这张规划图绘制在一张二维平面上，其中建筑和天桥分别是垂直和水平的线段。

第 $i$（$0 \le i \le n-1$） 栋建筑的底部坐落在坐标 （$x[i],0$） 上，建筑的高度为 $h[i]$。因此，它对应一条连接点 （$x[i],0$） 和 （$x[i],h[i]$） 的线段。

第 $j$（$0 \le j \le m-1$） 座天桥的两端分别在第 $l[j]$ 栋建筑和第 $r[j]$ 栋建筑上，并具有正的 $y$ 坐标 $y[j]$。因此，它对应一条连接点 （$x[l[j]],y[j]$） 和 （$x[r[j]],y[j]$） 的线段。

称某座天桥和某栋建筑相交，如果它们有某个公共的点。因此，一座天桥在它的两个端点处与两栋建筑相交，同时还可能在中间和其他建筑相交。

Kenan 想要找出从第 $s$ 栋建筑的底部到第 $g$ 栋建筑的底部的最短路径长度，或者确认这样的路径不存在。在这里行人只能沿着建筑和天桥行走，并且不允许在地面上行走，也就是说不允许沿着 $y$ 坐标为 $0$ 的水平线行走。

行人能够在任意交点从某座天桥走进某栋建筑，或者从某栋建筑走上某座天桥。如果两座天桥的端点之一在同一点上，行人也可以从其中一座天桥走上另一座天桥。

你的任务是帮助 Kenan 回答他的问题。

**实现细节**

你需要实现下列函数。
`int64 min_distance(int[] x,int[] h,int[] l,int[] r,int[] y,int s,int g)`

- $x$ 和 $h$：长度为 $n$ 的整数数组。
- $l$、$r$ 和 $y$：长度为 $m$ 的整数数组。
- $s$ 和 $g$：两个整数。
- 如果从第 $s$ 栋建筑的底部到第 $g$ 栋建筑的底部的最短路径存在，则该函数应该返回最短路径的长度。否则，该函数应该返回`-1`。

outputFormat: 共一行，为函数 `min_distance` 的返回值。

hint:
**样例说明**

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

**限制条件**

- $1 \le n,m \le 10^5$。
- $0 \le x[0] < x[1] < \cdots < x[n-1] \le 10^9$。
- $1 \le h[i] \le 10^9$（对于所有 $0 \le i \le n-1$）。
- $0 \le l[j] \le r[j] \le n-1$（对于所有 $0 \le j \le m-1$）。
- $1 \le y[j] \le \min(h[l[j]],h[r[j]])$（对于所有 $0 \le j \le m-1$）。
- $0 \le s,g \le n-1$。
- $s ≠ g$。
- 除在端点处外，任意两座天桥不会有其他公共的点。

**子任务**

1. （$10$ 分）$n,m \le 50$。
2. （$14$ 分）每座天桥最多与 $10$ 栋建筑相交。
3. （$15$ 分）$s=0$，$g=n-1$，且所有建筑的高度相等。
4. （$18$ 分）$s=0$，$g=n-1$。
5. （$43$ 分）没有任何附加限制。


title: [CQOI2010] 扑克牌

description:
你有 $n$ 种牌，第 $i$ 种牌的数目为 $c_i$。另外有一种特殊的牌：joker，它的数目是 $m$。你可以用每种牌各一张来组成一套牌，也可以用一张 joker 和除了某一种牌以外的其他牌各一张组成 $1$ 套牌。比如，当 $n=3$ 时，一共有 $4$ 种合法的套牌：$\{1,2,3\}$，$\{J,2,3\}$，$\{1,J,3\}$，$\{1,2,J\}$。

给出 $n$，$m$ 和 $c_i$，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）。

inputFormat:
第一行包含两个整数 $n$，$m$，即牌的种数和 joker 的个数。

第二行包含 $n$ 个整数 $c_i$，即每种牌的张数。

outputFormat: 输出仅一个整数，即最多组成的套牌数目。

hint:
**样例说明**

输入数据表明：一共有 $1$ 个 $1$，$2$ 个 $2$，$3$ 个 $3$，$4$ 个 joker。最多可以组成三副套牌：$\{1,J,3\}$，$\{J,2,3\}$，$\{J,2,3\}$，joker 还剩一个，其余牌全部用完。

**数据范围**

对于 $50\%$ 的数据，$2 \le n \le 5$，$0 \le m \le 10^6$，$0 \le c_i \le 200$。

对于 $100\%$ 的数据，$2 \le n \le 50$，$0 \le m,c_i \le 5 \times 10^8$。


title: [CQOI2010] 内部白点

description:
无限大正方形网格里有 $n$ 个黑色的顶点，所有其他顶点都是白色的（网格的顶点即坐标为整数的点，又称整点）。每秒钟，所有内部白点同时变黑，直到不存在内部白点为止。你的任务是统计最后网格中的黑点个数。

内部白点的定义：一个白色的整点 $P(x,y)$ 是内部白点当且仅当 $P$ 在水平线的左边和右边各至少有一个黑点（即存在$x_1 < x < x_2$ 使得 $(x_1,y)$ 和 $(x_2,y)$ 都是黑点），且在竖直线的上边和下边各至少有一个黑点（即存在 $y_1 < y < y_2$ 使得 $(x,y_1)$ 和 $(x,y_2)$ 都是黑点）。

inputFormat:
输入第一行包含一个整数 $n$，即初始黑点个数。

以下 $n$ 行每行包含两个整数 $x$，$y$，即一个黑点的坐标。没有两个黑点的坐标相同，坐标的绝对值均不超过 $10^9$。

outputFormat:
输出仅一行，包含黑点的最终数目。

如果变色过程永不终止，输出`-1`。


title: [CQOI2011] 分金币

description:
圆桌上坐着 $n$ 个人，每人有一定数量的金币，金币总数能被 $n$ 整除。每个人可以给他左右相邻的人一些金币，最终使
得每个人的金币数目相等。

你的任务是求出被转手的金币数量的最小值。

inputFormat:
第一行为整数 $n$（$ n \ge 3$）。

以下 $n$ 行每行一个正整数，按逆时针顺序给出每个人拥有的金币数。

outputFormat: 共一行，输出被转手金币数量的最小值。


title: [JSOI2011] 同分异构体计数

description:
Antonio 最近对有机化学比较感兴趣，他想请你帮助他快速计算出某种烃类的同分异构体的数目。

为了表述方便，我们作出如下定义：
- 环烷烃： 具有 $n$ 个碳原子的环烷烃可以表示成一张具有 $n$ 个顶点 $n$ 条边的无向连通简单图(基环+外向树)。每个顶点的度数不超过 $4$。
- M-环烷烃：至多有 $m$ 个顶点在环上的环烷烃。（注意环上至少有 $3$ 个顶点，因为任意两个顶点之间至多只能有 $1$ 条边）。
- 同构：假设结构 $A$ 和结构 $B$ 均具有 $n$ 个碳原子，$A$ 和 $B$ 同构当且仅当能够对 $A$ 和 $B$ 中的每个碳原子都按照 $1~n$ 编号，使得对于编号为 $v_1$ 和 $v_2$ 的两个碳原子，他们在 $A$ 中存在边相连当且仅当他们在 $B$ 中存在边相连。（换言之，$A$ 和 $B$ 对应的图同构）。

现在，给出 $n$，$m$，Antonio 希望你帮助他统计有多少种互不同构的含有 $n$ 个碳原子的 M-环烷烃。由于这个数量可能很大，你只需要输出它对 $p$ 的余数。（$p$ 是一个素数）。

在本题中，我们不考虑某结构在化学上是否能够稳定存在，也不考虑其他的异构方式。

inputFormat: 输入文件只有一行，用空格隔开的三个整数 $n$，$m$，$p$ 。

outputFormat: 输出文件有且仅有一行，表示具有 $n$ 个碳原子的互不同构的M-环烷烃 的数量，对 $p$ 取模。

hint:
**数据范围**

$3 \le n \le 1000$，$3 \le m \le 50$，$m \le n$，$10^4 \le p \le 2 \times 10^9$，保证 $p$ 为素数。


title: 排列计数

description:
我们记一个排列 $P$ 的升高为 $k$ 当且仅当存在 $k$ 个位置 $i$ 使得 $P_i<P_{i+1}$。

现在给定排列长度 $n$，对于所有整数 $k\in [0,n]$ 求有多少个排列的升高为 $k$。

inputFormat: 一个整数 $n$。

outputFormat: 一行，$n+1$ 个整数，第 $i$ 个整数表示长度为 $n$ 且升高为 $i-1$ 个排列的个数，对 $998244353$ 取模。

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


title: 点双连通图计数

description: 求 $n$ 个点的有标号点双连通图（简单无向图，整个图是一个点双连通分量）的个数，答案对 $998244353$ 取模。

inputFormat: 共五行，每行一个整数 $n$，表示一次询问。

outputFormat: 共五行，每行一个整数，表示一次询问的答案。


title: 边双连通图计数

description: 求 $n$ 个点的有标号边双连通图（简单无向图，整个图是一个边双连通分量）的个数，答案对 $998244353$ 取模。

inputFormat: 共五行，每行一个整数 $n$，表示一次询问。

outputFormat: 共五行，每行一个整数，表示一次询问的答案。


title: Fracture Ray

background:
破碎的镜面里倒映着破碎的射线；

破碎的文字中隐藏着破碎的——

description:
有一个 `long long` 类型的数组 `a[]`。

在给出所有操作之前，给定上界参数 $v$。

共有 $q$ 次操作。每次操作为以下两个函数之一：

```
void modify(int u,int p)
{
    for (int i=u;i<=v;i+=count(i))
        a[i]+=p;
}
long long query(long long u)
{
    long long ret=0;
    for (int i=u;i<=v;i+=count(i))
        ret+=a[i];
    return ret;
}
```

上述程序为 C++ 代码，其中 `count(i)` 表示 $i$ 二进制下 $1$ 的个数，例如 `count(0)` 的返回值为 $0$，而 `count(10001279)` 的返回值为 $15$。

上述程序中出现的变量 `v` 即上界参数 $v$。

你需要执行上述操作，并在每次执行 `query()` 函数后，输出函数的返回值。

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

第一行，两个正整数 $q,v$，表示操作数，以及上界参数。

接下来 $q$ 行，每行为以下二者之一：

+ `1 u p` 表示执行 `modify(u,p)`；
+ `2 u` 表示执行 `query(u)` 并输出一行一个整数，为函数的返回值。

outputFormat: 在每次执行 `query()` 函数后，输出函数的返回值。

hint:
子任务 1（$8$ 分）：$1\leq q\leq 10^3$，$1\leq v\leq 10^4$。

子任务 2（$23$ 分）：$1\leq v\leq 10^5$。

子任务 3（$16$ 分）：$1\leq q\leq 50$。

子任务 4（$28$ 分）：$1\leq q\leq 1000$。

子任务 5（$25$ 分）：无特殊限制。

对于全部数据，$1\leq q\leq 2\times 10^5$，$1\leq u\leq v< 2^{30}$，$-10^4\leq p\leq 10^4$。

请选手注意代码实现时常数因子带来的程序效率上的影响。

已加入 hack 数据。


title: 【模板】子序列自动机

background:
本题中，若 $x$ 是 $y$ 的子序列，则等价于存在一个**单调递增**序列 $z$，满足 $|z| = |x|$，$z_{|x|} \leq |y|$，且 $\forall i \in [1, ~|x|],~y_{z_i} = x_i$。其中 $|x|,~|y|,~|z|$ 分别代表序列 $x,~y,~z$ 的长度，$x_i,~y_i,~z_i$ 分别代表序列 $x,~y,~z$ 的第 $i$ 项。

这是一道在 ``yLOI2020`` 备选题里被毙掉的题目。

description: 给定一个长度为 $n$ 的正整数序列 $a$ ，有 $q$ 次询问，第 $i$ 次询问给定一个长度为 $L_i$ 的序列 $b_i$，请你判断 $b_i$ 是不是 $a$ 的子序列。序列 $a$ 和所有 $b_i$ 中的元素都不大于一个给定的正整数 $m$。

inputFormat:
每个测试点有且仅有一组数据。

输入的第一行是四个用空格隔开的整数，分别代表 $type,~n,~q,~m$。其中 $type$ 代表测试点所在的子任务编号，其余变量的含义见【题目描述】。

输入的第二行是 $n$ 个用空格隔开的整数，第 $i$ 个数字代表序列 $a$ 的第 $i$ 个元素 $a_i$。

第 $3$ 行至第 $(q + 2)$ 行，每行代表一次询问。第 $(i + 2)$ 行的输入格式为：

- 第 $(i + 2)$ 行的行首有一个整数 $l_i$，代表第 $i$ 次询问的序列长度。一个空格后有 $l_i$ 个用空格隔开的整数。该行的第 $(j + 1)$ 个整数代表序列 $b_i$ 的第 $j$ 个元素 $b_{i, j}$。

outputFormat: 对于每次询问，输出一行一个字符串，若给定的序列是 $a$ 的子序列，则输出 `Yes`，否则输出 `No`。

hint:
#### 样例 1 解释

- 对于第一次询问，原序列中没有 $5$，所以给定序列显然不是原序列的子序列。
- 对于第二次询问，存在两个合法的序列 $z$，分别是 $\{2,~3\}$ 和 $\{2,~4\}$。即 $a_{2} = b_{2, 1},~a_3 = b_{2, 2}$ 或 $a_2 = b_{2, 1},~a_{4} = b_{2, 2}$。这里 $b_{i, j}$ 代表序列 $b_i$ 的第 $j$ 个元素，序列 $z$ 的含义见【题目背景】，下同。
- 对于第三次询问，不存在合法的序列 $z$。
- 对于第四次询问，存在两个合法的序列 $z$，分别是 $\{1,~3,~5\}$ 和 $\{1,~4,~5\}$。
- 对于第五次询问，存在一个合法的序列 $z$，为 $\{1,~2,~3,~4,~5\}$。

#### 数据范围与约定

**本题采用多测试点捆绑测试，共有 3 个子任务**。

- Subtask 1（20 points）：$type = 1$，$n, q, m \leq 100$，$\sum_{i = 1}^{q} l_i \leq 10^3$。
- Subtask 2（35 points）：$type = 2$，$n,q \leq 10^5$，$m \leq 26$，$\sum_{i = 1}^{q} l_i \leq 10^6$。
- Subtask 3（45 points）：$type = 3$，$n,q,m \leq 10^5$，$\sum_{i = 1}^q L_i \leq 10^6$。

对于全部的测试点，保证 $1 \leq n, m, q \leq 10^5$，$1 \leq a_i, b_{i, j} \leq m$，$1 \leq l_i \leq 10^6$，$\sum_{i = 1}^{q} l_i \leq 10^6$。

### 提示

- 请注意常数因子对程序效率造成的影响。
- 本题输入规模较大，请注意数据读入对程序效率造成的影响。
- 请注意输入第一行的顺序为先输入询问次数 $q$，再输入序列元素最大值 $m$。


title: [CTSC2011] 字符串重排

description:
对于两个字符串 $A = a_1 a_2 \cdots a_n$ 和 $B = b_1 b_2 \cdots b_n$，定义其最长公共前缀长度 $\text{lcp} (A,B)$  如下：

$$\text{lcp}(A,B) = \max \{k|0 \le k \le n,k \le m,a_1 a_2 \cdots a_k = b_1 b_2 \cdots b_k \}$$

给定 $n$ 个由小写字母组成的两两不同的非空字符串 $S_1,S_2,\cdots , S_n$，对于一个 $1$ 到 $n$ 的排列 $P=(p_1,p_2,\cdots,p_n)$，定义 $P$ 的价值 $W(P)$ 如下：

$$W(P) = \sum_{i=2}^n (\text{lcp}(S_{p_i-1},S_{p_i}))^2$$

我们设能够产生最大价值的排列为 $P^*_G$。

此外，还有 $q$ 个附加任务。对于第 $i$ 个任务，给定两个 $1$ 到 $n$ 之间的不同的整数 $X_i$ 和 $Y_i$。对于排列 $P$，若 $P$ 在满足 $W(P) = W(P^*_G)$ 的前提条件之下，同时满足第 $X_i$ 个字符串 $S_{X_i}$ 恰好排在第 $Y_i$ 个字符串 $S_{Y_i}$ 之前， 即 $\text{pos}(S_{X_i}) + 1 = \text{pos}(S_{Y_i})$，其中 $\text{pos}(S_i)$ 表示字符串 $S_i$ 在排列中的位置，则排列 $P$ 还将获得 $2^i$ 的奖励。所有任务的奖励之和称之为总任务奖励。

我们设能够使得总任务奖励最大的排列为 $P^*_B$。

试求：

1. $W(P^*_G)$，即可能产生的最大价值；
2. $P^*_B$，在保证最大价值前提下，可以使总任务奖励最大的排列。

inputFormat:
第一行包含两个整数 $n$ 和 $q$，表示字符串和附加任务的数量，中间用一个空格隔开；

接下来 $n$ 行，描述字符串，其中第 $i$ 行包含一个字符串 $S_i$；

接下来 $q$ 行，描述附加任务，其中第 $i$ 行包含两个整数 $X_i$ 和 $Y_i$，中间用一个空格隔开。

outputFormat:
包含三行。

第一行包含一个非负整数 $W(P^*_G)$；

第二行若干个数，每两个数之间用一个空格隔开，这一行第一个数表示满足附加任务的数量 $k$，接下来 $k$ 个数为这些任务的序号，序号从 $1$ 开始，按从小到大的顺序输出；

第三行包含 $n$ 个用一个空格隔开的正整数，表示一个 $1$ 到 $n$ 的排列 $P^*_B$。

hint:
**评分标准**

对于一个测试点：

- 如果输出文件的第一行正确可以得到 $2$ 分；
- 如果输出文件的第二行正确可以得到 $4$ 分；
- 如果输出文件的第三行正确可以得到 $4$ 分；
- 如果输出文件的三行都正确则可以得到 $10$ 分。

对于第三问中的排列，如果存在多个解， 则输出任意一个解均可得分。

若某问无法完成，也请按照格式输出，以避免测评失败。

**数据范围**

- 对于 $10\%$ 的数据，$n \le 10$，$q=1$，每个字符串的长度不超过 $50$；
- 对于 $20\%$ 的数据，$n \le 50$，$q=1$，每个字符串的长度不超过 $50$；
- 对于 $50\%$ 的数据，$n,q \le 1000$，每个字符串的长度不超过 $1000$；
- 对于 $70\%$ 的数据，任意字符串不为其他任何一个字符串的前缀；
- 对于 $100\%$ 的数据，$n \le 4 \times 10^4$，$q \le 10^5$，每个字符串的长度不超过 $10^4$，所有字符串的长度和不超过 $2 \times 10^5$。


title: 跳树

background: 兔子喜欢跳树。

description:
一天，兔子在一棵点数为 $2^n-1$ 完全二叉树上的一个结点上，他准备进行若干次如下的跳跃。

- 跳到这个点的左儿子，保证这个点有左儿子。
- 跳到这个点的右儿子，保证这个点有右儿子。
- 跳到这个点的父亲，**若这个点是根，无视此操作**。

其中，$i$ 号点要么没有儿子，要么有左儿子 $2 \times i$ 和右儿子 $2 \times i + 1$。

兔子会计划性地跳树，他写下了一个长度为 $m$ 的序列 $op$。$op$ 中的每个数都是 $1$, $2$, $3$ 中的一种。操作 $i$ 对应从上到下第 $i$ 种跳跃方式。

每次，兔子会选择一段区间 $[l,r]$，依次进行跳跃 $op_l,op_{l+1},\ldots,op_r$。

有时兔子会对一个点的 $op$ 值进行修改。

现在你需要求出兔子每次会跳到哪个结点。

阅读样例解释可以对题意获得更好的理解。

inputFormat:
第一行三个整数 $n, m, q$，表示树的大小的幂次、$op$ 的长度、操作的次数。

第二行包含 $m$ 个整数 $op_{1,2,\ldots,m}$，表示序列的初值。

接下来 $q$ 行，每行一个整数 $type$，若 $type$ 为 $1$，接下来三个整数 $s,l,r$，描述起点和进行跳跃的区间；若 $type$ 为 $2$ ，接下来两个整数 $x,y$，描述修改的位置与值。

outputFormat: 对于每一个 $type=1$，输出一个数，表示跳跃到的结点。

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

其中红边为第一次跳跃的路径，蓝边为第二次，绿边为第三次。

所有测试数据的范围和特点如下表所示：

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

对于 $100\%$ 的数据，$1\leq n \leq 30$，$1\leq m,q \leq  5 \times 10^5$，$1\leq op_i\leq 3$。


title: 【模板】失配树

description:
给定一个字符串 $s$，定义它的 **$k$ 前缀** $\mathit{pre}_k$ 为字符串 $s_{1\dots k}$，**$k$ 后缀** $\mathit{suf}_k$ 为字符串 $s_{|s|-k+1\dots |s|}$，其中 $1 \le k \le |s|$。

定义 $\bold{Border}(s)$ 为**对于 $i \in [1, |s|)$，满足 $\mathit{pre}_i = \mathit{suf}_i$** 的字符串 $\mathit{pre}_i$ 的集合。$\bold{Border}(s)$ 中的每个元素都称之为字符串 $s$ 的 $\operatorname{border}$。

有 $m$ 组询问，每组询问给定 $p,q$，求 $s$ 的 **$\boldsymbol{p}$ 前缀** 和 **$\boldsymbol{q}$ 前缀** 的 **最长公共 $\operatorname{border}$**  的长度。

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

第二行一个整数 $m$。

接下来 $m$ 行，每行两个整数 $p,q$。

outputFormat: 对于每组询问，一行一个整数，表示答案。若不存在公共 $\operatorname{border}$，请输出 $0$。

hint:
样例 $2$ 说明：

对于第一个询问，$2$ 前缀和 $18$ 前缀分别是 ``zz`` 和 ``zzaaccaazzccaacczz``，由于 ``zz`` 只有一个 $\operatorname{border}$，即 ``z``，故最长公共 $\operatorname{border}$ 长度为 $1$。

---

对于 $16\%$ 的数据，$s$ 中的字符全部相等。

对于 $100\%$ 的数据，$1\leq p,q \le |s|\leq 10^6$，$1 \leq m \leq 10^5$，$s_i \in [\texttt{a}, \texttt{z}]$。


title: [ZJOI2016] 随机树生成器

background: 附加文件及样例可在页面底部「附件」中下载。

description:
小 Y 最近有了一个随机数生成器 (random number generator)。小 Y 想用这个随机数生成器生成 $n$ 个节点的树。树为一种没有环的无向连通图。

经过小 Y 的研究，她发现了 $4$ 种随机树生成方法。

第一种方法为首先生成一个 $1$ 到 $n$ 的全排列 $p_1,p_2,…,p_n$。接着对于所有的节点 $i (2 \leq i \leq n)$，由 $p_i$ 向 $p_j$ 连一条边，其中 $j$ 是 $1$ 到 $i-1$ 中的随机整数。

第二种方法为首先生成一个 $1$ 到 $n$ 的全排列 $p_1,p_2,…,p_n$。接着对于所有的节点 $i (2 \leq i \leq n)$，由 $p_i$ 向 $p_j$ 连一条边，其中 $j$ 是 $\lfloor \frac {i}{2} \rfloor$ 到 $i-1$ 中的随机整数。

第三种方法为首先有一个 $n$ 个点的图，里面没有边。接着等概率地随机生成点对 $u,v$ ，如果当前图中 $u,v$ 不连通，那么将边 $(u,v)$ 加入到图中。重复这个过程，直到这个图连通为止。

第四种方法为在所有 $n$ 个点的不同的有标号的树中，等概率地随机选取一棵树。两个树是不同的当且仅当存在一条边 $(u,v)$ 只出现在其中一棵树中。比如 $(1,2),(1,3)$ 和 $(1,2),(2,3)$ 是两棵不同的树。

小 Y 用这四种方法生成了很多棵 $n$ 个节点的树，但她忘记了这些树分别由哪种方法生成的。你能帮帮她辨认这些树由哪种随机方法生成吗？

在这个题目中令 $n=1000$，也就是小 Y 生成的树的节点个数都为 $1000$。

inputFormat:
第一行包含 $1$ 个正整数 $T$，表示是**第** $T$ 组测试数据。

接下来一个正整数 $m$，表示有 $m$ 棵树。

对于每棵树，共 $n-1$ 行。每行包含 $2$ 个正整数 $u,v$，表示这棵树中有一条节点 $u$ 与节点 $v$ 之间的边。

outputFormat: 输出共 $m$ 行，每行一个 $1$ 到 $4$ 之间的正整数，表示这棵树随机生成的方式。

samples: 见附件 见附件

hint:
对于所有的测试数据，保证输入的树是由上述四种方式随机生成。

各测试点满足以下约定：

| 测试点 | $m$ | 约定|
| --- | --- | --- |
| 1 | $=2000$ | 只会出现第 $1,2$ 种生成方式 |
| 2 | $=3000$ | 只会出现第 $1,2,3$ 种生成方式 |
| 3 | $=3000$ | 只会出现第 $1,3,4$ 种生成方式 |
| 4 | $=4000$ | 无 |
| 5 | $=4000$ | 无 |

对于每个测试点，保证每种可能出现的生成方式恰好出现 $1000$ 次。

#### 评分方式

对于每个测试点，有 $10$ 个评分参数 $a_{10},a_9,a_8,…,a_1$。

如果你的输出中错误的答案个数为 $x$, 那么你将获得 $2s$ 的分数，其中 $s$ 为满足 $x \leq a_s$ 最大的整数。如果 $x>a_1$，那么你将获得 $0$ 分。

如果输出格式有异常你将同样获得 $0$ 分，请确保你的输出中共有 $m$ 行，每行为一个 $1$ 到 $4$ 之间的正整数。

对于每个测试点的具体评分参数见附加文件中的 `scores`。


title: [USACO19DEC] Cow Gymnastics B

description:
为了提高健康水平，奶牛们开始进行体操训练了！Farmer John 选定了他最喜爱的奶牛 Bessie 来执教其他 $N$ 头奶牛，同时评估她们学习不同的体操技术的进度。

$K$ 次训练课的每一次，Bessie 都会根据 $N$ 头奶牛的表现给她们进行排名。之后，她对这些排名的一致性产生了好奇。称一对不同的奶牛是**一致的**，如果其中一头奶牛在每次训练课中都表现得都比另一头要好。

请帮助 Bessie 计算一致的奶牛的对数。

inputFormat: 输入的第一行包含两个正整数 $K$ 和 $N$。以下 $K$ 行每行包含整数 $1 \ldots N$ 的某种排列，表示奶牛们的排名（奶牛们用编号 $1 \ldots N$ 进行区分）。如果在某一行中 $A$ 出现在 $B$ 之前，表示奶牛 $A$ 表现得比奶牛 $B$ 要好。

outputFormat: 输出一行，包含一致的奶牛的对数。


title: [USACO19DEC] Where Am I? B

description:
Farmer John 出门沿着马路散步，但是他现在发现可能迷路了！

沿路有一排共 $N$ 个农场。不幸的是农场并没有编号，这使得 Farmer John 难以分辨他在这条路上所处的位置。然而，每个农场都沿路设有一个彩色的邮箱，所以 Farmer John 希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。

每个邮箱的颜色用 A..Z 之间的一个字母来指定，所以沿着道路的 $N$ 个邮箱的序列可以用一个长为 $N$ 的由字母 A..Z 组成的字符串来表示。某些邮箱可能会有相同的颜色。Farmer John 想要知道最小的 $K$ 的值，使得他查看任意连续 $K$ 个邮箱序列，他都可以唯一确定这一序列在道路上的位置。

例如，假设沿路的邮箱序列为 `ABCDABC` 。Farmer John 不能令 $K=3$，因为如果他看到了 `ABC`，沿路有两个这一连续颜色序列可能所在的位置。最小可行的 $K$ 的值为 $K=4$，因为如果他查看任意连续 4 个邮箱，这一颜色序列可以唯一确定他在道路上的位置。

inputFormat: 输入的第一行包含 $N$，第二行包含一个由 $N$ 个字符组成的字符串，每个字符均在 A..Z 之内。

outputFormat: 输出一行，包含一个整数，为可以解决 Farmer John 的问题的最小 $K$ 值。

hint: $1 \leq N \leq 100$。


title: [USACO19DEC] Livestock Lineup B

description:
每天，Farmer John 都要给他的 $8$ 头奶牛挤奶。她们的名字分别是 Bessie，Buttercup，Belinda，Beatrice，Bella，Blue，Betsy，和 Sue。

不幸的是，这些奶牛相当难以伺候，她们要求 Farmer John 以一种符合 $N$ 条限制的顺序给她们挤奶。每条限制的形式为“$X$ 必须紧邻着 $Y$ 挤奶”，要求奶牛 $X$ 在挤奶顺序中必须紧接在奶牛 $Y$ 之后，或者紧接在奶牛 $Y$ 之前。

请帮助 Farmer John 求出一种满足所有限制的奶牛挤奶顺序。保证这样的顺序是存在的。如果有多种顺序都满足要求，请输出字典序最小的一种。也就是说，第一头奶牛需要是所有可能排在任意合法奶牛顺序的第一位的奶牛中名字字典序最小的。在所有合法的以这头字典序最小的奶牛为首的奶牛顺序中，第二头奶牛需要是字典序最小的，以此类推。

inputFormat: 输入的第一行包含 $N$。以下 $N$ 行每行包含一句句子，以 "$X$ must be milked beside $Y$" 的格式描述了一条限制，其中 $X$ 和 $Y$ 为 Farmer John 的某些奶牛的名字（上文列举了八个可能的名字）。

outputFormat: 请用 $8$ 行输出一个奶牛的顺序，每行输出一头奶牛的名字，满足所有的限制。如果由多种顺序符合要求，输出字典序最小的奶牛顺序。

samples:
3
Buttercup must be milked beside Bella
Blue must be milked beside Bella
Sue must be milked beside Beatrice

samples:
Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup

hint:
$1 \leq N \leq 7$。

供题：Brian Dean


title: [USACO19DEC] MooBuzz S

description:
Farmer John 的奶牛们最近成为了一个简单的数字游戏“FizzBuzz”的狂热玩家。这个游戏的规则很简单：奶牛们站成一圈，依次从一开始报数，每头奶牛在轮到她的时候报一个数。如果一头奶牛将要报的数字是 $3$ 的倍数，她应当报 `Fizz` 来代替这个数。如果一头奶牛将要报的数字是 $5$ 的倍数，她应当报 `Buzz` 来代替这个数。如果一头奶牛将要报的数字是 $15$ 的倍数，她应当报 `FizzBuzz` 来代替这个数。于是这个游戏的开始部分的记录为：

`1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16`

由于词汇的匮乏，奶牛们玩的 FizzBuzz 中用`Moo` 代替了 `Fizz`、`Buzz`、`FizzBuzz`。于是奶牛版的游戏的开始部分的记录为：

`1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16`

给定 $N$，请求出这个游戏中第 $N$ 个被报的数。

inputFormat: 输入包含一个整数 $N$。

outputFormat: 输出游戏中被报出的第 $N$ 个数。

hint:
关于部分分：

测试点 $1$ 为样例。

测试点 $2\sim 5$ 满足 $N\le 10^6$。

对于 $100\%$ 的数据，$1 \leq N \leq 10^9$

供题：Brian Dean


title: [USACO19DEC] Meetings S

description:
有两个牛棚位于一维数轴上的点 $0$ 和 $L$ 处（$1 \leq L \leq 10^9$）。同时有 $N$ 头奶牛（$1 \leq N \leq 5 \times 10^4$）位于数轴上不同的位置（将牛棚和奶牛看作点）。每头奶牛 $i$ 初始时位于某个位置 $x_i$，并朝着正向或负向以一个单位每秒的速度移动，用一个等于 $1$ 或 $-1$ 的整数 $d_i$ 表示。每头奶牛还拥有一个在范围 $[1,10^3]$ 内的重量。所有奶牛始终以恒定的速度移动，直到以下事件之一发生：
- 如果奶牛 $i$ 移动到了一个牛棚，则奶牛 $i$ 停止移动。
- 当奶牛 $i$ 和 $j$ 占据了相同的点的时候，并且这一点不是一个牛棚，则发生了相遇。此时，奶牛 $i$ 被赋予奶牛 $j$ 先前的速度，反之亦然。注意奶牛可能在一个非整数点相遇。

令 $T$ 等于停止移动的奶牛（由于到达两个牛棚之一）的重量之和至少等于所有奶牛的重量之和的一半的最早时刻。请求出在时刻 $0 \ldots T$（包括时刻 $T$）之间发生的奶牛对相遇的总数。

inputFormat:
输入的第一行包含两个空格分隔的整数 $N$ 和 $L$。

以下 $N$ 行，每行包含三个空格分隔的整数 $w_i$，$x_i$ 以及 $d_i$。所有的位置 $x_i$ 各不相同，并且满足 $0<x_i<L$。

outputFormat: 输出一行，包含答案。

hint:
### 样例解释

在这个例子中，奶牛们按如下方式移动：

1. 第一和第二头奶牛于时刻 0.5 在位置 1.5 相遇。此时第一头奶牛拥有速度 -1，第二头奶牛拥有速度 1。
2. 第二和第三头奶牛于时刻 1 在位置 2 相遇。此时第二头奶牛拥有速度 −1，第三头奶牛拥有速度 1。
3. 第一头奶牛于时刻 2 到达左边的牛棚。
4. 第二头奶牛于时刻 3 到达左边的牛棚。
5. 由于到达牛棚的奶牛的总重量已经至少是所有奶牛的总重量的一半，这个过程此时终止。如果继续进行下去，第三头奶牛将会在时刻 4 到达右边的牛棚。

发生了恰好两次相遇。

### 子任务

测试点 $2\sim 4$ 满足 $N\le 10^2$，并且对所有 $i$，$w_i=1$。

测试点 $5\sim 7$ 满足 $N\le 10^2$。

供题：Benjamin Qi


title: [USACO19DEC] Milk Visits S

description:
Farmer John 计划建造 $N$ 个农场，用 $N-1$ 条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为更赛牛或荷斯坦牛之一。

Farmer John 的 $M$ 个朋友经常前来拜访他。在朋友 $i$ 拜访之时，Farmer John 会与他的朋友沿着从农场 $A_i$ 到农场 $B_i$ 之间的唯一路径行走（可能有 $A_i = B_i$）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的有些朋友只喝更赛牛的牛奶，其余的只喝荷斯坦牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

请求出每个朋友在拜访过后是否会高兴。

inputFormat:
输入的第一行包含两个整数 $N$ 和 $M$。

第二行包含一个长为 $N$ 的字符串。如果第 $i$ 个农场中的奶牛是更赛牛，则字符串中第 $i$ 个字符为 `G`，如果第 $i$ 个农场中的奶牛是荷斯坦牛则为 `H`。

以下 $N-1$ 行，每行包含两个不同的整数 $X$ 和 $Y$（$1 \leq X, Y \leq N$），表示农场 $X$ 与 $Y$ 之间有一条道路。

以下 $M$ 行，每行包含整数 $A_i$，$B_i$，以及一个字符 $C_i$。$A_i$ 和 $B_i$ 表示朋友 $i$ 拜访时行走的路径的端点，$C_i$ 是 `G` 或 `H` 之一，表示第 $i$ 个朋友喜欢更赛牛的牛奶或是荷斯坦牛的牛奶。

outputFormat: 输出一个长为 $M$ 的二进制字符串。如果第 $i$ 个朋友会感到高兴，则字符串的第 $i$ 个字符为 `1`，否则为 `0`。

hint:
在这里，从农场 1 到农场 4 的路径包括农场 1、2 和 4。所有这些农场里都是荷斯坦牛，所以第一个朋友会感到满意，而第二个朋友不会。

关于部分分：

测试点 $1$ 样例。

测试点 $2\sim 5$ 满足 $N\le 10^3$，$M\le 2\cdot 10^3$。

对于 $100\%$ 的数据，$1 \leq N \leq 10^5$，$1 \leq M \leq 10^5$。

供题：Spencer Compton


title: [COCI2015] Divljak

description:
Alice 有 $n$ 个字符串 ${S}_1, {S}_2, \ldots, {S}_n$，Bob 有一个字符串集合 ${T}$，一开始集合是空的。

接下来会发生 $q$ 个操作，操作有两种形式：

1. `1 P`：Bob 往自己的集合里添加了一个字符串 ${P}$。
2. `2 x`：Alice 询问 Bob，集合 ${T}$ 中有多少个字符串包含串 ${S}_x$（我们称串 ${A}$ 包含串 ${B}$，当且仅当 ${B}$ 是 ${A}$ 的子串）。

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

接下来 $n$ 行，第 $i$ 行一个字符串 ${S}_i$。

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

接下来 $q$ 行，每行一个操作。

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

hint: 对于 $100\%$ 的数据，$1 \leq n,q \leq 10^5$，字符串由小写字母构成，$S$ 和 $P$ 的总长分别 $\le 2 \times 10^6$。


title: [USACO19DEC] Milk Pumping G

description:
Farmer John 最近为了扩张他的牛奶产业帝国而收购了一个新的农场。这一新的农场通过一个管道网络与附近的小镇相连，FJ 想要找出其中最合适的一组管道，将其购买并用来将牛奶从农场输送到小镇。

这个管道网络可以用 $N$ 个接合点（管道的端点）来描述，将其编号为 $1 \ldots N$。接合点 $1$ 表示 FJ 的农场，接合点 $N$ 表示小镇。有 $M$ 条双向的管道，每条连接了两个接合点。使用第 $i$ 条管道需要 FJ 花费 $c_i$ 美元购入，可以支持每秒 $f_i$ 升牛奶的流量。

FJ 想要购买一条管道组成一条单一路径，路径的两端点分别为接合点 $1$ 和 $N$。这条路径的花费等于路径上所有管道的费用之和。路径上的流量等于路径上所有管道的最小流量（因为这是沿这条路径输送牛奶的瓶颈）。FJ 想要最大化路径流量与路径花费之比。保证存在从 $1$ 到 $N$之间的路径。

inputFormat: 输入的第一行包含 $N$ 和 $M$。以下 $M$ 行每行以四个整数描述一条管道：$a$ 和 $b$（管道连接的两个不同的接合点），$c$（管道的花费），以及 $f$（管道的流量）。花费和流量均为范围 $1 \ldots 1000$ 之内的正整数。

outputFormat: 输出 $10^6$ 乘以最优解的值，并向下取整（也就是说，如果这个数本身不是整数，输出小于它的最接近它的整数）。

hint:
在这个例子中，仅由一条路径从 $1$ 到 $N$。 它的流量为 $\min(3,4)=3$，花费为 $2+5=7$。

### 数据范围

测试点 $2\sim 5$ 满足 $N,M\le 100$。

对于 $100\%$ 的数据，$2 \leq N \leq 1000$，$1 \leq M \leq 1000$。

供题：Brian Dean


title: [USACO19DEC] Milk Visits G

description:
Farmer John 计划建造 $N$ 个农场，用 $N-1$ 条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为 $1$ 到 $N$ 之间的一个整数 $T_i$。

Farmer John 的 $M$ 个朋友经常前来拜访他。在朋友 $i$ 拜访之时，Farmer John 会与他的朋友沿着从农场 $A_i$ 到农场 $B_i$ 之间的唯一路径行走（可能有 $A_i = B_i$）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的每个朋友都只喝某种特定品种的奶牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

请求出每个朋友在拜访过后是否会高兴。

inputFormat:
输入的第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个空格分隔的整数 $T_1,T_2,\ldots, T_N$。第 $i$ 个农场内的奶牛的品种用 $T_i$ 表示。

以下 $N-1$ 行，每行包含两个不同的整数 $X$ 和 $Y$（$1 \leq X, Y \leq N$），表示农场 $X$ 与 $Y$ 之间有一条边。

以下 $M$ 行，每行包含整数 $A_i$，$B_i$，以及$C_i$。$A_i$ 和 $B_i$ 表示朋友 $i$ 拜访时行走的路径的端点，$C_i$（$1\le C_i\le N$）表示这个朋友喜欢的牛奶的奶牛品种。

hint:
测试点性质：

测试点 $2$ 为以下第二个样例。

测试点 $3$ 满足 $N\le 10^3$，$M\le 2\cdot 10^3$。

测试点 $4\sim 7$ 满足 $C_i\le 10$。

对于 $100\%$ 的数据，$1 \leq N \leq 10^5$，$1 \leq M \leq 10^5$。

供题：Spencer Compton


title: [USACO19DEC] Moortal Cowmbat G

description:
Bessie 玩格斗游戏真牛快打已经有很长时间了。然而，最近游戏开发者发布了一项更新，这迫使 Bessie 改变她的打法。

游戏总共使用 $M$ 个按键，标记为前 $M$ 个小写字母。Bessie 在游戏中最喜欢的组合键是一个长为 $N$ 的按键字符串 $S$。然而，由于最近的更新，现在每种组合键必须由一些“连击”所组成，其中连击的定义为相同的按键连续按下至少 $K$ 次。Bessie想要修改她最喜欢的组合键，创造一个同样长为 $N$ 的新组合键，然而这一新组合键由按键连击所组成，以适应规则的变化。

Bessie 需要消耗 $a_{ij}$ 天来训练她在组合键中某个特定的位置用按键 $j$ 来取代按键 $i$（也就是说，将 $S$ 中的某个特定的字符由 $i$ 变为 $j$ 的代价为 $a_{ij}$）。注意有可能将按键 $i$ 换成某种中间按键 $k$ 然后再从按键 $k$ 换成按键 $j$ 会比直接从按键 $i$ 换成按键 $j$ 消耗更短的时间（或者更一般地说，可能有一条起点为 $i$ 终点为 $j$ 的更改路径给出了从按键 $i$ 最终更改为按键 $j$ 的最小总代价）。

帮助 Bessie 求出她创建一个满足新要求的组合键所需要的最小天数。

inputFormat: 输入的第一行包含 $N$，$M$ 和 $K$。第二行包含 $S$，最后 $M$ 行包含一个 $M\times M$ 的数字方阵 $a_{ij}$，其中 $a_{ij}$ 为一个范围为 $0 \ldots 1000$ 的整数，并且对于所有的 $i$，有 $a_{ii} = 0$。

outputFormat: 输出一个整数，表示 Bessie 将她的组合键改为一个满足新要求的新的组合键所需要的最小天数。

hint:
在这个例子中的最优方案是将 `a` 改为 `b`，将 `d` 改为 `e`，再将两个 `e` 都改为 `c`。这总共消耗 $1+4+0+0=5$ 天，最终的组合键为 `bbccc`。

测试点性质：

测试点 $2\sim 4$ 满足 $N\le 1000$，$K\le 50$。

测试点 $5\sim 8$ 满足 $N\le 3\times 10^4$，$K\le 50$。

对于 $100\%$ 的数据，$1 \leq M \leq 26$，$1 \leq K\leq N \leq 10^5$。

供题：Eric Wei


title: [USACO19DEC] Greedy Pie Eaters P

background:
Farmer John has $M$ cows, conveniently labeled $1 \ldots M$, who enjoy the occasional change of pace
from eating grass.  As a treat for the cows, Farmer John has baked $N$ pies ($1 \leq N \leq 300$), labeled
$1 \ldots N$.  Cow $i$ enjoys pies with labels in the range $[l_i, r_i]$ (from $l_i$ to $r_i$ inclusive),
and no two cows enjoy the exact same range of pies.  Cow $i$ also has a weight, $w_i$, which
is an integer in the range $1 \ldots 10^6$.

Farmer John may choose a sequence of cows $c_1,c_2,\ldots, c_K,$ after which the
selected cows will take turns eating in that order. Unfortunately, the cows
don't know how to share! When it is cow $c_i$'s turn to eat, she will consume
all of the  pies that she enjoys --- that is, all remaining pies in the interval
$[l_{c_i},r_{c_i}]$.  Farmer John would like to avoid the awkward situation
occurring when it is a cows turn to eat but all of the pies she enjoys have already been
consumed. Therefore, he wants you to compute the largest possible total weight
($w_{c_1}+w_{c_2}+\ldots+w_{c_K}$) of a sequence $c_1,c_2,\ldots, c_K$ for which each cow in the
sequence eats at least one pie.

description:
Farmer John 有 $M$ 头奶牛，为了方便，编号为 $1,\dots,M$。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。Farmer John 一天烤了 $N$ 个派请奶牛吃，这 $N$ 个派编号为 $1,\dots,N$。第 $i$ 头奶牛喜欢吃编号在 $\left[ l_i,r_i \right]$ 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 $i$ 头奶牛有一个体重 $w_i$，这是一个在 $\left[ 1,10^6 \right]$ 中的正整数。

Farmer John 可以选择一个奶牛序列 $c_1,c_2,\dots,c_K$，并让这些奶牛按这个顺序轮流吃派。不幸的是，这些奶牛不知道分享！当奶牛  吃派时，她会把她喜欢吃的派都吃掉——也就是说，她会吃掉编号在 $[l_{c_i},r_{c_i}]$ 中所有剩余的派。Farmer John 想要避免当轮到一头奶牛吃派时，她所有喜欢的派在之前都被吃掉了这样尴尬的情况。因此，他想让你计算，要使奶牛按 $c_1,c_2,\dots,c_K$ 的顺序吃派，轮到这头奶牛时她喜欢的派至少剩余一个的情况下，这些奶牛的最大可能体重（$w_{c_1}+w_{c_2}+\ldots+w_{c_K}$）是多少。

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

接下来 $M$ 行，每行三个正整数 $w_i,l_i,r_i$。

outputFormat: 输出对于一个合法的序列，最大可能的体重值。

hint:
#### 样例解释
在这个样例中，如果奶牛 $1$ 先吃，那么奶牛 $2$ 就吃不到派了。然而，先让奶牛 $2$ 吃，然后奶牛 $1$ 只吃编号为 $2$ 的派，仍可以满足条件。

对于全部数据，$1 \le N \le 300,1 \le M \le \dfrac{N(N-1)}{2},1 \le l_i,r_i \le N,1 \le w_i \le 10^6$。
#### 数据范围
对于测试点 $2-5$，满足 $N \le 50,M \le 20$；

对于测试点 $6-9$，满足 $N \le 50$。

USACO 2019 December 铂金组T1


title: [USACO19DEC] Bessie's Snow Cow P

background:
Snow has arrived on the farm, and as she does at the beginning of every winter,
Bessie is building a snow-cow! Most of the time, Bessie strives to make her
sculpture look as much like a real cow as possible.  However, feeling
artistically inspired, this year she decides to pursue a more abstract route and
build a sculpture in the shape of a tree, consisting of $N$ snowballs
$(1\le N\le 10^5)$ connected by  $N-1$ branches, each connecting a pair of
snowballs such that there is a  unique path between every pair of snowballs.

Bessie has added a nose to one of the snowballs, so it represents the head of
the abstract snow cow.  She designates it as snowball number 1.  To add more
visual interest, she plans to dye some of the snowballs different colors in an
artistic fashion by filling old milk pails with colored dye and splashing them
onto the sculpture.  Colors are identified by integers in the range
$1 \ldots 10^5$, and  Bessie has an unlimited supply of buckets filled with dyes
of every possible color.

When Bessie splashes a snowball with a bucket of dye, all the snowballs in its
subtree are also splashed with the same dye (snowball $y$ is in the subtree of
snowball $x$ if $x$ lies on the path from $y$ to the head snowball). By
splashing each color with great care, Bessie makes sure that all colors a
snowball has been splashed with will remain visible. For example, if a snowball
had colors $[1,2,3]$ and Bessie splashes it with color $4$, the snowball will
then have colors $[1,2,3,4]$.

After splashing the snowballs some number of times, Bessie may also want to know
how colorful a part of her snow-cow is.  The "colorfulness" of a snowball $x$ is
equal to the number of distinct colors $c$ such that snowball $x$ is colored
$c$. If Bessie asks you about snowball $x$, you should reply with the sum of the
colorfulness values of all snowballs in the subtree of $x.$

Please help Bessie find the colorfulness of her snow-cow at certain points in
time.

description:
农场下雪啦！Bessie 和往年开冬一样在堆雪牛。她之前是个写实派，总是想把她的雪牛堆得和个真牛一样。但今年不一样，受到来自东方的神秘力量的影响，她想来点抽象艺术，因此她想堆成一棵树的样子。这棵树由 $N$ 个雪球，$N-1$ 根树枝构成，每根树枝连接两个雪球，并且每两个雪球之间路径唯一。

Bessie 要给她的雪牛来点细节。因此她给其中一个雪球加了个鼻子，来表示这是他那抽象的牛的头，并且把它称作雪球 $1$。为了让雪牛更好看，她还要给某些雪球来点不同的颜色。于是，她用旧牛奶桶装满了颜料泼到雪牛上。这些颜料分别被编号为 $1,2,\dots 10^5$，且每种颜色都无限量供应。

当 Bessie 把一桶颜料泼到一个雪球上时，这个雪球子树上的所有雪球也会被染色（我们称雪球 $y$ 在雪球 $x$ 的子树里当且仅当雪球 $x$ 处在雪球 $y$ 到雪球 $1$ 的路径上）。Bessie 有着精确的泼颜料技术，因此在泼完一种颜料后，一个雪球上之前被染过的所有颜色依然清晰可见。例如，一个雪球之前显现出来颜色 $\left[ 1,2,3 \right]$，然后 Bessie 把装有 $4$ 号颜色的牛奶桶泼上去，那么这个雪球将显现出来颜色 $\left[ 1,2,3,4 \right]$。 在泼了几桶颜料以后，Bessie 可能想要了解她的雪牛有多五彩斑斓。令雪球 $x$ 的『颜色丰富度』为这个雪球被染上的不同颜色总数 ，当 Bessie 想了解雪球 $x$ 的相关信息时，你应该回答她雪球 $x$ 的子树中所有的雪球的颜色丰富度之和。

救救孩子吧！

inputFormat:
第一行，$N$ 和询问数 $Q$。

接下来 $N-1$ 行每行两个用空格隔开的数 $a$ 和 $b$，表示雪球 $a$ 和 $b$ 中间有一根树枝相连。

最后 $Q$ 行每行一个请求，格式及对应含义如下：

 - `1 x c`（修改）：表示 Bessie 把一桶装有颜色 $c$ 的颜料泼到雪球 $x$ ，使得其子树上所有雪球被染色。
 - `2 x`（询问）：询问雪球 $x$ 的子树的颜色丰富度之和。

outputFormat: 对于每个询问，输出所询问子树的颜色丰富度之和。**为了防止溢出，你需要使用 64 位整数。**

hint:
#### 样例解释
执行完第一个修改后雪球 $4$ 被染上了颜色 $1$。

执行完第二个修改后雪球 $4$ 和雪球 $5$ 被染上了颜色 $2$。

执行完第三个修改后所有雪球都被染上了颜色 $1$。
#### 数据范围
对于测试点 $2,3$，$1\le N\le 10^2,1\le Q\le 2\times 10^2$；

对于测试点 $4-6$，$1\le N\le 10^3,1\le Q\le 2\times 10^3$；

对于 $100\%$ 的数据，$1\le N,\ Q,\ c \le 10^5, 1\le a,\ b,\ x \le N$。

USACO 2019 December 铂金组T2


title: [USACO19DEC] Tree Depth P

background:
For the new year, Farmer John decided to give his cows a festive binary search tree
(BST)!

To generate the BST, FJ starts with a permutation $a=\{a_1,a_2,\ldots,a_N\}$
of the integers $1\ldots N$, where $N\le 300$.  He then runs the following
pseudocode with arguments $1$ and $N.$

```
generate(l,r):
  if l > r, return empty subtree;
  x = argmin_{l <= i <= r} a_i; // index of min a_i in {a_l,...,a_r}
  return a BST with x as the root,
    generate(l,x-1) as the left subtree,
    generate(x+1,r) as the right subtree;
```
For example, the permutation $\{3,2,5,1,4\}$ generates the following BST:

```
    4
   / \
  2   5
 / \
1   3
```
Let $d_i(a)$ denote the depth of node $i$ in the tree corresponding to $a,$
meaning the number of nodes on the path from $a_i$ to the root. In the above
example, $d_4(a)=1, d_2(a)=d_5(a)=2,$ and $d_1(a)=d_3(a)=3.$

The number of inversions of $a$ is equal to the number of pairs of integers
$(i,j)$ such that $1\le i<j\le N$ and $a_i>a_j.$ The cows know that the $a$ that
FJ will use to generate the BST has exactly $K$ inversions
$(0\le K\le \frac{N(N-1)}{2})$.  Over all $a$ satisfying this condition, compute
the remainder when $\sum_ad_i(a)$ is divided by $M$ for each $1\le i\le N.$

description:
为了迎接新年，Farmer John 决定给他的奶牛们一个节日二叉搜索树！

为了生成这个二叉搜索树，Farmer John 从一个 $1 \dots N$ 的排列 $a= \{1,2, \dots ,N\}$ 开始，然后以参数 $l$ 和 $r$ 开始运行如下的伪代码：
```
generate(l,r):
  if l > r, return empty subtree;
  x = argmin_{l <= i <= r} a_i; // index of min a_i in {a_l,...,a_r}
  return a BST with x as the root,
    generate(l,x-1) as the left subtree,
    generate(x+1,r) as the right subtree;
```
例如，排列 $\{ 3,2,5,1,4 \}$ 将产生如下的二叉搜索树：

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

令 $d_i(a)$ 表示节点 $i$ 在用排列 $a$ 生成的二叉搜索树中的深度。深度定义为这个节点到根节点的路径上的点数。在上述例子中，$d_4(a)=1,d_2(a)=d_5(a)=2,d_1(a)=d_3(a)=3$。

$a$ 中的逆序对数等于满足 $1 \le i<j \le N$ 且 $a_i>a_j$ 的数对 $(i,j)$ 的个数。奶牛们知道 Farmer John 用来生成二叉搜索树的排列 $a$ 中恰好有 $K$ 个逆序对。对于所有满足条件的 $a$，请计算对于每个 $1 \le i \le N$，$\sum_a d_i(a)$ 对 $M$ 取模后的结果。

inputFormat: 输入只有一行，包含三个整数 $N,K,M$。

outputFormat: 输出一行 $N$ 个整数，第 $i$ 个整数表示 $\sum_a d_i(a) \bmod M$。两个整数之间用一个空格隔开。

hint:
#### 样例解释 1

对于这个样例，唯一满足条件的排列为 $a=\{1,2,3\}$。

#### 样例解释 2

对于这个样例，满足条件的两个排列分别为 $a=\{1,3,2\}$ 和 $a=\{2,1,3\}$。

#### 数据范围

对于全部数据，$1\le N\le 300$，$0\le K\le \frac{N(N-1)}{2}$，保证 $M$ 是一个 $\left[ 10^8,10^9+9 \right]$ 范围中的质数。

对于测试点 $3,4$，满足 $N \le 8$；

对于测试点 $5-7$，满足 $N \le 20$；

对于测试点 $8-10$，满足 $N \le 50$。

USACO 2019 December 铂金组T3


title: [SCOI2012] Blinker 的仰慕者

description: Blinker 有非常多的仰慕者，他给每个仰慕者一个正整数编号。而且这些编号还隐藏着特殊的意义，即编号的各位数字之积表示这名仰慕者对 Blinker 的重要度。 现在 Blinker 想知道编号介于某两个值 $A$,$B$ 之间，且重要度为某个定值 $K$ 的仰慕者编号和。

inputFormat:
输入的第一行是一个整数 $N$，表示 Blinker 想知道的信息个数。

接下来的 $N$ 行，每行有三个数，$A$,$B$,$K$。表示 Blinker想知道编号介于 $A$ 和 $B$ 之间的，重要度为 $K$ 的仰慕者的编号和。

outputFormat: 输出 $N$ 行，每行输出介于 $A$ 和 $B$ 之间，重要度为 $K$ 的仰慕者编号和。结果可能很大请对 $20120427$ 取模。


title: [SCOI2012] Blinker 的噩梦

description:
一天 Blinker 醒来，发现自己成为了一个二维世界的点，而且被标记上了一个奇怪的值。

这个世界是由 $N$ 个边界互不相交（且不相切）的图形组成，这里图形仅包括圆和凸多边形。每个图形还有一个权值。每次 Blinker 走进或走出某个图形时（相切时经过不算），Blinker 的标记值就会被异或上那个值。

现在，我们记录了 Blinker 在这个世界的 $M$ 天的信息。每天可能发生两种事情，一种是某个图形的权值更改为某个值；另一种是 Blinker 从某个点走到另一个点。

我们假设 Blinker 首次出发前的标记值为 $0$，我们希望知道他每次到达目的地后的标记值。

inputFormat:
输入的第一行包含 $2$ 个数，$N$ 和 $M$，分别表示这个世界的图形数和记录的天数。

接下来有 $N$ 行，每行表示一个图形。

如果一行以字符 `C` 开头，表示这个图形是一个圆，后面紧跟着三个实数 $x$, $y$, $r$ 和一个整数 $v$，分别表示圆的 $x$ 坐标，$y$ 坐标和圆的半径以及该图形对应的值。

如果一行以字符 `P` 开头，表示这个图形是凸多边形，后面紧跟着一个整数 $L$，表示凸多边形的点数，然后后面有 $L$ 对实数 $x_0$,$y_0$,$x_1$,$y_1$ $\cdots$，表示 $L$ 个点的坐标，这一行最后一个数是一个整数 $v$，表示这个图形对应的值，保证凸多边形上的点按照顺时针给出。

接下来有 $M$ 行，每行表示一天的记录信息。

如果一行以字符 `Q` 开头，表示这一天 Blinker 出行了，接下来有 $x_0,y_0,x_1,y_1$ 四个实数，分别表示出发点的坐标和目的地的坐标。

如果一行以字符 `C` 开头，表示这一天某个图形的值改变了，接下来有两个 $i$ 和 $v$，表示输入中第 $i$ 个出现的图形的值变成 $v$。

outputFormat: 对于 Blinker 的每个出行输出他到达目的地后的标记值，很显然这个值与 Blinker 的路径无关。

hint:
**样例解释**

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

样例的世界形如上图：

第一天 Binker 的初始标记值为 $0$，可能从 $A$ 沿直线走到 $B$，或者他绕过圆走到 $B$，他的标记值最终都保持不变为 $0$（假设沿直线从 $A$ 走到 $B$，共穿过 $4$ 次边界，Binker 的标记值变化过程为 $1,3,1,0$）;

第二天 Binker 的初始标记值为 $0$，他通过某种不经过图形边界的方法到达了 $C$ 点（即 Binker 瞬间移动或闪烁），然后从 $C$ 沿某种路径走到 $D$，这时他的标记值变为 $2$；

第三天圆的权值变为 $1005$；

第四天 Binker 的初始标记值为 $2$，他再次回到 $C$，并再次从 $C$ 走到 $D$，这时他的标记值又变为 $0$。

**数据范围**
- 对于 $30\%$ 的数据，$1 \le M \le 10.00$，凸多边形的点数加上圆的个数小于等于 $1000$；
- 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le M \le 10^5$，单个凸多边形的点数小于等于 $34$。图形互不相交，且 Binker 的出发点和目的地不在图形的边界。


title: [IOI2011] ricehub

description:
乡间有一条笔直而长的路称为“米道”。沿着这条米道上$R$  块稻田，每块稻田的坐标均为一个 $1$ 到 $L$ 之间(含 $1$ 和 $L$ )的整数。这些稻田按照坐标以不减的顺序给出，即对于 $0 \le i < R$，稻田 $i$ 的坐标 $X[i]$ 满足 $1 \le X[0] \le \cdots \le X[R-1] \le L$。

注意：可能有多块稻田位于同一个坐标上。

我们计划建造一个米仓用于储存尽可能多的稻米。和稻田一样，米仓将建在米道上，其坐标也是一个 $1$ 到 $L$ 之间的整数（含 $1$ 和 $L$）。这个米仓可以建在满足上述条件的任一个位置上，包括那些原来已有一个或多个稻田存在的位置。

在收获季节，每一块稻田刚好出产一滿货车的稻米。为了将这些稻米运到米仓，需要雇用一位货车司机来运米。司机的收费是每一满货车运送一个单位的距离收取 $1$ 元。換言之，将稻米从特定的稻田运到米仓的费用在数值上等于稻田坐标与米仓坐标之差的绝对值。

不幸的是，今年预算有限，我们至多只能花费 $B$ 元运费。你的任务是要帮我们找出一个建造米仓的位置，可以收集到尽可能多的稻米。

inputFormat:
第一行 三个整数 $R,L,B$；

接下来 $R$ 行 每行一个整数 表示 $X[i]$。

outputFormat: 一个整数，表示最多稻米数


title: [IOI2011] crocodile

description:
考古学家 Benjamas 考察了神秘的鳄鱼地下宫殿之后需要设法逃离。这个地下宫殿包含 $N$ 个洞穴和 $M$ 条双向的通道。每条通道连接一对不同的洞穴，两个洞穴之间最多只有一条通道，在不同的通道上行走可能需要不同的时间。$N$ 个洞穴中有 $K$ 个洞穴是出口洞穴， Benjamas 可以从出口洞穴逃离。Benjamas 从 $0$ 号洞穴出发，她希望尽快地到达一个出口洞穴。

鳄鱼门卫要阻止 Benjamas 逃离宫殿。它可以通过机关来堵住任意一个的通道（任意时刻，只能堵住一个通道）。即无论何时，鳄鱼门卫堵住一个新的通道，则之前堵住的通道就会被打开。

Benjamas 逃离过程可以描述如下：每次她试图离开一个洞穴时，鳄鱼门卫都会封闭一条连接该洞穴的通道。Benjamas 只能选择没有被封闭的通道走到下一个洞穴。Benjamas 一旦进入一条通道，在她到达该通道的另一端前，鳄鱼门卫不能封闭这条通道。当 Benjamas到达下一个洞穴，鳄鱼门卫可以选择再封闭一条通道（可以是 Benjamas 刚刚走过的那条通道）。

Benjamas 需要设计一个逃生计划，确切地说，她希望有一系列指令告诉她如何逃生。

设 $A$ 是一个洞穴，如果 $A$ 是出口洞穴，Benjamas 可以直接逃生。否则，对洞穴 $A$，指令是下列形式中的一种：

- 在洞穴 $A$，优先选择一条通道到洞穴 $B$。如果该通道被封堵，则选择另一通道去洞穴 $C$。

- 不用考虑洞穴 $A$，按照逃生计划不会到达 $A$。

注意：数据保证不管鳄鱼门卫如何封闭通道，总能找到一个好的逃生计划保证 Benjamas 在有限时间内可以到达一个出口洞穴。在所有逃生计划中，在最坏情况下用时最短的逃生计划所用的时间定义为 $T$。

inputFormat:
第一行三个整数 $N$，$M$，$K$；

接下来 $M$ 行 每行三个整数 表示一条无向边的两端和长度（无重边）；

接下来 $K$ 个整数 表示出口洞穴。

outputFormat: 一个整数 最小时间 $T$。


title: [IOI2005] bir

description:
今天是 Byteman 的生日。有 $n$ 个孩子参加他的生日宴会（包括 Byteman ）。孩子们从 $1$ 到 $n$ 编号。Byteman 的父母准备了一张大圆桌并放了n把椅子在圆桌周围。孩子们来了就坐下。$1$ 号孩子坐其中一个，然后 $2$ 号孩子坐在他左边，然后 $3$ 号孩子坐在 $2$ 号左边，以此类推。最后 $n$ 号孩子坐在最后一个空椅子上，也就是 $n-1$ 号孩子和 $1$ 号孩子之间。

Byteman 的父母非常了解这些孩子，知道如果有些孩子坐在一起就会非常吵。因此他们将按特定顺序调整这些孩子的座位。用一个置换 $p_1,p_2,\cdots,p_n$ ($p_1,p_2,\cdots,p_n$是 $1$ 到 $n$ 的整数)来表示这个顺序。孩子 $p_1$ 将坐在 $p_2$ 和 $p_n$ 之间，孩子 $p_i$ ($ i = 2,3,…n-1$)将坐在孩子 $p_i-1$ 和 $p_i+1$ 之间，孩子 $p_n$ 将坐在孩子 $p_n-1$ 和 $p_1$ 之间。需要注意的是 $p_1$ 可以坐在 $p_n$ 左边也可以坐在 $p_n$ 右边。

让所有孩子按给定顺序做好，Byteman 父母必须让每个孩子绕圆桌向左或向右移动一些座位。他们必须决定每个孩子如何移动，也就是说它们必须决定一个方向，以及距离。对于给定的移动信号，所有孩子立刻站起来，移到合适的位置坐下。 串座过程使研会变得乱七八糟，乱七八糟值等于所有孩子中最大移动距离，孩子们可以以很多种方式移动，Byteman 父母将选择乱七八糟值最小的。帮他们找到这一种方案。

你的任务是写一个程序： 从标准输入读入孩子的数目和描述目标序列的那个置换。 算出最小的乱七八糟值。

inputFormat:
第一行包括一个整数 $n$ ($1 \le n \le 10^6$)。

第二行包括 $n$ 个整数 $p_1,p_2,\cdots,p_n$，以一个空格分开。$p_1,p_2,\cdots,p_n$ 是集合 $\{1,2,\cdots,n\}$ 的一个置换，描述目标顺序。

outputFormat: 一行包含一个整数：最小的乱七八糟值。


title: [IOI2005] mea

description:
考虑一个非递减的整数序列 $S_1,\cdots,S_{n+1}$ ($S_i \le S{i+1}$，$1 \le i \le n$)。 序列 $M_1 \cdots M_n$ 是定义在序列 $S$ 的基础上，关系式为 $M_i = \frac{S_i + S_{i+1}}{2  }$（$1 \le i < n$）, 序列 $M$ 叫做序列 $S$ 的平均数序列。

例如序列 $1,2,2,4$ 的平均数序列为 $1.5,2,3$. 注意到平均数序列中的元素可能为小数。但是本题的任务只是处理平均数序列都为整数的情况。

给出一个 $n$ 个数字的非递减的整数序列 $M_1,M_2,\cdots,M_n$。请你计算出：序列 $S_1,\cdots,S_{n+1}$ 的平均序列是 $M_1,\cdots,M_n$。 求满足以上条件的序列 $S$ 的总个数。

任务：从标准输入文件中读入一个非递减的整数序列。计算出平均序列是给出序列的整数序列的总个数。把计算结果写到标准输出文件中。

inputFormat:
输入文件的第一行包含一个整数 $n$ （$ 2 \le n \le 5 \times 10^6$）。

接下来的 $n$ 行包含了这个给出的整数序列 $M_1,\cdots,M_n$。第 $i+1$ 行包含一个整数 $M_i$ ( $1 \le m_i \le 10^9$)。

outputFormat: 输出文件仅一行，即所求答案。


title: [IOI2005] mou

description:
游乐园已经开始运行一个崭新的模拟过山车。模拟的轨道由 $n$ 段铁轨组成，并且首尾相连。第一段铁轨从高度 $0$ 开始。

操作员 Byteman 能通过调整连续几段的铁轨高度来改造这条轨道。在被改造的一段前面的铁轨高度不受影响。 每一次铁轨被调整。后面的轨必须升起或降低来保持连通，并保证起点高度为 $0$。下页举例说明轨道改造过程。 每次开始时车都有足够能量到达高度 $h$。也就是说，只要轨道的高度不超过 $h$，车就一直开下去, 甚至直到结束。

给出每天的运行和改造情况, 为每次运行计算在车停止前，到达的铁轨数。铁轨以一个 $n$ 个数的数列形式表示 ，一个数对应一段铁轨。第 $i$ 个 $d_i$ 表示在第 $i$ 段铁轨上的高度变化。也就是说，在到达铁轨 $i$ 前，如果车的高度是 $h$，那么经过铁轨i后，高度变为 $h+d_i$。

最初轨道是一条水平线。就是说对于所有的 $i$ 都是 $d_i=0$。运行和改造交错进行。 每个改造用三个数表示: $a$ ，$b$ 和 $D$。表示从 $a$ 到 $b$ (包括 $a$,$b$) 的所有 $d_i$ 改为 $d_i=D$。每次运行给定一个数字 $h$ ——车能到达的最大高度。

inputFormat:
输入的第一行包括一个正整数 $n$ ——铁轨的数目。

下面的行包括改造和运行，各有一个标识符：

- 改造——一个字母 `I`，和整数$a$,$b$,$D$ ,中间用一个空格隔开。
- 运行——一个字母 `Q`，和一个整数 $h$，用一个空格隔开。
- 一个字母 `E` ——结束符号，表示输入结束。

你可以假设任意时刻任意铁轨的高度在 $[1，1000000000]$ 区间内。

输入不超过 $10000$ 行。

outputFormat: 第 $i$ 行需包含一个整数， 即第 $i$ 次运行经过的铁轨数。


title: Hello, 2020!

background:
时针与分针重合在「零」的那一霎那，嘀嗒声便宣告了新一年的到来。

在过去的一年里，世事无常。屏幕面前的你可能不久前才听闻「OI」，也可能暂时地结束了竞赛生涯；可能在赛场上叱咤风云名列榜首，也可能独自承受着比赛失利的落寞。

无论如何，过去仍旧是过去，将来依然是将来。

以此题为开端，迎接你的 2020 吧！

description:
本场比赛有 $n$ 名出题人，$m$ 名选手。

出题人从 $1$ 至 $n$ 依次标号，选手从 $1$ 至 $m$ 依次标号。

比赛结束后选手的最终排名为 $1$ 至 $m$ 中其一，且互不相同。

报名结束后，第 $i$ 位出题人看了看报名列表，对其他出题人说：「我觉得只有这 $k_i$ 位选手有可能最终排名第一，他们分别是 $a_{i,1},a_{i,2},\dots,a_{i,k_i}$。其他人不可能最终排名第一。」

你面前屏幕上的这道题的出题人通过时空隧道，预先得知了谁是最终排名第一的选手。

出题人把这 $n$ 位出题人的预测都告诉了你，还告诉你恰好只有 $p$ 个出题人的预测是正确的。

请你求出哪些选手可能最终获得第一名，并以从小到大的顺序依次输出这些选手的编号。

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

第一行，三个正整数 $n,m,p$，表示出题人数，选手数，与正确预测数。

接下来 $n$ 行，每行第一个非负整数 $k_i$ 表示第 $i$ 位出题人预测可能最终排名第一的选手位数；接下来 $k_i$ 个正整数 $a_{i,1},a_{i,2},\dots,a_{i,k_i}$，表示这位出题人预测可能最终排名第一的选手编号。

outputFormat:
输出数据至标准输出中。

第一行，输出一个非负整数，表示可能最终获得第一名的选手个数。

第二行，以从小到大的顺序依次输出这些选手的编号。

hint:
子任务 1（$6\%$）：$n\leq 20$，$m\leq 20$。

子任务 2（$30\%$）：$n\leq 100$，$m\leq 100$，$\sum k_i \leq 10^4$。

子任务 3（$24\%$）：$n\leq 1000$，$m\leq 1000$。

子任务 4（$40\%$）：无特殊限制。

对于全部数据，$1\leq n\leq 10^5$，$1\leq m\leq 10^6$，$0\leq \sum k_i \leq 10^6$，$0\leq p\leq n$。


title: [IOI2015] boxes

description:
IOI2015 开幕式正在进行最后一个环节。按计划在开幕式期间，每个代表队都将收到由主办方发放的一个装有纪念品的盒子。然而所有志愿者都被精彩的开幕式所吸引，除 Aman 外其他人完全忘记了发放纪念品这件事。Aman 是一位热情的志愿者，为使得 IOI 尽量圆满，他要用最短的时间将所有纪念品发放出去。

开幕式的场地是一个圆环，被分为 $L$个完全相等的区域，这些区域的编号依次为 $0$ 到 $L-1$，也就是说，对于$0\le
 i\le L-2$,区域 $i$ 与区域 $i+1$ 相邻，且区域 $L-1$ 与区域 $0$ 相邻。场地上共有 $N$ 个代表队，每队坐在上面的一个区域上，每个区域可以包含任意多个代表队，也可以为空。

一共有 $N$ 个相同的纪念品。开始，Aman 和所有纪念品都在区域 $0$。Aman 应该给每队一个纪念品，并且在发放完最后一个纪念品后他必须回到区域 $0$。注意，有些队可能坐在区域 $0$。

在任意时刻，Aman 只能够携带至多 $K$ 个纪念品。Aman 必须从区域 $0$ 取走这些纪念品，且取纪念品不需要时间。纪念品一旦从区域 $0$ 被取走后，Aman 只能将其发放给某个代表队或者随身携带。无论何时，Aman 携带一个或更多的纪念品到达一个这样的区域，该区域有一个代表队尚未收到纪念品，Aman 便可将他携带的一个纪念品发给这个代表队。这种发放也在瞬间完成。他所花的时间都消耗在区域之间的移动上。无论携带多少纪念品，Aman 都需要 $1$ 秒钟从一个区域移动到其相邻的区域（可以顺时针移动也可以逆时针移动）。

你的任务是计算出 Aman 发放完所有纪念品并返回到他的最初区域所需要的最短时间（秒数）。

inputFormat:
- 第 $1$ 行有三个整数 $N$，$K$，$L$，分别表示 代表队的数目，Aman 每次最多能携带的纪念品数量 ，开幕式场地上的区域数目；
- 第 $2$ 行有 $N$ 个整数，分别为 $p[0],\cdots,p[N−1]$，其中 $p[i]$ （$0\le i\le N-1$）代表第 $i$ 支代表队所在区域编号。$p$ 的元素按非递减排序。

outputFormat: 共一行，Aman 所需要的最短时间（秒数）。


title: [IOI2015] teams

description:
班里有 $N$ 个学生,他们的编号为从 $0$ 到 $N-1$。每天，老师都有一些项目需要学生去完成。每个项目都需要由一组学生在一天内完成。项目的难度可能不同。对于每个项目，老师知道应该选择由多少学生组成的小组去完成。

不同的学生对小组的规模有不同的喜好。更准确地说, 对学生 $i$ 而言, 他只愿意在小组规模介于 $A[i]$ 和 $B[i]$ 之间（含 $A[i]$ 和 $B[i]$）的小组工作。每一天，一个学生最多只能被分配到一个小组工作。有些学生可能未被分配到任何小组中。每个小组只负责一个项目。

老师已选择好接下来 $Q$ 天中每一天的项目。对于每一天, 现需要判断是否有一种分配学生的方案，使得每个项目都有一个小组负责。

inputFormat:
- 第 $1$ 行有一个正整数 $N$，表示班内学生的数量；
- 第 $2$ 到 $N+1$ 行有两个 $A[i]$，$B[i]$；
- 第 $N+2$ 行有一个正整数 $Q$；
- 第 $N+3$ 到 $N+Q+2$ 行，包含一个正整数 $M$，表示当天要完成的项目数， 后有一个长度为 $M$ 的序列 $K$。$K[i]$ （$1\le i\le M$） 表示项目 $i$ 所需的小组规模。

outputFormat: 共 $Q$ 行，对于每一个问题, 你的程序必须输出是否存在一种小组分配的方案，可以完成当天的所有项目。若可以完成分组去完成当天所有的项目，输出 `1`, 否则，应输出 `0`。

hint: 对于 $100\%$ 的数据，$1\le N\le 5 \times 10^5$，$1\le Q\le 2 \times 10^5$， $\sum M \leq 2\times 10^5$。


title: [IOI2015] sorting

description:
Aizhan 有一个由 $N$ 个互不相同的整数组成的序列 $S[0],S[1],\cdots,S[N-1]$，其中 $S[i]$ 取值范围是 $[0,N-1]$。Aizhan 试图通过交换某些元素对的方法将这个序列按照升序排序。Aizhan 的朋友 Ermek 也想交换某些元素对， Ermek 的交换未必有助于 Aizhan 的排序。

Ermek 和 Aizhan 打算通过若干轮次来修改这个序列。在每一轮，Ermek 首先做一次交换，然后 Aizhan 做另一次交换。更确切地说，做交换的人选择两个有效的下标并交换这两个下标的元素。请注意这两个下标可能相同。如果它们相等，则对这个元素自身做交换，并不改变这个序列。

Aizhan 知道 Ermek 并不关心对序列
$S$ 排序的事情。Aizhan还知道 Ermek 将会选择哪些下标。Ermek 打算参加 $M$ 轮交换，将这些轮次从 $0$ 到 $M-1$ 编号。对于 $0$ 到 $M-1$ 之间的每个 $i$，Ermek 在第 $i$ 轮将选择下标 $X[i]$ 和 $Y[i]$ 的元素进行交换。

Aizhan 要对序列 $S$ 按升序进行排序。在每一轮之前，如果 Aizhan 看到当前的序列已经按升序排列，她将结束这个排序过程。给定初始序列 $S$ 以及 Ermek 要选择的下标，请你找出一个交换的序列，使得 Aizhan 能完成对序列 $S$ 的排序。此外，在有些子任务中，你还要找出尽可能短的交换序列来完成排序任务。题目保证通过 $M$ 或更少的轮次能够将序列 $S$ 排好序。

请注意如果 Aizhan 发现在 Ermek 的交换之后，序列 $S$ 已经排好序，则 Aizhan 可以选择交换两个相同下标（例如 $0$ 和 $0$）的元素。这样，序列 $S$ 在这一轮次之后也完成排序，于是也达到了 Aizhan 的目标。另外，如果初始序列 $S$ 就已经排好序，那么所需的最少排序轮数就是 $0$。

inputFormat:
- 第 $1$ 行有一个正整数 $N$，表示序列 $S$ 的长度；
- 第 $2$ 行有 $N$ 个正整数，分别为 $S[0],\cdots,S[N-1]$，即初始序列 $S$；
- 第 $3$ 行有一个正整数 $M$，表示 Ermek 打算做交换的次数；
- 第 $4$ 到 $M+3$ 行，有两个正整数 $X[i]$，$Y[i]$，表示对于 $0\le i\le M-1$, 在第 $i$ 轮 Ermek 打算交换下标为 $X[i]$ 和 $Y[i]$ 的数组。

outputFormat:
- 第 $1$ 行 : 交换的长度 $R$；
- 第 $2+i$（$0\le i < R$）行：$P[i]$，$Q[i]$。

注：$P$，$Q$分别为两个整数数组。利用这两个数组报告 Aizhan 完成对序列 $S$ 排序的一种可能的交换序列，假设这个交换序列的长度为 $R$，对于 $0$ 到 $R-1$ 之间的每个 $i$，Aizhan 在轮次 $i$ 选择的下标将被存入 $P[i]$ 和 $Q[i]$。 你可以假设数组 $P$ 和 $Q$ 均已分别被分配了
$M$ 个元素。

hint: 对于 $100\%$ 的数据，$1 \le N\le 2 \times 10^5$，$1 \le M \le 6 \times 10^5$。要求 $R$ 取最小值。


title: 「SWTR-8」补题计划

background: 因为写博客，小 A 欠下了很多题没有补。

description:
小 A 一共有 $n$ 道题目没有补。评估后，他认为第 $i$ 题的难度为 $x_i$。

同时，他对自己的水平有评估值 $w$。他的水平会波动，因此 $w$ 会改变。

小 A 认为补难度和自己水平相近的题目（相差不超过 $b_1$）能带来收益 $inc$；相反，如果相差过大（相差超过 $b_2$）则浪费了时间，导致负收益 $dec$。因此，补第 $i$ 道题的收益为

$$
\begin{cases}
inc & |x_i - w| \leq b_1 \\
0 & b_1 < |x_i - w| \leq b_2 \\
dec & |x_i - w| > b_2 \\
\end{cases}
$$

保证 $b_1 \leq b_2$ 且 $dec < 0 < inc$。

此外，小 A 有一些喜欢和讨厌的题。如果他没有补任何喜欢的题，或补了任何讨厌的题，就会不高兴。

小 A 将选择一段编号连续的题目进行补题。他希望补每道题的收益之和最大，并且补完题目后不会不高兴。请你告诉他这个最大值。

**任意询问之间独立**。

inputFormat:
第一行一个整数 $S$，表示该测试点的 Subtask 编号。

第二行七个整数 $n, q, w, b_1, b_2, inc, dec$，其中 $q$ 表示事件数量。

第三行 $n$ 个整数 $x_1, x_2, \cdots, x_n$。

接下来若干行，每一行或三行表示一次事件：

- 首先一个整数 $op\in \{1, 2\}$。
- 若 $op = 1$，则接下来两个整数 $l, h$，表示喜欢的题目数量和讨厌的题目数量；接下来一行 $l$ 个整数 $il_1, il_2, \cdots, il_l$，表示喜欢的题目编号；接下来一行 $h$ 个整数 $ih_1, ih_2, \cdots, ih_h$，表示讨厌的题目编号。保证任意 $il_i \neq ih_j$。
- 若 $op = 2$，则接下来一个整数 $w$，表示新的水平评估值。

outputFormat: 对于每次 $op = 1$ 的事件，输出一行一个整数表示答案。

hint:
**「样例解释」**

$w = 1$ 时，每道题目的收益分别为 $2, 2, -3, 0, -3, 2, 2$。

第一次询问必须要补第 $4$ 题，不能补第 $3$ 题，最优方案为 $[4, 7]$，收益为 $1$。

第二次询问必须要补第 $3$ 题或第 $4$ 题，最优方案为 $[1, 7]$，收益为 $2$。

第三次询问必须要补第 $2$ 题或第 $4$ 题，最优方案为 $[1, 2]$，收益为 $4$。

$w = 1064$ 时，所有题目的收益均为 $-3$。

第四次询问必须要补第 $1$ 题，最优方案为 $[1, 1]$，收益为 $-3$。

$w = 5$ 时，每道题目的收益分别为 $-3, -3, 2, 2, 0, 0, 0$。

第五次询问必须要补第 $2$ 题或第 $7$ 题，不能补第 $4$ 题和第 $6$ 题，最优方案为 $[7, 7]$，收益为 $0$。

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

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

- Subtask #1（7 points）：$n, q\leq 100$。
- Subtask #2（12 points）：$n, q\leq 500$。依赖 Subtask #1。
- Subtask #3（20 points）：$n, q\leq 4 \times 10 ^ 3$。依赖 Subtask #2。
- Subtask #4（25 points）：$w, x_i \leq 100$。
- Subtask #5（11 points）：$l = 1$，$h = 0$。
- Subtask #6（15 points）：$w, x_i \leq 10 ^ 5$。依赖 Subtask #4。
- Subtask #7（10 points）：无特殊限制。依赖 Subtask #3，#5，#6。

对于 $100\%$ 的数据：

- $1\leq n, q \leq 10 ^ 5$。
- $0\leq w, x_i \leq 10 ^ 9$，$0\leq b_1 \leq b_2$ 且 $b_2$ 不大于 $w, x_i$ 上界的一半。
- $-10 ^ 4 \leq dec < 0 < inc \leq 10 ^ 4$。
- $1\leq l, il_i, ih_j \leq n$，$0 \leq h < n$，$l + h\leq 5$。
- 保证 $il$，$ih$ 递增，且一组询问每个下标至多出现一次。

**「帮助与提示」**

请注意 IO 优化。

**「题目来源」**

- [Sweet Round 8](https://www.luogu.com.cn/contest/73382) C
- Idea & Solution：[tzc_wk](https://www.luogu.com.cn/user/115194)。
- Tester：[Alex_Wei](https://www.luogu.com.cn/user/123294) & [chenxia25](https://www.luogu.com.cn/user/138400)。


title: [SEERC2018] Numbers

description: 一个回文数是一个正着写和倒着写得到的数字相等的整数。例如，数字 $142241$ 和数字 $102201$ 都是回文数，但数字 $1023401$ 和 $10510$ 不是。你想将一个数字 $n$ 分解成两个回文数之和的形式，请计算分解成上述形式的方案数。

inputFormat: 仅一行包含一个整数 $n \ (1 \leq n \leq 10^{18})$。

outputFormat: 输出一个整数，代表将 $n$ 分解为两个回文数之和的方案数。


title: [SEERC2018] Broken Watch

description:
一架 UFO 坠毁在地球上。外星人船长幸免于难，但他的手表没能逃过这一劫。

外星人的手表和人类的手表非常相似：手表有一个直径为 $\text{30 mm}$ 的表盘，有三个表针，长度分别为 $A, B$ 和 $C \ (1000 \leq A, B, C \leq 15000)$ 微米。然而，外星人有不同的时间单位：$1$ 分钟里有 $N \ (2 \leq N < 2^{32})$ 秒。因此，表盘的边缘上有 $N$ 个刻度而不是 $60$ 个。

手表的玻璃面板已经摔碎，表针也松了：它们可以独立地自由旋转。让三个表针分别指向任意刻度，以表针的尖端的顶点可以构成一个三角形（表针不共线的前提下）。

在救援来之前外星人闲着没事干，就思考起了这样一个问题：按上述方法构成的三角形中，有多少个三角形包含了表盘的中心（答案记为 $M$）。（表盘中心在三角形的某一边上的三角形也要统计。）

inputFormat: 仅一行包含整数 $A, B, C$ 和 $N$，四个数字之间用一个半角空格隔开。

outputFormat: 输出 $M \bmod 2^{64}$ 的值。


title: 传球游戏

background:
羊城有善蹴鞠者。会足协之杯，于校园之东北角，施两球场，蹴鞠者站球场中，$n$ 人，一球，二门，三裁判而已。观众团坐。少倾，但闻球场中哨声一响，满坐寂然，无敢哗者。

当是时，传球声，微微风声，队员疾跑声，教练呼喊声，拉拉队助威声，一时齐发，众妙毕备。满场观众无不伸颈，侧目，微笑，默叹，以为妙绝。

未几，我球员施一长传，彼球员截之，望我龙门冲来。

但见守门员 oql 立于门，若有所思——

description:
**原来他在想这么一个问题：**

场上的 $n$ 个球员围成一圈，编号从 $1$ 到 $n$ ，刚开始球在 $1$ 号球员手中。一共 $m$ 次传球，每次传球必须传给一个人，但不能传到自己手中。求第 $m$ 次传球以后传回 $1$ 号球员的方案数。

但他觉得这个问题太简单了，于是加了 $k$ 条限制，每条限制形如 $a,b$，表示 $a$ 号球员不能将球传给 $b$ 号球员。

为了使得 oql 的注意力转移回球场上，你需要在最短的时间内告诉他这个方案数是多少。

你只需要告诉他答案对 $998244353$ 取模后的结果。

inputFormat:
输入数据包括 $k+1$ 行：

第一行三个整数 $n,m,k$，分表代表球员数，传球次数，限制条数。

接下来 $k$ 行，每行两个整数 $a_i,b_i$，表示 $a_i$ 号球员不能将球传给 $b_i$ 号球员。

数据保证不会出现不同的 $i,j$ 使得 $a_i=a_j$ 且 $b_i=b_j$。

outputFormat: 输出一个整数，表示 $m$ 轮后传回 $1$ 号球员的合法方案数对 $998244353$ 取模后的结果。

hint:
对于 $10\%$ 的数据，$k=0$。

对于另外 $15\%$ 的数据，$n\leq 500$。

对于另外 $20\%$ 的数据，$n\leq 5\times 10^4$。

对于另外 $20\%$ 的数据，$k\leq 300$。

对于 $100\%$ 的数据，$1\leq n\leq 10^9$，$0\leq m\leq 200$，$0\leq k \leq \min(n\times(n-1),5\times 10^4)$，$1\leq a_i,b_i\leq n$，**不保证 $a_i,b_i$ 不相等**。


title: 【模板】笛卡尔树

description:
给定一个 $1 \sim n$ 的排列 $p$，构建其笛卡尔树。

即构建一棵二叉树，满足：

1. 每个节点的编号满足二叉搜索树的性质。
2. 节点 $i$ 的权值为 $p_i$，每个节点的权值满足小根堆的性质。

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

第二行一个排列 $p_{1 \dots n}$。

outputFormat:
设 $l_i,r_i$ 分别表示节点 $i$ 的左右儿子的编号（若不存在则为 $0$）。

一行两个整数，分别表示 $\operatorname{xor}_{i = 1}^n i \times (l_i + 1)$ 和 $\operatorname{xor}_{i = 1}^n i \times (r_i + 1)$。


title: [SEERC2018] Tree

description: 给定一棵 $n$ 个点的树，点的编号从 $1$ 到 $n$。每个点有黑色或白色的颜色。选出恰好 $m$ 个黑点，使得黑点两两之间的距离的最大值最小。输出这个最小的最大值。

inputFormat:
第一行包含两个整数 $n$ 和 $m \ (1 \leq m \leq n \leq 100)$，代表树的点数和要选出的黑点数量。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n \ (0 \leq p_i \leq 1)$。如果 $p_i=1$ 则点 $i$ 是黑色的，否则是白色的。数据保证黑点有不少于 $m$ 个。

接下来 $n-1$ 行每行包含两个整数 $v_i$ 和 $u_i \ (1 \leq v_i, u_i, \leq n)$，代表树上有一条连接点 $v_i$ 和 $u_i$ 的边。数据保证这些边构成一棵树。

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

hint:
第一个样例中，唯一的选法是选点 $1, 2$ 和 $4$，距离的最大值为 $2$。

第二个样例中，可行的一种选法是选点 $1, 3, 8$ 和 $9$，最大的距离是点 $3$ 和 $9$ 的距离。


title: [SEERC2018] Space Station

description:
Jones 实现了他的梦想：他加入了国际空间站（ISS）的一次任务。他接受了他的第一个任务：检查空间站上的电子设备的工作状况。

ISS 被分为 $N$ 个模块，模块从 $1$ 到 $N$ 编号。Jones 发现，为了提高效率，空间站的设计使任意两个模块之间仅存在一条简单路径。在一次太阳耀斑活动中，连接两个模块的双向通道很容易受到辐射影响。检查一条通道 $i$ 的状况必须花费 $C_i$ 的时间。Jones 需要找到一条从模块 $1$ 出发，经过每条通道至少一次，再回到模块 $1$ 的最快路径。

除了从模块之间的通道中通过之外，Jones 还可以穿上宇航服，跳出空间站，从外面直接从某一模块移动到任意模块上，但是这种方法只能进行最多 $M$ 次。Jones 假设进行一次需要花费固定的时间 $K$。

inputFormat:
第一行包含一个整数 $T$，代表测试组数。

每个测试组中，第一行包含三个整数 $N, M, K \ (1 \leq N, M \leq 1000)$，接下来 $N-1$ 行每一行包含三个整数 $A, B, C \ (1 \leq A \leq B \leq N; 0 \leq C,K \leq 10^6)$，代表在模块 $A$ 和 $B$ 之间有一条通道，检查它需要花费 $C$ 时间。

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


title: [SEERC2018] Fishermen

description:
大海可以看成平面直角坐标系下的第一象限。海里有 $n$ 条鱼，每个鱼有一个二维坐标。一个点上可能有多条鱼。

海边有 $m$ 个渔夫，每个渔夫有一个 $x$ 坐标，而他们的 $y$ 坐标都是 $0$。

每个渔夫都有一根长为 $l$ 的钓竿，因此，他能钓到与他距离不超过 $l$ 的鱼。一个 $x$ 坐标为 $x$ 的渔夫和一条坐标为 $(a,b)$ 的鱼之间的距离为 $|a-x|+b$。

分别计算出对于每个渔夫，他可以钓到多少条鱼。

inputFormat:
第一行包含三个整数 $n, m$ 和 $l \ (1 \leq n,m \leq 2 \cdot 10^5, 1 \leq l \leq 10^9)$，代表鱼的数量、渔夫的数量和钓鱼竿的长度。

接下来 $n$ 行每行包含两个整数 $x_i$ 和 $y_i \ (1 \leq x_i, y_i \leq 10^9)$，代表每条鱼的坐标。

接下来一行包含 $m$ 个整数 $a_i \ (1 \leq a_i \leq 10^9)$，代表每个渔夫的 $x$ 坐标。

outputFormat: 对于每个渔夫，输出一行答案。


title: [SEERC2018] Min Max Convert

description:
$A$ 是一个有 $N$ 个元素的数列。你可以对这个数列进行以下两种操作：

1. 选出一个下标的区间 $[a, b] \ (1 \leq a \leq b \leq N)$，设数列中在这个下标区间中的元素的最大值为 $x$，将这个下标区间中的所有元素替换为 $x$。
2. 选出一个下标的区间 $[a, b] \ (1 \leq a \leq b \leq N)$，设数列中在这个下标区间中的元素的最小值为 $x$，将这个下标区间中的所有元素替换为 $x$。

计算出一组操作方案，使数列 $A$ 变为另一个给定的数列 $B$（也有 $N$ 个元素）。方案中操作的数列必须小于等于 $2N$。

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

第二行包含一个有 $N$ 个元素的数列 $A$。

第三行包含另一个有 $N$ 个元素的数列 $B$。

outputFormat: 如果无解，输出 $-1$。否则在第一行输出一个整数 $x$，代表将数列 $A$ 变为 $B$ 所需的最小操作数量。接下来 $x$ 行每行包含一个字符（代表操作的类型，`m ` 代表使用了最小值的操作，`M` 代表使用了最大值的操作）和一个区间 $(a,b)$，描述了所需的每次操作信息。如果有多解，任意输出一组即可。

hint:
- $1 \leq N \leq 100, 000$
- 数列 $A$ 和 $B$ 中的元素都是区间 $[1, N]$ 中的整数


title: [SEERC2018] Matrix Queries

description:
给定一个 $2^n \times 2^n$ 的矩阵，最开始每个格子都是白色的。格子的颜色可以是白色或黑色。定义一个矩阵的*价值*为：

1. 如果矩阵是单色的，则它的价值为 $1$ 金币；
2. 否则，将矩阵分割成 $4$ 个大小相等的子矩阵，矩阵的价值为子矩阵的价值之和加 $1$ 金币。

给定 $q$ 个询问，每个询问给定一个行/列的编号 $x$，你需要改变这一行/列中每个格子的颜色（黑色变为白色，白色变为黑色），然后计算出改变之后的新矩阵的*价值*。

inputFormat:
第一行包含两个整数 $n$ 和 $q \ (0 \leq n \leq 20, 1 \leq q \leq 10^6)$，代表矩阵的大小为 $2^n \times 2^n$ 以及有 $q$ 个询问。

接下来 $q$ 行每行包含两个整数 $t$ 和 $x \ (0 \leq t \leq 1, 1 \leq x \leq 2^n)$。如果 $t=0$，则改变第 $x$ 行的颜色；否则，改变第 $x$ 列的颜色。

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


title: [SEERC2018] Modern Djinn

description:
你不是一个 leader，你是一个 president。幸运的是，你有一只精灵，能够实现你的愿望。你的其中一个愿望就是假装你的社会中有 democracy。

社会很简单。社会里有 $N$ 个人，编号从 $1$ 到 $N$，一些人“开心”而另一些很平常（“不开心”）。人类这种生物非常奇妙，人们只在别人不开心时才感到开心。人们共有 $M$ 个愿望，编号从 $1$ 到 $M$，$X \rightarrow Y$代表 $X$ 想要 $Y$ 不开心。一个人 $X$ 是开心的当且仅当他的至少一个愿望得到满足。

Democracy 也没那么复杂。有些人说为了实现 democracy，你需要至少一半的人是开心的（或一半的愿望得到满足），但这不全是事实。我刚才说过，你是一个好的 president，而不是一个好的 leader。你可以通过媒体来定义 democracy。因此，在所有的 $M$ 个愿望中，你决定实现至少 $\lfloor M/4 \rfloor +1$ 个愿望。

剩下的事情就是选出你想实现的愿望，然后精灵会处理好一切。

inputFormat:
输入包含多组测试数据。第一行包含一个整数 $T$，代表测试数据的组数。接下来的输入中会按顺序给出每组测试数据。

在每组测试数据中，第一行包含两个正整数 $N$ 和 $M$，代表社会中人的数量和愿望的数量。接下来 $M$ 行每行包含两个整数 $X, Y$，描述了一个愿望：$X$ 希望 $Y$ 不开心。

outputFormat: 对于每组测试数据，第一行输出一个整数 $K$，代表实现的愿望的数量，第二行输出 $K$ 个整数，代表实现的愿望编号，输出的顺序不做限制。

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

- $1 \leq T \leq 10, 000$
- $2 \leq N \leq 100,000$
- $1 \leq M \leq 200,000$
- 不存在 $X$ 希望 $X$ 不开心这样的愿望。
- 可能存在多个相同的 $X$ 希望 $Y$ 不开心的愿望。
- 每组数据保证解一定存在。
- 输出任何正确的解都可以。

**【样例解释】**

第一组测试数据中，我们可以实现最多 $1$ 个愿望，输出任意一个愿望都是可行的。

第二组测试数据中，另外一个可行的解是实现愿望 $1, 3$ 和 $4$，最少需要实现 $2$ 个愿望。


title: [SEERC2018] Inversion

description:
定义一个长为 $n$ 的*排列*为一个序列 $p_1, p_2, \dots, p_n$，其中 $[1, n]$ 范围内的整数都恰好在这个序列中出现一次。定义排列中的一个*逆序对*为一对整数 $(i, j)$，其中 $i, j \in [1,n]$，且满足 $i<j, p_i>p_j$。

定义一个*逆序对图*为一个有 $n$ 个点的图，图中存在一条 $(i, j)$ 的边当且仅当 $(i,j)$ 是一个逆序对。

定义一个图中的*独立集*为一个图中点的集合，满足集合中的点两两之间没有边相连。定义一个图中的*支配集*为一个图中点的集合，满足不在这个集合中的点都与集合中的某个点有边相连。定义一个图中的*独立支配集*为一个图中点的集合，这个集合既是独立集又是支配集。

给定某一个长为 $n$ 的排列的逆序对图，请计算出这个图中独立支配集的数量。

数据保证答案不会超过 $10^{18}$。

inputFormat:
第一行包含两个整数 $n$ 和 $m \ (1 \leq n \leq 100, 0 \leq m \leq \frac{n \times (n-1)}{2})$，代表图中的点数和边数。

接下来 $m$ 行每行包含两个整数 $u_i$ 和 $v_i \ (1 \leq u_i, v_i \leq n)$，代表图中点 $u_i$ 和 $v_i$ 之间有一条边相连。

数据保证图一定对应某一个排列。

outputFormat:
输出图中独立支配集的数量。

数据保证答案不会超过 $10^{18}$。


title: 蝴蝶与花

background:
Amazing John 做了一个梦，梦到他上辈子是只苍茫蝶。

深壑幽兰，雨落苍茫。

怜其折翅，苦其执魔。

琼片织翼，花露饯行。

伶仃蝶碎，兰枯有情。

君不识妾，妾仍思君。

description:
Amazing John 很喜欢花。

Amazing John 的花圃里有 $n$ 朵花，他每天都会在花园里散步。

对于每一朵花 Amazing John 会评价它好看或不好看。被评价好看的花的美丽值为 $2$，被评价不好看的花的美丽值为 $1$。

我们可以抽象的把这 $n$ 朵花看做在一条直线上。每次散步时， Amazing John 会从任意一朵花开始，一直往下一朵花走。到任意一朵花结束。在路途中，他会将所有经过的花的美丽值统计下来。（当然包括开始的花和结束的花）

现在 Amazing John 想知道，能否有一种散步方案，使得他从第 $l$ 朵花走到第 $r$ 朵花的美丽值之和正好是 $s$？

为了少走一些路， Amazing John 要你给出在所有方案中 $l$ 最小的方案。

当然，为了避免在花圃中散步过于单调， Amazing John 随时可能会将一朵花的美丽值更改。

每个询问之间互相独立，即统计过的花朵在下次询问时仍可被统计。

inputFormat:
第一行两个数 $n,m$，分别表示花的个数和 Amazing John 的要求个数。

第二行 $n$ 个数字 $a_i$，表示第 $i$ 朵花的美丽值。

接下来 $m$ 行，每一行表示一个询问操作或一个修改操作。

询问操作格式为 `A s`，表示询问是否有一种散步方案使得美丽值之和为 $s$。

修改操作格式为 `C i val`，表示将第 $i$ 朵花的美丽值改成 $val(val=1$ 或 $2)$。

outputFormat:
若有 $q$ 个 `A` 操作，输出应有 $q$ 行。

对于每一个询问，若有合法的方案，输出这个方案的左右端点位置（多种方案时输出左端点最小的方案），否则输出 `none`。

您应该保证 $1\leq l\leq r\leq n$。

hint:
$\operatorname{Subtask\ 1}\ (20pts)$：对于数据点 $1\sim 5$，满足 $1\leq n,m\leq 1000$。

$\operatorname{Subtask\ 2}\ (30pts)$：对于数据点 $6\sim 10$，满足 $1\leq n,m\leq 2.5\times 10^5$。

$\operatorname{Subtask\ 3}\ (50pts)$：对于数据点 $11\sim 15$，满足 $1\leq n,m\leq 2\times 10^6$。

对于 $100\%$ 的数据，有 $1\leq n,m\leq 2\times 10^6,0\leq s\leq 2^{31}-1$。每次修改操作时 $i\in[1,n],val\in\{1,2\}$。

对于所有数据点，时间限制 $2000\operatorname{ms}$，空间限制 $256\operatorname{MB}$。


title: [SEERC2018] Rabbit vs Turtle

description:
一只兔子和一只乌龟决定赛跑。由于乌龟来自 Craiova 而兔子来自 Ardeal，乌龟比兔子跑得快的多。我们的目标是帮助兔子赢得比赛。

比赛在一个 $N$ 个点 $M$ 条边的图上进行，比赛在点 $1$ 开始，点 $N$ 结束。比赛前，兔子和乌龟都要先选出一条比赛时他们各自使用的路径。因此，他们知道这个图的情况和经过图上每条边的时间。

乌龟可能跑的比兔子快，但他还是一只乌龟（后文叫做 George）。George 会在他的路径上选出一些点来睡一会。如果某一时刻他知道了兔子在作弊，George 就不再睡觉，直到完成比赛。

兔子（后文叫做 Stan）只有一个优势，他的一个祖祖祖……祖母是一只狐狸，因此他也有狡猾的一面。Stan 并不打算按照他选好的路径来比赛（但 George 会按照路径比赛）。他计划在某一点更改路线，直接通过最短路径到达点 $N$。唯一的问题是他必须做出明智的选择，因为 George 一旦发现 Stan 在作弊，就会不再睡觉，这是不利的。

Stan 只能在到达一个点后更改路线（还在边上移动的时候是不能更改的）。他并不知道 George 的休息计划，但你知道！计算出 Stan 可以更改路线并赢得比赛的时间点数量。当 Stan 开始作弊的时候，George 只要没有在睡觉，就会立即察觉到。如果那时 George 在睡觉，则他醒来的时候才会察觉。

inputFormat:
第一行包含两个整数 $N$ 和 $M$。接下来 $M$ 行用 $(A,B,T,R)$ 的格式来描述图中的边：有一条边连接点 $A$ 和 $B$，乌龟经过这条边需要花费 $T$ 时间，兔子需要花费 $R$ 时间。边按输入顺序从 $1$ 到 $M$ 编号。

接下来一行包含一个整数 $P_T$，代表 George 路径上的边数。接下来 $P_T$ 行用 (边的编号, 睡眠时间) 来描述路径上的边：路径上有一条给定编号的边，在经过这条边后，George 会睡一会，睡眠时间给定。最后一条边的睡眠时间是没有意义的，因为 George 已经到终点了。

接下来一行包含一个整数 $P_R$，代表 Stan 最开始选择的路径上的边数。最后一行包含 $P_R$ 个整数，代表 Stan 最开始路径上的边的编号。

outputFormat: 输出第一行包含一个整数 $x$，代表 Stan 可以开始作弊的时间点（也就是开始作弊所在的点）数量。第二行包含 $x$ 个递增顺序的整数，代表 Stan 可以开始作弊的点的编号。

hint:
- $2 \leq N \leq 100,000$
- $1 \leq P_R, P_T < 100,000$
- $1 \leq M \leq 200,000$
- $1 \leq T,R \leq 1,000,000,000$
- $0 \leq$ 睡眠时间 $\leq 1,000,000,000$
- 数据保证按照正确的顺序描述比赛路径上的边（即相邻两条边终点、起点相同）。
- 数据保证乌龟路径上的点不重复。
- 数据保证兔子路径上的点不重复。
- 如果兔子和乌龟同时到达终点，认为兔子赢了。
- 如果兔子在乌龟开始睡觉的时候开始作弊，那么乌龟会睡着，醒来时才察觉兔子在作弊。
- 认为兔子在作弊当且仅当他改变了路径且新路径严格快于原来的路径（否则就没必要作弊了）。
- 作弊路径可能与原始路径有相同的点。唯一的要求是在开始作弊的时候，兔子前往和原路径不同的点。在某些情况中，他也可能会回到之前经过的点。


title: [SEERC2018] Points and Rectangles

description:
给定一个空的二维平面，给定 $q$ 次询问。询问有两种类型：

- $1 \ x \ y$ — 向平面中添加一个坐标为 $(x,y)$ 的点。
- $2 \ x_1 \ y_1 \ x_2 \ y_2$ — 添加一个左下角坐标为 $(x_1,y_1)$、右上角坐标为 $(x_2,y_2)$ 的矩形。矩形的面积可以是 $0$，矩形也可以退化成一个点。

矩形和点可能会重叠。

每次询问操作完成之后，计算出使点在矩形内部或边上的点-矩形对数。

inputFormat:
第一行包含一个整数 $q \ (1 \leq q \leq 10^5)$，代表询问数。

接下来 $q$ 行每行描述一个询问：

- $1 \ x \ y \ (1 \leq x,y \leq 10^9)$ — 向平面中添加一个坐标为 $(x,y)$ 的点。
- $2 \ x_1 \ y_1 \ x_2 \ y_2 \ (1 \leq x_1 \leq x_2 \leq 10^9, 1 \leq y_1 \leq y_2 \leq 10^9)$ — 添加一个左下角坐标为 $(x_1,y_1)$、右上角坐标为 $(x_2,y_2)$ 的矩形。

outputFormat: 你需要输出 $q$ 行，第 $i$ 行包含一个整数，代表使点在矩形内部或边上的点-矩形对数。

hint:
第一个样例的解释：

第一次询问操作后，平面上有一个点 $(2,3)$，但没有矩形，因此没有满足条件的点-矩形对。

第二次询问操作后，平面上仍然没有矩形，因此仍然没有这样的对。

第三次询问操作后依然没有矩形。

在第四次询问中，我们向平面中添加了一个左下角为 $(1,1)$、右上角为 $(5,5)$ 的矩形。之前添加的所有的点都在这个矩形中，因此这样的对有 $3$ 个。

第五次询问操作后，我们有 $4$ 个这样的对：上面的 $3$ 对，以及第二次询问插入的点在第五次询问插入的矩形中新增的 $1$ 对。


title: [RC-02] XOR

background: FangZeLi 喜欢异或，所以就有了这道题（然而这并不是他出这种题的理由）。

description:
**注意，本题中一切 $\sum$ 均表示求异或和！**

一棵 $n$ 个节点，$n-1$ 条边的有根树，初始时以 $1$ 节点为根。

这棵树上的每个节点 $i$ 都有其点权 $V_{i}$。

令函数 $\operatorname{Xor}(x)=\sum_{y\in  \operatorname{Subtree}(x)}{V_{y}}$，其中 $\operatorname{Subtree}(x)$ 表示 $x$ 的子树。

现需支持以下五种操作：

1. `1 x`，表示将 $x$ 换为根，且查询 $\sum_{i=1}^{n}{\operatorname{Xor}(i)}$。
2. `2 x y`，表示令 $V_{x}=y$。
3. `3 x y` ，表示查询 $\operatorname{LCA}(x,y)$。
4. `4 x y`，表示查询 $x$ 到 $y$ 路径上的点的点权异或和。
5. `5 x`，表示查询 $\operatorname{Xor}(x)$。

inputFormat:
第一行三个整数，$n,m,q$，分别表示节点数，$1$ 操作个数，其余操作个数。

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

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

接下来 $m+q$ 行，每行两到三个整数，第一个数为操作序号，接下来为相应的操作。

outputFormat: 若干行，表示 $1,3,4,5$ 操作的结果。


title: [CSGRound3] 出游

description:
学校组织了一次暑期出游活动，报名将在第 $T$ 天截止。

一共有 $n$ 位同学，第 $i$ 位同学有 $a_i$ 位朋友。朋友关系是单向的，换句话说，小 Z 有一个朋友是小 Y，并不意味着小 Y 一定也有一个朋友是小 Z。另外，自己也可能是自己的朋友。

第 $0$ 天时，每位同学会决定自己是否参加活动。第 $i$ 位同学有 $p_i$ 的概率决定参加，$1-p_i$ 的概率决定不参加。

接下来的 $T$ 天里，每位同学会重新决定自己是否参加活动。第 $i$ 位同学这一天决定参加活动，当且仅当至少有一个他的朋友在前一天决定参加，否则便不参加。

你需要求出参加活动的同学人数期望，答案对 $998244353$ 取模。

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

接下来 $n$ 行，每行首先两个整数 $p_i, a_i$，$p_i$ 表示模 $998244353$ 意义下第 $i$ 位同学在第 $0$ 天决定参加的概率，$a_i$ 表示他的朋友数量，接下来 $a_i$ 个整数，表示他的朋友。

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

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

| 天数 | 第一位同学去的概率 | 第二位同学去的概率 | 第三位同学去的概率 |
| :--: | :----------------: | :----------------: | :----------------: |
| $0$  |        $1$         |        $0$         |     $\frac 12$     |
| $1$  |    $\frac 12 $     |    $\frac 12 $     |        $0$         |

---

**【数据范围】**

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

- Subtask 1（3 points）：$T = 0$。
- Subtask 2（14 points）：$T = 1$。
- Subtask 3（33 points）：$n \le 10$。
- Subtask 4（20 points）：$T \le 5 \times 10^3$。
- Subtask 5（15 points）：$n \le 100$。
- Subtask 6（15 points）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 500$，$0 \le T \le 10^9$，$0 \le p_i < 998244353$，$0 \le a_i \le n$ 且朋友互不相同。


title: Ringed Genesis

background: Enzyme runs through the Ringed Genesis，just like Rabbit runs through a Ring.

description:
有一个长长的环，环由 $n$ 个格子首尾相接形成，依次编号 $0$ 至 $n-1$。

还有一种动物——兔子。兔子的步长为 $k$。若兔子当前在第 $i$ 个格子，那么下一秒它将跳到第 $(i+k)\bmod n$ 个格子。

现在有 $m$ 只兔子，第 $i$ 只兔子的初始格子为第 $p_i$ 个格子。随着时间的流逝，有些格子被兔子经过了，有些却一直没有被兔子经过。

你需要求出的是，有多少个格子永远不可能被兔子经过。

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

第一行，三个正整数 $n,m,k$，表示环长，兔子数，步长。

第二行，$m$ 个非负整数 $p_1,p_2,\dots,p_m$，表示兔子的初始格子。

outputFormat:
输出数据至标准输出中。

共一行，一个整数，表示答案。

hint:
子任务 1（$10\%$）：$k=1$。

子任务 2（$20\%$）：$k|n$，也即 $\gcd(k,n)=k$。

子任务 3（$25\%$）：$1\leq n\leq 1000$，$1\leq m\leq 1000$。

子任务 4（$45\%$）：无特殊限制。

对于全部数据，$1 \leq n \leq 10^6$，$1 \leq m \leq 10^6$，$1 \leq k \leq n$。


title: 化简单词

description:
最近情报人员得到了一些经过加密的文章，每个单词都很长。破译人员想到先把单词化简一下，方法是把每个单词尽量取短些的前缀，但所取的前缀不能是其他单词的前缀。

这个任务现在就交给你来完成。

解释：“字符串 $\text{S}_1$ 是 $\text{S}_2$ 的前缀”是说把字符串 $\text{S}_2$ 的后面去掉某些，只保留与 $\text{S}_1$ 相同长度时，$\text{S}_2$ 就与 $\text{S}_1$ 完全相同。如：$\texttt{abc}$ 是 $\texttt{abcaade}$ 和 $\texttt{abc}$ 的前缀，但不是 $\texttt{abadc}$ 的前缀。

inputFormat:
第一行一个整数 $N$，表示单词的个数。

下面有 $N$ 行，每行一个单词。

outputFormat: 共 $N$ 行，每行一个单词，对应上面的 $N$ 个单词化简后的单词。

hint:
对于 $100\%$ 的数据，$1 \le N \le 50$，每个单词长度不超过 $50$，并且都是由小写字母构成。

保证所给单词没有一个单词是另一个单词的前缀。


title: 棋盘游戏

description:
为了增强幼儿园小朋友的数数能力，小虎老师给了一个家庭游戏作业。让小虎那一块空的围棋盘，随机在一些方格中放些棋子（有黑白两种颜色），如果一个方格和它的上、下、左、右四个方格之一有相同颜色的棋子，则认为两个格子是相互连通的。这期间，要求小虎不断统计共有多少个连通块。

如下图是一个 $5\times 9$ 的一块棋盘，其中 `.` 表示空格，`*` 表示黑棋子，`@`表示白棋子。

则有 $4$ 块连通子块。
```
.  .  .  .  .  .  .  .  .
.  .  *  *  .  .  @  @  .
.  *  *  @  @  .  @  @  .
.  .  *  @  .  .  *  .  .
.  .  .  .  .  .  .  .  .
```

哥哥大虎在一边看一边想，如果棋盘是 $N\times N$ 的，共放了 $M$ 个棋子，如何使用计算机解决这个问题呢？

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

接下来有 $M$ 行，每行三个整数：$c, x, y$。分别表示依次放入棋子的颜色（$0$ 表示白色，$1$ 表示黑色）、要放入格子的横坐标和格子的纵坐标。

outputFormat: 共 $M$ 行。第 $i$ 行一个整数，表示放入第 $i$ 个棋子后，当前有多少个棋子连通块。

hint:
对于 $30\%$ 数据：$1\le N \le 10$。

对于 $60\%$ 数据：$1\le N\le 100$。

对于 $100\%$ 数据：$1\le N\le 500$，$1\le M \le N \times N$，$ 0 \le c \le 1$，$ 1\le x, y \le N$。


title: 奖品

description:
学校刚开完运动会，准备为尽可能多的同学评奖，并为每个人颁发一份奖品。一份奖品包括 $N$ 个物品，如：$5$ 支铅笔、$10$ 本练习薄等。每份奖品完全一样。虽然学校的保管室里还有一些办去年运动会后剩余的物品。在商店里，每种物品都有很多，但是，只有两种包装：大盒或小盒，并且不拆开买。

现在的问题是，充分利用这 $M$ 元钱，最多可准备多少分这样的奖品？

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

下面有 $N$ 行，每行有六个正整数 $x,y,sm,pm,sv,pv$，分别表示一种物品的相关数据：

* $x$，一份奖品中，这种物品需要的件数。
* $y$，这种物品去年剩余的件数。
* $sm$，这种物品小包装的件数。
* $pm$，这种物品小包装的一盒价格。
* $sv$，这种物品大包装里的件数。
* $pv$，这种物品大包装的一盒价格。

outputFormat: 一个整数，最多可准备的礼品份数。

hint:
对于全部的数据，满足：

$1 \le N \le 100$，$1 \le M \le 10^5$。

$10 \le x, pm \le 100$，$1 \le y, sm \le 100$，$sm < sv \le 100$，$pm<pv\le 100$。


title: 放棋子

description:
小虎刚刚上了幼儿园，老师让他做一个家庭作业：首先画 $3$ 行格子，第一行有三个格子，第二行有 $2$ 个格子，第三行有 $1$ 个格子。每行的格子从左到右可以放棋子，但要求除第一行外，每行放的棋子数不能超过上一行的棋子。第一行的棋子数不能为 $0$，但剩下行可以为空。玩了一会儿，小虎对哥哥大虎说：”这个作业有很多种摆放法，我想找到，但我不知道有多少种方案，你能帮助我吗？”

大虎是学校信息学集训队的，立刻想到用计算机来解决这个问题，并很快有了解答：$13$。

第二天他把问题拿到学校，并说如果第一行有 $N$ 个格子，第二行有 $N-1$ 个格子，……，第 $N$ 行有 $1$ 个格子，怎么办？现在请你一块来帮助他解决这个难题。

inputFormat: 仅一行，一个正整数 $N$。

outputFormat: 一行，方案总数。


title: 小欧与回文串构造

description:
小欧很喜欢字符串，尤其是只有 `0` 和 `1` 两种字符的回文串。

小欧也喜欢回文串，尤其是有那么一些回文子串但不是很多的串。

小欧更喜欢构造，所以他思考如下问题：

给定正整数 $n$ 和 $k$，保证 $k\le n$，能否构造一个长为 $n$ 的，只含有字符 `0` 和 `1` 的字符串 $S$，使得 $S$ 的本质不同非空回文子串个数恰好为 $k$ 呢？

小欧是构造小鬼，打不过已经爆切十万甚至九万道构造的先辈们，因此他找你帮忙解决这个问题，并希望你在有解时给出任意一个构造。

下面给出一些关于字符串的基本定义，字符串大手子可以跳过不读。

- 对于长为 $n$ 的字符串 $S$，定义 $S_i$ 为字符串 $S$ 的从左至右第 $i$ 个字符，
- 对于长为 $n$ 的字符串 $S$，定义其子串 $S[l;r]\; (1\le l\le r\le n)$ 为将字符 $S_l,S_{l+1},\ldots,S_{r}$ 自左至右拼接形成的字符串。特别地，空串也是 $S$ 的子串。
- 称 $S$ 的两个子串 $S[l_1;r_1]$ 和 $S[l_2;r_2]$ 本质不同，当且仅当 $S[l_1;r_1] \ne S[l_2;r_2]$。
- 对于长为 $n$ 的字符串 $S$，定义它的反串 $S^{T}$ 为将字符 $S_n,S_{n-1},\ldots,S_1$ 自左至右拼接形成的字符串。
- 字符串 $S$ 为回文串，当且仅当 $S=S^{T}$。

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

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

对于每组数据：

一行两个正整数，表示这组数据给出的 $n$ 和 $k$。

outputFormat:
对于每组数据：

若该组数据没有解，输出一行一个字符串 `No`；

否则输出两行，第一行一个字符串 `Yes`，接下来一行一个长为 $n$ 的 `01` 串，为你构造的解。有多个解输出任意一个即可。

hint:
对于第一组数据，本质不同的回文子串有：`1`，`0`，`101`，`010` 共四个。

### 数据范围与约定

对于 $20\%$ 的数据，$n\le 15$。
另有 $10\%$ 的数据，$k=n$。
另有 $20\%$ 的数据，$1000\le n\le 2000$，$k\ge \left\lfloor\dfrac{n}{2}\right\rfloor+100$。
对于 $100\%$ 的数据，$1 \le T \le 10$，$1\le k\le  n\le 2\times 10^5$。


title: [IOI2015] horses

description:
像他的祖先一样，Mansur 喜欢繁殖马匹。目前，他拥有哈萨克斯坦最大的马场。以前情况可不是这样，$N$ 年前 Mansur 年轻时，他只拥有一匹马，但他一直梦想着成为富豪，最终,他美梦成真。

按照时间的先后顺序将年份编号为 $0$ 到 $N-1$（即 $N-1$ 年是最近的一年）。每年的天气会影响马匹的繁殖。Mansur 用一个正整数 $X[i]$ 记录第 $i$ 年的繁殖系数，如果第 $i$ 年开始时有 $h$ 匹马，那么这一年结束时会有 $h \times X[i]$ 匹马。

每年，只有年底的时候可以出售马匹。Mansur 用一个正整数 $Y[i]$ 记录第 $i$ 年末卖出一匹马的售价。Mansur 可以卖出任意多匹马，每匹售价均为 $Y[i]$。

现在，Mansur 想知道如果在 $N$ 年中，他总能在最佳时间出售马匹，他能获得的最大收益是多少？你正好在 Mansur 家做客，所以他想请你帮他回答这个问题。

Mansur 对记录下的 $X$ 和 $Y$ 做了 $M$ 次更新，每次更新，Mansur 要么改变一个 $X[i]$，要么改变一个 $Y[i]$。每次更新后，他都会问你出售马匹能获得的最大收益。Mansur 的更新是累加的，即你的每个回答时都应该考虑之前的所有更新。注意：某个 $X[i]$ 或者 $Y[i]$ 可能会被更新多次。

对于 Mansur 的问题，实际的答案可能是一个非常大的数字，你只要给出实际答案模 $10^9+7$ 后的结果即可。

inputFormat:
- 第 $1$ 行，一个整数 $N$，表示总共有 $N$ 年。
- 第 $2$ 行，共 $N$ 个正整数 $X[0],\cdots,X[N - 1]$，对于 $0\le i \le N-1$，$X[i]$ 表示 $i$ 年的繁殖系数。
- 第 $3$ 行，共 $N$ 个正整数 $Y[0],\cdots,Y[N - 1]$，对于 $0\le i \le N-1$，$Y[i]$ 表示 $i$ 年末出售一匹马的价格。
- 第 $4$ 行，一个整数 $M$，表示更新次数。
- 第 $5,\cdots,M+4$ 行，每行 $3$ 个数字 $type$，$pos$，$val$ （$type=1$ 表示更改 $X[ pos ]$ 为 $val$，$type=2$ 表示更改 $Y[ pos ]$ 为 $val$）。

outputFormat:
- 共 $M+1$ 行
- 第 $1$ 行：一个整数表示初始状态下，Mansur 获得的最大收益模 $10^9+7$ 后的值。
- 第 $2,\cdots,M+1$ 行：每行一个整数，表示这次更新后 Mansur 获得的最大收益模 $10^9+7$ 后的值。


title: [IOI2014] friend 朋友

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

description:
我们建立了一个由编号为 $0,\cdots,n - 1$ 的 $n$ 个人组成的社交网络。网络中的有些对会成为朋友。如果 $x$ 号人成为 $y$ 号人的朋友，则 $y$ 号人同时也会成为 $x$ 号人的朋友。

这些人将通过 $n$ 个阶段加入这个网络，阶段也编号为 $0$ 至 $n−1$。第 $i$ 号人在第 $i$ 个阶段加入。在阶段 $0$，$0$ 号人加入网络并成为唯一的人。此后 $n - 1$ 个阶段的各个阶段，都有一个人会被主持人加入到网络中，而这个主持人可以是已在网络中的任何一个人。在阶段 $i$ 中（$1\le i\le n−1$），该阶段的主持人可以用如下三种方式之一把第 $i$ 号人加入到网络中：

- IAmYourFriend：将第 $i$ 号人仅变成主持人的朋友。
- MyFriendsAreYourFriends：将第 $i$ 号人变成主持人当前的每一个朋友的朋友。 注意，这个方式不会将第 $i$ 号人变成主持人的朋友。
- WeAreYourFriends：将第 $i$ 号人变成主持人的朋友，同时也变成主持人当前的每一个朋友的朋友。

在建立此网络之后，我们想挑选一个调查的样本，也就是说要从网络中选择一组人。由于朋友之间通常拥有相似的兴趣，因此样本不应包含任何一对互为朋友的人。每个人都会有一个调查的可信度，表示为一个正整数，而我们想要找出一个可信度总和最大的样本。

### 任务

给定各阶段的描述以及每个人的可信度值，请找出一个可信度总和最大的样本。你只需要实现函数 `findSample`。

* `findSample(n, confidence, host, protocol)`
	* $n$: 人数.
	* `confidence`: 大小为 $n$ 的数组；`confidence[i]` 表示第 $i$ 号人的可信度。
	* `host`: 大小为 $n$ 的数组；`host[i]` 表示阶段 i 的主持人。
	* `protocol`: 大小为 $n$ 的数组；`protocol[i]` 表示在阶段 （$0<i<n$） 所采用的方式的代码: `0` 代表 IAmYourFriend，`1` 代表 MyFriendsAreYourFriends，而 `2` 代表 WeAreYourFriends。
	* 由于在阶段 `0` 中没有主持人，因此 `host[0]` 和 `protocol[0]` 是没有被定义的，而且在你的程序中也不应访问它们。

这个函数应该返回样本可信度总和的最大值。

inputFormat:
以下为交互库的输入格式。

第 $1$ 行：一个正整数 $n$，为人数。

第 $2$ 行：共 $n$ 个整数 $\mathrm{confidence}[0],\ldots,\mathrm{confidence}[n-1]$.

第 $3$ 行：共 $2n-2$ 个整数 $\mathrm{host}[1],\mathrm{protocol}[1], \mathrm{host}[2], \mathrm{protocol}[2],\cdots, \mathrm{host}[n-1], \mathrm{protocol}[n-1]$。

outputFormat:
本题只支持 C++ 系列语言。

你只能提交一个源文件实现上述的函数，其命名与接口需遵循下面的要求。**不需要添加额外的头文件**。

`int findSample(int n, int confidence[], int host[], int protocol[]);`

hint:
对于 $100\%$ 的数据，$2 \le n \le 10^5$，$1 \le \mathrm{confidence}[i] \le 10^6$。

|**子任务**|**分值**|$n$|**可信度**|**采用的方式**|
|:-:|:-:|:-:|:-:|:-:|
|1|$11$|$n\leq 10$|$1\leq \mathrm{confidence}\leq 10^6$|全部三种方式|
|2|$8$|$n\leq 1000$|$1\leq \mathrm{confidence}\leq 10^6$|只有 `MyFriendsAreYourFriends`|
|3|$8$|$n\leq 1000$|$1\leq \mathrm{confidence}\leq 10^6$|只有 `WeAreYourFriends`|
|4|$19$|$n\leq 1000$|$1\leq \mathrm{confidence}\leq 10^6$|只有 `IAmYourFriend`|
|5|$23$|$n\leq 1000$|所有可信度值均为 $1$|只有 `MyFriendsAreYourFriends` 和 `IAmYourFriend` 两种方式|
|6|$31$|$n\leq 10^5$|$1\leq \mathrm{confidence}\leq 10^4$|全部三种方式|


title: 「SWTR-4」Easy Math Problems

background: 数学老师给小 A 布置了 $2$ 道 Easy Math Problems。

description:
给定 $n,c,f,l,r$，有集合 $S=\{x\in\mathbb{N_+}\mid\gcd(x,n)\leq c\}$ 和集合 $Q=\{x\in S\mid l\leq x\leq r\}$。

- 集合 $S$ 为所有与 $n$ 的 $\gcd$ 不超过 $c$ 的正整数，集合 $Q$ 为 $S$ 中不小于 $l$，不大于 $r$ 的数。

第一问：请求出集合 $S$ 中第 $f$ 小的数。

第二问：请求出集合 $Q$ 中包含的元素个数。

由于数字很大，所以小 A 想请你帮他求出问题的答案。

inputFormat: 一行五个整数 $n,c,f,l,r$ —— 意义见题目描述。

outputFormat: 输出两行整数 —— 第一行为第一问的答案，第二行为第二问的答案。


title: [CTSC2015] misc

description:
小强和 B 君是好朋友。

小强除了 B 君还有很多好朋友，比如洁妹。

B 君除了小强也还有很多好朋友，比如R君。他们还有很多共同的好朋友，比如小花，葱娘和其他 $3$ 个人。

B 君发现，人与人之间的关系可以看成是一个无向图，每个人看成一个点，人与人之间的关系看成一条边。

不同的人在社会中的号召力不一样，我们用 $a_i$ 来表示第 $i$ 个人的号召力。

人与人之间的关系也各不相同，可能非常友好，可能只是泛泛之交；可能天天腻在一起，可能一年才联系一次。为此，我们用长度边权 $b_j$ 来刻画第 $j$ 条边对应的两个用户的亲密程度，长度约小，双方就越亲密；同时，我们用宽度边权 $c_j$ 来刻画第 $j$ 条边对应的两个用户的交流频率，宽度越大，两个人沟通的频率也就越高。

一条路径的长度指的是这条路径上的所有边的长度边权之和，一条路径的宽度指的是这条路径上的所有边的宽度边权的乘积。

当两个人 $s$ 和 $t$ 想要交流的时候，他们会选择长度最短的路径来交流。由于最短路可能有多个，我们称 $s$ 到 $t$ 的最短路的宽度为 $\sigma_{st}$，是所有 $s$ 到 $t$ 的长度最短的路径的宽度和。同时，我们用 $\sigma_{st} (v)$ 表示所有从 $s$ 到 $t$，且经过 $v$ 的长度最短的路径的宽度和，即 $v$ 对 $s$,$t$ 的影响力。
一个人 $v$ 在图中的传播力 $R(v)$ 可以被定义为如下函数：

 $$R(v)=\sum\limits_{s \ne v \ne t} \frac{a_s a_t \sigma_{st}(v)}{\sigma_{st}}$$

即对图中所有不包含 $v$ 的点对，分别计算 $v$ 对该点对的影响力除以该点对的最短路的宽度，再乘上这个点对中两个点的号召力，最后将所有点对的计算结果加和得到节点在图中的传播力。

B 君想快速知道所有节点在图中的传播力。当他去问小强的时候，小强说：“我有一个绝妙的做法，可惜题面太短，写不下。”

你知道怎么做吗？

inputFormat:
第一行包含 $2$ 个正整数 $n$,$m$，分别表示图的点数和边数。

接下来 $n$ 行中的第 $i$ 行有 $1$ 个非负整数 $a_i$，表示第 $i$ 个人的号召力。
接下来 $m$ 行中的第 $j$ 行有 $3$ 个整数 $x_j$,$y_j$,$b_j$ 和一个实数 $c_j$ ，表示点 $x_j$ 和点 $y_j$ 之间有一条长度边权为 $b_j$，宽度边权为 $c_j$ 的边。

outputFormat: 共 $n$ 行，每行一个实数 $R(i)$，表示第 $i$ 个点在图中的传播力。

hint:
**评分标准**

我们会将输出文件的每个数与参考答案进行比较，如果该数与参考答案的相对误差或绝对误差不超过 $10^{-6}$，则判定该数正确。对于参考答案为 $0$ 的数，必须满足绝对误差不超过 $10^{-6}$ 才判定为正确。

如果输出正确数的个数为 $q$，那么你在该测试点上的得分是 $\left\lfloor\ 5(\dfrac{q}{n})^7 \right\rfloor$

**数据规模和约定**

对于测试点 $1$,$2$,$3$,$4$，有 $n \le 100$。

对于测试点 $5$,$6$,$7$,$8$，所有 $b_j=1$。

对于测试点 $9$,$10$,$11$,$12$，有 $m=n-1$。

对于测试点 $1$,$3$,$5$,$7$,$9$,$11$,$13$,$15$,$17$,$19$，所有 $a_i=1$。

对于测试点 $1$,$2$,$5$,$6$,$9$,$10$,$13$,$14$,$17$,$18$，所有 $c_j=1$。

对于所有的数据，有 $n \le 1000$，$m \le 4 \times 10^3$，$0<a_j \le 255$，$0<b_j \le 15$，$0.5 \le c_j \le 2$，$c_j$ 的小数部分最多 $12$ 位。数据保证图是连通的。


title: [CTSC2013] 没头脑和不高兴

description:
没头脑和不高兴是一对形影不离的好朋友，他们一起上学也一起玩耍。

这天，这对好朋友聚在一起玩纸牌游戏。他们所玩的纸牌总共有 $N$ 张，每一张上面都有一个 $1-N$ 的数字，任意两张纸牌上的数字都不相同。根据他们制定的游戏规则，在每局游戏的开始，所有的牌需要按照从 $1-N$ 的顺序排好。在开心地玩完了一局牌之后，他们发现牌的顺序被弄得乱七八糟，将它们排好序是一件挺麻烦的事情。

他们将凌乱的纸牌在桌面上排成一排，然后开始了排序工作。不高兴由于在上一局游戏中输了牌，非常不高兴。他只将其中**奇数位置**的牌排成了升序，然后把剩下的任务推给了没头脑。没头脑非常没头脑，他采取了一个有些笨的排序方式。每次，他找到两张相邻并且顺序不对的牌交换它们，直到整个序列被排好序为止。

乐于探究的你，想要研究在初始排列随机的情况下没头脑花在交换纸牌上的时间。假设没头脑每交换一对纸牌花费的时间为 $1$，你希望求出他排序时间的期望。此外，为了更好地分析这个问题，你还希望能够计算出所花时间的方差。更进一步地，如果**被不高兴排好序的位置发生了变化**，你是否还能求出没头脑用来排序时间的期望呢？

inputFormat:
- 输入文件共 $M+1$ 行。
- 第一行包含两个正整数 $N$,$M$。
- 接下来 $M$ 行，每行包含三个整数 $l$,$r$,$v$。其中 $1 \le l \le r \le n$，$v\in\{0,1\}$。若 $v=0$ 则表示不高兴不再对 $l$ 到 $r$ 之间的位置排序；反之若 $v=1$ 则表示被不高兴排序的位置将涵盖 $l$ 到 $r$。

outputFormat:
- 输出文件共 $M+2$ 行。每行输出一个形如 `p/q` 的有理数，其中 $\gcd(p,q)=1$，$q \ne 1$，$p,q \in Z$。
- 第一行输出在初始条件下没头脑排序时间的期望。
- 第二行输出在初始条件下没头脑排序时间的方差。
- 接下来 $M$ 行，每行分别输出在对不高兴排序的位置进行了前若干次修改之后没头脑排序时间的期望。


title: [IOI2014] game 游戏

description:
健佳是一个喜欢做游戏的小男生。当有人问问题时，他更喜欢通过玩游戏的方式作答，而不是直接回答。健佳碰到了他的朋友梅玉，跟她讲了台湾的航空网。在台湾有 $n$ 个城市（编号为 $0,\cdots,n−1$），其中有些城市之间有航线。每个航线连接两个城市，并且是双向的。

梅玉问健佳，是否任意两个城市之间都可以坐飞机互达（直接或间接），健佳不想直接回答，而是要通过做游戏的方式来告诉她。梅玉可以问"城市 $u$ 和 $v$ 之间有直接航线吗？"，健佳会立刻直接回答该问题。梅玉会询问每对城市恰好一次，因此总计会有 $r = \frac{n (n−1)}{2}$ 个问题。如果由前 $i$（$i<r$）个问题的答案可以推断出整个航空网是否连通，也就是说，是否任意一对城市之间都可以坐飞机互达（直接或间接），梅玉就获胜。否则意味着她需要知道全部 $r$ 个回答，此时健佳获胜。

为了让游戏更好玩，他们俩同意，健佳可以不要管台湾的真实航空网，而是可以随着游戏的进展而编造航空网，也就是根据梅玉此前的提问来决定此后如何作答。你的任务是，通过决定健佳如何回答，来帮助他赢得游戏。

inputFormat:
- 第 $1$ 行：一个正整数 $n$，代表城市数量。
- 余下 $r$ 行：每行包含两个整数 $u$ 和 $v$，表示对城市 $u$ 和 $v$ 的提问。

outputFormat: - 共 $r$ 行，对于每次梅玉的提问，你必须回答在城市 $v$ 和 $u$ 之间是否有直接航线。具体而言，返回值 $1$ 表示有，$0$ 表示没有。


title: [CTSC2014] 随机数

description:
露露、花花和萱萱最近对计算机中的随机数产生了兴趣。为大家所熟知的是，有计算机生成的随机数序列并非真正的随机数，而是由一定法则生成的伪随机数。

某一天，露露了解了一种生成随机数的方法，称为 Mersenne twister。给定初始参数 $m \in Z+$，$ x \le Z+\cap[0,2m)$ 和初值 $M_0 \in Z+\cap [0,2m)$，它通过下列递推式构造伪随机数列$\{M_n\}$:

 $$M_n=\begin{cases}2M_{n-1} & 2M_{n-1}<2^m\\(2M_{n-1}-2^m) \ XOR \ x & 2M_{n-1}\geq 2^m\end{cases}$$

 其中 $XOR$ 是二进制异或运算（C/C++ 中的 $^$ 运算）。而参数 $x$ 的选取若使得该数列在长度趋于无穷时，近似等概率地在 $Z+ \cap (0,2m)$ 中取值，就称 $x$ 为好的。例如，在 $m>1$时 $x=0$ 就显然不是好的。

在露露向伙伴们介绍了 Mersenne twister 之后，花花想用这一些经典的随机性测试来检验它的随机性强度。为此，花花使用计算机计算
了一些 $M_k$。

但细心的萱萱注意到，花花在某次使用二进制输入 $k$ 时，在末尾多输入了 $l$ 个 $0$。她正想告诉花花这个疏忽，然而花花已经计算并记录了
错误的 $M_k$ 而没有记录 $k$ 的值。虽然这其实不是什么致命的问题，但是在萱萱告诉花花她这个疏漏时，作为完美主义者的花花还是恳求萱萱帮她修正 $M_k$ 的值。萱萱便把这个任务交给了她的 AI ——你。

inputFormat:
- 第一行包含一个正整数 $m$；
- 第二行为二进制表示的 $x$（共 $m$ 个数，从低位到高位排列）；
- 第三行为二进制表示的 $M_0$（排列方式同 $x$）；
- 第四行包含一个整数 $type$。

接下来分为两种可能的情况：
1. $type=0$（萱萱记下了花花的输入）：则第五行包含一个整数，表示萱萱记下来的正确的 $k$ 值。
2. $type=1$（萱萱未能记下花花的输入）：则第五行为 $l$，第六行输入花花计算出错误的二进制表示的 $M_k$。

outputFormat: 仅一行，为m位的01串，表示你求得的正确Mk（同样要求从低位到高位）。


title: 『MdOI R1』Path

description:
给定一棵 $n$ 个点的无根树，边有边权。

令 $V(x,y),E(x,y)$ 分别表示树上 $x,y$ 之间的简单路径上的所有点的集合和所有边的集合，特别地，当 $x=y$ 时，$V(x,y) = \{x\}$，$E(x,y) = \varnothing$。

再令边集 $E$ 的权值 $f(E)$ 为 $E$ 中所有边的权值的 **异或和**，当 $E = \varnothing$ 时，$f(E) = 0$。

现在，要你求出
$$
\max_{1\le x,y,u,v \le n,V(x,y)\cap V(u,v) = \varnothing}(f(E(x,y)) + f(E(u,v)))
$$
通俗的讲，你要选择两条简单路径，满足没有重合的点，且边权异或和之和最大。

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

接下来 $n-1$ 行，每行三个整数 $x,y,w$，表示编号为 $x$ 和 $y$ 的点之间有一条权值为 $w$ 的边。

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

hint:
【样例 1 解释】

样例中的树如图所示，选择标红色和蓝色的两条路径，满足没有重合的点，且边权异或和之和最大，为 $(7\oplus 1\oplus 8)+(5\oplus 2)=21$（其中 $\oplus$ 表示异或运算）。

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

【样例 2 解释】

样例中的树如图所示，为一条链的形状，选择标红色和蓝色的两条路径，蓝色路径退化成了一个点，使异或和之和达到最大值 $2+0=2$。注意红色路径并不能延申到 $3$，否则蓝色路径将无法存在。

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

---

【数据范围】

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

| 子任务编号 |    $n\leq$     |  特殊性质   | 分值 | 时限 |
| :--------: | :------------: | :---------: | :--: | :--: |
|     1      |      $50$      |     无      |  12  |  1s  |
|     2      | $2\times 10^3$ |     无      |  28  |  2s  |
|     3      | $2\times 10^4$ | $y = x + 1$ |  20  |  3s  |
|     4      | $3\times 10^4$ |     无      |  40  | 3.5s |

对于 $100\%$ 的数据，$2\leq n\leq 3\times 10^4$，$1\leq x,y\leq n$，$0\leq w\leq 10^9$。


title: [IOI2014] holiday 假期

description:
健佳正在制定下个假期去台湾的游玩计划。在这个假期，健佳将会在城市之间奔波，并且参观这些城市的景点。

在台湾共有 $n$ 个城市，它们全部位于一条高速公路上。这些城市连续地编号为 $0$ 到 $n-1$。

对于城市 $i$（$0 < i < n-1$ ）而言，与其相邻的城市是 $i-1$ 和 $i+1$。但是对于城市 $0$，唯一与其相邻的是城市 $1$。而对于城市 $n-1$，唯一与其相邻的是城市 $n-2$。

每个城市都有若干景点。健佳有 $d$ 天假期并且打算要参观尽量多的景点。健佳已经选择了假期开始要到访的第一个城市。在假期的每一天，健佳可以选择去一个相邻的城市，或者参观所在城市的所有景点，但是不能同时进行。即使健佳在同一个城市停留多次，他也不会去重复参观该城市的景点。请帮助健佳策划这个假期，以便能让他参观尽可能多的景点。

inputFormat:
- 第 $1$ 行：有三个非负整数， $n$ 代表城市数目，$start$ 代表起点城市编号，$d$ 代表假期天数。
- 第 $2$ 行：$n$ 个非负整数 $a[0],\cdots, a[n-1]$，对于 $0 \le i \le n-1$，$a[i]$ 代表城市 $i$ 的景点数目。

outputFormat: - 共一行，最多参观的景点数目。


title: [IOI2013] game 游戏

background: 警告：**滥用本题评测将被封号**。

description:
Bazza 和 Shazza 正在玩游戏。游戏在一个 $R$ 行 $C$ 列的网格上进行。其中， $R$ 行编号为 $0,\cdots, R - 1 $， $C$ 列编号为 $0,\cdots, C - 1 $。我们用 $(P, Q)$ 表示位于 $P$ 行 $Q$ 列的单元格。每个单元格包含一个非负整数，游戏开始时所有单元格内的整数均为零。

游戏如下进行：任意时刻，Bazza 可以做如下动作之一：
- 修改一个单元格 $(p, q)$ 内包含的整数值；
- 要求 Shazza 计算一个给定子矩阵中所有单元格内数字的最大公约数（GCD），子矩阵的两个对角分别为 $(p, q)$ 和 $(u, v)$ （子矩阵包含给定的两个对角点）。

Bazza 会做 $N_U + N_Q$ 次动作(其中，修改单元格内数据 $N_U$ 次，询问 GCD $N_Q$ 次) 。

你的任务是对 Bazza 提出的问题给出正确答案。

inputFormat:
- 第1行: $R$ 表示网格行数，$C$ 表示网格列数，$N$ 表示操作总数。
- 接下来的 $N$ 行: 每行表示一个动作，以动作发生的先后顺序给出。

表示每个动作的一行的格式如下：
- `update(P,Q,K)` 表示为： `1 P Q K`
- `calculate(P,Q,U,V)` 表示为： `2 P Q U V`

outputFormat:
共 $N_Q$ 行，对于每次询问，输出答案。

**说明**

`update(P,Q,K)`

- 当Bazza改变单元格中的整数时调用此函数，即把第 $P$ 行第 $Q$ 列的数改为 $K$。
- $P$: 单元格的行号（$0 \le P \le R - 1$ ）。
- $Q$: 单元格的列号（$0 \le Q \le C - 1$ ）。
- $K$: 这个单元格中新的整数（ $0 \le K \le 10^{18}$）。这个新整数可能与原来的整数相同。

`calculate(P,Q,U,V)`

- 该函数计算以 $(P, Q)$ 和 $(U, V)$ 为对角点的子矩阵中所有整数的最大公约数。这个范围是包含单元格 $(P, Q)$ 和 $(U, V)$ 的。

- 如果这个子矩阵中的所有整数都是 $0$，那么该函数返回 $0$。

- $P$: 子矩阵左上角单元格的行号（ $0 \le P \le R - 1$ ）。
- $Q$: 子矩阵左上角单元格的列号 （$ 0 \le Q \le C - 1$ ）。
- $U$: 子矩阵右下角单元格的行号（ $P \le U \le R - 1$ ）。
- $V$: 子矩阵右下角单元格的列号（ $Q \le V \le C - 1$ ）。


title: [IOI2013] robots 机器人

description:
Marita 的弟弟把玩具扔在客厅地板上，乱七八糟。庆幸的是，Marita 设计了一种特殊的机器人可以收拾玩具。 不过，她需要确定哪个机器人去拣起哪个玩具。

一共有 $T$ 个玩具,整数 $W[i]$ 表示这个玩具的重量，整数 $S[i]$ 表示这个玩具的体积。机器人有两种，分别是：弱机器人和小机器人。

- 有 $A$ 个弱机器人。每个弱机器人有一个重量限制 $X[i] $，它只能拿起重量严格小于 $X[i]$ 的玩具，与玩具的体积大小没关系。
- 有 $B$ 个小机器人。每个小机器人有一个体积限制 $Y[i] $，它只能拿起体积严格小于 $Y[i]$ 的玩具，与玩具的重量大小没有关系。

Marita 的每个机器人用 $1$ 分钟将一个玩具拿走放好。不同的机器人可以同时拿走并放好不同的玩具。

你的任务是确定 Marita 的机器人是否可以将所有的玩具都收拾好，如果是，那么最少用多少时间可以收拾好。

inputFormat:
- 第1行: $A$ 表示弱机器人的数目，$B$ 表示小机器人的数目，$T$ 表示玩具的数目；
- 第2行: 长度为 $A$ 的数组 $X[0],\cdots,X[A-1]$，对于 $0 \le i \le A-1$，$X[i]$ 表示第 $i$ 个弱机器人的重量限制；
- 第3行: 长度为 $B$ 的数组 $Y[0],\cdots,Y[B-1]$，对于 $1 \le i \le B-1$，$Y[i]$ 表示第 $i$ 个小机器人的体积限制；
- 接下来 $T$ 行: $W[i]$，$S[i]$，对于 $1 \le i \le T$，$W[i]$ 代表第 $i$ 个玩具的重量，$S[i]$ 代表第 $i$ 个玩具的体积。

- 如果 $A = 0$ 或者 $B = 0$ ，那么相应的行（第 $2$ 行或者第 $3$ 行）为空。

outputFormat: - 共 $1$ 行，输出机器人收拾好所有玩具所需要的最短时间，如果无法收拾好所有玩具，输出 `-1`。


title: [IOI2013] dreaming 梦想

description:
天地之初，IOI 尚在遥远的梦想之中。

Serpent(水蛇) 生活的地方有 $N$ 个水坑，编号为 $0，\cdots，N - 1$，有 $M$ 条双向小路连接
这些水坑。每两个水坑之间至多有一条路径（路径包含一条或多条小路）相互连接，有些水坑之间根本无法互通(即 $M ≤ N-1$ )。Serpent 走过每条小路需要一个固定的天数，不同的小路需要的天数可能不同。

Serpent 的朋友袋鼠希望新修 $N - M - 1$ 条小路，让Serpent 可以在任何两个水坑间游走。袋鼠可以在任意两个水坑之间修路，Serpent 通过每条新路的时间都是 $L$ 天。

袋鼠希望找到一种修路方式使得修路之后 Serpent 在每两个水坑之间游走的最长时间最短。

**举例说明**

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

上图中有 $12$ 个水坑 $8$ 条小路 ($N = 12 , M = 8$)。假如 $L = 2$，即 Serpent 通过任何一条新路都需要 $2$ 天。那么，袋鼠可以修建 $3$ 条新路：
- 水坑 $1$ 和水坑 $2$ 之间；
- 水坑 $1$ 和水坑 $6$ 之间；
- 水坑 $4$ 和水坑 $10$ 之间。

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

上图显示了修路后的最终状态。从水坑 $0$ 走到水坑 $11$ 的时间最长，需要 $18$ 天。这是最佳结果，无论袋鼠如何选择修路方式，总会存在一些水坑对，Serpent 需要 $18$ 天或者更长时间从其中一个走到另一个。

inputFormat:
- 第 $1$ 行: $N$ 表示水坑的数目，$M$ 表示原本存在的小路的数目，$L$ 表示 Serpent 通过新修的路径的时间。
- 第 $2,\cdots, M + 1$ 行: $A[i]$，$B[i]$，$T[i]$。$A$，$B$，$T$ 分别为三个包含 $M$ 个元素的数组，分别表示每条小路的两个端点和通过这条小路的时间。例如，第 $i$ 条小路连接水坑 $A[i-1]$ 和水坑 $B[i-1]$，通过这条小路的时间是 $T[i-1]$ 天。

例如：题目中的例子应该表示为以下格式

```
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
```

outputFormat: 如上所述，表示游走于两个距离最远的水坑之间所需的时间


title: [IOI2016] aliens

description:
我们的卫星刚刚通过观测一个遥远的星球发现了外星文明。我们也已经获得了该星球的一个正方形区域的低分辨率照片。这个照片上有许多智能生命的迹象。专家们也已经确定了照片上的 $n$ 个兴趣点。这些兴趣点被编号为 $0$ 到 $n−1$。现在我们希望拍摄一些能包含全部 $n$ 个兴趣点的高分辨率照片。

卫星已将低分辨率照片的区域划分成由 $m \times m$ 个单位正方形的小方格组成的网络。网格的行和列被连续地编号为 $0$ 到 $m−1$（从上到下和从左到右）。我们用坐标 $(s,t)$ 来表示第 $s$ 行与第 $t$ 列上的小方格。第 $i$ 个兴趣点位于小方格 $(r_i,c_i)$ 上，每个小方格子上可以包含任意多个兴趣点。

卫星在一个固定的轨道上运行，而它刚好也直接经过这个网格的主对角线的上方。主对角线就是指在网络中连接左上角和右下角的那条线段。卫星能够在任意的区域上拍摄高分辨率的照片，但必须满足以下条件：

- 拍摄的区域必须是正方形。
- 这个正方形的两个对角（注：变通理解为主对角线）全部包含在网格的主对角线中。
- 网格中的每个小方格或者完全在拍摄范围内，或者完全在拍摄范围外。
卫星最多只能拍摄 $k$ 张高分辨率照片。

一旦卫星拍摄完成，它将把每个拍摄区域的高分辨率照片传送到地面基站（无论这些区域是否包含兴趣点）。尽管一个小方格可能会被多次拍摄，但每个被拍摄到的小方格上的数据只会被传送一次。

因此，我们必须选择最多 $k$ 个正方形区域进行拍摄，而且要保证：

- 每个包含至少一个兴趣点的小方格必须被至少拍摄到一次
- 被拍摄到至少一次的小方格数目必须是最小的。

你的任务就是去找出被拍摄到的小方格有可能的最小值。

inputFormat:
- 第 $1$ 行：整数 $n$ 代表兴趣点的数目，$m$ 代表网格中的行数（也是列数） 和 $k$ 代表卫星能够拍摄高分辨率照片的最大次数；
- 第 $2+i$ （$0 \le i \le n−1$） 行：整数 $r_i$ 和 $c_i$。$r$ 和 $c$ 为两个长度为 $n$ 的数组，描述网格中包含兴趣点的那些小方格的坐标。对于 $0\le i\le n−1$，第 $i$ 个兴趣点位于坐标为 $(r_i,c_i)$ 的小方格。

outputFormat: - 共一行，被至少拍摄一次的小方格的总数的最小值（这些照片必须覆盖所有兴趣点）。


title: [IOI2013] wombats

description:
布里斯班被变异的袋熊占领，你必须带领大家去安全的地方。

布里斯班的道路像一个大网格，有 $R$ 条东西向的横向道路，从北向南依次编号为 $0,\cdots, (R - 1) $，有 $C$ 条南北向的纵向道路，从西向同东依次编号为 $0,\cdots, (C- 1)$ ，如下图所示。

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

袋熊从北方入侵，人们逃向南方。人们可以在横向道路上双方向移动，但是在纵向道路上只能往南面安全的地方走。

横向道路 $P$ 和纵向道路 $Q$ 的交点表示为 $(P, Q)$ 。相邻 $2$ 个交点之间的道路线段上
有一些袋熊，且数目是随时间变化的。 你的任务是引导每个人从最北边（在横向道路 $0$ 上）的指定交点逃到最南端（在横向道路 $R - 1$ 上）的指定交点，路上经过
的袋熊最少。

首先会告诉你网格的规模以及每条道路线段上的袋熊的数量。然后给你一系列 $E$ 事件，每个事件是下列两者之一：
- 变化，表示有些道路线段上的袋熊数量发生变化；
- 逃离, 表示有些人已到达横向道路 $0$ 上指定交点，你必须给他们指出一条路，通往横向道路 $R - 1$ 上指定交点且路上遇到的袋熊最少。

**举例**

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

上图所示的初始地图中有 $3$ 条横向道路 （$ R = 3$ ）和 $4$ 条纵向道路（$ C = 4$ ），每
条道路线段上的袋熊数目如线段上的标记所示。考虑下列事件：
- 一个人到达交点 $A = (0, 2)$ ,希望逃到交点 $B = (2, 1)$ 。如图上虚线所示，他最少需要经过 $2$ 只袋熊。
- 又一个人到达交点 $X = (0, 3)$ ，希望逃到交点 $Y = (2, 3)$ 。如图上虚线所示，他最少需要经过 $7$ 只袋熊。
- 发生 $2$ 个变化事件：纵向道路 $0$ 上最上面那条道路线段上的袋熊数目变为 $5 $，横向道路 $1$ 上中间那条道路线段上的袋熊数目变为 $6 $，见下图中圈出来的两个数字。

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

- 第3个人到达交点 $A = (0, 2)$ ，希望逃到交点 $B = (2, 1)$ ，现在他最少需要经过 $5$ 只袋熊，如图中虚线所示。

inputFormat:
- 第 $1$ 行： $R$ 表示横向道路的数目，$C$ 表示纵向道路的数目。
- 第 $2$ 行： $H[0][0],\cdots,H[0][C-2]$。
- $\cdots$
- 第 $(R + 1)$ 行： $H[R-1][0],\cdots,H[R-1][C-2]$。
- 第 $(R + 2)$ 行： $V[0][0],\cdots,V[0][C-1]$。
- $H$: 二维数组 $R × (C - 1)$ ，其中 $H[P][Q]$ 表示交点 $(P, Q)$ 和交点 $(P, Q +1)$ 之间的横向道路线段上的袋熊数目。
- $\cdots$
- 第 $(2R)$ 行： $V[R-2][0],\cdots,V[R-2][C-1]$。
- $V$: 二维数组 $(R - 1) × C$ ，其中 $V[P][Q]$ 表示交点 $(P, Q)$ 和交点 $(P + 1,Q)$ 之间的纵向道路线段上的袋熊数目。
- 下一行: $E$。
- 下 $E$ 行：每行一个事件，按照事件发生的顺序给出。

如果 $C = 1$ ，表示横向道路上每条道路线段上的袋熊数目的若干空行(第 $2$ 到 $R +1$ 行)将会被省略。

表示每个事件的那一行格式如下：

- `1 P Q W` 表示 将交点 $(P, Q)$ 和交点 $(P, Q + 1)$ 之间的横向道路线段上的袋熊数目改为 $W$。
- `2 P Q W` 表示 将交点 $(P, Q)$ 和交点 $(P + 1, Q)$ 之间的纵向道路线段上的袋熊数目改为 $W$。
- `3 V1 V2` 表示 计算一个人从交点 $(0, V1)$ 逃到交点 $(R-1, V2)$ 最少需要经过多少只袋熊。

例如：题目中的例子应该表示为以下格式

```
3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1

```

outputFormat: 对于每一次询问，给出最少经过袋熊数。

hint: 对于 $100\%$ 的数据，$2 \le R \le 5 \times 10^3$，$1 \le C \le 200$，最多 $500$ 个变化，最多 $2 \times 10^5$ 次询问，任意时刻一条道路上最多 $10^3$ 只袋熊。


title: [COCI2014-2015#1] Kamp

description:
一颗树 $n$ 个点，$n-1$ 条边，经过每条边都要花费一定的时间，任意两个点都是联通的。

有 $K$ 个人（分布在 $K$ 个不同的点）要集中到一个点举行聚会。

聚会结束后需要一辆车从举行聚会的这点出发，把这 $K$ 个人分别送回去。

请你回答，对于 $i=1 \sim n$ ，如果在第 $i$ 个点举行聚会，司机最少需要多少时间把 $K$ 个人都送回家。

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

接下来 $n-1$ 行，每行三个数 $x,y,z$ 表示 $x$ 到 $y$ 之间有一条需要花费 $z$ 时间的边。

接下来 $K$ 行，每行一个数，表示 $K$ 个人的分布。

outputFormat:
输出 $n$ 个数。

第 $i$ 行的数表示：如果在第 $i$ 个点举行聚会，司机需要的最少时间。

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

- 对于 $50\%$ 的数据，保证 $n\le 2\times 10^3$。
- 对于 $100\%$ 的数据， $1 \le k \le n \leq 5\times 10^5$，$1 \le x,y \le n$，$1 \le z \le 10^8$ 。


title: [COCI2014-2015#2] Norma

description:
给定一个正整数序列 $a_1,a_2,\cdots,a_n$ ，求

$$\sum_{i=1}^{n}\sum_{j=i}^{n}(j-i+1)\min(a_i,a_{i+1},\cdots,a_j)\max(a_i,a_{i+1},\cdots,a_j)$$

inputFormat:
第一行一个整数 $n$ 。
接下来 $n$ 行，每行一个正整数，表示输入序列 $a_1,a_2,\cdots,a_n$ 。

outputFormat: 输出答案对 $10^9$ 取模后的结果。


title: [RC-02] 开门大吉

description:
$n$ 位选手去参加节目“开门大吉”。共有 $m$ 套题，每套题包含 $p$ 个题目，第 $i$ 位选手答对第 $j$ 套题中第 $k$ 道的概率为 $f_{i,j,k}$。

若一位选手答对第 $i$ 题，会在已得到奖励的基础上，再得到 $c_i$ 元奖励。选手总是从第一道开始，按顺序答题的。

同时，为了防止过多的选手做同一套题，还有 $y$ 条形如“第 $i$ 位选手的套题编号必须至少比第 $j$ 位的大 $k$”的限制。

你需要给每一位选手分配一套题（不同选手可以相同），使得所有人的期望奖励和最小。

inputFormat:
输入包含多组数据。第一行是一个整数 $T$，为数据组数。

对于每组数据，第一行四个整数 $n,m,p,y$。

接下来一行 $p$ 个整数，第 $i$ 个为 $c_i$。

接下来 $m$ 个 $n\times p$ 的矩阵，第 $j$ 个矩阵中第 $i$ 行第 $k$ 个实数为 $f_{i,j,k}$。

接下来 $y$ 行，每行三个整数 $i,j,k$（$1\le i,j\le n$，$-m<k<m$），描述一条限制。

outputFormat:
对于每组数据，输出一个实数，为答案。无解输出 `-1`。

本题有 Special Judge，答案误差在 $5\times 10^{-4}$ 以内都算对。

由于 SPJ 敏感，请在每组数据末尾都输出一个换行符，并不要再输出其它字符。

hint:
【样例解释】

这里只解释第二组数据。

一共只有两套题，而第二个人的套题编号大于第三个人，因此第二个人一定是选第二套，第三个人选第一套。

第二个人选第二套，期望支出：$0.2\times (1-0.5)\times 10+0.2\times 0.5 \times (1-0.3) \times 20+0.2\times 0.5 \times 0.3\times (1-0.6)  \times 30+0.2\times 0.5 \times 0.3\times 0.6  \times 50=3.66$。

其他人的计算方法类似。

【数据范围】

**本题捆绑测试。**

对于所有数据，$1\le n,m,p\le 80$，$0\le y\le 10^3$，$0\le f_{i,j,k} \le 1$，$0\le c_i\le 10^5$，$1 \le T\le 50$。保证每个测试点的输入数据大小小于 $10\text{MB}$。

Subtask 1（20 pts）：$n,m,p,y\le 7$；

Subtask 2（20 pts）：$T\le 6$，$y=0$；

Subtask 3（20 pts）：$n,m,p\le 30$，$y\le 200$；

Subtask 4（20 pts）：$T=1$；

Subtask 5（20 pts）：$T\le 5$。


title: The Forest

background:
Deep in the forest, swift in the night.

They come out, with the frightening shouting under the moonlight.

You stare at the horrible figures. They are real, alive.

I promise you've never experienced a worse night.

They come nearer, nearer, till a meter left.

You see their real faces. Scary eyes and hair in a mess.

You think they coming for you, then you are wrong.

They only want your delicious cheese, which is produced in a scary farm.

That's what happens in the forest. Enjoy your time!

description:
**请注意，本题的时间限制为 5s！**

探险家小 A 和小 B 需要用灯泡照亮这个森林。

有 $n$ 个灯泡，编号为 $1, 2, \cdots, n$。小 A 用 $n - 1$ 条红色绳子把它们连成了一棵树，小 B 用 $n - 1$ 条蓝色绳子把它们连成了另一棵树。

一开始所有灯泡都是熄灭的，现在要点亮若干个灯泡。小 A 喜欢联通块，而小 B 喜欢链。他们想知道：有多少种点亮灯泡的方案，满足点亮的灯泡在小 A 的树上形成一个联通块，在小 B 的树上形成一条链呢？

inputFormat:
第一行一个数 $T$，表示有 $T$ 组数据，对于每组数据：

第一行一个数 $n$。

第 $2$ 行到第 $n$ 行，第 $i + 1$ 行两个数 $a_i, b_i$，表示小 A 的树上的一条边。

第 $n + 1$ 行到第 $2n - 1$ 行，第 $i + n$ 行两个数 $c_i, d_i$，表示小 B 的树上的一条边。

outputFormat: 输出 $T$ 行，第 $i$ 行是第 $i$ 组数据的答案。

hint:
**样例解释：**

[点击查看三组数据的图解](https://www.luogu.com.cn/paste/l5u1f2ob)。

对于第一组数据，可以点亮的灯泡集合有：

+ $\{1\}$；
+ $\{2\}$；
+ $\{3\}$；
+ $\{1, 2\}$；
+ $\{1, 2, 3\}$。

注意不能点亮集合 $\{1, 3\}$，因为编号为 $1, 3$ 的灯泡在小 A 的树上不构成联通块；也不能点亮集合 $\{2, 3\}$，因为编号为 $2, 3$ 的灯泡在小 B 的树上不构成一条链。

对于第二组数据，可以点亮的，**至少包含两个灯泡的**的灯泡集合有：

+ $\{1, 2\}$；
+ $\{1, 2, 3\}$；
+ $\{1, 2, 3, 4\}$；
+ $\{1, 2, 3, 4, 5\}$。

显然大小为 $1$ 的灯泡集合都合法，所以答案为 $4 + 5 = 9$。

**限制与约定：**

对于 $20 \%$ 的数据，$n \le 50$，满足特殊限制 $X$。
对于 $40 \%$ 的数据，$n \le 3000$，满足特殊限制 $X$。
对于 $70 \%$ 的数据，满足特殊限制 $X$。
对于 $100 \%$ 的数据，$T = 3, 1 \le n \le 10^5$。

特殊限制 $X$：$c_i = i, d_i = i + 1$，也就是说**小 B 的树**是一条链，编号相邻的点之间有边。


title: [IOI2012] 理想城

description:
像许多同龄的科学家和艺术家一样，小 L 对城市规划和城区设计很感兴趣.他致力于构建一个理想城。理想城由 $N$ 个区块组成，而这些区块放在一个无限大的正方形网格上。第 $x$ 行第 $y$ 列的单元格由有序数对 $(x,y)$来标识。单元格 $(0,0)$ 位于网格的左上角。给定一个单元格 $(x,y)$，与之相邻的单元格（如果存在的话）分别为：$(x-1,y)$，$(x+1,y)$，$(x,y-1)$，$(x,y+1)$。每个区块在网格上恰好覆盖一个单元格。一个区块能够被放置在单元格 $(x,y)$ 上，当且仅当 $1 \le x,y \le 2^{31}-2$ 。我们将使用单元格的坐标同时来代表单元格上面的区块。若两个区块被放在相邻的单元格中，则视它们为相邻区块.理想城所有的区块连在一起，里面没有“洞”存在.换言之，所有单元格必须满足下述两个条件：
- 对于任意两个空白的单元格，至少存在一连串相邻的空白单元格连接它们。
- 对于任意两个非空的单元格，至少存在一连串相邻的非空单元格连接它们。

以下 $4$ 个图中的区块放置均不满足理想城的条件。前两个图不满足第一个条件。第 $3$ 个图不满足第二个条件，第 $4$ 个图两个条件均不满足。

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

当遍历理想城时，一个**跳步**代表**从一个区块走到一个相邻的区块**。跳步时不能移进空白单元格。假设 $v_0,v_1,\cdots,v_{N-1}$ 是 $N$ 个区块的坐标。对于任意两个不同的区块 $v_i$ 和 $v_j$，它们的距离 $d(v_i,v_j)$ 是从 $v_i$ 移动到 $v_j$ 所需的最小跳步数目。

下图是一个由 $11$ 个区块组成的理想城。区块坐标分别为

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

$$v_0=(2,5) \quad v_1=(2,6) \quad v_2=(3,3)$$
$$v_3=(3,6) \quad v_4=(4,3) \quad v_5=(4,4)$$
$$v_6=(4,5) \quad v_7=(4,6) \quad v_8=(5,3)$$
$$v_9=(5,4) \quad v_{10}=(5,6)$$

其中，$d(v_1,v_3)=1$，$d(v_1,v_8)=6$，$d(v_6,v_10)=2$，$d(v_9,v_10)=4$。

给定一个理想域，试求
$$S=\sum_{i=0}^{N-2}\sum_{j=i+1}^{N-1}d(v_i,v_j)$$

inputFormat:
第 $1$ 行为一个正整数 $N$，为理想城区块的数目。

第 $2$ 行到第 $N+1$ 行，每行有两个非负整数。第 $i+2$ 行为第 $i$ 个区块的坐标 $v_i = (x_i， y_i)$。

outputFormat: 输出仅一行一个正整数，为 $S$ 的值。由于 $S$ 的值可能较大，你只需输出 $S$ 对 $10^9$ 取模的值。


title: [IOI2009] Regions

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

IOI2009 D2T3

原题时间限制 8s，为节约评测资源，时间限制改为 4s。

description:
联合国区域发展委员会（The United Nations Regional Development Agency, UNRDA）有一个良好的组织结构。它任用了 $N$ 名委员，每名委员都属于几个地区中的一个。委员们按照其资历被编号为 $1$ 到 $N$ ，$1$ 号委员是主席，资历最高。委员所属地区被编号为 $1$ 到 $R$。除了主席之外所有委员都有一个直接导师。任何直接导师的资历都比他所指导的委员的资历要高。

我们称委员 $A$ 是委员 $B$ 的导师当且仅当 $A$ 是 $B$ 的直接导师或者 $A$ 是 $B$ 的直接导师的导师。显然，主席是所有其他委员的导师，没有任何两名委员互为导师。

现在，为了调查大量对 UNRDA 偏向某些地区的不平衡的组织结构的指控，UNRDA 想要建立一个计算机系统：在给定委员之间的直接导师关系的情况下，该系统可以回答下述形式的问题：给定两个地区 $r_1$ 和 $r_2$，要求系统回答委员会中有多少对委员 $e_1$ 和 $e_2$，满足 $e_1$ 属于 $r_1$，而 $e_2$ 属于 $r_2$，并且 $e_1$ 是 $e_2$ 的导师。每次询问都有两个参数 $r_1$ 和 $r_2$，结果是一个整数：满足上述条件的 $(e_1, e_2)$ 二元组的数量。

**任务**：编写一个程序，给定每个委员的地区和直接导师，**在线** 回答上述询问。

**强制在线将以交互的格式进行**。

inputFormat:
第一行包含三个整数 $N, R, Q$，分别由一个空格隔开，分别表示雇员人数，区域数和查询数。

接下来 $N$ 行按照资历的顺序给出了 $N$ 个委员的描述信息。其中第 $k$ 行描述了编号为 $k$ 的委员。第一行（描述主席的一行）包含一个整数：主席所属的地区 $H_1$。其余的 $N - 1$ 行，每行包含两个整数，以一个空格隔开分别表示委员 $k$ 的直接导师 $S_k$ 和委员 $k$ 所属的地区 $H_k$。

### 交互格式

在读入所有输入数据之后，你的程序必须依次从标准输入中读入询问，并将询问结果输出至标准输出。必须依次回答 $Q$ 个询问，每次回答一个。**在读入下一个询问之前，你必须先回答当前询问**。

每个询问是标准输入的一行，用两个不同整数 $r_1, r_2$ 表示。

outputFormat:
对查询的回答是标准输出的一行，包含一个整数，表示在 UNRDA 中有多少对委员 $e_1$ 和 $e_2$ 满足下述条件：$e_1$ 属于地区 $r_1$，$e_2$ 属于地区 $r_2$，并且 $e_1$ 是 $e_2$ 的导师。

**注意**：输入数据保证给出的任意询问的正确答案小于 $10 ^ 9$。

**特别注意**：为了正确地和交互库交互，你的程序必须 **在回答每次询问后刷新标准输出缓冲区**。你同样需要避免意外地在读入标准输入时堵住了输入流，这有可能在你使用 `scanf("%d\n", ...)` 的语句时发生。

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

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

特别的，对于 C++ 语言，在输出换行时如果你使用 `std::endl` 而不是 `'\n'`，也可以自动刷新缓冲区。

samples:
1 [刷新缓冲区]

3 [刷新缓冲区]

2 [刷新缓冲区]

1 [刷新缓冲区]

hint:
### 数据范围与约定

- 对于 $30\%$ 的数据，$N\leq 500$。
- 对于 $55\%$ 的数据，没有地区包含超过 $500$ 个委员。
- 同时满足上述两个条件的数据有 $15\%$，至少满足上述一个条件的数据有 $70\%$。
- 对于 $100\%$ 的数据，$1 \le N, Q \le 2 \times 10^5$，$1 \le H_k, r_1, r_2 \le R \le 2.5 \times 10^4$，$1 \le S_k < k$。


title: 线段树

background: 小 W 学习了一种叫做线段树的数据结构。

description:
很快，小 W 就发现：线段树实在是太浪费空间了！

比如，一棵 $n=6$ 的线段树长下面这样：

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

可以发现，只有 $11$ 个节点存储了有用信息，但使用的数组下标到了 $13$。

令 $f(n)$ 表示一棵 $n$ 个叶子节点的线段树所占的最大数组下标，现在小 W 想让你求出：
$$f(l)\;\oplus\;f(l+1)\;\oplus\;f(l+2)\;\oplus\cdots \oplus\;f(r)$$
其中，$\oplus$ 表示异或运算，相当于 C++ 中的`^`符号。

inputFormat: 一行两个整数，表示 $l,r$，意义如上。

outputFormat: 一行一个整数，表示结果。

hint:
## 样例解释
$f(6)=13$，故答案为 $13$。
## 提示
如果你不知道什么是线段树：
```cpp
void build(int k,int l,int r)
{
	if(l==r)
	{
		//do something
		//e.g. tree[k]=a[l]
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	//do something
	//e.g. tree[k]=tree[k<<1]+tree[k<<1|1]
}
```
翻译成人话就是：编号为 $k$ 节点有一个线段 $[l,r]$，如果 $l\neq r$，那么令 $mid=\lfloor\dfrac{l+r}2\rfloor$，它有两个子节点，左儿子编号为 $2k$，线段为 $[l,mid]$；右儿子编号为 $2k+1$，线段为 $[mid+1,r]$，然后在子节点上递归建树。

调用`build(1,1,n)`后就建好了一棵线段树，即编号为 $1$ 的结点的线段为 $[1,n]$。
## 数据范围
对于 $10\%$ 的数据，$1\le l\le r\le10^3$。
对于 $40\%$ 的数据，$1\le l\le r\le 10^6$。
对于 $100\%$ 的数据，$1\le l\le r\le10^{15}$，答案在`long long`范围内。


title: 轴对称

background: 小 W 学习了轴对称变换。

description:
小 W 觉得轴对称变换实在太好玩了，于是在平面上随机点了 $n$ 个点 $A_1,A_2,\cdots,A_n$，然后进行了一系列轴对称变换，得到了 $B_1,B_2,\cdots,B_n$ 这 $n$ 个点，其中 $A_1$ 得到 $B_1$，以此类推。

可是他突然忘记自己是怎么变换到的了，所以他请你帮他找到一组步数尽量少的合法的变换。

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

接下来 $n$ 行，第 $i+1$ 行两个实数 $x,y$，表示 $A_i$ 的横、纵坐标。

接下来 $n$ 行，第 $i+n+1$ 行两个实数 $x,y$，表示 $B_i$ 的横、纵坐标。

outputFormat:
第一行一个整数 $k$ ，表示最少的步数。

接下来 $k$ 行，第 $i+1$ 行三个实数 $A,B,C$，表示第 $i$ 次轴对称变换的轴为直线 $Ax+By+C=0$。

hint:
## 样例解释
![](https://cdn.luogu.com.cn/upload/image_hosting/8msdygxi.png)
## 提示
对于直线 $Ax+By+C=0$，如果 $B$ 非零，那么它就是一次函数 $y=-\dfrac ABx-\dfrac CB$ 的图像；否则，它表示一条垂直于 $x$ 轴的直线 $x=-\dfrac CA$。

本题带有 $\text{SPJ}$。**因为某种原因，本题不提供** $\text{SPJ}$ **给选手。**

对于每个测试点，如果你的 $k$ 正确，则获得 $30\%$ 的分数；

接下来，我们将对 $A_1,A_2,\cdots,A_n$ 分别进行你给的 $k$ 次轴对称变换，记 $A_i$ 得到的点为 $C_i$。如果对于所有的 $i$，$B_i$ 与 $C_i$ 的 $x,y$ 坐标之差的绝对值都不超过 $10^{-2}$，则你获得 $100\%$ 的分数。

如果你只想输出 $k$，也请在后面随意输出一些值，防止 $\text{UKE}$。
## 数据范围

| 测试点编号 | $n=$ | 构造数据时翻折的次数 |
| ---------- | ---- | -------------------- |
| 1,2        | $1$  | $\le1$               |
| 3,4        | $2$  | $\le10$              |
| 5,6        | $5$  | $\le10^3$            |
| 7,8,9,10   | $10$ | $\le10^5$            |

对于所有数据，$1\le n\le10$，$|x|,|y|\le 10^5$。

所有数据点已经经过 $\text{SPJ}$ 验证无误。

请保证你的输出中的所有 $A,B,C$ 满足 $|A|,|B|,|C|\le 10^5$。


title: [IOI2009] Salesman

background: IOI2009 D2T4

description:
旅行商已经发现，最佳的陆上旅行计划是一个难以解决的计算问题，所以他将他的生意转移到多瑙河的线性世界。他有一条很快的船，可以在很短的时间内把他从沿河的任何地方送到任何地方，但不幸的是，这条船耗油量很大。旅行商向上游（靠近河流源头的方向）移动每一米的成本为 $U$ 美元，向下游（远离河流源头的方向）移动每一米的成本为 $D$ 美元。

沿河有 $N$ 个展销会，旅行商想参加。每场展销会只举行一天。对于每个展销会 $X$，旅行商知道它的日期 $T_X$（他买船后的天数为第 $0$ 天），集市的位置 $L_X$ 和他在这场集市上能获得的盈利 $M_X$。位置表示集市到河流源头的距离，以米为单位。他必须在位置为 $S$ 的家 **开始和结束** 他的旅程。

帮助旅行商选择参加哪些展销会（如果有的话）以及按什么顺序，这样他可以在旅行结束时最大化他的利润。旅行商的总利润是指他在参加集市时获得的美元减去他在河上下游旅行所花费的美元的总和。

请记住，如果展销会 $A$ 的举办时间早于展销会 $B$，则旅行商只能按此顺序去展销会（即，他不能先去展销会 $B$，然后再去展销会 $A$）。但是，如果两个集市在同一天举行，旅行商可以按任何顺序参观。旅行商一天去多少个集市是没有限制的，但他不能在同一个集市盈利两次。他可以经过他已经参观过的集市而一无所获。

**任务**：编写一个程序，给定所有展销会的日期，位置和旅行商的盈利额，以及旅行商的家的位置和他移动的代价，求出他在旅行结束时的最大利润。

inputFormat:
第一行包含四个整数 $N, U, D, S$，分别由一个空格隔开，分别表示展销会数，向上游（$U$）或下游（$D$）移动的单位代价，以及旅行商的家的位置。

接下来的 $N$ 行描述了 $N$ 个展销会。其中第 $k$ 行描述了第 $k$ 个展销会的信息，包含三个整数，分别由一个空格隔开，分别表示展销会日期 $T_k$，它的位置 $L_k$，以及旅行商在该次展销会能获得的的盈利 $M_k$。

outputFormat: 一行一个整数表示旅行商在旅行结束时的最大利润。

hint:
### 样例解释

在一个最优方案中，旅行商参加了编号为 $1$ 和 $3$ 的展销会（位置分别为 $80$ 和 $75$）。事件序列以及对应的利润如下：

- 旅行商从家出发，向上游移动 $20$ 米，花费 $100$ 美元。目前利润：$-100$。
- 旅行商参加展销会 $1$ 并赚取 $100$ 美元。目前利润：$0$。
- 旅行商向上游移动 $5$ 米，花费 $25$ 美元。目前利润 $-25$。
- 旅行商参加展销会 $3$ 并赚取 $150$ 美元。目前利润：$125$。
- 旅行商向下游移动 $25$ 米，回到自己的家，花费 $75$ 美元。最终利润：$50$。

### 数据范围与约定

- 对于 $60\%$ 的数据，没有两个展销会在同一天举行。
- 对于 $40\%$ 的数据，输入的所有数不超过 $5000$。
- 同时满足上述两个条件的数据有 $15\%$，至少满足上述一个条件的数据有 $85\%$。
- 对于 $100\%$ 的数据，$1 \le N, T_k \le 5\times 10^5$，$1 \le D \le U \le 10$，$1 \le S, L_k \le 5 \times 10^5 +1$，$1 \le M_k \le 4000$。


title: 【模板】树上 K 级祖先

background: **本题仅作为长链剖分求树上 $k$ 级祖先评测用，不保证卡掉了其他复杂度不正确的做法。**

description:
给定一棵 $n$ 个点的有根树。

有 $q$ 次询问，第 $i$ 次询问给定 $x_i, k_i$，要求点 $x_i$ 的 $k_i$ 级祖先，答案为 $ans_i$。特别地，$ans_0 = 0$。

本题中的询问将在程序内生成。

给定一个随机种子 $s$ 和一个随机函数 $\operatorname{get}(x)$：

```cpp
#define ui unsigned int
ui s;

inline ui get(ui x) {
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return s = x;
}
```

你需要按顺序依次生成询问。

设 $d_i$ 为点 $i$ 的深度，其中根的深度为 $1$。

对于第 $i$ 次询问，$x_i = ((\operatorname{get}(s) \operatorname{xor} ans_{i-1}) \bmod n) + 1$，$k_i = (\operatorname{get}(s) \operatorname{xor} ans_{i-1}) \bmod d_{x_i}$。

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

第二行 $n$ 个整数 $f_{1\dots n}$，其中 $f_i$ 表示 $i$ 的父亲。特别地，若 $f_i = 0$，则 $i$ 为根。

outputFormat: 一行一个整数，表示 $\operatorname{xor}_{i=1}^q i \times ans_i$。


title: 【模板】全源最短路（Johnson）

description:
给定一个包含 $n$ 个结点和 $m$ 条带权边的有向图，求所有点对间的最短路径长度，一条路径的长度定义为这条路径上所有边的权值和。

注意：

1. 边权**可能**为负，且图中**可能**存在重边和自环；

2. 部分数据卡 $n$ 轮 SPFA 算法。

inputFormat:
第 $1$ 行：$2$ 个整数 $n,m$，表示给定有向图的结点数量和有向边数量。

接下来 $m$ 行：每行 $3$ 个整数 $u,v,w$，表示有一条权值为 $w$ 的有向边从编号为 $u$ 的结点连向编号为 $v$ 的结点。

outputFormat:
若图中存在负环，输出仅一行 $-1$。

若图中不存在负环：

输出 $n$ 行：令 $dis_{i,j}$ 为从 $i$ 到 $j$ 的最短路，在第 $i$ 行输出 $\sum\limits_{j=1}^n j\times dis_{i,j}$，注意这个结果可能超过 int 存储范围。

如果不存在从 $i$ 到 $j$ 的路径，则 $dis_{i,j}=10^9$；如果 $i=j$，则 $dis_{i,j}=0$。

hint:
【样例解释】

左图为样例 $1$ 给出的有向图，最短路构成的答案矩阵为：

```
0 4 11 8 11
1000000000 0 7 4 7
1000000000 -5 0 -3 0
1000000000 -2 5 0 3
1000000000 -1 4 1 0
```

右图为样例 $2$ 给出的有向图，红色标注的边构成了负环，注意给出的图不一定连通。

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

【数据范围】

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^3,\ \ 1\leq m\leq 6\times 10^3,\ \ 1\leq u,v\leq n,\ \ -3\times 10^5\leq w\leq 3\times 10^5$。

对于 $20\%$ 的数据，$1\leq n\leq 100$，不存在负环（可用于验证 Floyd 正确性）

对于另外 $20\%$ 的数据，$w\ge 0$（可用于验证 Dijkstra 正确性）

upd. 添加一组 Hack 数据：针对 SPFA 的 SLF 优化


title: [POI2014] HOT-Hotels 加强版

background:
同 [[POI2014]HOT-Hotels](https://www.luogu.com.cn/problem/P3565)，数据范围加大到 $1 \le n \le 10^5$。

来源于 BZOJ4543。

description:
给出一棵有 $n$ 个点的树，求有多少组点 $(i,j,k)$ 满足 $i,j,k$ 两两之间的距离都相等。

$(i,j,k)$ 与 $(i,k,j)$ 算作同一组。

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

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

outputFormat: 一行一个整数，表示所有合法的点的组数。

hint: 对于 $100\%$ 的数据， $1\le n\le10^5, 1\le a\le b\le n$。


title: [Cnoi2020] 光图

background:
> 简洁中蕴含着伟大。

Cirno 不经意地把一个内部完全反射的圆分成了 $12$ 等分，等分点分别记作 $A_0$, $A_1$, $A_2$, $\cdots$ , $A_{11}$。

随后，她不经意地将一束光从一点发出，朝向另一点，重复，反射，迭代，便得到了一幅美妙的光图。

这一切都发生在不经意之间。

她不经意地发现了这一幕，并且不经意地记下了这个不经意的结论，又在某一刻不经意地回忆起。

幻想乡的每一天一切都是这么不以为意，多好的一天啊！

description:
Rumia 有一个单位圆，被分成 $n$ 等分，等分点分别记作 $A_0$, $A_1$, $A_2$, $\cdots$ , $A_{n-1}$。

现在她从 $A_0$ 向 $A_p$ 发射一束光，经过 $k$ 次反射，到达了 $A_t$。

Rumia 想知道 $t$ 的值，由于 Cirno 并不想帮她，所以 Rumia 转而求助于你。

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

outputFormat: 一行，一个整数 $t$。

hint:
### Sample1 解释

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

### 后置物理知识
 - **连续曲线反射规律** : 入射光线与出射光线关于入射点在曲线上切线夹角相等。

### 数据范围约定

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

 - Subtask1( $80\%$ ) : $n, k \le 10^6$
 - Subtask2( $20\%$ ) : $n, k \le 10^9$

对于 $100\%$ 的数据 : $0 < p < n \le 10^9$, $0 < k \le 10^9$。

### 后记
 - Cirno 得到的光图就是传说中的**十二芒星图**。


title: [Cnoi2020] 向量

background:
> 向量(vector)，指具有大小(Magnitude)和方向(Direction) 的量。
> 与向量对应的量叫做数量(Scalar)，数量只有大小，没有方向。

对于 Cirno 来说，整天环绕氷屋的旋转 Sangetsusei 们是向量而不是数量。
 - Sunny Milk 以 $r_1$ 为半径做匀速圆周运动。
 - Luna Child 以 $r_2$ 为半径做匀加速圆周运动。
 - Star Sapphire 以 $r_3$ 为半径做变加速圆周运动。

为了尽可能的减小三月精们的影响，一些重要的参数必需被计算。

description:
以氷屋为原点，三月精的位置分别记作向量 $\vec{a}$, $\vec{b}$, $\vec{c}$。

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

由定义可知，$|\vec{a}|=r_1$, $|\vec{b}|=r_2$, $|\vec{c}|=r_3$。

现在 Cirno 分配给你的任务是计算其 **破坏极限指数** $\sigma$。

$$\sigma=\min\{\vec{a}\cdot\vec{b}+\vec{b}\cdot\vec{c}+\vec{c}\cdot\vec{a}\}$$

其中「$\cdot$」表示 **向量内积**。

outputFormat: 一行，一个 **实数** $\sigma$。（**小数点后保留一位数字**）

hint:
### Sample1 解释

$\cos\langle\vec{a},\vec{b}\rangle=0,\cos\langle\vec{b},\vec{c}\rangle=-\frac{4}{5},\cos\langle\vec{c},\vec{a}\rangle=-\frac{3}{5}$ 时答案最小。

### 后置数学知识
 - **向量内积定义** : $\vec{a}\cdot\vec{b}=|\vec{a}||\vec{b}|\times \cos\langle\vec{a},\vec{b}\rangle$
 - **向量内积坐标表示** : $(x_1,y_1)\cdot(x_2,y_2)=x_1x_2+y_1y_2$

### 数据范围约定

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

 - Subtask1( $20\%$ ) : $r_1=r_2=r_3$
 - Subtask2( $40\%$ ) : $r_1,r_2,r_3 \le 10$
 - Subtask3( $40\%$ ) : $r_1,r_2,r_3 \le 10^9$

对于 $100\%$ 的数据 $0 < r_1 \le r_2 \le r_3 \le 10^9$