title: [Code+#1] 可做题

description:
qmqmqm希望给sublinekelzrip出一道可做题。于是他想到了这么一道题目：给一个长度为$n$的非负整数序列$a_i$,你需要计算其异或前缀和$b_i$,满足条件$b_1=a_1$,$b_i=b_{i-1}\ xor\ a_i(i \geq 2)$.

但是由于数据生成器出现了问题，他生成的序列$a$的长度特别长，并且由于内存空间不足，一部分$a_i$已经丢失了，只剩余$m$个位置的元素已知。现在qmqmqm找到你，希望你根据剩余的$a_i$,计算出所有可能的$a$序列对应的$b$序列中$\sum_{i=1}^n b_i$的最小值。

inputFormat:
输入第一行两个非负整数$n$,$m$,分别表示原始序列$a$的长度及剩余元素的个数。

之后$m$行，每行$2$个数$i$,$a_i$，表示一个剩余元素的位置和数值。

outputFormat: 输出一个整数表示可能的最小值。

hint:
### 样例解释

已知的$a$序列为：$X,X,7,0,0$,其中$X$表示这个位置丢失了。一种可能的$a$序列为$0,7,7,0,0$,对应的$b$序列为$0,7,0,0,0$,和最小为$7$。可以证明不存在和更小的情况。

 ![](https://cdn.luogu.com.cn/upload/pic/12823.png)

注意未知的$a_i$可以超过已知$a_i$的范围。

保证输入中所有的$i$不同，且满足$1 \leq i \leq n$。

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/卢政荣 命题/卢政荣 验题/何昊天

Git Repo：https://git.thusaac.org/publish/CodePlus201711

感谢腾讯公司对此次比赛的支持。


title: [Code+#1] 大吉大利，晚上吃鸡！

type: P

background:
最近《绝地求生：大逃杀》风靡全球，皮皮和毛毛也迷上了这款游戏，他们经常组队玩这款游戏。

在游戏中，皮皮和毛毛最喜欢做的事情就是堵桥，每每有一个好时机都能收到不少的快递。

当然，有些时候并不能堵桥，皮皮和毛毛会选择在其他的必经之路上蹲点。

K博士作为一个老年人，外加有心脏病，自然是不能玩这款游戏的，但是这并不能妨碍他对这款游戏进行一些理论分析，比如最近他就对皮皮和毛毛的战术很感兴趣。

description:
游戏的地图可以抽象为一张 $n$ 个点 $m$ 条无向边的图，节点编号为 $1$ 到 $n$ ，每条边具有一个正整数的长度。

**假定大魔王都会从 $S$ 点出发到达 $T$ 点（ $S$ 和 $T$ 已知），并且只会走最短路，**皮皮和毛毛会在 $A$ 点和 $B$ 点埋伏大魔王。

为了保证一定能埋伏到大魔王，同时又想留大魔王一条生路，皮皮和毛毛约定 $A$ 点和 $B$ 点必须满足：

- 大魔王所有可能路径中，必定会经过 $A$ 点和 $B$ 点中的任意一点

- 大魔王所有可能路径中，不存在一条路径同时经过 $A$ 点和 $B$ 点

K博士想知道，满足上面两个条件的 $A,B$ 点对有多少个，交换 $A,B$ 的顺序算相同的方案。

inputFormat:
第一行输入四个整数 $n,m,S,T(1 \le n \le 5 \times 10^{4}, 1 \le m \le 5 \times 10^{4}, 1 \le S,T \le n)$ ，含义见题目描述。

接下来输入 $m$ 行，每行输入三个整数 $u,v,w(1 \le u,v \le n, 1 \le w \le 10^{9})$ 表示存在一条长度为 $w$ 的边链接 $u$ 和 $v$ 。

outputFormat: 输出一行表示答案。

hint:
### 样例1解释

合法的方案为$<2,3>,<2,4>,<4,3>,<4,5>,<6,3>,<6,5>$ 。

 ![](https://cdn.luogu.com.cn/upload/pic/12824.png)

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/陈宇 命题/陈宇 验题/邢健开

Git Repo：https://git.thusaac.org/publish/CodePlus201711

感谢腾讯公司对此次比赛的支持。


title: [Code+#1] Yazid 的新生舞会

background: 这道题是没有舞伴的 Yazid 用新生舞会的时间出的。

description:
Yazid 有一个长度为 $n$ 的序列 $A$，下标从 $1$ 至 $n$。显然地，这个序列共有 $\frac{n\left( n+1\right)}{2}$ 个子区间。

对于任意一个子区间 $[l,r]$，如果该子区间内的众数在该子区间的出现次数严格大于 $\frac{r-l+1}{2}$（即该子区间长度的一半），那么 Yazid 就说这个子区间是“新生舞会的”。

所谓众数，即为该子区间内出现次数最多的数。特别地，如果出现次数最多的数有多个，我们规定值最小的数为众数。

现在，Yazid 想知道，共有多少个子区间是“新生舞会的”。

inputFormat:
第一行两个用空格隔开的非负整数 $n, type$，表示序列的长度和**数据类型**。数据类型的作用将在「子任务」中说明。

第二行 $n$ 个用空格隔开的非负整数，依次为 $A_1,A_2,...,A_n$，描述这个序列。

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

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

“新生舞会的”子区间有 $[1,1],[1,2],[1,3],[2,2],[2,4],[3,3],[3,4],[3,5],[4,4],[5,5]$ 共 $10$ 个。

 ![](https://cdn.luogu.com.cn/upload/pic/12825.png)

对于所有数据，保证 $0\leq A_i\leq n-1$。

对于 $type=0$ 的数据，没有任何特殊约定。

对于 $type=1$ 的数据，保证 $A_i\in \{ 0, 1 \}$。

对于 $type=2$ 的数据，保证序列 $A$ 的众数在整个序列中的出现次数不超过 $15$。

对于 $type=3$ 的数据，保证 $A_i\leq 7$。

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/郑林楷 命题/王聿中 验题/郑林楷

Git Repo：https://git.thusaac.org/publish/CodePlus201711

感谢腾讯公司对此次比赛的支持。


title: [JXOI2017] 数列

description:
九条可怜手上有一个长度为 $n$ 的整数数列 $r_i$，她现在想要构造一个长度为 $n$ 的，满足如下条件的整数数列 $A$ ：

- $1 \le A_i \le r_i$

- 对于任意 $3 \le i \le n$ ，令 $R$ 为 $A_1$ 至 $A_{i-2}$ 中大于等于 $A_{i-1}$ 的最小值，$L$ 为 $A_1$ 至 $A_{i-2}$ 中小于等于 $A_{i-1}$ 的最大值。$A_i$ 必须满足 $L \le A_i \le R$ 。如果不存在大于等于 $A_{i-1}$ 的，那么 $R=+\infty$ ；如果不存在小于等于 $A_{i-1} $ 的，那么 $L = -\infty$ 。

现在可怜想要知道共有多少不同的数列满足这个条件。两个数列 $A$ 和 $B$ 是不同的当且仅当至少存在一个位置 $i$ 满足 $A_i \neq B_i$ 。

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


title: [JXOI2017] 加法

description:
可怜有一个长度为 $n$ 的正整数序列 $A$，但是她觉得 $A$ 中的数字太小了，这让她很不开心。

于是她选择了 $m$ 个区间 $[l_i,r_i]$ 和两个正整数 $a,k$。她打算从这 $m$ 个区间里选出恰好 $k$ 个区间，并对每个区间执行一次区间加 $a$ 的操作。（每个区间最多只能选择一次）。

对区间 $[l,r]$ 进行一次加 $a$ 操作可以定义为对于所有 $i$ ∈ $[l,r]$，将 $A_i$ 变成 $A_i+a$。现在可怜想要知道怎么选择区间才能让操作后的序列的最小值尽可能的大，即最大化 $\min\{A_i\}$。

inputFormat:
第一行输入一个整数表示数据组数。

对于每组数据第一行输入四个整数 $n,m,k,a$。

第二行输入 $n$ 个整数描述序列 $A$。

接下来 $m$ 行每行两个整数 $l_i,r_i$ 描述每一个区间。数据保证所有区间两两不同。

outputFormat: 对于每组数据输出一个整数表示操作后序列最小值的最大值。


title: [JXOI2017] 颜色

description:
可怜有一个长度为 $n$ 的正整数序列 $A_i$，其中相同的正整数代表着相同的颜色。

现在可怜觉得这个序列太长了，于是她决定选择一些颜色把这些颜色的所有位置都删去。

删除颜色 $i$ 可以定义为把所有满足 $A_j = i$ 的位置 $j$ 都从序列中删去。

然而有些时候删去之后，整个序列变成了好几段，可怜不喜欢这样，于是她想要知道有多少种删去颜色的方案使得最后剩下来的序列非空且连续。

例如颜色序列 $\{1, 2, 3, 4, 5\}$，删除颜色 $3$ 后序列变成了 $\{1, 2\}$ 和 $\{4, 5\}$ 两段，不满足条件。而删除颜色 $1$ 后序列变成了 $\{2, 3, 4, 5\}$，满足条件。

两个方案不同当且仅当至少存在一个颜色 $i$ 只在其中一个方案中被删去。

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

每组数据第一行，输入一个整数 $n$ 表示数列长度；第二行输入 $n$ 个整数描述颜色序列。

outputFormat: 对于每组数据输出一个整数表示答案。

hint:
满足条件的删颜色方案有 $\{1\}, \{1, 3\}, \{1, 2, 3\}, \{1, 3, 4\}, \{2, 3, 4\}, \varnothing$。

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

对于 $40\%$ 的数据，保证 $1 \le \sum n \le  500$。

对于 $60\%$ 的数据，保证 $1 \le \sum n \le  10^4$。

对于 $100\%$ 的数据，保证 $1 \le  T,\sum n \le  3 \times 10^5, 1 \le  A_i \le  n$。

$\text{Statement fixed by @Starrykiller.}$


title: [SHOI2003] 吃豆豆

description:
两个 PACMAN 吃豆豆。一开始的时候，PACMAN 都在坐标原点的左下方，豆豆都在右上方。PACMAN 走到豆豆处就会吃掉它。
PACMAN 行走的路线很奇怪，只能向右走或者向上走，他们行走的路线可以有交点但不能互相穿过。
请你帮这两个 PACMAN 计算一下，他们俩加起来最多能吃掉多少豆豆。

inputFormat: 第一行为一个整数 $N$，表示豆豆的数目。 接下来 $N$ 行，每行一对正整数，表示第 $i$ 个豆豆的坐标。任意两个豆豆的坐标都不会重合。

outputFormat: 仅有一行包含一个整数，即两个 PACMAN 加起来最多能吃掉的豆豆数量


title: [JSOI2009] 计数问题

description:
一个 $n \times\ m$ 的方格，初始时每个格子有一个整数权值。接下来每次有 2 种操作：

- 改变一个格子的权值；

- 求一个子矩阵中某种特定权值出现的个数。

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

接下来 $n$ 行，每行 $m$ 个数，第 $i+1$ 行第 $j$ 个数表示格子 $(i,j)$ 的初始权值。

接下来输入一个整数 $Q$。

之后 $Q$ 行，每行描述一个操作。

操作 1：输入一行四个整数 $1\ x\ y\ c$，表示将格子 $(x,y)$ 的权值改成 $c$。

操作 2：输入一行六个整数 $2\ x_1\ x_2\ y_1\ y_2\ c$。表示询问所有满足格子颜色为 $c$，且满足 $x_1\le x\le x_2,y_1\le y\le y_2$ 的格子个数。

outputFormat: 对于每个操作 2，按照在输入中出现的顺序，依次输出一行一个整数表示所求得的个数。

hint:
【数据规模与约定】

对于 $30\%$ 的数据，满足：$n,m\le 30$，$Q\le 5\times 10^4$。

对于 $100\%$ 的数据，满足：$1\le n,m\le 300$，$1\le Q\le 2\times 10^5$。

对于操作 1，保证：$1\le x
\le n$，$1\le y\le m$，$1\le c\le 100$；

对于操作 2，保证：$1\le x_1≤x_2\le n$，$1\le y_1\le y_2\le m$，$1\le c\le 100$。


title: [JSOI2009] 火星藏宝图

description:
在火星游玩多日,jyy 偶然地发现了一张藏宝图。根据藏宝图上说法，宝藏被埋藏在一个巨大的湖里的 $N$ 个岛上 $(2\le N \le 2 \times 10^{5})$。为了方便描述，地图把整个湖划分成 $M$ 行 $M$ 列 $(1\le M\le 1000)$,共 $M \times M$ 个小块，并把所有岛按照 $1...N$ 编了号。第 $i$ 个岛位于第 $X_i$ 行 $Y_i$ 列 (设其坐标为 $(X_i,Y_i)$的格子 （ $X_i,Y_i$ 均为整数，并且满足 $1<=X_i,Y_i<=M$ ）,岛上藏有价值财富 $V_i(1\le V_i\le 10,000)$。湖的左上角 $(1,1)$ 和右下角 $(M,M)$ 都有岛，有桥将它们与陆地相连。

jyy 没费多大劲，就找到了那个湖，同时哭笑不得地发现，所谓的财富，是各个岛上出产的珍稀水果。jyy 在左上角的岛的岸边找到了一条小木船，他可以划船到其他岛上去。划船是要消耗体力的，具体地说，等于两岛 Euclidean 距离的平方(即，从 $(X_1,Y_1)$ 划船到 $(X_2,Y_2)$ 所耗费的体力为 $(X_1-X_2)^2+(Y_1-Y_2)^2$ 个单位)。jyy 可以吃水果来恢复体力，吃掉 $1$ 单位价值的水果能恢复 $1$ 单位体力。

现在 jyy 打算从 $(1,1)$ 旅行到 $(M,M)$，沿途收集珍稀水果。按藏宝图上的提示，jyy 离开一个岛后，就只能去该岛右下方的区域（正下和正右方向也是允许的），否则会遭遇水怪。jyy 可以在旅行途中饿一段时间，即体力为负。但抵达终点后，只要身边有足够多的水果，他就会通过吃水果将体力恢复到旅行前的水平。

jyy想知道，经过一次旅行，他最多能得到多少收益，即 `jyy 收集到的水果总价值- jyy 在旅途中花的总体力` 。(如果吃完所有水果他还饿着，收益就是负数，具体的例子见样例)

inputFormat: 第 $1$ 行：两个整数 $N,M$。第 $2...N+1$ 行：每行 $3$ 个整数，第 $i+1$ 行的 $3$ 个整数分别为 $ X_i$，$Y_i$，$V_i$。每个岛的坐标不同。保证存在坐标 $(1,1)$ 和 $(M,M)$ 的岛。

outputFormat: 第 $1$ 行：输出一个整数，表示最大收益。


title: [JSOI2007] 合金

description:
某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。

现在，用户给出了 $n$ 种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。

inputFormat:
第一行两个整数 $m$ 和 $n$，分别表示原材料种数和用户需要的合金种数。

第 $2$ 到 $m+1$ 行，每行三个实数 $a_i, b_i, c_i$，分别表示铁铝锡在一种原材料中所占的比重。

第 $m+2$ 到 $m+n+1$ 行，每行三个实数 $d_i, e_i, f_i$，分别表示铁铝锡在一种用户需要的合金中所占的比重。

outputFormat: 一个整数，表示最少需要的原材料种数。若无解，则输出 `–1`。

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

对于全部的测试点，满足 $1\le m,n\le 500$，$0 \leq a_i,b_i,c_i,d_i,e_i,f_i \leq 1$，且 $a_i+b_i+c_i=1$，$d_i+e_i+f_i=1$，小数点后最多有六位数字。


title: [JSOI2007] 字符加密

description:
喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。

例如‘JSOI07’，可以读作：  JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序： 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符：I0O7SJ，就是加密后的字符串（其实这个加密手段实在很容易破解，鉴于这是突然想出来的，那就^^）。 但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？

inputFormat: 输入文件包含一行，欲加密的字符串。注意字符串的内容不一定是字母、数字，也可以是符号等。

outputFormat: 输出一行，为加密后的字符串。

hint:
对于40%的数据字符串的长度不超过10000。

对于100%的数据字符串的长度不超过100000。


title: 洞穴遇险

background:
**ZRQ**在洞穴中准备采集矿物的时候遇险了！洞穴**要塌了**！

题目来源：[zhoutb2333](https://www.luogu.org/space/show?uid=31564)

description:
整个洞穴是一个$N*N$的方格图，每个格子形如$(X,Y),1 \le X,Y \le N$。其中$X$表示从上到下的行数，$Y$表示从左到右的列数。$(1,1)$在左上角,$(1,N)$在右上角，$(N,1)$在左下角，$(N,N)$在右下角。

满足$X+Y$为奇数格子的有一个不稳定度$V_{X,Y},X+Y$为偶数的格子的不稳定度为$0$。

**ZRQ**现在手里恰巧有$M$个可以支撑洞穴的柱子，柱子的力量可以认为是无穷大。

只要支撑住了一个格子那么这个格子的不稳定度将降为$0$。

每个柱子是$L$型的，它除了要占据当前的格子外，还需要占据两个相邻的格子（这三个格子形成$L$型,可以选择任意方向放置，一共有$4$个方向）。

 ![](https://cdn.luogu.com.cn/upload/pic/13049.png)

**柱子占据相邻的格子不会降低其不稳定度（换句话说就是柱子只有在拐角处有力量）**。

有些格子的顶已经塌下来了，无法在其位置放置柱子了，这些格子也不能被占据了。这样已经塌了的格子有$K$个（他们的不稳定度都为$0$,**即使$X+Y$为奇数，塌下来的格子的不稳定度也会为$0$**）。

**ZRQ**想问你，在放置一些柱子后 ，最小的不稳定度之和为多少（可以不将$M$个柱子都放完）。

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

接下来$N$行每行$N$个整数，表示每个格子的不稳定度，**保证$X+Y$为偶数的格子和已经塌下的格子的不稳定度为$0$**。

接下来$K$行每行$2$个整数$X,Y$，表示已经塌下的格子的坐标。

outputFormat: 一行一个整数，表示最小的不稳定度的和。


title: MloVtry与jump

background: 浏览～

description:
众所周知，MloVtry有很多纸片人老婆（我永远喜欢IA.jpg），不过很可惜，并不是所有人都是死宅，所以很多人无法理解MloVtry 的兴趣。

Vittorio就是一个坏文明，他十分喜欢刁难MloVtry。

现在Vittorio构建了一个n个点的地图，MloVtry必须穿过这张图才能prpr到它的纸片人老婆。但是穿过地图听起来就太费力气了，于是MloVtry就咬住1号点狠狠一抖，把这张图甩成了一颗有根树。

MloVtry是个好文明，它有一个高科技的设备---弹力装置---来帮助自己。具体的，如果MloVtry在i号点，这个装置会把它从当前点向下弹出a[i]（这个值被称为弹力值）个距离---我们认为1号点是在上方的，并且每条边的距离是1。不过问题是MloVtry并不能准确控制自己的落点，换言之降落在哪个位置是不确定的，但是MloVtry可以肯定的是降落的点一定可以让它不拐弯的走回出发的点（也就是只能落在子树内）---它一向认为自己是头耿直的生物。当然，由于a[i]是个正整数，所以它一定可以跳到它老婆的身旁。

现在MloVtry有几个问题，它想知道假设它从x号点出发，赶到老婆身边的期望步数是多少，不过由于化图为树这个操作太耗费能量了，所以这个问题就只能交给它最好的好朋友---您这头神犇了。

但是之前说过，Vittorio是个坏文明，他对弹力装置做了些手脚，每个弹力装置只有在没有树内的落点时才会跳出。并且他可能会偷偷更换掉一些节点上的弹力装置，这可能会带来一点难度，不过您一定没问题。

inputFormat:
第1行两个整数n,q，表示这个图有n个节点，并且接下来有q个操作。

第2行是一行整数，表示a[i]数组的初始值。

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

接下来q行，每行有3~2个整数，具体的：

1  x  y   表示Vittorio将x号节点上的弹力装置换成了一个弹力值为y的弹力装置。

0  x      表示MloVtry想知道从x号节点出发的期望步数是多少。

outputFormat:
请对每个询问输出一个分数

特别的，如果分母为1也请把它输出出来

（如：2/1）

hint:
样例解释

第一个询问

1-2-4-5-out

1-2-5-out

1-8-out

1-3-6-10-out

1-3-7-out

总路径数为:5

总跳跃次数为:16

1-4-9-out

1-5-out

1-6-10-out

1-7-out

（由于存在树内的落点，所以1-out无法行走）

总路径数为:4

总跳跃次数为:10

n<=100000 ,q<=200000

不对a[i]的值做出保证

对于30%的数据，有n<=1000

对于50%的数据，有n<=10000

特殊的

对于20%的数据，有a[i]=1

保证最后答案在2147483647的范围之内。

数据保证在window环境下随机生成。


title: [WC2013] 平面图

description:
在一个平面中有 $n$ 个顶点和 $m$ 条直线段，第 $i$ 个顶点的坐标为 $(x_i, y_i)$， 第 $j$ 条直线段连接顶点 $u_j$ 和顶点 $v_j$，权值为 $h_j$， 除顶点 $u_j$ 和 $v_j$ 外直线段 $j$ 不经过其他的顶点。任意两条直线段如果存在公共点，则该公共点一定是一个顶点，此时这两条直线段都会连接这个顶点。对于任意的两个顶点 $x$ 和 $y$，总是可以找到一顶点序列 $a_1,a_2,\cdots,a_k$ 使得 $a_1=x$，$a_k=y$ 且对于任意 $1\le i< k$ 满足 $a_i$ 和 $a_{i+1}$ 被一条直线段直接连接。

这 $m$ 条直线段将整个平面分成了若干个区域，其中只有一个区域是无穷大的，其余均是有界的，我们称无穷大的区域为禁区。

现在给出 $q$ 次询问，每次给定平面中的任意两个不是顶点且分别不在任意一条直线段上的点 $A$ 和 $B$，请画一条曲线连接 $A$ 和 $B$，要求曲线不能经过禁区以及任何顶点，并使得穿过的直线段中权值最大的尽可能小。你需要对每次询问回答这个值最小为多少。

inputFormat:
第一行有两个正整数 $n,m$，分别表示顶点数和直线段数。

接下来 $n$ 行，每行两个整数，这部分中第 $i$ 行（总第 $i+1$ 行）的两个整数 $x_i,y_i$ 为顶点 $i$ 的坐标。

接下来 $m$ 行，每行三个正整数 $u,v,h$，表示有一条直线段连接顶点 $u$ 和顶点 $v$，权值为 $h$。其中 $u\neq v$。

接下来的一行，有一个正整数 $q$，表示询问数量。

接下来 $q$ 行，每行四个实数 $A_x,A_y,B_x,B_y$， 表示一组两个点的坐标分别为 $(A_x, A_y)$ 和 $(B_x, B_y)$ 的询问。

outputFormat: 输出 $q$ 行，每行一个正整数，依次表示每个询问的答案。特别的，若不需要跨过任何一条边即可到达，请输出 $0$；若不存在合法的曲线，请输出 $-1$。

hint:
【样例说明】

![QQ20180112214336.png](https://www.z4a.net/images/2018/01/12/QQ20180112214336.png)

【数据规模与约定】

本题共设有 $10$ 个测试点，每个测试点的规模与特征如下：

![QQ20180112215357.png](https://www.z4a.net/images/2018/01/12/QQ20180112215357.png)

对于全部数据，均满足 $5$ ≤ $n$, $m$, $q$ ≤ $100,000$，所有直线段的权值不会超过 $10^9$。所有询问坐标均为不超过 $10^7$ 的实数，且保证是 $0.5$ 的整数倍。


title: [WC2013] 糖果公园

description:
Candyland 有一座糖果公园，公园里不仅有美丽的风景、好玩的游乐项目，还有许多免费糖果的发放点，这引来了许多贪吃的小朋友来糖果公园游玩。

糖果公园的结构十分奇特，它由 $n$ 个游览点构成，每个游览点都有一个糖果发放处，我们可以依次将游览点编号为 $1$ 至 $n$。有 $n - 1$ 条双向道路连接着这些游览点，并且整个糖果公园都是连通的，即从任何一个游览点出发都可以通过这些道路到达公园里的所有其它游览点。

糖果公园所发放的糖果种类非常丰富，总共有 $m$ 种，它们的编号依次为 $1$ 至 $m$。每一个糖果发放处都只发放某种特定的糖果，我们用 $C_i$ 来表示 $i$ 号游览点的糖果。

来到公园里游玩的游客都不喜欢走回头路，他们总是从某个特定的游览点出发前往另一个特定的游览点，并游览途中的景点，这条路线一定是唯一的。他们经过每个游览点，都可以品尝到一颗对应种类的糖果。

大家对不同类型糖果的喜爱程度都不尽相同。 根据游客们的反馈打分，我们得到了糖果的美味指数， 第 $i$ 种糖果的美味指数为 $V_i$。另外，如果一位游客反复地品尝同一种类的糖果，他肯定会觉得有一些腻。根据量化统计，我们得到了游客第 $i$ 次品尝某类糖果的新奇指数 $W_i$。如果一位游客第 $i$ 次品尝第 $j$ 种糖果，那么他的愉悦指数 $H$ 将会增加对应的美味指数与新奇指数的乘积，即 $V_j \times W_i$。这位游客游览公园的愉悦指数最终将是这些乘积的和。

当然，公园中每个糖果发放点所发放的糖果种类不一定是一成不变的。有时，一些糖果点所发放的糖果种类可能会更改（也只会是 $m$ 种中的一种），这样的目的是能够让游客们总是感受到惊喜。

糖果公园的工作人员小 A 接到了一个任务，那就是根据公园最近的数据统计出每位游客游玩公园的愉悦指数。但数学不好的小 A 一看到密密麻麻的数字就觉得头晕，作为小 A 最好的朋友，你决定帮他一把。

inputFormat:
从文件 `park.in` 中读入数据。

第一行包含三个正整数 $n, m, q$， 分别表示游览点个数、 糖果种类数和操作次数。

第二行包含 $m$ 个正整数 $V_1, V_2, \ldots, V_m$。

第三行包含 $n$ 个正整数 $W_1, W_2, \ldots, W_n$。

第四行到第 $n + 2$ 行，每行包含两个正整数 $A_i, B_i$，表示这两个游览点之间有路径可以直接到达。

第 $n + 3$ 行包含 $n$ 个正整数 $C_1, C_2, \ldots, C_n$。

接下来 $q$ 行， 每行包含三个整数 $Type, x, y$，表示一次操作：

- 若 $Type$ 为 $0$，则 $1 \leq x \leq n$， $1 \leq y \leq m$，表示将编号为 $x$ 的游览点发放的糖果类型改为 $y$；
- 若 $Type$ 为 $1$，则 $1 \leq x, y \leq n$，表示对出发点为 $x$，终止点为 $y$ 的路线询问愉悦指数。

outputFormat:
输出到文件 `park.out` 中。

按照输入的先后顺序，对于每个 $Type$ 为 $1$ 的操作输出一行，用一个正整数表示答案。

hint:
【样例解释】

我们分别用

![QQ20180112220959.png](https://www.z4a.net/images/2018/01/12/QQ20180112220959.png)

代表 $C_i$ 为 $1$、 $2$、 $3$ 的节点，在修改之前：

![QQ20180112221024.png](https://www.z4a.net/images/2018/01/12/QQ20180112221024.png)

在将 $C_2$ 修改为 $1$ 之后：

![QQ20180112221106.png](https://www.z4a.net/images/2018/01/12/QQ20180112221106.png)

【数据规模与约定】

对于所有的数据： $1 \leq V_i, W_i \leq 10^6$，$1 \leq A_i, B_i \leq n$， $1 \leq C_i \leq m$， $W_1, W_2, \ldots, W_n$ 是非递增序列，即对任意 $1 < i \leq n$， 满足 $W_i \le W_{i-1}$。

其它的限制条件如下表所示：

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


title: Qtree1

background: **数据规模和 spoj 上有所不同**。

description:
给定一棵 $n$ 个节点的树，有两种操作：
- `CHANGE i t` 把第 $i$ 条边的边权变成 $t$
- `QUERY a b` 输出从 $a$ 到 $b$ 的路径上最大的边权。当 $a=b$ 时，输出 $0$

inputFormat:
第一行是一个整数 $n$，表示节点个数。
第二行到第 $n$ 行每行输入三个整数 $u,v,w$ ，分别表示 $u$ 与 $v$ 有一条边，边权是 $w$。
第 $n+1$ 行开始，一共有不定数量行，每一行先包含一个字符串，分别有以下三种可能：

- `CHANGE`  接下来包含两个整数 $x, t$ ，表示一次修改操作。
- `QUERY`  接下来包含两个正整数 $a, b$ ， 表示一次查询操作。
- `DONE`  表示输入结束。

outputFormat: 对于每个 `QUERY` 操作，输出一行一个数，表示 $a,b$ 的路径上最大的边权。

samples:
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

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

对于全部的测试点，保证：

- $1 \leq n \leq 10^5$。
- $1 \leq u, v, a, b \leq n$，$1 \leq x < n$。
- $1 \leq w, t \leq 2^{31} - 1$。
- 操作次数不大于 $3 \times 10^5$。


title: [USACO17DEC] Standing Out from the Herd P

description:
Just like humans, cows often appreciate feeling they are unique in some way. Since Farmer John's cows all come from the same breed and look quite similar, they want to measure uniqueness in their names.

Each cow's name has some number of substrings. For example, "amy" has substrings {a, m, y, am, my, amy}, and "tommy" would have the following substrings: {t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy}.

A cow name has a "uniqueness factor" which is the number of substrings of that name not shared with any other cow. For example, If amy was in a herd by herself, her uniqueness factor would be 6. If tommy was in a herd by himself, his uniqueness factor would be 14. If they were in a herd together, however, amy's uniqueness factor would be 3 and tommy's would be 11.

Given a herd of cows, please determine each cow's uniqueness factor.

定义一个字符串的「独特值」为只属于该字符串的本质不同的非空子串的个数。如 "amy" 与 “tommy” 两个串，只属于 "amy" 的本质不同的子串为 "a" "am" "amy" 共 3 个。只属于 "tommy" 的本质不同的子串为 "t" "to" "tom" "tomm" "tommy" "o" "om" "omm" "ommy" "mm" "mmy" 共 11 个。 所以 "amy" 的「独特值」为 3 ，"tommy" 的「独特值」为 11 。

给定 N ($N \leq 10^5$) 个字符集为小写英文字母的字符串，所有字符串的长度和小于 $10^5$，求出每个字符串「独特值」。

inputFormat: The first line of input will contain $N$ ($1 \le N \le 10^5$). The following $N$ lines will each contain the name of a cow in the herd. Each name will contain only lowercase characters a-z. The total length of all names will not exceed $10^5$.

outputFormat: Output $N$ numbers, one per line, describing the uniqueness factor of each cow.


title: [USACO17DEC] Push a Box P

description:
**题目译自 [USACO 2017 December Contest, Platinum](http://usaco.org/index.php?page=dec17results) Problem 2. [Push a Box](http://usaco.org/index.php?page=viewproblem2&cpid=769)**

一个谷仓是一个 $N \times M$ 的矩形网格，有一些网格里有干草。 Bessie 站在其中一个格子内，还有一个格子里有一个大木箱。 Bessie 不能和大木箱在一个格子里，也不能和干草在一个格子里。

如果她不与干草在同一个格子，她就可以往自己旁边的四个方向（东西南北）移动，如果她想移动到有木箱的格子里，那个木箱就会被她推一格（只要木箱的那个方向还有空间），如果没有空间，那 Bessie 就不能移动了。

给你谷仓的布局（空格子，干草以及木箱位置）以及 Bessie 的出发位置和箱子要被推到的位置，请你帮忙计算 Bessie 能不能把木箱推到指定位置。

inputFormat:
第一行有三个数 $N,M,Q$，其中 $N$ 是谷仓的行数，$M$ 是列数，$Q$ 是询问数。

接下来 $N$ 行是谷仓的初始布局，其中 `.` 代表空格子， `#` 代表干草格子， `A` 代表 Bessie 的初始位置， `B` 是木箱的初始位置。

接下来 $Q$ 行，每行一个坐标 $(R,C)$ ，代表第 $R$ 行第 $C$ 行。对于每行，你要输出 Bessie 是否有可能把箱子推到这个位置。

outputFormat: $Q$ 行，每行一个答案，如果 Bessie 能走到，输出 `YES` ，否则输出 `NO` 。


title: [USACO17DEC] Greedy Gift Takers P

description:
Farmer John's nemesis, Farmer Nhoj, has $N$ cows ($1 \leq N \leq 10^5$), conveniently numbered $1 \dots N$. They have unexpectedly turned up at Farmer John's farm, so the unfailingly polite Farmer John is attempting to give them gifts.

To this end, Farmer John has brought out his infinite supply of gifts, and Nhoj's cows have queued up in front of him, with cow $1$ at the head of the queue and cow $N$ at the tail. Farmer John was expecting that at every timestep, the cow at the head of the queue would take a gift from Farmer John and go to the tail of the queue. However, he has just realized that Nhoj's cows are not that polite! After receiving her gift, each cow may not go to the tail of the queue, but rather may cut some number of cows at the tail, and insert herself in front of them. Specifically, cow $i$ will always cut exactly $c_i$ cows ($0 \leq c_i \leq N-1$).

Farmer John knows that some cows might receive multiple gifts; as he has an infinite supply, this does not worry him. But he is worried that some cows might become unhappy if they do not get any gifts.

Help Farmer John find the number of cows who never receive any gifts, no matter how many gifts are handed out.

有 N($1≤N≤10^5$)头牛按顺序排成一列，编号从 1 到 N，1 号牛在队头，N 号牛在队尾。

每次位于队头的牛 i 拿到一个礼物，然后插入到从队尾数$c_i$头牛之前的位置。。举个栗子： 初始队列 1,2,3,4,5 $c_1$ = 2，$c_2$ = 3，则第一次操作后的序列为 2,3,1,4,5，第二次操作后的序列为 3,2,1,4,5。重复无限次操作，求最后有几头牛拿不到礼物。

inputFormat:
The first line contains a single integer, $N$.

The second line contains $N$ space-separated integers $c_1, c_2, \dots, c_N$.

outputFormat: Please output the number of cows who cannot receive any gifts.


title: [USACO17DEC] A Pie for a Pie G

description:
Bessie and Elsie have each baked $N$ pies ($1 \leq N \leq 10^5$). Each of the $2N$ pies has a tastiness value according to Bessie and a (possibly different) tastiness value according to Elsie.

Bessie is thinking about giving one of her pies to Elsie. If Elsie receives a pie from Bessie, she will feel obligated to give one of her pies to Bessie. So as to not appear stingy nor flamboyant, Elsie will try to pick a pie that is at least as tasty (in Elsie's eyes) as the pie she received, but no more than $D$ units tastier ($0 \leq D \leq 10^9$). Such a pie may not exist, in which case Elsie will adopt a pseudonym and exile herself to Japan.

But if Elsie does give Bessie a pie in return, Bessie will similarly try to give Elsie a pie which is at least as tasty but no more than $D$ units tastier (in Bessie's eyes) as the pie Elsie just gave her. Should this be impossible, Bessie too will exile herself. Otherwise she will give her chosen pie to Elsie. This cycle will continue until one of the cows is exiled, an unhappy outcome, or one of the cows receives a pie which she accords a tastiness value of $0$, in which case the gift exchange will end and both cows will be happy.

Note that a pie may not be gifted twice, nor can either cow return a pie gifted to her.

For each of the $N$ pies Bessie could select as her initial gift to Elsie, determine the minimum number of pies that could possibly be gifted in the resulting exchange before the cows are happy.

inputFormat:
The first line contains the two integers $N$ and $D$.

The next $2N$ lines contain two space-separated integers each, respectively denoting the value of a particular pie according to Bessie, and the value of that pie according to Elsie.

The first $N$ lines refer to Bessie's pies, and the remaining $N$ lines refer to Elsie's pies.

It is guaranteed that all tastiness values are in the range $[0,10^9]$.

outputFormat: There should be $N$ lines in the output. Line $i$ should contain a single integer: the minimum number of pies that could be gifted in a happy gift exchange started with Bessie's pie $i$. If no gift exchange starting with pie $i$ is happy, then line $i$ should contain the single integer $-1$ instead.

translation:
原翻译出锅严重且有机翻痕迹，请尽快更换新的翻译
```plain
Bessie和Elsie各自烤了$N\:(1≤N≤10^5)$个馅饼）。Bessie 会这$2N$个馅饼打分，Elsie 也会。二者的打分均为一个$\le 10^9$的非负整数。由于她们口味不同，每个派的两个分数可能不同。
她们想互赠礼物。开始时，Bessie 送给 Elsie 一个馅饼。她们收到礼物（对方做的馅饼）后都会回赠对方一个自己做的馅饼。
她们选择回礼的方法相同。以 Elsie 为例，Elsie **根据自己的打分**来选择回礼。回礼的分数至少要大于她收到的馅饼的分数，但两个馅饼的分数差不能大于$D\:(0≤D≤10^9)$。如果有多个馅饼满足要求，Elsie 可以选择其中的任意一个作为回礼。若没有馅饼满足要求，Elsie 会放弃。Bessie 选择回礼的方法同理。
她们之间的礼物交换将持续到一头牛放弃（Bad End），或一头牛收到一个她自己打分为$0$的馅饼，此时礼物交换愉快结束（Happy End）。
请注意，不能把一个馅饼赠送两次，不能把馅饼送给自己。
Bessie 想知道：对于每个她做的馅饼，如果她将这个馅饼作为最开始送给 Elsie 的礼物，她俩至少要互赠多少次馅饼（Bessie 给 Elsie 算一次，Elsie 回赠 Bessie 又算一次），才能 Happy End 。如果不可能 Happy End，请输出 `-1`。
#### 输入格式
第一行有两个整数 $N, D$。
在接下来的$2N$行中，每行有两个整数，表示对于某个馅饼，Bessie 的打分和 Elsie 的打分。其中，前$N$行表示 Bessie 做的馅饼，后$N$行则是 Elsie 做的馅饼。
#### 输出格式
输出共$N$行，每行一个整数。
第$i$行的整数表示：如果 Bessie 将馅饼$i$作为最开始送给 Elsie 的礼物，她俩至少要互赠多少次馅饼才能 Happy End 。如果不可能 Happy End，请在该行输出 `-1`。
```
Bessie和Elsie各自烤了 $N\:(1≤N≤10^5)$ 个馅饼）。Bessie 会这 $2N$ 个馅饼打分，Elsie 也会。二者的打分均为一个 $\le 10^9$ 的非负整数。由于她们口味不同，每个派的两个分数可能不同。
她们想互赠礼物。开始时，Bessie 送给 Elsie 一个馅饼。她们收到礼物（对方做的馅饼）后都会回赠对方一个自己做的馅饼。
她们选择回礼的方法相同。以 Elsie 为例，Elsie **根据自己的打分**来选择回礼。回礼的分数至少要大于她收到的馅饼的分数，但两个馅饼的分数差不能大于 $D\:(0≤D≤10^9)$ 。如果有多个馅饼满足要求，Elsie 可以选择其中的任意一个作为回礼。若没有馅饼满足要求，Elsie 会放弃。Bessie 选择回礼的方法同理。
她们之间的礼物交换将持续到一头牛放弃（Bad End），或一头牛收到一个她自己打分为 $0$ 的馅饼，此时礼物交换愉快结束（Happy End）。
请注意，不能把一个馅饼赠送两次，不能把馅饼送给自己。
Bessie 想知道：对于每个她做的馅饼，如果她将这个馅饼作为最开始送给 Elsie 的礼物，她俩至少要互赠多少次馅饼（Bessie 给 Elsie 算一次，Elsie 回赠 Bessie 又算一次），才能 Happy End 。如果不可能 Happy End，请输出 `-1`。
#### 输入格式
第一行有两个整数 $N, D$。
在接下来的 $2N$ 行中，每行有两个整数，表示对于某个馅饼，Bessie 的打分和 Elsie 的打分。其中，前 $N$ 行表示 Bessie 做的馅饼，后 $N$ 行则是 Elsie 做的馅饼。
#### 输出格式
输出共 $N$ 行，每行一个整数。
第 $i$ 行的整数表示：如果 Bessie 将馅饼 $i$ 作为最开始送给 Elsie 的礼物，她俩至少要互赠多少次馅饼才能 Happy End 。如果不可能 Happy End，请在该行输出 `-1`。

翻译者：Planet6174


title: [USACO17DEC] Barn Painting G

description:
Farmer John has a large farm with $N$ barns ($1 \le N \le 10^5$), some of which are already painted and some not yet painted. Farmer John wants to paint these remaining barns so that all the barns are painted, but he only has three paint colors available. Moreover, his prize cow Bessie becomes confused if two barns that are directly reachable from one another are the same color, so he wants to make sure this situation does not happen.

It is guaranteed that the connections between the $N$ barns do not form any 'cycles'. That is, between any two barns, there is at most one sequence of connections that will lead from one to the other.

How many ways can Farmer John paint the remaining yet-uncolored barns?

inputFormat:
The first line contains two integers $N$ and $K$ ($0 \le K \le N$), respectively the number of barns on the farm and the number of barns that have already been painted.

The next $N-1$ lines each contain two integers $x$ and $y$ ($1 \le x, y \le N, x \neq y$) describing a path directly connecting barns $x$ and $y$.

The next $K$ lines each contain two integers $b$ and $c$ ($1 \le b \le N$, $1 \le c \le 3$) indicating that barn $b$ is painted with color $c$.

outputFormat: Compute the number of valid ways to paint the remaining barns, modulo $10^9 + 7$, such that no two barns which are directly connected are the same color.

translation: 题意：给定一颗 $N$ 个节点组成的树，你要给每个点涂上三种颜色之一，其中有 $K$ 个节点已染色，要求任意两相邻节点颜色不同，求合法染色方案数。答案对 $10^9+7$ 取模。


title: [USACO17DEC] Haybale Feast G

description:
Farmer John is preparing a delicious meal for his cows! In his barn, he has $N$ haybales ($1 \le N \le 100,000$). The $i$th haybale has a certain flavor $F_i$ ($1 \le F_i \le 10^9$) and a certain spiciness $S_i$ ($1 \le S_i \le 10^9$).

The meal will consist of a single course, being a contiguous interval containing one or more consecutive haybales (Farmer John cannot change the order of the haybales). The total flavor of the meal is the sum of the flavors in the interval. The spiciness of the meal is the maximum spiciness of all haybales in the interval.

Farmer John would like to determine the minimum spiciness his single-course meal could achieve, given that it must have a total flavor of at least $M$ ($1 \le M \le 10^{18}$).

inputFormat: The first line contains the integers $N$ and $M$, the number of haybales and the minimum total flavor the meal must have, respectively. The next $N$ lines describe the $N$ haybales with two integers per line, first the flavor $F$ and then the spiciness $S$.

outputFormat: Please output the minimum spiciness in a single course meal that satisfies the minimum flavor requirement. There will always be at least one single-course meal that satisfies the flavor requirement.

translation:
农夫约翰正在为他的奶牛准备一顿美味的晚餐!在他的谷仓里，他有 $N$ 个干草捆 $(1 \le N \le 10^5)$ 。第 $i$ 个干草捆有一定的风味 $F_i(1 \le F_i \le 10^9)$ 和一定的辣度 $S_i(1 \le S_i \le 10^9)$ 。

这顿饭将由一道菜组成，是一个连续的区间，包含一个或多个连续的干草捆(农夫约翰不能改变干草捆的顺序)。这顿饭的总体的风味是这段区间里风味的总和。这顿饭的总体辣度是区间中所有草包的最大辣度。

农夫约翰想确定他的这道菜所能达到的最小辣度，但是这道菜的总风味必须至少为 $M(1 \le M \le 10^{18})$ 。

### 输入格式

第一行包含两个整数 $N$ 和 $M$ ，分别是干草包的数量和这顿饭必须有的最小风味之和。

接下来的 $N$ 行，每行两个整数描述这 $N$ 个草包，首先是风味 $F_i$，然后是辣度 $S_i$。

### 输出格式

请输出这道菜中在满足最低风味时的最低辣度。保证至少有一顿单道菜的饭能满足风味的要求。


title: [USACO17DEC] My Cow Ate My Homework S

description:
In your bovine history class, you have been given a rather long homework assignment with $N$ questions ($3 \leq N \leq 100,000$), each graded with an integer score in the range 0...10,000. As is often customary, your teacher plans to assign a final grade by discarding a question on which you received the lowest score and then averaging the remaining scores together. Unfortunately, your pet cow Bessie has just eaten your answers to the first $K$ questions! ($K$ could be as small as 1 or as large as $N-2$).

After copious explanation, your teacher finally believes your story, and agrees to grade the remaining non-eaten part of the assignment the same way as before -- by removing the lowest-scoring question (or one such question, in the event of a tie) and averaging the rest.

Please output all values of $K$ which would have earned you the maximum possible score according to this grading scheme, in sorted order.

inputFormat: The first line of input contains $N$, and the next line contains the scores on the $N$ homework questions.

outputFormat: Please output, one value per line, all values of $K$ which would have earned you the maximum possible score.

translation:
在你的历史课上，你得到了一个很长的作业。这个作业包含了 $N$ 个题目（$3 \le N \le 100,000$），每个题目的成绩在 $0 \sim 10,000$ 之间。

按照惯例，你的老师按照以下方式计算最终成绩：去掉你最低的一个成绩，然后将其余成绩的平均成绩作为最终成绩。但不幸的是，你的宠物牛“贝西”刚刚吃了前 $K$ 个题目的答案！（$1 \le K \le N-2$）

经过你的一番解释，老师终于相信了你的故事，并且同意对你有答案的题目（没有被吃掉答案的题目）像之前一样给分——通过去掉最低的成绩（如果有多个最低成绩，则只去掉其中一个）并取剩余成绩的平均成绩。

根据这一成绩计算方案，请按升序输出所有可以使你最终成绩最高的 $K$ 的值，相邻输出之间用**换行**隔开。

hint: If Bessie eats the first two questions, then the remaining scores are 9, 2, and 7. Removing the minimum and averaging, we get a final grade of 8, which is the highest possible.


title: [USACO17DEC] Milk Measurement S

description:
Each of Farmer John's cows initially produces $G$ gallons of milk per day ($1 \leq G \leq 10^9$). Since the milk output of a cow is known to potentially change over time, Farmer John decides to take periodic measurements of milk output and write these down in a log book. Entries in his log look like this:

35 1234 -2

14 2345 +3

The first entry indicates that on day 35, cow #1234's milk output was 2 gallons lower than it was when last measured. The next entry indicates that on day 14, cow #2345's milk output increased by 3 gallons from when it was last measured. Farmer John has only enough time to make at most one measurement on any given day. Unfortunately, he is a bit disorganized, and doesn't necessarily write down his measurements in chronological order.

To keep his cows motivated, Farmer John proudly displays on the wall of his barn the picture of whichever cow currently has the highest milk output (if several cows tie for the highest milk output, he displays all of their pictures). Please determine the number of days on which Farmer John would have needed to change this display.

Note that Farmer John has a very large herd of cows, so although some of them are noted in his log book as changing their milk production, there are always plenty of other cows around whose milk output level remains at $G$ gallons.

最初，农夫约翰的每头奶牛每天生产G加仑的牛奶$(1≤G≤10^9)$。由于随着时间的推移，奶牛的产奶量可能会发生变化，农夫约翰决定定期对奶牛的产奶量进行测量，并将其记录在日志中。

他的日志中的记录如下:

35 1234 -2

14 2345 +3

第一个条目表明：在第35天，1234号奶牛的产奶量比上次测量时降低了2加仑。

第二个条目表明：在第14天，2345号奶牛的产奶量比上次测量时增加了3加仑。

农夫约翰只有在任何一天内做最多一次测量的时间（即每天最多做一次测量，但可能不做）。不幸的是，约翰有点杂乱无章，他不一定按照时间顺序记下测量结果。为了保持奶牛的产奶动力，农夫约翰自豪地在谷仓的墙上展示了目前产奶量最高的奶牛的照片（如果有若干头奶牛的产奶量最高，他就会展示所有的图片）。

请求出约翰需要调整所展示的照片的次数。

请注意，农夫约翰有一大群奶牛。所以尽管日志中记录了一些奶牛改变了产奶量，但仍然还有很多奶牛的产奶量保持在G加仑。

inputFormat:
The first line of input contains the number of measurements $N$ that Farmer John makes ($1 \leq N \leq 100,000$), followed by $G$. Each of the next $N$ lines contains one measurement, in the format above, specifying a day (an integer in the range $1 \ldots 10^6$), the integer ID of a cow (in the range $1 \ldots 10^9$), and the change in her milk output since it was last measured (a nonzero integer). Each cow's milk output will always be in the range $0 \ldots 10^9$.

第一行是两个整数N和G，分别表示测量的次数和初始产奶量。

接下来N行，每行为一次测量。每行三个数：分别表示日期一（在整数1...$10^6$范围内），奶牛的编号（在整数1...$10^9$范围内），该奶牛的产奶量变化值（一个非零整数）。无论如何，每头奶牛的产奶量永远保证在$0...10^9$范围内。

outputFormat:
Please output the number of days on which Farmer John needs to adjust his motivational display.

请输出约翰总共调整所展示的照片的次数。


title: [USACO17DEC] The Bovine Shuffle S

description:
Convinced that happy cows generate more milk, Farmer John has installed a giant disco ball in his barn and plans to teach his cows to dance!

Looking up popular cow dances, Farmer John decides to teach his cows the "Bovine Shuffle". The Bovine Shuffle consists of his $N$ cows ($1 \leq N \leq 100,000$) lining up in a row in some order, then performing successive "shuffles", each of which potentially re-orders the cows. To make it easier for his cows to locate themselves, Farmer John marks the locations for his line of cows with positions $1 \ldots N$, so the first cow in the lineup will be in position 1, the next in position 2, and so on, up to position $N$.

A shuffle is described with $N$ numbers, $a_1 \ldots a_N$, where a cow in position $i$ moves to position $a_i$ during the shuffle (and so, each $a_i$ is in the range $1 \ldots N$). Every cow moves to its new location during the shuffle. Unfortunately, all the $a_i$'s are not necessarily distinct, so multiple cows might try to move to the same position during a shuffle, after which they will move together for all remaining shuffles.

Farmer John notices that some positions in his lineup contain cows in them no matter how many shuffles take place. Please help him count the number of such positions.

inputFormat: The first line of input contains $N$, the number of cows. The next line contains the $N$ integers $a_1 \ldots a_N$.

outputFormat: Please output the number of positions that will always contain cows, no matter how many shuffles take place.

translation:
背景

FJ 坚信快乐的牛可以产出更多的牛奶，因此 FJ 在牛棚里安装了一个巨大的迪斯科球并且打算让奶牛们学会跳舞。

FJ在许多出名的奶牛舞中选择了一种叫做 `Bovine Shuffle` 的舞蹈。这种舞蹈由 FJ 的 $N$ 头奶牛组成。$N$ 头奶牛以一种顺序排成一行，接着表演数次 `shuffle`。每次的 `shuffle` 会将奶牛重新排列。FJ 为了让奶牛们更加快乐，让奶牛们更容易找到重新排列后的位置，他标记了 $N$ 头奶牛的位置。在最开始，所有奶牛排成一排，第一头奶牛会在位置 $1$ 上，第二只在 $2$ 上，以此类推。

我们用 $N$ 个正整数 $a_1,a_2\dots a_n$ 来描述每次的 `shuffle`。$a_i$ 说明了在位置 $i$ 上的奶牛在经过这回合的 `shuffle` 之后，会跑到位置 $a_i$ 上。令 FJ 倍感非洲的是，即使 $i$ 与$j$ 不同，$a_i$ 也可能会等于 $a_j$ ！所以可能在一次 `shuffle` 后，有多头奶牛会跑到同一位置上，在这之后这群奶牛也会一同行动。

作为一名资深的养牛大户&坑牛专家的 FJ 猛然发现，无论经过多少次的 `shuffle`，一直都有 $k$ 个位置上有奶牛。FJ现在要你在 $1$ 秒内帮他得出 $k$ 的值，否则就赏你 $10^{18} \bmod10$ 大板！

输入格式

第一行包含一个整数，$N$

第二行包含 $N$ 个整数，描述题目中的$a_1,a_2\dots a_n$

输出格式

一个整数，代表 $k$


title: [HEOI2016/TJOI2016] 求和

description:
在2016年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。

现在他想计算这样一个函数的值:

$$f(n)=\sum_{i=0}^n\sum_{j=0}^i S(i,j)\times 2^j \times (j!)$$

S(i, j)表示第二类斯特林数，递推公式为:

$S(i, j) = j \times S(i - 1, j) + S(i - 1, j - 1), 1 \le j \le i - 1$。

边界条件为：$S(i, i) = 1(0 \le i), S(i, 0) = 0(1 \le i)$

你能帮帮他吗?

inputFormat: 输入只有一个正整数 $n$。

outputFormat: 输出 $f(n)$。由于结果会很大，输出 $f(n)$ 对 998244353 ($7 \times 17 \times 2^{23} + 1$) 取模的结果即可。

hint:
对于 $50\%$ 的数据，$1\leq n \leq5\times10^3$。

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


title: [HEOI2016/TJOI2016] 树

description:
在 2016 年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树，根为 $1$ ，有以下两种操作：

1. 标记操作：对某个结点打上标记。（在最开始，只有结点 $1$ 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）

2. 询问操作：询问某个结点最近的一个打了标记的祖先。（这个结点本身也算自己的祖先）

你能帮帮她吗?

inputFormat:
第一行两个正整数 $N$ 和 $Q$ 分别表示节点个数和操作次数。

接下来 $N-1$ 行，每行两个正整数 $u,v \,\, (1 \leqslant u,v \leqslant n)$ 表示 $u$ 到 $v$ 有一条有向边。

接下来 $Q$ 行，形如 `oper num` ，`oper`  为 `C` 时表示这是一个标记操作, `oper` 为 `Q` 时表示这是一个询问操作。

outputFormat: 输出一个正整数，表示结果

hint:
$30\%$ 的数据，$1 \leqslant N, Q \leqslant 1000$ ；

$70\%$ 的数据，$1 \leqslant N, Q \leqslant 10000$ ；

$100\%$ 的数据，$1 \leqslant N, Q \leqslant 100000$ 。


title: [HEOI2016/TJOI2016] 序列

description:
佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。

玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在**任意一种变化和原序列**中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可。

inputFormat:
输入的第一行有两个正整数 $n,m$，分别表示序列的长度和变化的个数。

接下来一行有 $n$ 个整数，表示这个数列原始的状态。

接下来 $m$ 行，每行有 $2$ 个整数 $x,y$，表示数列的第 $x$ 项可以变化成 $y$ 这个值。

outputFormat: 输出一个整数，表示对应的答案。

hint:
注意：每种变化最多只有一个值发生变化。

在样例输入中，所有的变化是：
```plain
1 2 3
2 2 3
1 3 3
1 1 3
1 2 4
```
选择子序列为原序列，即在任意一种变化中均为不降子序列。

对于 $20\%$ 数据，所有数均为正整数，且小于等于 $300$。

对于 $50\%$ 数据，所有数字均为正整数，且小于等于 $3000$。

对于 $100\%$ 数据，所有数字均为正整数，且小于等于 $10^5$。$1\le x\le n$。


title: [HEOI2016/TJOI2016] 字符串

description:
佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为 $n$ 的字符串 $s$，和 $m$ 个问题。佳媛姐姐必须正确回答这 $m$ 个问题，才能打开箱子拿到礼物，升职加薪，出任 CEO，嫁给高富帅，走上人生巅峰。

每个问题均有 $a,b,c,d$ 四个参数，问你子串 $s[a..b]$ 的所有子串和 $s[c..d]$ 的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？

inputFormat:
输入的第一行有两个正整数 $n,m$，分别表示字符串的长度和询问的个数。

接下来一行是一个长为 $n$ 的字符串。接下来 $m$ 行，每行有 $4$ 个数 $a,b,c,d$，表示询问 $s[a..b]$ 的所有子串和 $s[c..d]$ 的最长公共前缀的最大值。

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

hint:
对于 $10\%$ 的数据，$1\le n,m\le 300$。

对于 $40\%$ 的数据，$1\le n,m\le 3,000$，字符串中仅有 `a`,`b`。

对于 $100\%$ 的数据，$1\le n,m\le 100,000$，字符串中仅有小写英文字母，$a\le b$，$c\le d$，$1\le a,b,c,d\le n$。


title: [HEOI2012] 采花

description:
萧薰儿是古国的公主，平时的一大爱好是采花。

今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。

花园足够大，容纳了 $n$ 朵花，共有 $c$ 种颜色，用整数 $1 \sim c$ 表示。且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴。同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。

由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了 $m$ 个行程，然后一一向你询问公主能采到的花共有几种不同的颜色。

inputFormat:
输入的第一行是三个用空格隔开的整数，分别代表花的个数 $n$，花的颜色数 $c$，以及行程数 $m$。

输入的第二行是 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 朵花的颜色 $x_i$。

第 $3$ 行到第 $(m + 2)$ 行，每行两个整数 $l, r$，第 $(i + 2)$ 行的数字代表第 $i$ 次行程为第 $l$ 到第 $r$ 朵花。

outputFormat: 共输出 $m$ 行，每行一个整数。第 $i$ 行的整数代表第 $i$ 次行程公主能采到的花共有几种不同的颜色。

hint:
#### 输入输出样例 $1$ 解释

共有五朵花，颜色分别为 $1,~2,~2,~3,~1$。

对于第一次行程，公主采花的区间为 $[1, 5]$，可以采位置 $1,~2,~3,~5$ 处的花，共有 $1$ 和 $2$ 两种不同的颜色。

对于第二次行程，公主采花的区间为 $[1, 2]$，但是颜色为 $1$ 和 $2$ 的花都只出现了一次，因此公主无花可采。

对于第三次行程，公主采花的区间为 $[2, 2]$，但是颜色为 $2$ 的花只出现了一次，公主无花可采。

对于第四次行程，公主采花的区间为 $[2, 3]$，可以采 $2,~3$ 位置的花，只有 $2$ 这一种颜色。

对于第五次行程，公主采花的区间为 $[3,5]$，但是颜色为 $1, 2, 3$ 的花都只出现了一次，因此公主无花可采。

#### 数据范围与约定

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

对于子任务 $1$，分值为 $100$ 分，保证 $1 \leq n, c, m \leq 3 \times 10^5$。

对于子任务 $2$，分值为 $100$ 分，保证 $1 \leq n, c, m \leq 2 \times 10^6$。

对于全部的测试点，保证 $1 \leq x_i \leq c$，$1 \leq l \leq r \leq n$。


title: [HEOI2013] Eden 的新背包问题

background: “ 寄 没 有 地 址 的 信 ，这 样 的 情 绪 有 种 距 离 ，你 放 着 谁 的 歌 曲 ，是 怎 样 的 心 情 。 能 不 能 说 给 我 听 。”

description:
失忆的 Eden 总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。

记忆中，她总是喜欢给 Eden 出谜题：在 valentine's day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden 这样的一个问题：有 $n$ 个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱 $m$ 固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过 $m$，且价值和最大。

众所周知的，这是一个很经典的多重背包问题，Eden 很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。

这下 Eden 犯难了，不过 Eden 不希望自己被难住，你能帮帮他么？

inputFormat:
第一行有一个整数，代表玩偶的个数 $n$，玩偶从 $0$ 开始编号。

第二行开始后面的 $n$ 行，每行三个整数，第 $(i + 2)$ 行的整数  $a_i, b_i, c_i$，分别表示买一个第 $i$ 个玩偶需要的价钱，获得的价值以及第 $i$ 个玩偶的限购次数。

接下来的一行有一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个整数 $d_i, e_i$，表示每个询问去掉的是哪个玩偶（注意玩偶从 $0$ 开始编号）以及该询问对应的新的总价钱数。（去掉操作不保留，即不同询问互相独立）。

outputFormat: 输出 $q$ 行，第 $i$ 行输出对于第 $i$ 个询问的答案。

hint:
#### 样例解释

一共五种玩偶，分别的价钱价值和限购次数为 $(2,3,4)$， $(1,2,1)$， $(4,1,2)$， $(2,1,1)$， $(3,2,3)$。

五个询问，以第一个询问为例。

第一个询问表示的是去掉编号为 $1$ 的玩偶， 且拥有的钱数为 $10$ 时可以获得的最大价值，则此时剩余玩偶为 $(2,3,4$)，$(4,1,2)$， $(2,1,1)$，$(3,2,3)$，若把编号为 $0$ 的玩偶买 $4$ 个（即全买了），然后编号为 $3$ 的玩偶 买一个，则刚好把 $10$ 元全部花完，且总价值为 $13$。可以证明没有更优的方案了。

注意买某种玩偶不一定要买光。

---

#### 数据规模与约定

- 对于 $10\%$ 的数据，保证 $n \leq 10$。
- 另外存在 $20\%$ 的数据，保证  $n \leq 100$，$c_i = 1$，$q \leq 100$。
- 另外存在 $20\%$ 的数据，保证 $n \leq 100$，$q \leq 100$。
- 另外存在 $30\%$ 的数据，保证 $c_i = 1$。
- 对于 $100\%$ 的数据，保证  $1 \leq n \leq 1000$，$1 \leq q \leq 3\times 10^5$， $1 \leq a_i,b_i,c_i \leq 100$，$0 \leq d_i < n$，$0 \leq e_i \leq 1000$。


title: [HEOI2013] Eden 的博弈树

description:
对于有两个玩家的，状态透明且状态转移确定的博弈游戏，博弈树是常用的分析工具。博弈树是一棵有根树，其中的节点为游戏的状态。若节点 B 的父亲是 A，则说明状态 A 能通过一次决策转移到状态 B。每个状态都有一个唯一的决策方，即这个状态下应该由哪一方做出决策。我们规定双方在任何时候都是轮流做出决策的，即树上相邻节点的决策方总是不相同的。

在这个问题中，我们只关心两个玩家的胜负情况，且规定游戏不会出现平局。

我们称两个玩家分别为黑方和白方，其中根节点的决策方为黑方。显然每个节点只有两个状态：黑方胜和白方胜。若某内节点（即存在后继节点的节点）的决策方为黑方，则该节点为黑方胜的充要条件为它的儿子中存在黑方胜的节点，反之亦然。求解博弈树即为判明博弈树根节点的状态。

如果我们得知了所有叶节点（即无后继节点的节点）的状态，那么博弈树就很容易求解了。但是现在的情况是所有叶节点的状态均为未知的，需要进一步的计算。对于一个由叶节点构成的集合 $S$，如果 $S$ 中的节点均被判明为黑方胜，就可以断言根节点为黑方胜的话，则称 $S$ 为一个黑方胜集合。对于黑方胜集合 $S$， 如果对于任意的黑方胜集合 $S'$ 均满足 $|S| \le |S'|$（$|S|$ 表示集合 $S$ 中的元素数目）， 则称 $S$ 为一个最小黑方胜集合。同样地，也可以定义白方胜集合和最小白方胜集合。

Eden 最近在研究博弈树问题。他发现，如果一个叶节点既属于某一个最小黑方胜集合，又属于一个最小白方胜集合，那么求解这个节点的状态显然最有益于求解根节点的状态。像这样的叶节点就称之为关键叶节点。对于一棵给定的博弈树，Eden 想要知道哪些叶节点是关键叶节点。

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

测试数据的第一行包含一个正整数 $n$，表示博弈树的节点数目。节点从 $1$ 到 $n$ 编号，且 $1$ 号节点为根节点。

之后 $n - 1$ 行，每行包含一个正整数。第 $i$ 行的正整数表示节点 $i$ 的父节点的编号。

outputFormat: 在一行内输出三个空格分隔的正整数，分别是编号最小的关键叶节点的编号，关键叶节点的数目和所有关键叶节点的编号的异或和。

hint:
【样例说明】

  ![](https://cdn.luogu.com.cn/upload/pic/13130.png)

如图所示，黑色节点表示决策方为黑方的节点，反之亦然

所有的最小黑方胜集合为 $\{4, 5\}$ 和 $\{6, 7\}$。

所有的最小白方胜集合为 $\{4, 6\}$，$\{4, 7\}$，$\{5, 6\}$ 和 $\{5, 7\}$。

所以关键叶节点的集合为 $\{4, 5, 6, 7\}$。

- 对于 $30\%$ 的数据，$n \le 100$；
- 对于 $40\%$ 的数据，$n \le 1000$；
- 对于 $50\%$ 的数据，$n \le 10 ^ 4$，且树是随机生成的；
- 对于 $100\%$ 的数据，$1 \le n \le 2\times 10 ^ 5$，且对于节点 $i$（$i \ne 1$），其父节点的编号小于 $i$。


title: 【模板】李超线段树 / [HEOI2013] Segment

description:
要求在平面直角坐标系下维护两个操作：

1. 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$。
2. 给定一个数 $k$，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号。

inputFormat:
**本题输入强制在线**。

输入的第一行是一个整数 $n$，代表操作的个数。

接下来 $n$ 行，每行若干个用空格隔开的整数，第 $i + 1$ 行的第一个整数为 $op$，代表第 $i$ 次操作的类型。

若 $op = 0$，则后跟一个整数 $k$，代表本次操作为查询所所有与直线 $x = (k + lastans - 1) \bmod 39989 + 1$ 相交的线段中，交点纵坐标最大的线段编号。

若 $op = 1$，则后跟四个整数 $x_0, y_0, x_1, y_1$，记 $x_i' = (x_i + lastans - 1) \bmod 39989 + 1$，$y_i' = (y_i + lastans - 1) \bmod 10^9 + 1$。本次操作为插入一条两端点分别为 $(x_0', y_0')$，$(x_1',y_1')$ 的线段。

其中 $lastans$ 为上次询问的答案，初始时，$lastans = 0$。

outputFormat: 对于每次查询，输出一行一个整数，代表交点纵坐标最大的线段的编号。若不存在任何一条线段与查询直线有交，则输出 $0$；若有多条线段与查询直线的交点纵坐标都是最大的，则输出编号最小的线段，同时 $lastans$ 也应更新为编号最小的一条线段。

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

对于第一次操作，解密后为 `1 8 5 10 8`。

对于第二次操作，解密后为 `1 6 7 2 6`。

对于第三次操作，解密后为 `0 2`，此时 $lastans$ 被更新为 $2$。

对于第四次操作，解密后为 `0 11`，此时 $lastans$ 被更新为 $0$。

对于第五次操作，解密后为 `1 4 7 6 7`。

对于第六次操作，解密后为 `0 5`。

### 数据范围与约定

对于 $30\%$ 的数据，保证 $n \leq 10^3$。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq k, x_0, x_1 \leq 39989$，$1 \leq y_0, y_1 \leq 10^9$。

### 提示

不保证 $x_0 \neq x_1$。对于一条 $x_0' = x_1'$ 的线段，认为其与 $x = x_0'$ 的交点为其两端点中纵坐标较大的端点。


title: [HEOI2013] ALO

description:
Welcome to ALO (Arithmetic and Logistic Online）。这是一个 VR MMORPG，如名字所见，到处充满了数学的谜题。

现在你拥有 $n$ 颗宝石，第 $i$ 颗宝石有一个能量密度，记为 $a_i$，这些宝石的能量密度**两两不同**。现在你可以选取**连续**的一些宝石（必须多于一个）进行融合，设他们的能量密度为 $a_i,a_{i+1},\cdots,a_j$，则融合而成的宝石的能量密度为这些宝石中能量密度的次大值与其他任意一颗宝石的能量密度按位异或的值的最大值。即，假设该段宝石能量密度次大值为 $k$，则生成的宝石的能量密度为 $\max\{k\oplus a_p\mid a_p\ne k, i\le p\le j\}$。

现在你需要知道你怎么选取需要融合的宝石，才能使生成的宝石能量密度最大。

inputFormat:
第一行，一个整数 $n$，表示宝石个数。

第二行，$n$ 个整数，分别表示 $a_1$ 至 $a_n$，表示每颗宝石的能量密度，保证对于 $i\ne j$ 有 $a_i\ne a_j$。

outputFormat: 输出一行一个整数，表示最大能生成的宝石能量密度。


title: [HEOI2013] SAO

description:
Welcome to SAO ( Strange and Abnormal Online)。这是一个 VR MMORPG， 含有 n 个关卡。但是，挑战不同关卡的顺序是一个很大的问题。

某款游戏有 $n-1$ 个对于挑战关卡的限制，诸如第 $i$ 个关卡必须在第 $j$ 个关卡前挑战，或者完成了第 $k$ 个关卡才能挑战第 $l$ 个关卡。并且，如果不考虑限制的方向性，那么在这 $n-1$ 个限制的情况下，任何两个关卡都存在某种程度的关联性。即，我们不能把所有关卡分成两个非空且不相交的子集，使得这两个子集之间没有任何限制。

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

对于每组数据，第一行一个整数 n，表示关卡数。接下来 n – 1 行，每行为 “i sign j”，其中 0 ≤ i, j ≤ n – 1 且 i ≠ j，sign 为“<”或者“>”，表示第 i 个关卡 必须在第 j 个关卡前/后完成。

outputFormat: 对于每个数据，输出一行一个整数，为攻克关卡的顺序方案个数，mod 1,000,000,007 输出。

hint:
对于 $20\%$ 的数据有 $n \le 10$。

对于 $40\%$ 的数据有 $n \le 100$。

对于另外 $20\%$ 的数据有，保证数据中 sign 只会是 <，并且 $i<j$。

对于 $100\%$ 的数据有 $T \le 5$，$1 \le n \le 1000$。


title: [HEOI2013] 钙铁锌硒维生素

description:
银河队选手名单出来了！小林，作为特聘的营养师，将负责银河队选手参加宇宙比赛的饮食。

众所周知，前往宇宙的某个星球，通常要花费好长好长的时间，人体情况在这之间会发生变化，因此，需要根据每天的情况搭配伙食，来保证营养。

小林把人体需要的营养分成了 $n$ 种，这些营养包括但不限于铁，钙。他准备 了 $2$ 套厨师机器人，一套厨师机器人有 $n$ 个，每个厨师机器人只会做一道菜，这道菜一斤能提供第 $i$ 种营养 $x_i$ 微克。想要吃这道菜的时候，只要输入一个数，就 能吃到对应数量的这道菜了。为防止摄入过量对身体造成的伤害，每个机器人还有防过量摄入药，只要输入一个数，就能生成一定剂量的药，吃了这些药，就能 减少相当于食用对应数目的这道菜提供的营养。

小林之所以准备 $2$ 套厨师机器人，正是因为旅途漫漫，难以预计，也许某一 个厨师机器人在途中坏掉，要是影响了银河队选手的身体，就不好了。因此，第 $2$ 套厨师机器人被用来做第 $1$ 套的备用。小林需要为每一个第 $1$ 套厨师机器人选 一个第 $2$ 套厨师机器人作备份，使得当这个机器人坏掉时，用备份顶替，整套厨师机器人仍然能搭配出任何营养需求，而且，每个第 $2$ 套厨师机器人只能当一个第 $1$ 套厨师机器人的备份。

inputFormat: 输入文件的第一行包含一个正整数 $n$。接下来 $n$ 行，每行 $n$ 个整数，表示第 $1$ 套厨师机器人做的菜每一斤提供的每种营养。再接下来 $n$ 行，每行 $n$ 个整数， 表示第 $2$ 套厨师机器人做的菜每一斤提供的每种营养。

outputFormat:
输出文件的第一行是一个字符串，如果无法完成任务，输出 `NIE`，否则输出 `TAK`，并跟着 $n$ 行，第 $i$ 行表示第 $i$ 个第 $1$ 套机器人的备份是哪一个第 $2$ 套机器人。

为了避免麻烦，如果有多种可能的答案，请给出字典序最小的那一组。


title: [HEOI2014] 人人尽说江南好

description:
小 Z 是一个不折不扣的 ZRP（Zealot Round-game Player，回合制游戏狂热玩家），最近他想起了小时候在江南玩过的一个游戏。

在过去，人们是要边玩游戏边填词的，比如这首《菩萨蛮》就是当年韦庄在玩游戏时填的：人 人 尽 说 江 南 好， 游 人 只 合 江 南 老。

然而我们今天不太关心人们填的词是什么，我们只关心小 Z 那时玩过的游戏。游戏的规则是这样的，给定 $n$ 堆石子，每堆石子一开始只有 $1$ 个。小 Z 和他的小伙伴轮流操作，小 Z 先行操作。操作可以将任意两堆石子合并成为一堆，当谁不再能操作的时候，谁就输掉了。

不过，当一堆石子堆的太高时可能发生危险，因此小 Z 和他的小伙伴规定，任何时刻任意一堆石子的数量不能超过 $m$。即假如现在有两堆石子分别有 $a$ 个和 $b$ 个，而且 $a + b > m$，那么这两堆石子就不能合成一堆。

小 Z 和他的小伙伴都是很聪明的，所以他们总是会选择对自己最有利的策略。现在小 Z 想要知道，在这种情况下，对于一个给定的 $n$ 和 $m$，到底是谁能够获得胜利呢？

inputFormat:
本题包括多组数据  数据第一行为一个数 $T$，为数据组数。

以下 $T$ 行，每行两个正整数 $n,m$。

outputFormat: 输出 $T$ 行，每行为 $0$ 或 $1$，如果为 $0$ 意为小 Z（即先手）会取得胜利，为 $1$ 则为后手会取得胜利。


title: [HEOI2014] 林中路径

description:
Alice 和 Marisa 都住在一个巨大的由 $N$ 个路口与 $M$ 条单向小道构成的森林中。Marisa 非常喜欢到 Alice 家里去玩，但是 Alice 并不喜欢这位鲁莽的来客。Alice 非常擅长观察， 因此每当她发现 Marisa 走了一条与之前完全相同的路径来到她家时，她就会装作不在家， Marisa 就只好败兴而归。Marisa 发现了这个秘密，因此她决定每次走不同的路径到 Alice 家。

Marisa 体力有限，她不想走超过 K 条边到达 Alice 家，并且，每当她走 $t$（ $t$ $\leq$ $K$ ）条边 到达 Alice 家时，她需要付出 $t^2$ 的体力。Marisa 想知道，在 Alice 无论如何都不想接见她之前（即 Marisa 无法走一条长度不超过 $K$ 的与之前不同的路径），她会消耗多少体力。

现在 Marisa 拿到了一张森林的地图，但因为 Marisa 非常笨，她并不知道自己的家和 Alice 的家在哪一个路口，因此她会给询问你 $Q$ 次，每次询问假如 Marisa 的家的位置在 $S$ 而 Alice 的家的位置在 $T$ 时的答案。

一条路径 $A$ 的定义是指一个长度为 $P$（$P$ 可以为任意正整数或零）的边的序列 $A_{m_0},A_{m_1},A_{m_2},…,A_{m_{T-1}}$，其中对于任意 $1 \leq i ＜ P$，有 $A_{m_{i-1}}$ 的结束节点是 $Am_i$ 的起始节点。

两条路径 $A$ 和 $B$ 完全相同是指两条路径的长度均为 T 并且对任意 $0\leq i＜P$，有 $A_{m_i} = B_{m_i}$。

inputFormat:
输入数据第一行包含四个整数 $N$ , $M$ , $K$ , $Q$ ，含义如题所述。

接下来 $M$ 行，每行两个整数 $X$ , $Y$ ，表示从第 $X$ 个路口到第 $Y$ 个路口有一条单向小道。路口的标号为 $1,2,3,…,N$ ，在输入数据第 $i+1$ 行的边的标号为 $i$。  接下来 $Q$ 行，每行两个整数 $S$ 和 $T$，含义如题所述。

outputFormat: 对于每个询问，输出一行，表示这次询问的答案。由于 Marisa 接受不了非常大的数， 你只需要输出答案模 $10^9+7$ 的值。

hint:
对于 $20\%$ 的数据，$N\leq  5$，$M\leq 10$，$K\leq 3$，$Q\leq 10$。

对于 $40\%$ 的数据，$N\leq  30$，$M\leq 900$，$K\leq 100$，$Q\leq 100$。

对于 $60\%$ 的数据，$N\leq  50$，$M\leq 2,500$，$K\leq 10,000,000$，$Q\leq 1,000$。

对于 $100\%$ 的数据，$2\leq  N\leq 100$，$0\leq M\leq 100,000$，$0\leq K\leq 1,000,000,000$，$0\leq Q\leq 10,000$，$1\leq X,Y,S,T\leq N$。

```cpp
g++ paths.cpp –o paths –Wl,--stack=268435456 –O2
```
样例一解释 从 $S$ 到 $T$ 不存在路径

样例二解释 Marisa 可以重复经过一个路口，即使这个路口就是 Alice 的家或 Marisa 的家


title: [HEOI2014] 大工程

description:
国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。

我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。

在 $2$ 个国家 $a,b$ 之间建一条新通道需要的代价为树上 $a,b$ 的最短路径的长度。

现在国家有很多个计划，每个计划都是这样，我们选中了 $k$ 个点，然后在它们两两之间 新建 $\dbinom{k}{2}$ 条新通道。

现在对于每个计划，我们想知道：
1. 这些新通道的代价和。
2. 这些新通道中代价最小的是多少。
3. 这些新通道中代价最大的是多少。

inputFormat:
第一行 $n$ 表示点数。

接下来 $n-1$ 行，每行两个数 $a,b$ 表示 $a$ 和 $b$ 之间有一条边。点从 $1$ 开始标号。

接下来一行 $q$ 表示计划数。对每个计划有 $2$ 行，第一行 $k$ 表示这个计划选中了几个点。

第二行用空格隔开的 $k$ 个互不相同的数表示选了哪 $k$ 个点。

outputFormat: 输出 $q$ 行，每行三个数分别表示代价和，最小代价，最大代价。


title: [HEOI2014] 平衡

description:
下课了，露露、花花和萱萱在课桌上用正三棱柱教具和尺子摆起了一个“跷跷板”。

这个“跷跷板”的结构是这样的：底部是一个侧面平行于地平面的正三棱柱教具，上面 摆着一个尺子，尺子上摆着若干个相同的橡皮。尺子有 2n + 1 条等距的刻度线，第 n + 1 条 刻度线恰好在尺子的中心，且与正三棱柱的不在课桌上的棱完全重合。

露露发现这个“跷跷板”是不平衡的（尺子不平行于地平面）。于是，她又在尺子上放 了几个橡皮，并移动了一些橡皮的位置，使得尺子的 2n + 1 条刻度线上都恰有一块相同质 量的橡皮。“跷跷板”平衡了，露露感到很高兴。

花花觉得这样太没有意思，于是从尺子上随意拿走了 k 个橡皮。令她惊讶的事情发生了： 尺子依然保持着平衡！     萱萱是一个善于思考的孩子，她当然不对尺子依然保持平衡感到吃惊，因为这只是一个 偶然的事件罢了。令她感兴趣的是，花花有多少种拿走 k 个橡皮的方法，使得尺子依然保 持平衡？当然，为了简化问题，她不得不做一些牺牲——假设所有橡皮都是拥有相同质量的 质点。但即使是这样，她也没能计算出这个数目。放学后，她把这个问题交给了她的哥哥/ 姐姐——Hibarigasaki 学园学生会会长，也就是你。当然，由于这个问题的答案也许会过于 庞大，你只需要告诉她答案 mod p 的值。

inputFormat:
第一行，一个正整数，表示数据组数 T（萱萱向你询问的次数）。

接下来 T 行，每行 3 个正整数 n, k, p。

outputFormat: 共 T 行，每行一个正整数，代表你得出的对应问题的答案。


title: [HEOI2014] 南园满地堆轻絮

description:
小 Z 是 ZRP（Zombies’ Republic of Poetry，僵尸诗歌共和国）的一名诗歌爱好者，最近 他研究起了诗词音律的问题。

在过去，诗词是需要编成曲子唱出来的，比如下面这首《菩萨蛮》，唱出来的话其对应的音符就是这样的：

```cpp
 南  园  满 地 堆 轻 絮， 愁 闻 一 霎 清 明 雨
 1   1  5 5 6 6 5  4 4 3 3 2 2 1
```
因而可以发现，`1 1 5 5 6 6 5 4 4 3 3 2 2 1`这串音符就成为了研究音律的关键。

小 Z 翻阅了众多史料发现，过去的一首曲子的音调是不下降的。 小 Z 想要知道对于一首给定的曲子，如何通过提高音调或者降低音调，将它的音调修改的不下降，而且使得修改幅度最大的那个音符的修改幅度尽量小。即如果把一个包含 $n$ 个音 符的曲子看做是一个正整数数列 $A[1] \cdots A[n]$，那么目标是求另一个正整数数列 $B[1]…B[n]$， 使得对于任意的 $1≤i<n$ 有 $B[i] ≤B[i+1]$，而且使得 $Ans = Max\{|A[j]-B[j]|,1≤j≤n\}$尽量 小。
小 Z 很快就想清楚了做法，但是鉴于他还忙着写诗，所以这个任务就交给了你。

inputFormat:
由于数据规模可能较大，因此采用如下方式生成数据。

每个数据包含 7 个数：$n,S_a,S_b,S_c,S_d,A[1],Mod$，即共有 n 个音符，第一个音符为 A[1]。

生成规则如下： 定义生成函数 $F(x) = S_a*x^3 + S_b*x^2 + S_c*x + S_d$; 那么给出递推公式 $A[i] =( F(A[i-1]) + F(A[i-2]) )\%mod$，此处规定 $A[0] = 0$. 由于中间过程的数可能会特别大，所以要求每一步与 $A$ 中的每个数都对一个给定的数 $Mod$ 取模。

outputFormat: 输出一行，包含一个正整数 $Ans$。


title: [HEOI2014] 逻辑翻译

description:
在人类的神经系统中，每个信号都可以用−1或+1来表示。这些信号组合起来最后形成 了喜怒哀乐，酸甜苦辣，红黄绿蓝等各种各样的复杂信息。纳米探测科技的突破让生物学家 可以测量大脑中特定区域的完整逻辑功能。然而超大数据的处理一直是令 H 教授头疼的问 题。

假设一个逻辑单元接受N个信号输入，并产生一个代表某种意义的实数值r。那么总共可能的 情况有2N种。通过 长时间的累积测量， H 教授可以准确地获得输入信号与r的关系表：

$$f :{-1,1}N \to \mathbb{R} $$

然而进一步研究发现，神经元的运算方式可以被建模为人们熟知的多项式。由于一个输 入信号值的平方一定为1，所以我们可以用不含幂的2N项的多项式来唯一表示任何一个逻辑 f。

例如
$x_1=+1; x_2=+1 \to 0$

$x_1=+1; x_2=-1 \to 1$

$x_1=-1; x_2=+1 \to 2$

$x_1=-1; x_2=-1 \to 3$

可以 写成

$$f(x_1,x_2)=1.5-0.5x_2-x_1$$

研究一个逻辑单元的多项式形式对了解大脑工作十分有意义，于是小 M 决定帮 H 教授 把测量出的逻辑关系表全部转换成多项式的形式。这么简单的工作一定难不倒编程能手小M 的吧？

inputFormat: 第一行是N (1≤N≤20)，接下来共2N行，每一行是一组逻辑输入和一个对应值，代表 x\_1...x\_N的符号以及对应的r。详见样例。数据保证所有逻辑值的绝对值不超过100，且不包含超过 2 位小数。保证所有逻辑的输入串都互不相同。

outputFormat:
最多$2^N$行，代表多项式每一项的系数，如果答案为整数，输出整数形式。否则输出最 简分数形式。如果系数恰好为 0，则省略整行。变量和系数用空格隔开，常数项不用加空格。

顺序按多项式的字典序：

1. 常数项优先；

2. 没有常数项时，最小x下标更小的项优先；

3. 当两项含有相同最小下标时，按除掉最小下标x以后，以同样规则递归比较。

例：1,x1,x1x2,x1x2x3,x1x3,x2,x2x3,x3 详见 样例。

hint:
本题共有 10 个测试数据。

对于第 1 个数据， N≤3;

对于第 2 个数据， N≤8;

对于第 3，4 个数据，N≤11;

对于第 5，6 个数据， 答案多项式中只有一个非零项，如样例#2。

对于第 7，8 个数据， 答案多项式中最多有 5 个非零项。

对于 100%的数据， $1 \le N \le 20,|r| \le 100, 100r\in \mathbb{Z} $
友情提示

请注意输入输出的效率。


title: [HEOI2015] 兔子与樱花

description:
很久很久之前，森林里住着一群兔子。有一天，兔子们突然决定要去看樱花。

兔子们所在森林里的樱花树很特殊。樱花树由 $n$ 个树枝分叉点组成，编号从 $0$ 到 $n-1$，这 $n$ 个分叉点由 $n-1$ 个树枝连接，我们可以把它看成一个有根树结构，其中 $0$ 号节点是根节点。

这个树的每个节点上都会有一些樱花，其中第 $i$ 个节点有 $c_i$ 朵樱花。樱花树的每一个节点都有最大的载重 $m$，对于每一个节点 $i$，它的儿子节点的个数和 $i$ 节点上樱花个数之和不能超过 $m$，即 $son(i) + c_i \leq m$，其中 $son(i)$ 表示 $i$ 的儿子的个数，如果 $i$ 为叶子节点，则 $son(i) = 0$。

现在兔子们觉得樱花树上节点太多，希望去掉一些节点。当一个节点被去掉之后，这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除，那么就会继续向上连接，直到第一个没有被删除的节点为止。

现在兔子们希望计算在不违背最大载重的情况下，最多能删除多少节点。

注意根节点不能被删除，被删除的节点不被计入载重。

inputFormat:
第一行输入两个正整数，$n$ 和 $m$ 分别表示节点个数和最大载重。

第二行 $n$ 个整数 $c_i$，表示第 $i$ 个节点上的樱花个数。

接下来 $n$ 行，每行第一个数 $k_i$ 表示这个节点的儿子个数，接下来 $k_i$ 个整数表示这个节点儿子的编号。

outputFormat: 一行一个整数，表示最多能删除多少节点。

hint:
- 对于 $30\%$ 的数据，$n \leq 5 \times 10^3$，$m \leq 100$，$c_i \leq 100$；
- 对于 $70\%$ 的数据，$n \leq 2 \times 10^5$，$m \leq 2 \times 10^3$，$c_i \leq 10^3$；
- 对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^6$，$1 \leq m \leq 10^5$，$0 \leq c_i \leq 10^3$，保证初始时，每个节点樱花数与儿子节点个数之和大于 $0$ 且不超过 $m$。


title: [HEOI2015] 公约数数列

description:
设计一个数据结构. 给定一个正整数数列 $a_0, a_1, \cdots, a_{n - 1}$，你需要支持以下两种操作：

1. $\text{\texttt{MODIFY} \textit{id} \textit{x}}$：将 $a_{id}$ 修改为 $x$；
2. $\text{\texttt{QUERY} \textit{x}}$：求最小的整数 $p \ (0 \le p < n)$，使得 $\gcd(a_0, a_1, \cdots, a_p) \times  \operatorname{xor}(a_0, a_1, \cdots, a_p) = x$。其中 $\operatorname{xor}(a_0, a_1, \cdots, a_p)$ 代表 $a_0, a_1, \cdots, a_p$ 的异或和，$\gcd$ 表示最大公约数。

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

接下来一行包含 $n$ 个正整数 $a_0,a_1,\cdots,a_{n-1}$。

之后一行包含一个正整数 $q$，表示询问的个数。

之后 $q$ 行，每行包含一个询问。格式如题目中所述。

outputFormat: 对于每个 $\texttt{QUERY}$ 询问，在单独的一行中输出结果。如果不存在这样的 $p$，输出 `no`。


title: [HEOI2015] 定价

description:
在市场上有很多商品的定价类似于 999 元、4999 元、8999 元这样。它们和 1000 元、5000 元和 9000 元并没有什么本质区别，但是在心理学上会让人感觉便宜很多，因此也是商家常用的价格策略。不过在你看来，这种价格十分荒谬。于是你如此计算一个价格 $p$（$p$ 为正整数）的荒谬程度：

1. 首先将 $p$ 看做一个由数字组成的字符串（不带前导 $0$）；
2. 然后，如果 $p$ 的最后一个字符是 $0$，就去掉它。重复这一过程，直到 $p$ 的最后一个字符不是 $0$；
3. 记 $p$ 的长度为 $a$，如果此时 $p$ 的最后一位是 $5$，则荒谬程度为 $2a - 1$；否则为 $2a$。

例如，$850$ 的荒谬程度为 $3$，而 $880$ 则为 $4$，$9999$ 的荒谬程度为 $8$。

现在，你要出售一样闲置物品，你能接受的定价在 $[L, R]$ 范围内，你想要给出一个荒谬度最低的价格。

inputFormat:
输入文件的第一行包含一个正整数 $T$，表示测试数据的数目。

每个测试数据占单独的一行，包含两个空格分隔的正整数 $L, R$，表示定价的区间。

outputFormat: 对于每个测试数据，在单独的一行内输出结果。如果荒谬度最低的价格不唯一，输出最小的那个。


title: [HEOI2015] 小L的白日梦

description:
在某一天，你有了一个女性朋友。

你打算利用k天时间陪她，每天有很多种娱乐方式可供选择，你需要从中选择一种进行（一天只能进行一个项目），比如说一起去看电影、一起去主题公园，一起去逛街等等，一共n种项目。当然每个项目重复太多次你都会觉得无聊，因此第i个项目最多进行c[i]次。你虽然智商很高，但是情商堪忧，即使这些你准备的活动都是希望让她开心的，不过由于你笨拙的语言表达和过于理智的行动，可能使这些活动出现意外。经过你悉心的计算，你发现如果某一天进行了第i个项目，如果一切顺利的话她应该是很高兴的，但她会有a[i]的概率不高兴。如果她本来是很高兴的，但突然今天你让她不高兴了，她就会觉得很失落，并且对你的好感度大大下降。你希望尽可能避免这种情况发生，因此你要安排这k天之内每天进行的项目，最小化她感到失落的期望次数。

你的女性朋友十分在意你，所以她的心情只会因为你发生改变。第一天之前，因为你没有邀请她进行任何活动，所以她是不高兴的。

inputFormat:
第一行有一个非负整数t，表示一共有t组数据。

对于每组数据，第一行有两个非负整数n,k，分别表示你准备的项目个数和你用来陪她的天数。（n<=10^5, k<=10^9）

接下来n行，每一行描述一个项目，形如“x[i]/y[i] c[i]”且三个数均为非负整数，表示进行完这个项目之后她有x[i]/y[i]的概率不高兴，并且这个项目只能进行不超过c[i]次。（x[i],y[i] <= 10^4,c[i] <= 10^9）

outputFormat: 一共t行，对于每组数据输出使她感到失落的最小期望次数，四舍五入保留6位小数。

hint:
【样例说明】

考虑第三组数据，因为只有一个项目所以只好每天都安排这个。

在第一天之前她总是不高兴的，一共有：

第一天不高兴，第二天也不高兴、

第一天高兴，第二天不高兴、

第一天不高兴，第二天高兴、

第一天不高兴，第二天也不高兴，

这四种情况，又因为每天的项目让她高兴或者是不高兴的概率都是0.5，因此这四种情况是等概率发生的。

只有在第二种情况下，她会感到失落一次。

因此答案是(1\*1+0\*3)/4=0.25.

【数据规模与约定】

对于前10%的数据，n,k<=5.

对于前30%的数据，n,k<=7.

对于前40%的数据，n,k<=10.

对于前60%的数据，n<=1000,k<=10^5.

对于100%的数据，n<=10^5，k<=10^9，数据组数不会太多，大概不超过10组，数据保证分数有意义并且∑c[i]>=k。


title: [HEOI2015] 小 Z 的房间

description:
你突然有了一个大房子，房子里面有一些房间。事实上，你的房子可以看做是一个包含 $n\times m$ 个格子的格状矩形，每个格子是一个房间或者是一个柱子。在一开始的时候，相邻的格子之间都有墙隔着。

你想要打通一些相邻房间的墙，使得所有房间能够互相到达。在此过程中，你不能把房子给打穿，或者打通柱子（以及柱子旁边的墙）。同时，你不希望在房子中有小偷的时候会很难抓，所以你希望任意两个房间之间都只有一条通路。现在，你希望统计一共有多少种可行的方案，答案对 $10^9$ 取模。

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

接下来 $n$ 行，每行 $m$ 个字符 `.` 或 `*`，其中 `.` 代表房间，`*` 代表柱子。

outputFormat: 一行一个整数，表示合法的方案数对 $10^9$ 取模后的值。

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

- 对于 $20\%$ 的数据，$n,m \le 3$。
- 对于 $50\%$ 的数据，$n,m \le 5$。
- 有 $40\%$ 的数据，$\min(n,m) \le 3$。
- 有 $30\%$ 的数据，不存在柱子。
- 对于 $100\%$ 的数据，$1 \le n,m \le 9$。


title: [HEOI2015] 最短不公共子串

description:
在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。

下面给出一些定义：

- 一个串的“子串”指的是它的连续的一段，例如 `bcd` 是 `abcdef` 的子串，但 `bde` 不是。
- 一个串的“子序列”指的是它的可以不连续的一段，例如 `bde` 是 `abcdef` 的子串，但 `bdd` 不是。

下面，给两个小写字母串 $a, b$，请你计算：

1. $a$ 的一个最短的子串，它不是 $b$ 的子串。
2. $a$ 的一个最短的子串，它不是 $b$ 的子序列。
3. $a$ 的一个最短的子序列，它不是 $b$ 的子串。
4. $a$ 的一个最短的子序列，它不是 $b$ 的子序列。

inputFormat: 有两行，每行一个小写字母组成的字符串，分别代表 $a$ 和 $b$。

outputFormat: 输出 $4$ 行，每行一个整数，依次表示以上 $4$ 个问题的答案的长度。如果没有符合要求的答案，输出 $-1$。

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

- 对于 $20\%$ 的数据，保证 $a$ 和 $b$ 的长度都不超过 $20$。
- 对于 $50\%$ 的数据，保证 $a$ 和 $b$ 的长度都不超过 $500$。
- 对于 $100\%$ 的数据，保证 $a$ 和 $b$ 的长度都不超过 $2000$。


title: Qtree4

background:
#欢迎提供更强的数据，本题目支持无限加数据（可私信，百度网盘地址）

#数据范围和spoj略有不同

description:
给出一棵边带权的节点数量为n的树，初始树上所有节点都是白色。有两种操作：

C x，改变节点x的颜色，即白变黑，黑变白

A，询问树中最远的两个白色节点的距离，这两个白色节点可以重合(此时距离为0)。

inputFormat:
In the first line there is an integer N (N <= 100000)

In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of value c (-1000 <= c <= 1000)

In the next line, there is an integer Q denotes the number of instructions (Q <= 200000)

In the next Q lines, each line contains an instruction "C a" or "A"

outputFormat: For each "A" operation, write one integer representing its result. If there is no white node in the tree, you should write "They have disappeared.".


title: Qtree3

description:
给出 $N$ 个点的一棵树（$N-1$ 条边），节点有白有黑，初始全为白。

有两种操作：

`0 i`：改变某点的颜色（原来是黑的变白，原来是白的变黑）。

`1 v`：询问 $1$ 到 $v$ 的路径上的第一个黑点，若无，输出 $-1$。

inputFormat:
第一行 $N$，$Q$，表示 $N$ 个点和 $Q$ 个操作。

第二行到第 $N$ 行 $N-1$ 条无向边。

再之后 $Q$ 行，每行一个操作 `0 i` 或者 `1 v`。

outputFormat: 对每个 `1 v` 操作输出结果


title: [Ynoi2018] 五彩斑斓的世界

background:
……羽毛

从天而降的羽毛

如雪一般的纯白，

在海风中摇曳，

在凉风中舞动，

仿佛要将谁的心带走一样——神仙的羽毛。

……

“求求你”

谁这样说到

“求求你了”

“救救我们”

……梦

我知道的，这是一场梦

随即，那个人又说话了，在我这纯白的梦里

“我们会一直在这里等着的……”

于是，我踏上了漫长的旅途

我有着非去不可的地方

为了实现那个人的愿望

所以我想，如果……

如果，我的愿望能够实现的话。

那样的话，或许，我和你……

![](https://cdn.luogu.com.cn/upload/pic/13166.png)

……世界终结了

已经终结了

我没赶上，不管什么，所有的事情……

……可憎

不可原谅

我……

……我、绝对、不会原谅你

现在、就出发……

我一定……一定要，把你……！

![](https://cdn.luogu.com.cn/upload/pic/13167.png)

手……牵着手，就能连着心

……我的左手，没有牵着任何人的，我的手

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

实现愿望。

只留下这个事实，然后我们两人就会分别。

就是希望着这一点，我们才会两个人一起走到今天。

是这样吧？

![](https://cdn.luogu.com.cn/upload/pic/13168.png)

来，出发吧，去选择那独一无二的明天

![](https://cdn.luogu.com.cn/upload/pic/13169.png)

description:
二阶堂真红给了你一个长为 $n$ 的序列 $a$，有 $m$ 次操作

1. 把区间 $[l,r]$ 中大于 $x$ 的数减去 $x$。
2. 查询区间 $[l,r]$ 中 $x$ 的出现次数。

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

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

接下来 $m$ 行，每行四个整数：

- `1 l r x`：把区间 $[l,r]$ 所有大于 $x$ 的数减去 $x$。
- `2 l r x`：查询区间 $[l,r]$ 内的 $x$ 的出现次数。

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

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

对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le m\le 5\times 10^5$，$1\le l\le r \le n$，$0 \le a_i,x \le 10^5+1$。

By nzhtl1477


title: [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？

background:
今天真是多谢你了

让我体验了许多美好

我留下了如同美梦一般的回忆 不过时间到了

最后我还想拜托你一件事

希望你可以把我忘掉

 ![](https://cdn.luogu.com.cn/upload/pic/13170.png)

在自己消失之前

心怀不想消失的愿望

希望让某个人记住我

希望能留下羁绊

我这么希望着，又有什么不可以的吗

 ![](https://cdn.luogu.com.cn/upload/pic/13171.png)

香香甜甜的，真好闻

看起来很好吃

 ![](https://cdn.luogu.com.cn/upload/pic/13173.png)

我遵守了...

约...约定

我非常...非常努力哦...

 ![](https://cdn.luogu.com.cn/upload/pic/13172.png)

欢迎回来，珂朵莉

description:
珂朵莉给了你一个长为 $n$ 的序列 $a$，有 $m$ 次操作。

1. 把区间 $[l,r]$ 内所有数都加上 $x$。
2. 查询区间 $[l,r]$ 内的最大子段和，可以不选数。

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

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

后面 $m$ 行：

- `1 l r x`：把区间 $[l,r]$ 内所有数加上 $x$。
- `2 l r`：查询区间 $[l,r]$ 的最大子段和。

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

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

$1 \le n , m \le 10^5$，$| a_i | \leq 10^9$，$|x|\leq 10^9$。

**保证任意时刻 $|a_i|\leq 2\times 10^9$。**

By nzhtl1477 & ccz181078


title: [Ynoi2018] 未来日记

background:
所以说，小雪的未来是由乃的~

 ![](https://cdn.luogu.com.cn/upload/pic/13174.png)

嗯...我知道你的未来会怎样

听好吧，我妻由乃

 ![](https://cdn.luogu.com.cn/upload/pic/13175.png)

因为小雪改变了未来，所以他们三人才能在一起...

为什么...

这样我简直就是坏人...

 ![](https://cdn.luogu.com.cn/upload/pic/13176.png)

我不会刺的

因为...这就是未来啊

这里...就是我的家

![](https://cdn.luogu.com.cn/upload/pic/13177.png)

description:
我妻由乃给了你一个长为 $n$ 的序列 $a$，有 $m$ 次操作。

1. 把区间 $[l,r]$ 内所有的 $x$ 变成 $y$。
2. 查询区间 $[l,r]$ 内第 $k$ 小值。

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

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

后面 $m$ 行：

`1 l r x y` : 把区间 $[l,r]$ 中所有 $x$ 变成 $y$。

`2 l r k` : 查询区间 $[l,r]$ 中的 $k$ 小值。

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

hint:
Idea：f321dd，Solution：f321dd&nzhtl1477，Code：nzhtl1477&Claris，Data：nzhtl1477&Juan_feng

$1\le n,m,a_i \le 10^5$。

By f321dd & nzhtl1477 & Claris


title: 采集矿石

background:
**ZRQ** 成功从坍塌的洞穴中逃了出来。终于，他看到了要研究的矿石。他想挑一些带回去完成任务。

题目来源：[Zhang\_RQ](https://www.luogu.org/space/show?uid=31565)~~哦对了 ZRQ 就他，嗯~~

description:
**ZRQ** 发现这里有 $N$ 块排成一排的矿石。

他用一个小写字母来表示每块矿石，他还发现每块矿石有一个重要度 $V_i$。

**ZRQ** 想采集一段连续的矿石回研究所。

他非常严格，被采集的一段矿石必须满足**小写字母的字典序降序排名等于这段矿石的重要度和。**

**这里多个出现在不同位置的本质相同串的字典序排名相同。**

比如说字母串为 `aa`，那么第一个 `a` 的排名和第二个 `a` 的排名相同，都是 `2`（第 `1` 是 `aa`）。

**ZRQ** 问你，在原串中有哪些不同的子串可以被采集？

**这里子串不同定义为出现位置不同，也就是说本质相同的子串出现在不同位置都要计算一次（当然重要度和等于排名是前提）。**

比如共有 $4$ 块矿石，小写字母串为 `abcd`，重要度各为 `10 0 1 1`。

我们把所有的子串按照字典序从大到小排名：`1:d 2:cd 3:c 4:bcd 5:bc 6:b 7:abcd 8:abc 9:ab 10:a`。

那么串 `d` 的排名为 $1$（第一大），重要度和为 $1$，可以被采集。

串 `cd` 的排名为 $2$，重要度和为 $2$，可以被采集。

串 `a` 的排名为 $10$，重要度和为 $10$，可以被采集。

其他串则不满足这个条件，故有三个串可以被采集。

inputFormat:
第一行一个长度为 $N$ 由小写字母组成的字符串，每个字符代表一个矿石。

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

outputFormat:
一行一个整数，表示能被采集的子串个数 $S$。

接下来 $S$ 行每行两个整数 $L,R$，分别表示每个可采集子串的左端点与右端点，按照左端点升序为第一关键字，右端点升序为第二关键字排序。

hint:
共 $10$ 个测试点，每个点 $10$ 分，计 $100$ 分。

![pcg6nP.png](https://s1.ax1x.com/2018/01/19/pcg6nP.png)

对于所有测试点，有 $N\leq 10^5$，$0 \le V_i \le 1000$。保证每个点可被采集的子串不超过 $10^5$ 个。

**样例#1解释**放在题面里了。

**样例#2解释：**

每个子串都不满足条件。

串 `a` 的排名是 $4$，重要度和都是 $1$。

串 `aa` 的排名是 $3$，重要度和都是 $2$。

串 `aaa` 的排名是 $2$，重要度和都是 $3$。

串 `aaaa` 的排名是 $1$，重要度和都是 $4$。

**样例 #3解释：**

串 `a` 的排名是 $3$，重要度和都是 $1$。

串 `aa` 的排名是 $2$，重要度和都是 $2$，共有两个串`aa`，位置分别为 $1$~$2$ 和 $2$~$3$。

串 `aaa` 的排名是 $1$，重要度和都是 $3$。

**样例 #4解释：**

可以发现，串 $2$~$3$（第二个 `aa`）不满足条件了。它的排名还是 $2$ 不变，但是重要度和为 $3$。


title: [WC2005] 双面棋盘

description:
佳佳有一个 $n$ 行 $n$ 列的黑白棋盘，每个格子都有两面，一面白色，一面黑色。佳佳把棋盘平放在桌子上，因此每个格子恰好一面朝上，如下图所示：

![QQ20180116200234.png](https://www.z4a.net/images/2018/01/16/QQ20180116200234.png)

我们把每行从上到下编号为 $1$，$2$，$3$，……，$n$，各列从左到右编号为 $1$，$2$，$3$，……，$n$，则每个格子可以用棋盘坐标$(x, y)$表示。在上图中，有 $8$ 个格子黑色朝上，另外 $17$ 个格子白色朝上。

如果两个同色格子有一条公共边，我们称这两个同色格子属于同一个连通块。上图共有 $5$ 个黑色连通块和 $3$ 个白色连通块。

佳佳可以每分钟将一个格子翻转（即白色变成黑色，黑色变成白色），然后计算当前有多少个黑色连通块和白色连通块，你能算得更快吗？

inputFormat:
输入文件的第一行包含一个正整数 $n$，为格子的边长。以下 $n$ 行每行 $n$ 个整数，非 $0$ 即 $1$，表示初始状态。$0$ 表示白色，$1$ 表示黑色。

下一行包含一个整数 $m$，表示操作的数目。以下 $m$ 行每行两个整数 $x$, $y$ ( $1 \le x,y \le n$ )，表示把坐标为 $(x, y)$ 的格子翻转。

outputFormat: 输出文件包含 $m$ 行，每行对应一个操作。该行包括两个整数 $b$, $w$，表示黑色区域和白色区域数目。


title: [WC2012] 记忆中的水杉树

description:
江苏省常州高级中学是一所百年名校，这里萦绕着无数人难以忘怀的回忆。$Will$ 记得，在他小的时候，常州高级中学改建以前，学校里有一片高大的水杉林，每到水杉落叶之时，针状的叶子会像毯子一样盖在地上，走在上面浪漫而又闲适。那时，$Will$ 和同学们还喜欢用这些针叶，在水杉树下，玩“取叶子”的游戏。 游戏一开始，大家先将 $n$ 片针叶平铺在地上。接着，每一轮可以有一个同学选择一片针叶，按水平或者垂直方向将针叶移走（也就是平移到无穷远处）——当然，前提是移动过程中不被任何尚未移走的针叶所阻碍。如果某一轮针叶的移动会被阻碍，那么这次移动就是非法的，是不被允许的。$n$轮过后，当针叶都被移走时，游戏也就结束了。 针叶并不是任何时刻都可以被移动的。当针叶很多的时候，判断每一轮中一片针叶是否可以按一个特定的方向移动是一件很麻烦的事情。 现在我们将地面抽象为平面直角坐标系，$n$ 片针叶抽象为平面上 $n$ 条互不相交的线段，并将其从$1$到$n$编号，$Will$ 还将给出每一轮游戏中，他想要移动的针叶编号以及移动方向，请你帮助他：

$1$.找出最早的一次非法移动出现在哪一轮；

$2$.给出一个合法的移动方案完成这个游戏。

注意：在线段移动时仅端点接触不会造成阻碍，具体请参见样例。

inputFormat:
输入文件的第一行包含一个正整数$n$，表示针叶的数量。

接下来$n$行，每行$4$个整数，描述针叶的位置信息。其中第 $i$ 行的整数为 $a_i$，$b_i$，$c_i$，$d_i$，表示编号为 $i$ 的针叶所抽象成的线段的端点为$(a_i, b_i)$和$(c_i, d_i)$。

接下来 $n$ 行，每行 $2$ 个整数，描述移动操作。其中第 $i$ 行的整数为 $p_i$，$q_i$，表示第 $i$ 轮移动的针叶编号为 $p_i$，方向为 $q_i$。其中 $q_i$为一个 $0$ 到 $3$ 之间的整数，$0$ 表示向左平移（即 $x$ 轴负方向） ，$1$ 表示向上平移（即 $y$ 轴正方向） ，$2$ 表示向右平移，$3$ 表示向下平移。

输入数据保证：

○所有线段长度为正，两两之间没有公共点，且不存在垂直或者水平的线段;

○$p_1$到$p_n$恰好组成一个$1$到$n$的排列；

○$Will$所给出的移动操作中一定存在非法移动；

○$n$轮均合法的移动操作总是存在的。

outputFormat:
输出文件一共包含$n$ + $1$行。

输出的第一行包含一个$1$到$n$之间的整数，表示最早出现非法移动的是哪一轮。

接下来$n$行，每行两个整数，内容同输入格式所述，描述一个合法的移动序列。

hint:
【样例说明】

在 $Will$ 给出的移动方案的第$3$轮中，编号为$4$的针叶向左移动会被编号为$5$的针叶阻碍。

【数据范围】

具体数据范围见下表。

![QQ20180116204421.png](https://www.z4a.net/images/2018/01/16/QQ20180116204421.png)

对于一个测试点：

如果非法移动判断正确，但是给出的方案错误，可以得到 $5$ 分。此时会提示：`An invalid move in step`

如果非法移动判断错误，但是给出的方案正确，可以得到 $5$ 分。此时会提示：`Negative error detection!`

如果非法移动的判断与给出方案均正确，则可以得到 $10$ 分；

否则，得 $0$ 分。

 如果程序的输出格式不正确，将被直接判作输出格式不正确，将被直接判作 $0$ 分。


title: [USACO17DEC] Blocked Billboard B

description:
During long milking sessions, Bessie the cow likes to stare out the window of her barn at two huge rectangular billboards across the street advertising "Farmer Alex's Amazingly Appetizing Alfalfa" and "Farmer Greg's Great Grain". Pictures of these two cow feed products on the billboards look much tastier to Bessie than the grass from her farm.

One day, as Bessie is staring out the window, she is alarmed to see a huge rectangular truck parking across the street. The side of the truck has an advertisement for "Farmer Smith's Superb Steaks", which Bessie doesn't quite understand, but she is mostly concerned about the truck potentially blocking the view of her two favorite billboards.

Given the locations of the two billboards and the location of the truck, please calculate the total combined area of both billboards that is still visible. It is possible that the truck obscures neither, both, or only one of the billboards.

在平面直角坐标系中，有两个矩形（保证不相交），然后给出第三个矩形，求这两个矩形没有被第三个矩形遮住的部分的面积。

inputFormat:
The first line of input contains four space-separated integers: x1 y1 x2 y2, where (x1,y1) and (x2,y2) are the coordinates of the lower-left and upper-right corners of the first billboard in Bessie's 2D field of view. The next line contains four more integers, similarly specifying the lower-left and upper-right corners of the second billboard. The third and final line of input contains four integers specifying the lower-left and upper-right corners of the truck. All coordinates are in the range -1000 to +1000. The two billboards are guaranteed not to have any positive area of overlap between themselves.

题目给出三个坐标，分别表示三个矩形的左下、右上坐标

outputFormat: Please output the total combined area of both billboards that remains visible.

hint:
Here, 5 units of area from the first billboard and 12 units of area from the second billboard remain visible.

Problem credits: Brian Dean


title: [AHOI2009] 最小割

description:
A,B两个国家正在交战，其中A国的物资运输网中有$N$个中转站，$M$条单向道路。设其中第$i (1≤i≤M)$条道路连接了$v_i,u_i$两个中转站，那么中转站$v_i$可以通过该道路到达$u_i$中转站，如果切断这条道路，需要代价$c_i$。

现在B国想找出一个路径切断方案，使中转站$s$不能到达中转站$t$，并且切断路径的代价之和最小。

小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题：

- 问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？
- 问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？

现在请你回答这两个问题。

inputFormat:
第一行有$4$个正整数，依次为$N,M,s,t$。

第$2$行到第$(M+1)$行每行$3$个正整数$v,u,c$，表示$v$中转站到$u$中转站之间有单向道路相连，单向道路的起点是$v$， 终点是$u$,切断它的代价是$c(1≤c≤100000)$。

注意:两个中转站之间可能有多条道路直接相连。 同一行相邻两数之间可能有一个或多个空格。

outputFormat: 对每条单向边，按输入顺序，依次输出一行，包含两个非$0$即$1$的整数，分别表示对问题一和问题二的回答(其中输出$1$表示是，输出$0$表示否)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。


title: [AHOI2009] 同类分布

description: 给出两个数$a,b$，求出$[a,b]$中各位数字之和能整除原数的数的个数。

inputFormat: 一行，两个整数$a$和$b$

outputFormat: 一个整数，表示答案

hint: 对于所有的数据，$1 ≤ a ≤ b ≤ 10^{18}$


title: [SHOI2006] 有色图

description:
如果一张无向完全图（完全图就是任意两个不同的顶点之间有且仅有一条边相连）的每条边都被染成了一种颜色，我们就称这种图为有色图。如果两张有色图有相同数量的顶点，而且经过某种顶点编号的重排，能够使得两张图对应的边的颜色是一样的，我们就称这两张有色图是同构的。以下两张图就是同构的，因为假如你把第一张图的顶点 $(1,2,3,4)$ 置换成第二张图的 $(4,3,2,1)$，就会发现它们是一样的。

![](https://cdn.luogu.com.cn/upload/pic/13240.png)

你的任务是，对于计算所有顶点数为 $n$，颜色种类不超过 $m$ 的图，最多有几张是两两不同构的图。由于最后的答案会很大，你只要输出结论模 $p$ 的余数就可以了（$p$ 是一个质数）。

inputFormat: 输入文件只有一行，由三个正整数 $n,m,p$ 组成。

outputFormat: 即总数模 $p$ 后的余数。


title: [SHOI2006] 仙人掌

background:
#本题不同于bzoj1023
bzoj1023快捷通道：[[SHOI2008] cactus仙人掌图(II)](https://www.luogu.org/problemnew/show/P4244)

description:
仙人掌图（cactus）是一种无向连通图，它的每条边最多只能出现在一个简单回路（simple cycle）里面。从直观上说，可以把仙人掌图理解为允许存在回路的树。但是仙人掌图和树之间有个本质的不同，仙人掌图可以拥有多个支撑子图（spanning subgraph），而树的支撑子图只有一个（它自身），我们把仙人掌图的支撑子图的数目称为“仙人数”。你的任务就是计算给定图的“仙人数”。

一些关于仙人掌图的举例：

 ![](https://cdn.luogu.com.cn/upload/pic/13241.png)

第一张图是一个仙人掌图，第二张图的边（2，3）在两个不同的回路里面，所以不是仙人掌图，第三张图不是一个连通图，所以也不是仙人掌图。

以下是对一些术语的解释：

简单回路（simple cycle）：简单回路是原图的一条路径，这条路径的边集构成了回路，回路中顶点只能出现一次。比如对于上例中第二个图来说，它一共有三个简单回路，分别是（4，3，2，1，6，5）、（7，8，9，10，2，3）和（4，3，7，8，9，10，2，1，6，5）

支撑子图（spanning subgraph）：支撑子图也是原图的子图，这种子图可以比原来少一些边，但是不能破坏图的连通性，也不能去除原来图上的任何顶点。“支撑”的概念类似于我们熟知的“最小支撑树”，对于上例中的第一张图来说，任意去除回路I中的图或回路II中的一条边都能构成一个支撑子图，所以它的支撑子图一共有6 + 4 + 6 × 4 + 1 = 35种（注意图自身也是自己的一个子图）

inputFormat:
输入文件的第一行是两个整数n和m（1≤n≤20000, 0≤m≤1000）。n代表图的顶点数，顶点的编号总是从1到n表示的。

接下来一共有m行。每行都代表了图上的一条路径（注意：这里所表示的一条路径可不一定是一条回路）。这些行的格式是首先有一个整数ki（2≤ki≤1000）代表这条路径通过了几个顶点，接下来是ki个在1到n之间的数字，其中每个数字代表了图上的一个顶点，相邻的顶点之间就定义了一条边。一条路径上可能通过一个顶点好几次，比如对于第一个例子，第一条路径从2经过3，又从8返回到了3，但是我们保证所有的边都会出现在某条路径上，而且不会重复出现在两条路径上，或者在一条路径上出现两次。

outputFormat: 输出这张图的“仙人数”，如果它不是一张仙人掌图，输出0。注意最后的答案可能是一个很大很大的数。


title: [NOI2007] 项链工厂

background:
T公司是一家专门生产彩色珠子项链的公司，其生产的项链设计新颖、款式多样、价格适中，广受青年人的喜爱。

最近T公司打算推出一款项链自助生产系统，使用该系统顾客可以自行设计心目中的美丽项链。该项链自助生产系

统包括硬件系统与软件系统，软件系统与用户进行交互并控制硬件系统，硬件系统接受软件系统的命令生产指定的

项链。该系统的硬件系统已经完成，而软件系统尚未开发，T公司的人找到了正在参加全国信息学竞赛的你，你能

帮助T公司编写一个软件模拟系统吗？

description:
一条项链包含 $N$ 个珠子，每个珠子的颜色是 $1,2,…,c$ 中的一种。项链

被固定在一个平板上，平板的某个位置被标记位置 $1$ ，按顺时针方向其他位置被记为 $2,3,…,N$。

 ![](https://cdn.luogu.com.cn/upload/pic/13560.png)

你将要编写的软件系统应支持如下命令：

 ![](https://cdn.luogu.com.cn/upload/pic/13561.png)

![](https://cdn.luogu.com.cn/upload/pic/13562.png)

inputFormat:
输入文件第一行包含两个整数 $N, c$，分别表示项链包含的珠子数目以及颜色数目。

第二行包含 $N$ 个整数，$x_1, x_2…, x_n$，表示从位置 $1$ 到位置 $N$ 的珠子的颜色，$1 \le x_i \le c$。

第三行包含一个整数 $Q$，表示命令数目。

接下来的 $Q$ 行每行一条命令，如上文所述。

outputFormat: 对于每一个 ``C`` 和 ``CS`` 命令，应输出一个整数代表相应的答案。

hint:
【数据规模和约定】

对于60%的数据，$N \le 1000$，$Q \le 1000$；

对于100%的数据，$N \le 500000$，$Q \le 500000$，$c \le 1000$。

关于旋转和翻转

注意旋转命令旋转“珠子”但不改变“位置”的编号，而反转命令始终以位置 1 为对称轴。例如当 N=10 时，项链上的位置编号如图1：

但注意此时项链上的位置编号仍然如图1所示，于是翻转的对称轴不变。因而再执行一次“F”命令时，项链的颜色如图4所示。

 ![](https://cdn.luogu.com.cn/upload/pic/13244.png)

 ![](https://cdn.luogu.com.cn/upload/pic/13245.png)

关于CountSegment命令

CS命令表示查询一个“线段”中有多少个“部分”。尤其注意当查询的长度等于 N 时，我们仍然将查询部分作为“线段”理解。

例如在图4所示的情况中，执行“CS 1 10”命令，查询从位置 1 开始到位置 10 结束的这个长度为 10 的线段中有多少个“部分”，于是得到返回值 3 。与之形成对照的是，若执行“C”命令，返回值则为 2


title: [IOI2011] Race

description: 给一棵树，每条边有权。求一条简单路径，权值和等于 $k$，且边的数量最小。

inputFormat:
第一行包含两个整数 $n,k$，表示树的大小与要求找到的路径的边权和。

接下来 $n-1$ 行，每行三个整数 $u_i,v_i,w_i$，代表有一条连接 $u_i$ 与 $v_i$，边权为 $w_i$ 的无向边。

**注意：点从 $0$ 开始编号**。

outputFormat:
输出一个整数，表示最小边数量。

如果不存在这样的路径，输出 $-1$。

hint: 对于 $100\%$ 的数据，保证 $1\leq n\leq 2\times10^5$，$0\leq k,w_i\leq 10^6$，$0\leq u_i,v_i<n$。


title: [WC2005] 友好的生物

description:
$W$ 星球是一个和地球一样气候适宜、物种聚集的星球。经过多年的研究，外星生物学家们已经发现了数万种生物，而且这个数字还在不断增大。

$W$ 星球上的生物很有趣，有些生物之间很友好，朝夕相伴，形影不离；但有些却很敌对，一见面就难免发生战斗。为了能够更好地了解它们之间的友好程度，外星生物学家希望进行一些量化的计算。他们发现，两种生物之间的友好程度和它们的 $K$ 种属性有关，暂且将它们编号为属性 $1$、属性 $2$、……、属性 $K$，这些属性都是可以进行量化的。外星生物学家研究发现，如果前 $K-1$ 种属性的差别越大，这两种生物就越友好；但是属性 $K$ 与众不同，这种属性差别越小的两种生物越友好。

因此他们猜想是不是可以用这样一个公式量化两种生物之间的友好程度：$Friendliness=(\sum_{i=1}^{k-1} C_id_i)-C_Kd_K$

其中 $C_i$ 是非负常数，$d_i$ 是属性 $i$ 的差别。如果知道了每种生物的各种属性，利用上述公式就很容易算出它们之间的友好程度了。现在，外星生物学家们想问一问：在目前发现的这些生物当中，关系最友好的那对生物是哪一对呢？它们之间的友好程度是多少？

inputFormat:
输入文件的第一行是两个整数 $N$ 和 $K$，分别表示目前发现的生物种数和属性的种数。

第二行有 $K$ 个非负整数 $C_i$，即计算友好程度时所需的常数。

接下来的 $N$ 行，描述每种生物，按照先后顺序依次编号为生物 $1$、生物 $2$、……、生物 $N$。每一行都有 $K$ 个整数，给出该种生物的各项属性值，按照先后顺序依次编号为属性 $1$、属性 $2$、……、属性 $K$。

outputFormat:
输出文件包含两行。第一行为两个整数 $i$ 和 $j$（$i \neq j$），表示你所找到的关系最友好的两种生物为生物 $i$ 和生物 $j$。若最友好的不止一对，输出任意一对。

第二行为一个整数，表示生物 $i$ 和生物 $j$ 之间的友好程度。


title: [NOIP2022] 种花

description:
小 C 决定在他的花园里种出 $\texttt{CCF}$ 字样的图案，因此他想知道 $\texttt C$ 和 $\texttt F$ 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。

花园可以看作有 $n\times m$ 个位置的网格图，从上到下分别为第 $1$ 到第 $n$ 行，从左到右分别为第 $1$ 列到第 $m$ 列，其中每个位置有可能是土坑，也有可能不是，可以用 $a_{i,j} = 1$ 表示第 $i$ 行第 $j$ 列这个位置有土坑，否则用 $a_{i,j} = 0$ 表示这个位置没土坑。

一种种花方案被称为 $\texttt{C-}$ **形**的，如果存在 $x_1, x_2 \in [1, n]$，以及 $y_0, y_1, y_2 \in [1, m]$，满足 $x_1 + 1 < x_2$，并且 $y_0 < y_1, y_2 \leq m$，使得第 $x_1$ **行**的第 $y_0$ 到第 $y_1$ **列**、第 $x_2$ **行**的第 $y_0$ 到第 $y_2$ **列**以及第 $y_0$ **列**的第 $x_1$ 到第 $x_2$ **行**都**不为土坑**，且只在上述这些位置上种花。

一种种花方案被称为 $\texttt{F-}$ **形**的，如果存在 $x_1, x_2, x_3 \in [1, n]$，以及 $y_0, y_1, y_2 \in [1, m]$，满足 $x_1 + 1 < x_2 < x_3$，并且 $y_0 < y_1, y_2 \leq m$，使得第 $x_1$ **行**的第 $y_0$ 到第 $y_1$ **列**、第 $x_2$ **行**的第 $y_0$ 到第 $y_2$ **列**以及第 $y_0$ **列**的第 $x_1$ 到第 $x_3$ **行**都**不为土坑**，且只在上述这些位置上种花。

样例一解释中给出了 $\texttt{C-}$ 形和 $\texttt{F-}$ 形种花方案的图案示例。

现在小 C 想知道，给定 $n, m$ 以及表示每个位置是否为土坑的值 $\{a_{i,j}\}$，$\texttt{C-}$ 形和 $\texttt{F-}$ 形种花方案分别有多少种可能？由于答案可能非常之大，你只需要输出其对 $998244353$ 取模的结果即可，具体输出结果请看输出格式部分。

inputFormat:
第一行包含两个整数 $T, id$，分别表示数据组数和测试点编号。如果数据为样例则保证 $id = 0$。

接下来一共 $T$ 组数据，在每组数据中：

第一行包含四个整数 $n, m, c, f$，其中 $n, m$ 分别表示花园的行数、列数，对于 $c, f$ 的含义见输出格式部分。

接下来 $n$ 行，每行包含一个长度为 $m$ 且仅包含 $0$ 和 $1$ 的字符串，其中第 $i$ 个串的第 $j$ 个字符表示 $a_{i,j}$，即花园里的第 $i$ 行第 $j$ 列是不是一个土坑。

outputFormat: 设花园中 $\texttt{C-}$ 形和 $\texttt{F-}$ 形的种花方案分别有 $V_C$ 和 $V_F$ 种，则你需要对每一组数据输出一行用一个空格隔开的两个非负整数，分别表示 $(c \times V_C) \bmod 998244353$，$(f \times V_F ) \bmod 998244353$ ，其中 $a \bmod P$ 表示 $a$ 对 $P$ 取模后的结果。


title: [NOIP2022] 喵了个喵

description:
小 E 喜欢上了一款叫做《喵了个喵》的游戏。这个游戏有一个牌堆和 $n$ 个可以从栈底删除元素的栈，任务是要通过游戏规则将所有的卡牌消去。开始时牌堆中有 $m$ 张卡牌，从上到下的图案分别是 $a_1, a_2,\dots, a_m$。所有的卡牌一共有 $k$ 种图案，从 $1$ 到 $k$ 编号。牌堆中每一种图案的卡牌都有偶数张。开始时所有的栈都是空的。这个游戏有两种操作：

- 选择一个栈，将牌堆顶上的卡牌放入栈的顶部。如果这么操作后，这个栈最上方的两张牌有相同的图案，则会自动将这两张牌消去。
- 选择两个不同的栈，如果这两个栈栈**底**的卡牌有相同的图案，则可以将这两张牌消去，原来在栈底上方的卡牌会成为新的栈底。如果不同，则什么也不会做。

这个游戏一共有 $T$ 关，小 E 一直无法通关。请你帮小 E 设计一下游戏方案，即对于游戏的每一关，给出相应的操作序列使得小 E 可以把所有的卡牌消去。

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

接下来一共 $T$ 组数据，在每组数据中：

第一行包含三个正整数 $n, m, k$，分别表示栈的个数、卡牌的个数、卡牌上图案的种类。

第二行包含 $m$ 个正整数，分别表示 $a_1, a_2,\dots, a_m$，分别从上到下表示牌堆中卡牌的图案。

输入数据保证有解。

outputFormat:
对于每一组数据，输出若干行。

其中第一行包含一个正整数 $\mathrm{op}$，表示操作的次数。你需要保证 $m \leq \mathrm{op} \leq 2\times m$。

接下来 $\mathrm{op}$ 行，每行包含两个或三个正整数，整数之间用一个空格隔开。

若为两个整数 $\texttt{1 s}$，则进行一次第一个操作并选择栈 $s$。

若为三个整数 $\texttt{2 s1 s2}$，则进行一次第二个操作并选择栈 $s_1$ 和 $s_2$。

你需要保证 $1 \leq s, s_1, s_2 \leq n$，且 $s_1 \neq s_2$。

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

下图是初始状态。

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

下图是前两次操作之后的结果。

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

下图是第三次和第四次操作之后的结果。

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

下图是第五次操作之后的结果。

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

**【样例 2】**

见选手目录下的 $\texttt{meow/meow2.in}$ 与 $\texttt{meow/meow2.ans}$。

**【数据范围】**

设 $S$ 为所有 $T$ 组数据中 $m$ 的总和。

对于所有数据，保证 $S \leq 2 \times 10^6$，$1 \leq n  \leq 300$，$1 \leq a_i \leq k$。

| 测试点 | $T=$ | $n$ | $k=$ | $m \leq$ |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1\sim 3$ | $1001$ | $\leq 300$ | $2n-2$ | 无限制 |
| $4\sim 6$ | $1002$ | $=2$ | $2n-1$ | 无限制 |
| $7\sim 10$ | $3$ | $=3$ | $2n-1$ | $14$ |
| $11\sim 14$ | $1004$ | $=3$ | $2n-1$ | 无限制 |
| $15\sim 20$ | $1005$ | $\leq 300$ | $2n-1$ | 无限制 |

**【评分方式】**

对于每一组数据，若在按顺序进行所有操作后，牌堆为空且所有的栈均为空，则认为你的答案正确。

**【提示】**

你可以通过 $T$ 的个位数来判断这个测试点是属于哪一类数据。

你的输出不需要与样例输出一致，输出任意一个合法解即可得分。


title: [BJOI2012] 算不出的等式

background: 曾经有一个老掉牙的游戏放在我面前，我没有珍惜。直到这个游戏停产才追悔莫及。人世间最痛苦的事情莫过于此，如果上天给我一个再玩一次的机会，我一定要，通关！

description:
如果你真的很想玩这个游戏，那么就先看看我的题目吧，搞不定这些的话是没办法通关的哟。第一关其实很简单，只有一个关闭的有密码锁的大门。这大门上写着一个奇怪的算式，估计是要你利用它算出密码来开门吧（果然是老掉牙的情节）。

传说中这个式子中的p和q是两个奇质数，等号右边算出来应该就是密码了吧，你是真的算不出来么？

$\sum_{k=1}^{\frac{p-1}{2}} \biggl\lfloor\frac{kq}{p}\biggr\rfloor+\sum_{k=1}^{\frac{q-1}{2}} \biggl\lfloor\frac{kp}{q}\biggr\rfloor$

inputFormat: 只有一行，两个奇质数，分别表示p,q。

outputFormat: 一个数,表示算式结果。


title: [BJOI2012] 最多的方案

description:
第二关和很出名的斐波那契数列有关，地球上的 OIer 都知道：
$$F_n = \begin{cases} 1 & (n \le 2) \\ F_{n-1}+F_{n-2} & (n \ge 3) \end{cases}$$
每一项都可以称为斐波那契数。

现在给一个正整数 $n$，它可以写成一些斐波那契数的和的形式。如果我们要求不同的方案中不能有相同的斐波那契数，那么对一个 $n$ 最多可以写出多少种方案呢？

inputFormat: 只有一个整数 $n$。

outputFormat: 一个整数表示方案数。


title: 上帝造题的七分钟 2 / 花神游历各国

background: XLk 觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。

description:
"第一分钟，X 说，要有数列，于是便给定了一个正整数数列。

第二分钟，L 说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。

第三分钟，k 说，要能查询，于是便有了求一段数的和的操作。

第四分钟，彩虹喵说，要是 noip 难度，于是便有了数据范围。

第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。

第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过 $64$ 位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。"

——《上帝造题的七分钟·第二部》

所以这个神圣的任务就交给你了。

inputFormat:
第一行一个整数 $n$，代表数列中数的个数。

第二行 $n$ 个正整数，表示初始状态下数列中的数。

第三行一个整数 $m$，表示有 $m$ 次操作。

接下来 $m$ 行每行三个整数 `k l r`。

- $k=0$ 表示给 $[l,r]$ 中的每个数开平方（下取整）。

- $k=1$ 表示询问 $[l,r]$ 中各个数的和。

**数据中有可能 $l>r$，所以遇到这种情况请交换 $l$ 和 $r$。**

outputFormat: 对于询问操作，每行输出一个回答。


title: [BJOI2012] 连连看

description: 凡是考智商的题里面总会有这么一种消除游戏。不过现在面对的这关连连看可不是 QQ 游戏里那种考眼力的游戏。我们的规则是，给出一个闭区间 $[a,b]$ 中的全部整数，如果其中某两个数 $x$，$y$（$x>y$）的平方差 $x^2-y^2$ 是一个完全平方数 $z^2$，并且 $y$ 与 $z$ 互质，那么就可以将 $x$ 和 $y$ 连起来并且将它们一起消除，同时得到 $x+y$ 点分数。那么过关的要求就是，消除的数对尽可能多的前提下，得到足够的分数。快动手动笔算一算吧。

inputFormat: 只有一行，两个整数，分别表示 $a$，$b$。

outputFormat: 两个数，可以消去的对数，及在此基础上能得到的最大分数。


title: 谁能赢呢？

description:
小明和小红经常玩一个博弈游戏。给定一个 $n\times n$ 的棋盘，一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。

假如小明先移动石头，而且两个选手都以最优策略走步，问最后谁能赢？

inputFormat:
输入文件有多组数据。

输入第一行包含一个整数 $n$，表示棋盘的规模。

当输入 $n$ 为 $0$ 时，表示输入结束。

outputFormat: 对于每组数据，如果小明最后能赢，则输出 `Alice`，否则输出 `Bob`，每一组答案独占一行。


title: [Violet] 天使玩偶/SJY摆棋子

description:
Ayu 在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了地下。而七年后 的今天，Ayu 却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。

我们把 Ayu 生活的小镇看作一个二维平面坐标系，而 Ayu 会不定时地记起可能在某个点 $(x, y)$ 埋下了天使玩偶；或者 Ayu 会询问你，假如她在 $(x,y)$，那么她离近的天使玩偶可能埋下的地方有多远。

因为 Ayu 只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为 $\operatorname{dist}(A,B)=|A_x-B_x|+|A_y-B_y|$。其中 $A_x$ 表示点 $A$ 的横坐标，其余类似。

inputFormat:
第一行包含两个整数 $n$ 和 $m$，在刚开始时，Ayu 已经知道有 $n$ 个点可能埋着天使玩偶， 接下来 Ayu 要进行 $m$ 次操作。

接下来 $n$ 行，每行两个非负整数 $(x_i,y_i)$，表示初始 $n$ 个点的坐标。

再接下来 $m$ 行，每行三个非负整数 $t,x_i,y_i$。

* 如果 $t=1$，则表示 Ayu 又回忆起了一个可能埋着玩偶的点 $(x_i,y_i)$。
* 如果 $t=2$，则表示 Ayu 询问如果她在点 $(x_i,y_i)$，那么在已经回忆出来的点里，离她近的那个点有多远

outputFormat: 对于每个 $t=2$ 的询问，在单独的一行内输出该询问的结果。

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

对于 $100\%$ 的数据 保证 $1 \leq n,m\leq 3 \times 10^5$，$0 \leq x_i,y_i \leq 10^6$。


title: [Violet] 蒲公英

background:
亲爱的哥哥：

你在那个城市里面过得好吗？

我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说！它把人们的房子和田地搞坏，还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受的时候才做出这样的事的……

最近村子里长出了一大片一大片的蒲公英。一刮风，这些蒲公英就能飘到好远的地方了呢。我觉得要是它们能飘到那个城市里面，让哥哥看看就好了呢！

哥哥你要快点回来哦！

爱你的妹妹 Violet

Azure 读完这封信之后微笑了一下。

“蒲公英吗……”

description:
在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。

为了简化起见，我们把所有的蒲公英看成一个长度为 $n$ 的序列 $\{a_1,a_2..a_n\}$，其中 $a_i$ 为一个正整数，表示第 $i$ 棵蒲公英的种类编号。

而每次询问一个区间 $[l, r]$，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。

**注意，你的算法必须是在线的**。

inputFormat:
第一行有两个整数，分别表示蒲公英的数量 $n$ 和询问次数 $m$。

第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 棵蒲公英的种类 $a_i$。

接下来 $m$ 行，每行两个整数 $l_0, r_0$，表示一次询问。输入是加密的，解密方法如下：

令上次询问的结果为 $x$（如果这是第一次询问，则 $x = 0$），设 $l=((l_0+x-1)\bmod n) + 1,r=((r_0+x-1) \bmod n) + 1$。如果 $l > r$，则交换 $l, r$。
最终的询问区间为计算后的 $[l, r]$。

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


title: 作诗

background:
神犇 SJY 虐完 HEOI 之后给傻× LYD 出了一题：

SHY 是 T 国的公主，平时的一大爱好是作诗。

description:
由于时间紧迫，SHY 作完诗之后还要虐 OI，于是 SHY 找来一篇长度为 $n$ 的文章，阅读 $m$ 次，每次只阅读其中连续的一段 $[l,r]$，从这一段中选出一些汉字构成诗。因为 SHY 喜欢对偶，所以 SHY 规定最后选出的每个汉字都必须在 $[l,r]$ 里出现了正偶数次。而且 SHY 认为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好（为了拿到更多的素材！）。于是 SHY 请 LYD 安排选法。

LYD 这种傻×当然不会了，于是向你请教……

问题简述：给定 $n$ 个不大于 $c$ 的正整数 $a_1 \dots a_n$ 和 $m$ 组询问，每次问 $[l,r]$ 中有多少个数出现正偶数次。

inputFormat:
**本题强制在线**。

第一行有三个整数 $n$、$c$ 以及 $m$ 。表示文章字数、汉字的种类数、要选择 $m$ 次。

第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个汉字的编码 $a_i$。

接下来 $m$ 行每行两个整数 $l$ 和 $r$，设上一个询问的答案为 $ans$（第一个询问时 $ans=0$），令 $L=(l+ans)\mod n+1$，$R=(r+ans)\mod n+1$，若 $L>R$，交换 $L$ 和 $R$，则本次询问为 $[L,R]$。

outputFormat: 输出共 $m$ 行，每行一个整数，第 $i$ 个数表示 SHY 第 $i$ 次能选出的汉字的最多种类数。

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

对于 $100\%$ 的数据，$1\le n,c,m\le 10^5$，$1 \leq a_i \leq c$，$1 \leq l, r \leq n$。


title: Rmq Problem / mex

description:
有一个长度为 $n$ 的数组 $\{a_1,a_2,\ldots,a_n\}$。

$m$ 次询问，每次询问一个区间内最小没有出现过的自然数。

inputFormat:
第一行，两个正整数 $n,m$。
第二行，$n$ 个非负整数 $a_1, a_2, \ldots , a_n$。
接下来 $m$ 行，每行两个正整数 $l,r$，表示一次询问。

outputFormat: 输出 $m$ 行，每行一个数，依次表示每个询问的答案。

hint:
对于 $30\%$ 的数据：$1\leq n,m\leq 1000$。
对于 $100\%$ 的数据：$1\leq n,m\leq 2\times {10}^5$，$1\leq l\leq r\leq n$，$0\leq a_i\leq 2\times 10^5$。


title: [JOISC2014] 挂饰

description:
JOI君有N个装在手机上的挂饰，编号为1...N。 JOI君可以将其中的一些装在手机上。

JOI君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有1个。

此外，每个挂件有一个安装时会获得的喜悦值，用一个整数来表示。如果JOI君很讨厌某个挂饰，那么这个挂饰的喜悦值就是一个负数。

JOI君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰，而且一个都不挂也是可以的。

inputFormat:
第一行一个整数N，代表挂饰的个数。

接下来N行，第i行(1<=i<=N)有两个空格分隔的整数Ai和Bi，表示挂饰i有Ai个挂钩，安装后会获得Bi的喜悦值。

outputFormat: 输出一行一个整数，表示手机上连接的挂饰总和的最大值

hint:
$1\leq N\leq 2000$

$0\leq Ai\leq N(1\leq i\leq N)$

$-10^6\leq Bi\leq 10^6(1\leq i\leq N)$


title: 月下“毛景树”

background: 毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。

description:
爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有 $N$ 个节点和 $N-1$ 条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数：

- `Change k w`：将第k条树枝上毛毛果的个数改变为 $w$ 个。
- `Cover u v w`：将节点 $u$ 与节点 $v$ 之间的树枝上毛毛果的个数都改变为 $w$ 个。
- `Add u v w`：将节点 $u$ 与节点 $v$ 之间的树枝上毛毛果的个数都增加 $w$ 个。

由于毛毛虫很贪，于是他会有如下询问：

-  `Max u v`：询问节点 $u$ 与节点 $v$ 之间树枝上毛毛果个数最多有多少个。

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

接下来 $N-1$ 行，每行三个正整数 $U_i,V_i$ 和 $W_i$，第 $i+1$ 行描述第 $i$ 条树枝。表示第 $i$ 条树枝连接节点 $U_i$ 和节点 $V_i$，树枝上有 $W_i$ 个毛毛果。 接下来是操作和询问，以 `Stop` 结束。

outputFormat: 对于毛毛虫的每个询问操作，输出一个答案。

samples:
4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop

hint:
对于全部数据，$1\le N\le 10^5$，操作和询问数目不超过 $10^5$。

保证在任意时刻，所有树枝上毛毛果的个数都不会超过 $10^9$ 个。


title: 奇数国

description:
在一片美丽的大陆上有 $100\,000$ 个国家，记为 $1$ 到 $100\,000$。这里经济发达，有数不尽的账房，并且每个国家有一个银行。

某大公司的领袖在这 $100\,000$ 个银行开户时都存了 $3$ 大洋，他惜财如命，因此会不时地派小弟 GFS 清点一些银行的存款或者让 GFS 改变某个银行的存款。

该村子在财产上的求和运算等同于我们的乘法运算，也就是说领袖开户时的存款总和为 $3^{100000}$。这里发行的软妹面额是最小的 $60$ 个素数（$p_1=2,p_2=3,\ldots, p_{60}=281$），任何人的财产都只能由这 $60$ 个基本面额表示，即设某个人的财产为 $fortune$（正整数），则 $fortune=p_1^{k_1} \times p_2^{k_2} \times \ldots p_{60}^{k_{60}}$。

领袖习惯将一段编号连续的银行里的存款拿到一个账房去清点，为了避免 GFS 串通账房叛变，所以他不会每次都选择同一个账房。GFS 跟随领袖多年已经摸清了门路,知道领袖选择账房的方式。如果领袖选择清点编号在 $[a,b]$ 内的银行财产，他会先对 $[a,b]$ 的财产求和（记为 $product$），然后在编号属于 $[1,product]$ 的账房中选择一个去清点存款，检验自己计算是否正确同时也检验账房与 GFS 是否有勾结。GFS 发现如果某个账房的编号 $number$ 与 $product$ 相冲，领袖绝对不会选择这个账房。

怎样才算与 $product$ 不相冲呢？若存在整数 $x,y$ 使得 $number \times x+product \times y=1$，那么我们称 $number$ 与 $product$ 不相冲，即该账房有可能被领袖相中。当领袖又赚大钱了的时候，他会在某个银行改变存款，这样一来相同区间的银行在不同的时候算出来的 $product$ 可能是不一样的，而且领袖不会在某个银行的存款总数超过 $10^6$。

现在 GFS 预先知道了领袖的清点存款与变动存款的计划，想请你告诉他，每次清点存款时领袖有多少个账房可以供他选择，当然这个值可能非常大，GFS 只想知道对 $19\,961\,993$ 取模后的答案。

inputFormat:
第一行一个整数 $x$ 表示领袖清点和变动存款的总次数。

接下来 $x$ 行，每行 $3$ 个整数 $a_i,b_i,c_i$。$a_i$ 为 $0$ 时表示该条记录是清点计划，领袖会清点 $b_i$ 到 $c_i$ 的银行存款，你需要对该条记录计算出 GFS 想要的答案。$a_i$ 为 $1$ 时表示该条记录是存款变动，你要把银行 $b_i$ 的存款改为 $c_i$，不需要对该记录进行计算。

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


title: 消失之物

description:
ftiasch 有 $n$ 个物品, 体积分别是 $w_1,w_2,\dots,w_n$。由于她的疏忽，第 $i$ 个物品丢失了。

“要使用剩下的 $n-1$ 物品装满容积为 $x$ 的背包，有几种方法呢？”——这是经典的问题了。

她把答案记为 $\text{cnt}(i,x)$ ，想要得到所有$i \in [1,n]$, $x \in [1,m]$ 的 $\text{cnt}(i,x)$ 表格。

![](https://cdn.luogu.com.cn/upload/pic/13426.png)

inputFormat:
第一行两个整数 $n,m$，表示物品的数量和最大的容积。
第二行 $n$ 个整数 $w_1,w_2,\dots,w_n$，表示每个物品的体积。

outputFormat: 输出一个 $n \times m$ 的矩阵，表示 $\text{cnt}(i,x)$ 的**末位数字**。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n,m \le 2000$，且 $1\le v_i\le m$。

【样例解释】
如果物品 3 丢失的话，只有一种方法装满容量是 2 的背包，即选择物品 1 和物品 2。

---

$\text{upd 2023.8.11}$：新增加五组 Hack 数据。


title: 上帝与集合的正确用法

description:
根据一些书上的记载，上帝的一次失败的创世经历是这样的：

第一天，上帝创造了一个世界的基本元素，称做元。

第二天，上帝创造了一个新的元素，称作 $\alpha$ 。 $\alpha$ 被定义为元构成的集合。容易发现，一共有两种不同的 $\alpha$ 。

第三天，上帝又创造了一个新的元素，称作 $\beta$ 。 $\beta$ 被定义为 $\alpha$ 构成的集合。容易发现，一共有四种不同的 $\beta$。

第四天，上帝创造了新的元素 $\gamma$，$\gamma$ 被定义为 $\beta$ 的集合。显然，一共会有 $16$ 种不同的 $\gamma$。

如果按照这样下去，上帝创造的第四种元素将会有 $65536$ 种，第五种元素将会有 $2^{65536}$种。这将会是一个天文数字。

然而，上帝并没有预料到元素种类数的增长是如此的迅速。他想要让世界的元素丰富起来，因此，日复一日，年复一年，他重复地创造着新的元素……

然而不久，当上帝创造出最后一种元素 $\theta$ 时，他发现这世界的元素实在是太多了，以致于世界的容量不足，无法承受。因此在这一天，上帝毁灭了世界。

至今，上帝仍记得那次失败的创世经历，现在他想问问你，他最后一次创造的元素 $\theta$ 一共有多少种？

上帝觉得这个数字可能过于巨大而无法表示出来，因此你只需要回答这个数对p取模后的值即可。

你可以认为上帝从 $\alpha$ 到 $\theta$ 一共创造了 $10^9$ 次元素，或 $10^{18}$ 次，或者干脆 $\infty$ 次。

一句话题意：

定义 $a_0=1,a_n=2^{a_{n-1}}$，可以证明 $b_n=a_n\bmod p$ 在某一项后都是同一个值，求这个值。

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

接下来 $T$ 行，每行一个正整数 $p$，代表你需要取模的值。

outputFormat: $T$ 行，每行一个正整数，为答案对 $p$ 取模后的值。


title: 序列终结者

background:
网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……

这样我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。

这道题目就叫序列终结者吧。

description:
给定一个长度为N的序列，每个序列的元素是一个整数（废话）。要支持以下三种操作：

1. 将$[L,R]$这个区间内的所有数加上$V$。
2. 将$[L,R]$这个区间翻转，比如`1 2 3 4`变成`4 3 2 1`。
3. 求$[L,R]$这个区间中的最大值。

最开始所有元素都是$0$。

inputFormat:
第一行两个整数`N，M`。`M`为操作个数。

以下$M$行，每行最多四个整数，依次为`K，L，R，V`。`K`表示是第几种操作，如果不是第1种操作则`K`后面只有两个数。

outputFormat: 对于每个第3种操作，给出正确的回答。


title: [NOIP2022] 建造军营

description:
A 国与 B 国正在激烈交战中，A 国打算在自己的国土上建造一些军营。

A 国的国土由 $n$ 座城市组成，$m$ 条双向道路连接这些城市，使得**任意两座城市均可通过道路直接或间接到达**。A 国打算选择一座或多座城市（**至少一座**），并在这些城市上各建造一座军营。

众所周知，军营之间的联络是十分重要的。然而此时 A 国接到情报，B 国将会于不久后袭击 A 国的一条道路，但具体的袭击目标却无从得知。如果 B 国袭击成功，这条道路将被切断，可能会造成 A 国某两个军营无法互相到达，这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路（**可以是一条或多条，也可以一条也不看守**)，A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。

A 国希望制定一个建造军营和看守道路的方案，使得 B 国袭击的无论是 A 国的哪条道路，都不会造成某两座军营无法互相到达。现在，请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多，你只需要输出其对 $1,000,000,007\left(10^{9}+7\right)$ 取模的值即可。两个方案被认为是不同的，当且仅当存在至少一 座城市在一个方案中建造了军营而在另一个方案中没有，或者存在至少一条道路在一个 方案中被派兵看守而在另一个方案中没有。

inputFormat:
第一行包含两个正整数 $n,m$，分别表示城市的个数和双向道路的数量。

接下来 $m$ 行，每行包含两个正整数 $u_{i},v_{i}$，描述一条连接 $u_{i}$ 和 $v_{i}$ 的双向道路。保证没有重边和自环。

outputFormat: 输出一行包含一个整数，表示建造军营和看守道路的方案数对 $1,000,000,007\left(10^{9}+ 7\right)$ 取模的结果。

samples:
见附加文件里的 barrack/barrack3.in
见附加文件里的 barrack/barrack3.ans

samples:
见附加文件里的 barrack/barrack4.in
见附加文件里的 barrack/barrack4.ans


title: [WC2015] k 小割

description:
给出一个有向带权网络 $G = (V, E)$，权值函数 $w: E \rightarrow \mathbb{Z^{*}}$（即任意边 $e$ 的权值 $w(e)$ 均为正整数），和点 $s, t \in E$，使得在 $G' = (V, E - S)$ 上不存在 $s$ 到 $t$ 的路径。

设 $\mathfrak{S}$ 是所有满足条件的边集 $S$ 的全集，按 $w(S)$ 从小到大输出 $\mathfrak{S}$ 中前 $k$ 小的边集的边权和。其中 $w(S) = \sum_{e \in S} w(e)$。

inputFormat:
第一行包含 $5$ 个正整数 $n, m, s, t, k$，其中 $s, t, k$ 意义如上，$n, m$ 分别表示 $\lvert V \rvert, \lvert E \rvert$（即点数和边数）。规定图中的节点用 $1$ 到 $n$ 的整数表示。保证 $s \neq t$。

接下来 $m$ 行，每行 $3$ 个整数 $x, y, z$，表示一条边权为 $z$ 的从 $x$ 到 $y$ 的边。可能有重边但保证没有自环。

outputFormat:
如果 $\lvert \mathfrak{S} \rvert < k$，先输出 $\lvert \mathfrak{S} \rvert$ 行，每行包含一个整数，表示前 $\lvert \mathfrak{S} \rvert$ 个 $w(S)$；再输出一行一个整数 $-1$。

如果 $\lvert \mathfrak{S} \rvert \geq k$，则输出 $k$ 行，表示前 $k$ 个 $w(S)$。

两种情况均需按照 $w(S)$ 从小到大输出。


title: [JSOI2010] 满汉全席

description:
满汉全席是中国最丰盛的宴客菜肴，有许多种不同的材料透过满族或是汉族的料理方式，呈现在数量繁多的菜色之中。由于菜色众多而繁杂，只有极少数博学多闻技艺高超的厨师能够做出满汉全席，而能够烹饪出经过专家认证的满汉全席，也是中国厨师最大的荣誉之一。世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成，而他们之间还细分为许多不同等级的厨师。

为了招收新进的厨师进入世界满汉全席协会，将于近日举办满汉全席大赛，协会派遣许多会员当作评审员，为的就是要在参赛的厨师之中，找到满汉界的明日之星。

大会的规则如下：每位参赛的选手可以得到 $n$ 种材料，选手可以自由选择用满式或是汉式料理将材料当成菜肴。

大会的评审制度是：共有 $m$ 位评审员分别把关。每一位评审员对于满汉全席有各自独特的见解，但基本见解是，要有两样菜色作为满汉全席的标志。如某评审认为，如果没有汉式东坡肉跟满式的涮羊肉锅，就不能算是满汉全席。但避免过于有主见的审核，大会规定一个评审员除非是在认为必备的两样菜色都没有做出来的状况下，才能淘汰一位选手，否则不能淘汰一位选手。

换句话说，只要参赛者能在这两种材料的做法中，其中一个符合评审的喜好即可通过该评审的审查。如材料有猪肉，羊肉和牛肉时，有四位评审员的喜好如下表：

```
评审一 评审二 评审三 评审四
满式牛肉 满式猪肉 汉式牛肉 汉式牛肉
汉式猪肉 满式羊肉 汉式猪肉 满式羊肉
```

如参赛者甲做出满式猪肉，满式羊肉和满式牛肉料理，他将无法满足评审三的要求，无法通过评审。而参赛者乙做出汉式猪肉，满式羊肉和满式牛肉料理，就可以满足所有评审的要求。

但大会后来发现，在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话，所有的参赛者最多只能通过部分评审员的审查而不是全部，所以可能会发生没有人通过考核的情形。

如有四个评审员喜好如下表时，则不论参赛者采取什么样的做法，都不可能通过所有评审的考核：

```
评审一 评审二 评审三 评审四
满式羊肉 满式猪肉 汉式羊肉 汉式羊肉
汉式猪肉 满式羊肉 汉式猪肉 满式猪肉
```

所以大会希望有人能写一个程序来判断，所选出的 $m$ 位评审，会不会发生没有人能通过考核的窘境，以便协会组织合适的评审团。

inputFormat:
第一行包含一个数字 $K$（$1\le K \le 50$），代表测试文件包含了 $K$ 组数据。

每一组测试数据的第一行包含两个数字 $n$ 跟 $m$（$n≤100$，$m≤1000$），代表有 $n$ 种材料，$m$ 位评审员。

为方便起见，舍弃做法的中文名称而给予编号，编号分别从 $1$ 到 $n$。

接下来的 $m$ 行，每行都代表对应的评审员所拥有的两个喜好，每个喜好由一个英文字母跟一个数字代表，如 $m1$ 代表这个评审喜欢第 $1$ 个材料透过满式料理做出来的菜，而 $h2$ 代表这个评审员喜欢第 $2$ 个材料透过汉式料理做出来的菜。

outputFormat: 每组测试数据输出一行，如果不会发生没有人能通过考核的窘境，输出 ```GOOD```；否则输出 ```BAD```（均为大写字母）。


title: [WC2015] 混淆与破解

background: 本题暂时无 spj。

description:
小强和阿米巴是好朋友。

阿米巴研发出了一套相当高端的图片识别系统，并把它写成了一个手机app。这个识别系统具备特殊的识别能力，比如说，它能够识别一张图片里是否有萌萌的小狗。

这个app由两个模块组成，特征提取模块和分类模块。每当小强拍摄一张图片，特征提取模块就从中提取出一个长度为 $n$ 的 01 串并存储起来。当小强希望进行识别的时候，分类模块就会根据提取出的 01 串进行分类（即，输出一个 $0$ 或者 $1$ 的答案）。

为了保护分类算法，阿米巴的这个 app 是经过加密处理的。经过对阿米巴的死缠烂打，小强弄明白了这个分类算法的工作原理。

分类模块会从输入的这个 $n$ 位 01 串中恢复出 $m$ 位的“有效信息”。每个“有效信息” 都是经过某些输入变量的异或。之后，分类模块会利用这些 “有效信息” 进行运算来得到真正的结果。为了进一步加密，阿米巴还会加入 “噪声”。所谓 “噪声”，是指这个分类模块会故意按一定的比例将结果反转。小强拿到的可能是经过了反转的结果。

举个例子，分类模块的算法步骤可能是这样的：

```cpp
function f(x[]):
    z[0] = x[0] xor x[4] xor x[7]
    z[1] = x[12] xor x[2]
    z[2] = x[0] xor x[1] xor x[2] xor x[3]
    result = h(z[])
    return result xor g(x[])
```
其中 x[] 是一个 01 串，x[i] 表示其中的第 $i$ 位，即一个 $0$ 或 $1$ 的函数。

g(x[]) 是某个在大多数情况下返回 $0$，偶尔返回 $1$ 的函数。$h$ 是某个关于 z[] 的函数，其返回值为 $0$ 或 $1$。

z[0], z[1], z[2] 就是 “有效信息”。

为了让小强无法从app中看出算法，这个算法被进行了混淆。为了方便起见，我们把混淆之后的算法叫做“混淆版算法”。混淆版算法的代码共有 $Q$ 行，它的每一行都是这个样子：

```cpp
y[u] = (not (y[v] and y[s])) xor y[d] xor y[e]
```
其中 y[] 是一个长度为 $L$ 的 01 数组；xor 表示异或，and 表示与，not 表示非。$u, v, s, d, e$ 是这一行的参数。初始的时候，y[0]～y[n - 1] 里面放置了 x[0]～x[n - 1] 这 $n$ 个输入位，其他地方都是 $0$。执行完这 $Q$ 行代码之后，y[0] 这个位就是输出。

对于阿米巴的这种以损失性能为代价进行加密的行径，小强感到很愤怒。于是，小强打算从混淆版算法中破解出阿米巴的分类算法。为了方便起见，我们把破解得到的算法叫做“破解版算法”。小强希望你能够帮他破解出：

如何提取有效信息。这个可以表述为 $m$ 个 $\{0, 1, \dots, n - 1\}$ 的子集，每个子集对应了一个有效信息是从哪几个输入位异或得到的；

把这 $m$ 位有效信息映射到分类结果上的函数 $h$。该函数用一个长度为 $2^m$，每一位均为 $0$ 或 $1$ 的查找表表示；这 $2^m$ 位分别对应了 $m$ 位有效信息每一种可能的情况。

当然，这种破解算法是不唯一的，即，可能会有多种有效信息提取方法和查找表的组合。你只需要给出其中的一种即可。

阿米巴保证，引入的噪声比例不超过 $p$。即，你需要求出的破解版算法，和混淆版算法至少在 $2^n(1 - p)$ 个不同输入上得到的结果是一样的；并且阿米巴保证这样的算法是存在的。

同时，阿米巴也保证，这 $m$ 个有效信息都是必须的，即，$h$ 无法化简为少于 $m$ 个输入的函数。

inputFormat:
第一行包含 $4$ 个整数 $n, m, L, Q$。

接下来 $Q$ 行，每行包含 $5$ 个整数 $u, v, s, d, e$，表示每行的参数。

outputFormat:
先输出 $m$ 行，每行包含 $1$ 个 $n$ 位 01 串，表示每个有效信息是由哪些输入位异或得到的。其中 $1$ 表示包含该输入位，$0$ 表示不包含。

接下来输出一行一个长度为 $2^m$ 的 01 串，表示 $h$ 函数的查找表。查找表中的项按字典序进行排列。即，先排第一个有效信息是 $0$ 的，再排第一个有效信息是 $1$ 的。排第一个有效信息是 $0$ 的项的时候，先排第二个有效信息是 $0$ 的，再排第二个有效信息是 $1$ 的，以此类推。

hint:
【样例解释】

样例输入等价于如下代码

```cpp
y[] = 0000
input x[0..n-1]
y[0..n-1] = x[0..n-1]
y[0] = (not (y[1] and y[2])) xor y[2] xor y[2]
output y[0]
```
其中 x[0..n-1] 表示 01 串 $x$ 的第 $0$ 位到第 $n - 1$ 位。

在这段代码中，每一种输入对应的输出如下：

```cpp
input    000    001    010    011    100    101    110    111
output    1    1    1    0    1    1    1    0
```
样例输出是一种破解方案，等价于如下代码：

```cpp
input x[0..n-1]
z[0] = x[2]
z[1] = x[1]
output h(z[])
```
$h$ 函数的输入和输出有如下对应关系：

```cpp
z[]        00    01    10    11
h(z[])    1    1    1    0
```
可以发现，对于每一种输入，破解版算法和混淆版算法的输出是相同的。

【限制与约定】

对于 10% 的数据，$m = 1$，$p = 0$；

对于另外 30% 的数据，$m = 1$；

对于另外 20% 的数据，$m = 2$；

对于另外 20% 的数据，$m = 3$；

对于另外 20% 的数据，$m = 4$。

对于所有的数据，$1 \leq n \leq 64$，$1 \leq L \leq 256$，$1 \leq Q \leq 1024$，$0 \leq p \leq 0.01$，$0 \leq u, v, s, d, e < L$（注意，输入中并没有把 $p$ 的值给你）。

【提示】

使用位运算一次在多个输入上求出函数值可以极大的加速你的程序。


title: 简单题

description:
你有一个$N \times N$的棋盘，每个格子内有一个整数，初始时的时候全部为 $0$，现在需要维护两种操作：

- `1 x y A`    $1\le x,y\le N$，$A$ 是正整数。将格子`x`,`y`里的数字加上 $A$。
- `2 x1 y1 x2 y2`    $1 \le x_1 \le x_2 \le N$，$1 \le y_1\le y_2 \le N$。输出 $x_1, y_1, x_2, y_2$ 这个矩形内的数字和
- `3`    无 终止程序

inputFormat:
输入文件第一行一个正整数 $N$。

接下来每行一个操作。每条命令除第一个数字之外，均要异或上一次输出的答案 `last_ans`，初始时 `last_ans` $=0$。

outputFormat: 对于每个 $2$ 操作，输出一个对应的答案。

hint: $1\leq N\leq 5\times 10^5$，操作数不超过 $2\times 10^5$ 个，内存限制 $20\texttt{MB}$，保证答案在 int 范围内并且解码之后数据仍合法。


title: 玉蟾宫

background: 有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。

description:
这片土地被分成 $N\times M$ 个格子，每个格子里写着 'R' 或者 'F'，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。

现在 freda 要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着 'F' 并且面积最大。

但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为 $S$，它们每人给你 $S$ 两银子。

inputFormat:
第一行两个整数 $N$，$M$，表示矩形土地有 $N$ 行 $M$ 列。

接下来 $N$ 行，每行 $M$ 个用空格隔开的字符 'F' 或 'R'，描述了矩形土地。

outputFormat: 输出一个整数，表示你能得到多少银子，即 ($3\times \text{最大 'F' 矩形土地面积}$) 的值。

samples:
5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F


title: 残缺的字符串

description:
很久很久以前，在你刚刚学习字符串匹配的时候，有两个仅包含小写字母的字符串 $A$ 和 $B$，其中 $A$ 串长度为 $m$，$B$ 串长度为 $n$。可当你现在再次碰到这两个串时，这两个串已经老化了，每个串都有不同程度的残缺。

你想对这两个串重新进行匹配，其中 $A$ 为模板串，那么现在问题来了，请回答，对于 $B$ 的每一个位置 $i$，从这个位置开始连续 $m$ 个字符形成的子串是否可能与 $A$ 串完全匹配？

inputFormat:
第一行包含两个正整数 $m,n$，分别表示 $A$ 串和 $B$ 串的长度。

第二行为一个长度为 $m$ 的字符串 $A$。

第三行为一个长度为 $n$ 的字符串 $B$。

两个串均仅由小写字母和 $\texttt *$ 组成，其中 $\texttt *$ 表示相应位置已经残缺。

outputFormat:
第一行包含一个整数 $k$，表示 $B$ 串中可以完全匹配 $A$ 串的位置个数。

若 $k>0$，则第二行输出 $k$ 个正整数，从小到大依次输出每个可以匹配的开头位置（下标从 $1$ 开始）。

hint: $100\%$ 的数据满足 $1 \le m \le n \le 3 \times 10^5$。


title: [SCOI2015] 国旗计划

description:
A 国正在开展一项伟大的计划 —— 国旗计划。这项计划的内容是边防战士手举国旗环绕边境线奔袭一圈。这项计划需要多名边防战士以接力的形式共同完成，为此，国土安全局已经挑选了 $N$ 名优秀的边防战士作为这项计划的候选人。

A 国幅员辽阔，边境线上设有 $M$ 个边防站，顺时针编号 $1$ 至 $M$。每名边防战士常驻两个边防站，并且善于在这两个边防站之间长途奔袭，我们称这两个边防站之间的路程是这个边防战士的奔袭区间。$N$ 名边防战士都是精心挑选的，身体素质极佳，所以每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含。

现在，国土安全局局长希望知道，至少需要多少名边防战士，才能使得他们的奔袭区间覆盖全部的边境线，从而顺利地完成国旗计划。不仅如此，安全局局长还希望知道更详细的信息：对于每一名边防战士，在他必须参加国旗计划的前提下，至少需要多少名边防战士才能覆盖全部边境线，从而顺利地完成国旗计划。

inputFormat:
第一行，包含两个正整数 $N,M$，分别表示边防战士数量和边防站数量。

随后 $N$ 行，每行包含两个正整数。其中第 $i$ 行包含的两个正整数 $C_i$、$D_i$ 分别表示 $i$ 号边防战士常驻的两个边防站编号，$C_i$ 号边防站沿顺时针方向至 $D_i$ 号边防站力他的奔袭区间。数据保证整个边境线都是可被覆盖的。

outputFormat: 输出数据仅 $1$ 行，需要包含 $N$ 个正整数。其中，第 $j$ 个正整数表示 $j$ 号边防战士必须参加的前提下至少需要多少名边防战士才能顺利地完成国旗计划。

hint: $N\leqslant 2×10^5,M<10^9,1\leqslant C_i,D_i\leqslant M$。


title: [WC2011] 最大XOR和路径

description:
XOR（异或）是一种二元逻辑运算，其运算结果当且仅当两个输入的布尔值不相等时才为真，否则为假。 XOR 运算的真值表如下（$1$ 表示真， $0$ 表示假）：

| 输入 | 输入 | 输出 |
| :----------: | :----------: | :----------: |
| A | B | A XOR B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

而两个非负整数的 XOR 是指将它们表示成二进制数，再在对应的二进制位进行 XOR 运算。

譬如 $12$ XOR $9$ 的计算过程如下：

$$
12=(1100)_2\ \ \ 9=(1001)_2\\
\begin{matrix}
&1\ 1\ 0\ 0\\
\text{XOR}&1\ 0\ 0\ 1\\
\hline
&0\ 1\ 0\ 1\\
\end{matrix}\\
(0101)_2=5
$$

故 $12$ XOR $9 = 5$。

容易验证， XOR 运算满足交换律与结合律，故计算若干个数的 XOR 时，不同的计算顺序不会对运算结果造成影响。从而，可以定义 $K$ 个非负整数 $A_1$，$A_2$，……，$A_{K-1}$，$A_K$的 XOR 和为

$A_1$ XOR $A_2$ XOR …… XOR $A_{K-1}$ XOR $A_K$

考虑一个边权为非负整数的无向连通图，节点编号为 $1$ 到 $N$，试求出一条从 $1$ 号节点到 $N$ 号节点的路径，使得路径上经过的边的权值的 XOR 和最大。

路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 XOR 和时也要被计算相应多的次数，具体见样例。

inputFormat:
输入文件 xor.in 的第一行包含两个整数 $N$ 和 $M$， 表示该无向图中点的数目与边的数目。

接下来 $M$ 行描述 $M$ 条边，每行三个整数 $S_i$， $T_i$ ， $D_i$， 表示 $S_i$ 与 $T_i$ 之间存在一条权值为 $D_i$ 的无向边。

图中可能有重边或自环。

outputFormat: 输出文件 xor.out 仅包含一个整数，表示最大的 XOR 和（十进制结果）。

hint:
【样例说明】

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

如图，路径$1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 4 \rightarrow 5$对应的XOR和为

$2$ XOR $1$ XOR $2$ XOR $4$ XOR $1$ XOR $1$ XOR $3 = 6$

当然，一条边数更少的路径$1 \rightarrow 3 \rightarrow 5$对应的XOR和也是$2$ XOR $4 = 6$。

【数据规模】

对于 $20 \%$ 的数据，$N \leq 100$， $M \leq 1000$，$D_i \leq 10^{4}$；

对于 $50 \%$ 的数据，$N \leq 1000$， $M \leq 10000$，$D_i \leq 10^{18}$；

对于 $70 \%$ 的数据，$N \leq 5000$， $M \leq 50000$，$D_i \leq 10^{18}$；

对于 $100 \%$ 的数据，$N \leq 50000$， $M \leq 100000$，$D_i \leq 10^{18}$。


title: [WC2009] 最短路问题

description:
【问题描述】

一个 $6 * n$ 的方格，初始每个格子有一个非负权值。有如下两种操作形式：

○改变一个格子的权值（改变以后仍然非负）；

○求两个格子之间的最短路的权值。

【注解与任务】

任意格子 $P$ 的坐标$(x_P, y_P)$满足 $1 \leq x_P \leq 6$， $1 \leq y_P \leq n$。格子 $P$ 和 $Q$ 的曼哈顿距离定义为$|x_P - x_Q| + |y_P - y_Q|$。一个有序方格序列$(p_1, p_2, ..., p_n)$，若满足任意 $p_i$ 和 $p_i + 1$ 的曼哈顿距离为 $1$，则称该序列为一条从 $p_1$ 到 $p_n$ 的路径，其权值为$d(p1) + d(p2) + $...$ + d(p_n)$，其中 $d(P)$ 表示格子 $P$ 的权值。两个格子 $P$ 和 $Q$ 之间的最短路定义为从 $P$ 到 $Q$ 权值最小的路径。

inputFormat:
第一行一个整数 $n$。接下来 $6$ 行，每行 $n$ 个整数，第 $i + 1$ 行第 $j$ 个整数表示初始格子$(i, j)$的权值。接下来是一个整数 $Q$， 后面的 $Q$ 行，每行描述一个操作。

输入的操作有以下两种形式：

操作 $1$： "$1\ x\ y\ c$"(不含双引号)。表示将格子$(x, y)$的权值改成 $c$ ($1 \leq x \leq 6$, $1 \leq y \leq n$, $0 \leq c \leq 10000$) 。

操作 $2$： "$2\ x_1\ y_1\ x_2\ y_2$"(不含双引号)。表示询问格子$(x_1, y_1)$和格子$(x_2, y_2)$之间的最短路的权值。（$1 \leq x_1, x_2 \leq 6$, $1 \leq y_1, y_2 \leq n$）

outputFormat:
对于每个操作 $2$，按照它在输入中出现的顺序，依次输出一行一个整数表示

求得的最短路权值。


title: [WC2014] 时空穿梭

description:
小X驾驶着他的飞船准备穿梭过一个 $n$ 维空间，这个空间里每个点的坐标可以用 $n$ 个实数来表示，即 $(x_1, x_2, ... , x_n)$ 。

为了穿过这个空间，小 X 需要在这个空间中选取 $c$ $(c \geq 2)$ 个点作为飞船停留的地方，而这些点需要满足以下三个条件：

$1$. 每个点的每一维坐标均为正整数，且第 $i$ 维坐标不超过 $m_i$ 。

$2$. 第 $i + 1$ $(1 \leq i < c)$ 个点的第 $j$ $(1 \leq j \leq n)$ 维坐标必须严格大于第 $i$ 个点的第 $j$ 维坐标。

$3$. 存在一条直线经过所选的所有点。在这个 $n$ 维空间里，一条直线可以用 $2n$个实数 $p_1$, $p_2$, … , $p_n$, $v_1$, $v_2$, … , $v_n$ 表示。 直线经过点 $(x_1, x_2, ... , x_n)$ ，当且仅当存在实数 $t$，使得对 $i = 1$ … $n$ 均满足 $x_i$ = $p_i + tv_i$。

小 X 还没有确定他的最终方案，请你帮他计算一下一共有多少种不同的方案满足他的要求。由于答案可能会很大，你只需要输出答案 mod $10 007$ 后的值。

inputFormat:
输入文件 space.in 的第一行包含一个正整数 $T$ ，表示有 $T$ 组数据需要求解。

每组数据包含两行，第一行包含两个正整数 $n$, $c$ $(c \geq 2)$ ，分别表示空间的维数和需要选择的暂停点个数。

第二行包含 $n$ 个正整数，依次表示 $m_1$, $m_2$, … , $m_n$。

outputFormat:
输出文件 space.out 包含 $T$ 行，每行包含一个非负整数，依次对应每组数据

的答案。


title: [SCOI2006] 整数划分

description:
从文件中读入一个正整数 $n$（$10 \le n \le 31000$）。要求将 $n$ 写成若干个正整数之和，并且使这些正整数的乘积最大。

例如，$n=13$，则当 $n$ 表示为 $4+3+3+3$（或 $2+2+3+3+3$）时，乘积 $=108$ 为最大。

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

outputFormat:
第 $1$ 行输出一个整数，为最大乘积的位数。

第 $2$ 行输出最大乘积的前 $100$ 位，如果不足 $100$ 位，则按实际位数输出最大乘积。

hint:
### 数据范围及约定

对于全部数据，$10 \le n \le 31000$，同时保证最大乘积的位数不超过 $5000$ 位。


title: [SCOI2009] 粉刷匠

description:
windy 有 $N$ 条木板需要被粉刷。 每条木板被分为 $M$ 个格子。 每个格子要被刷成红色或蓝色。

windy 每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。

如果 windy 只能粉刷 $T$ 次，他最多能正确粉刷多少格子？

一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

inputFormat:
第一行包含三个整数，$N,M,T$。

接下来有 $N$ 行，每行一个长度为 $M$ 的字符串，``0`` 表示红色，`1` 表示蓝色。

outputFormat: 包含一个整数，最多能正确粉刷的格子数。


title: [SCOI2009] 迷路

background: windy 在有向图中迷路了。

description:
该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy 从节点 $1$ 出发，他必须恰好在 $t$ 时刻到达节点 $n$。

现在给出该有向图，你能告诉 windy 总共有多少种不同的路径吗？

答案对 $2009$ 取模。

注意：windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

inputFormat:
第一行包含两个整数，分别代表 $n$ 和 $t$。

第 $2$ 到第 $(n + 1)$ 行，每行一个长度为 $n$ 的字符串，第 $(i + 1)$ 行的第 $j$ 个字符 $c_{i, j}$ 是一个数字字符，若为 $0$，则代表节点 $i$ 到节点 $j$ 无边，否则代表节点 $i$ 到节点 $j$ 的边的长度为 $c_{i, j}$。

outputFormat: 输出一行一个整数代表答案对 $2009$ 取模的结果。

hint:
#### 样例输入输出 1 解释

路径为 $1 \to 1 \to 2$。

#### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $n \leq 5$，$t \leq 30$。
- 对于 $100\%$ 的数据，保证 $2 \leq n \leq 10$，$1 \leq t \leq 10^9$。


title: [SCOI2009] 生日快乐

description:
windy 的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为 $X$ 和 $Y$ 的矩形蛋糕。

现在包括 windy，一共有 $N$ 个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。

windy 主刀，每一切只能平行于一块蛋糕的一边（任意一边），并且必须把这块蛋糕切成两块。

这样，要切成 $N$ 块蛋糕，windy 必须切 $N-1$ 次。

为了使得每块蛋糕看起来漂亮，我们要求 $N$ 块蛋糕的长边与短边的比值的最大值最小。

你能帮助 windy 求出这个比值么？

inputFormat: 一行三个整数 $X,Y,N$。

outputFormat: 一行一个浮点数，保留 $6$ 位小数。


title: [SCOI2009] 游戏

description:
windy 学会了一种游戏。

对于 $1$ 到 $N$ 这 $N$ 个数字，都有唯一且不同的 $1$ 到 $N$ 的数字与之对应。

最开始 windy 把数字按顺序 $1,2,3,\cdots,N$ 写一排在纸上。

然后再在这一排下面写上它们对应的数字。

然后又在新的一排下面写上它们对应的数字。

如此反复，直到序列再次变为 $1,2,3,\cdots,N$。

如：$1\ 2\ 3\ 4\ 5\ 6$

对应的关系为：$1\to 2$，$2\to 3$，$3\to 1$，$4\to 5$，$5\to 4$，$6\to 6$。

windy 的操作如下：

`1 2 3 4 5 6`

`2 3 1 5 4 6`

`3 1 2 4 5 6`

`1 2 3 5 4 6`

`2 3 1 4 5 6`

`3 1 2 5 4 6`

`1 2 3 4 5 6`

这时，我们就有若干排 $1$ 到 $N$ 的排列，上例中有 $7$ 排。

现在 windy 想知道，对于所有可能的对应关系，有多少种可能的排数。

inputFormat: 一个整数，N。

outputFormat: 一个整数，可能的排数。


title: [SCOI2009] 最长距离

description: windy 有一块矩形土地，被分为 $N\times M$ 块 $1\times 1$ 的小格子。 有的格子含有障碍物。 如果从格子 A 可以走到格子 B，那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子 A 不可以走到格子 B，就没有距离。如果格子 X 和格子 Y 有公共边，并且 X 和 Y 均不含有障碍物，就可以从 X 走到 Y。 如果 windy 可以移走 $T$ 块障碍物，求所有格子间的最大距离。保证移走 $T$ 块障碍物以后，至少有一个格子不含有障碍物。

inputFormat: 第一行包含三个整数，$N,M,T$。 接下来有 $N$ 行，每行一个长度为 $M$ 的字符串，`0` 表示空格子，`1` 表示该格子含有障碍物。

outputFormat: 包含一个浮点数，保留 $6$ 位小数。


title: [SCOI2007] 排列

description: 给一个数字串 $s$ 和正整数 $d$, 统计 $s$ 有多少种不同的排列能被 $d$ 整除（可以有前导 $0$）。例如 $123434$ 有 $90$ 种排列能被 $2$ 整除，其中末位为 $2$ 的有 $30$ 种，末位为 $4$ 的有  $60$ 种。

inputFormat: 输入第一行是一个整数 $T$，表示测试数据的个数，以下每行一组 $s$ 和 $d$，中间用空格隔开。$s$ 保证只包含数字 $0,1,2,3,4,5,6,7,8,9$。

outputFormat: 每个数据仅一行，表示能被 $d$ 整除的排列的个数。

hint:
$100\%$ 的数据满足：$s$ 的长度不超过 $10$，$1\le d\le 1000$，$1\le T\le 15$。

在前三个例子中，排列分别有 $1,3,3628800$ 种，它们都是 $1$ 的倍数。


title: [WC2016] 论战捆竹竿

description:
是一个美好的下午，小 W 和小 C 在竹林里切磋捆竹竿的技艺。

竹林里有无数根完全一样的短竹子，每一根竹子由 $n$ 节组成。

这些竹子比较特别，每一节都被染上了颜色。可能的颜色一共 26 种，分别用小写英文字母 $\underline{a}$ 到 $\underline{z}$ 表示。也就是说，如果把竹子的底端到顶端的颜色按顺序写出来可以排成一个由小写英文字母组成的字符串。

小 W 和小 C 都是捆竹竿的高手，他们知道怎样才能把零散的短竹子捆成一整根长竹竿。 初始时你拿着一根短竹子作为当前的竹竿。 每次你可以选择一根短竹子，短竹子底端若干节（可以是 $0$ 节）与竹竿的最上面若干节对应地一节一节捆起来，而短竹子前面剩下的节伸出去，这样就得到了一根更长的竹竿。注意，竹子的底端是靠近根部的那一端，不可以颠倒。

小 W 对竹竿的审美要求很高， 他捆竹竿时有一个癖好： 如果两根竹子的某两节被捆在了一起，那么它们的颜色必须相同。

我们假设一根短竹子从底端到顶端每节的颜色为 $\underline{aba}$。

那么两根竹子可以首尾捆在一起，可以得到一根颜色为 $\underline{abaaba}$ 的竹竿；也可以将第一根顶端的一节 $\underline{a}$ 与第二根底端的一节 $\underline{a}$ 捆在一起，得到一根颜色为$\underline{ababa}$ 的竹竿； 还可以直接将每一节都对应起来，捆成一根颜色为 $\underline{aba}$ 的竹竿。

假设我们在颜色为 $\underline{ababa}$ 的竹竿顶端再捆一根竹子，则可以捆成 $\underline{ababaaba}$，$\underline{abababa}$ 和 $\underline{ababa}$ 三种不同的情况。

但是小 C 在这个问题上有不同的看法，他认为小 W 捆不出很多种长度不同的竹竿。小 W 非常不服，于是他找到了你——现在请你求出在竹竿长度不超过 $w$ 的情况下， 小 W 可以捆出多少种长度不同的竹竿。 其中， 竹竿的长度指从底端到顶端的竹子的节的个数。

注意：如果 $w < n$，则没有合法的长度，此时答案为 $0$。

inputFormat:
输入文件 jie.in 第一行包含 $1$ 个整数 $t$，为数据组数。

每组数据的第一行包含 $2$ 个正整数 $n$ 和 $w$， 表示短竹子的长度和竹竿的长度上限。

每组数据的第二行包含一个长度为 $n$ 的字符串，该字符串仅由小写英文字母构成，表示短竹子从底端到顶端每节的颜色。

outputFormat:
输出文件为 jie.out。

输出共 $T$ 行，每行包含一个整数表示捆成竹竿的不同长度种数。

samples:
2
44 1000
baaaaaabaabbaaabbbbabbbaaabbbababaaabaaabaaa
41 1000
abaabbabaaabaabbbbbbbbbbbababbbbaaabaabbb

hint:
【样例解释$1$】

可以捆成长度不超过 $11$ 的竹竿有 $6$ 种不同的情况：

$bbab$
$bbabbab$

$bbabbbab$

$bbabbabbab$

$bbabbabbbab$

$bbabbbabbab$

后两种竹竿长度相同，因此不同长度的竹竿共有 $5$ 种。长度分别为： $4$， $7$，$8$， $10$， $11$。

【数据规模和约定】

对于所有的测试数据，保证所有的字符串均由小写字母构成。

各测试点满足以下约定：

![QQ20180128185500.png](https://www.z4a.net/images/2018/01/28/QQ20180128185500.png)


title: [WC2006] 水管局长

background: SC 省 MY 市有着庞大的地下水管网络，嘟嘟是 MY 市的水管局长（就是管水管的啦）。

description:
每天供水公司可能要将一定量的水从 $u$ 处送往 $v$ 处，嘟嘟需要为供水公司找到一条从 $u$ 至 $v$ 的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。

在处理每项送水任务之前，路径上的水管都要进行一系列的准备操作，如清洗、消毒等等。嘟嘟在控制中心一声令下，这些水管的准备操作同时开始，但由于各条管道的长度、内径不同，进行准备操作需要的时间可能不同。

供水公司总是希望嘟嘟能找到这样一条送水路径，路径上的所有管道全都准备就绪所需要的时间尽量短。嘟嘟希望你能帮助他完成这样的一个选择路径的系统，以满足供水公司的要求。另外，由于 MY 市的水管年代久远，一些水管会不时出现故障导致不能使用，你的程序必须考虑到这一点。

不妨将 MY 市的水管网络看作一幅简单无向图（即没有自环或重边）：水管是图中的边，水管的连接处为图中的结点。整张图共有 $n$ 个节点和 $m$ 条边，节点从 $1$ 至 $n$ 编号。

inputFormat:
第一行有三个整数，分别表示管道连接处（结点）的数目 $n$，目前水管（无向边）的数目 $m$，以及你的程序需要处理的任务数目（包括寻找一条满足要求的路径和接受某条水管坏掉的事实）$q$。

以下 $m$ 行，每行三个整数 $u, v, t$，表示存在一条连接 $(u, v)$ 的水管，准备时间为 $t$。

以下 $q$ 行，每行三个整数 $k, u, v$，描述一项任务。其中 $k$ 表示任务类型：

- 若 $k = 1$，则表示你需要为供水公司寻找一条满足要求的从 $u$ 到 $v$ 的水管路径，满足准备时间最短；
- 若 $k = 2$，则表示直接连接 $u$ 和 $v$ 的水管宣布报废。

outputFormat: 对于每个 $k = 1$ 的任务，输出一行一个整数表示答案。

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

对于全部的测试点，保证：

- $1 \leq n \leq 10^3$，$1 \leq m, q \leq 10^5$。
- $1 \leq k \leq 2$，$1 \leq u, v \leq n$，$1 \leq t \leq 10^9$。
- 给出的图无重边无自环，保证在宣布一条水管报废之前，该水管一定存在于图上且没有报废，
- 宣布报废的水管不超过 $5 \times 10^3$ 条，且在任意时刻，图一定是联通的。


title: [SCOI2007] 组队

description:
NBA每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为minV，身高最矮的球员高度为minH，那么这支球队的所有队员都应该满足: A × ( height – minH ) + B × ( speed – minV ) <= C 其中A和B，C为给定的经验值。这个式子很容易理解，如果一个球队的球员速度和身高差距太大，会造成配合的不协调。

请问作为球队管理层的你，在N名选秀球员中，最多能有多少名符合条件的候选球员。

inputFormat: 第一行四个数N、A、B、C 下接N行每行两个数描述一个球员的height和speed

outputFormat: 最多候选球员数目。

hint: 数据范围： N <= 5000 ,height和speed不大于10000。A、B、C在长整型以内。


title: [SCOI2007] 最大土地面积

description: 在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。

inputFormat: 第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。

outputFormat: 最大的多边形面积，答案精确到小数点后3位。


title: [CQOI2007] 涂色

description:
假设你有一条长度为 $5$ 的木板，初始时没有涂过任何颜色。你希望把它的 $5$ 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 $5$ 的字符串表示这个目标：$\texttt{RGBGR}$。

每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 $\texttt{RRRRR}$，第二次涂成 $\texttt{RGGGR}$，第三次涂成 $\texttt{RGBGR}$，达到目标。

用尽量少的涂色次数达到目标。

inputFormat: 输入仅一行，包含一个长度为 $n$ 的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。

outputFormat: 仅一行，包含一个数，即最少的涂色次数。


title: [CTSC2010] 星际旅行

description: 公元$3000$年，地球联盟已经攻占了银河系内的$N$个星球，出于资金的考虑，政府仅仅在星球间建立了$N-1$条双向时空隧道保证任意两个星球之间互相可达。出于管理上的考虑，第$i$个星球的行政长官要求每个公民在一年内不得从该星球利用时空隧道次数超过$H_i$次（这一统计是基于离开次数统计的，如果你已经使用从该星球离开过$H_i$次，那么这一年内你就不能再使用时空隧道离开这个星球了）。Louis Paosen是一个星际旅行家，他希望能使用尽量多次的时空隧道，但又不希望最终被迫定居的星球条件太过恶劣。所以他希望能知道对于每个星球$i$，若从$0$号星球出发，最终以$i$号星球为终点，这样的星际旅行途中最多可以使用多少次时空隧道。

inputFormat: 输入文件galaxy.in的第一行包含一个整数$N$。接下来的一行包含$N$个整数$H_i$，分别表示每个星球的离开次数限制。接下来$N-1$行每行两个整数，表示这两个星球之间有时空隧道连接。星球的编号从$0$开始，Louis Paosen一开始在$0$号星球。

outputFormat: 输出文件为galaxy.out。文件包含$N$行，每行一个整数，表示如果最终旅行结束在这个星球，最多可以使用时空隧道的次数。

hint:
$40 \%$的数据$N \leq 500$

$100 \%$的数据中$N \leq 50000$。

所有星球的离开次数限制满足$1 \leq H_i \leq 40000$，且每个星球的$H_i$大于等于与该星球直接相连的星球数（即度数）。