title: [Cnoi2020] 高维

background: > 本质上，幻想乡是高维的。

description:
Cirno 捕获了一只 $n$ 维蚂蚁，它想从 $S(0,0,...,0)$ 爬到 $T(1,1,...,1)$ 。

被封闭在这个 $1\times1\times...\times1$ 的方格中，蚂蚁每一步只能爬向一个坐标相邻的点。

现在 Cirno 想考考你蚂蚁最多能找到多少条从 $S$ 到 $T$ 的路径两两没有交点( 除 $S$, $T$ )。

并要求你构造这样一组路径。

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

outputFormat:
第一行，一个整数 $t$，表示最多的路径数。

以下 $t$ 行，每行一条合法路径。

合法路径表示方式 :

> $S$ [空格] $P_1$ [空格] $P_2$ [空格] ... [空格] $T$

其中 $P_i$ 是一个二进制压缩的 $01$ 串 表示一个 $n$ 维坐标。

**请不要输出多余的空格**。

hint:
**「本题使用 Special Judge」**

### Sample1解释

第 $1$ 条路径：$(0,0) \rightarrow (0,1) \rightarrow (1,1)$

第 $2$ 条路径：$(0,0) \rightarrow (1,0) \rightarrow (1,1)$

二者除了 $S$ 与 $T$ 无交点。

### 数据范围约定

**「本题不采用捆绑测试，数据有梯度」**

对于 100% 的数据 $3 \le n \le 60$。

### 后置代码片段

 - 二进制压位函数

```cpp
/**
 * For only cpp11, cpp14, cpp17, cpp20.
 *
 * @param: __s : The binary high-dimension position inputed.
 * @return: Standard output format( U64 ).
**/

unsigned long long zip( std::string __s )
  { unsigned long long __r = 0;
    for( auto __c : __s )
      { ( __r <<= 1ull ) |= ( __c - 0x30 ); }
    return __r; }

```
 - SPJ代码
```cpp
//SPJ
#include "testlib.h"
#include<bits/stdc++.h>

typedef unsigned long long ULL;
typedef std::vector<std::string> SEQ;
typedef std::string STR;

SEQ split( std::string _par, char _sgn )
  { SEQ _rat = SEQ();
	STR _rem = STR();

    for( char __c : _par )
      { if( __c = _sgn ) _rat.push_back( _rem ), _rem = "";
	    else _rem += __c; }

	if( _rem != "" ) _rat.push_back( _rem );

	return _rat; }

ULL to_ULL( std::string _str )
  { ULL _rat = 0;

	for( char __c : _str )
	  { ( _rat *= 10ull ) += (ULL)( __c - '0' ); }

	return _rat; }

bool isPw2( ULL x )
  { return !( x & (x - 1ull) ); }

std::map<ULL, bool> MP;

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);

	ULL n = inf.readLong();
	ULL S = 0, T = (1ull << n) - 1ull;
	ULL N = ouf.readLong();

	if( N != n ) quitf( _wa, "Count paths wrongly." );

	ouf.readEoln();

    while( n -- ) {
    	std::string path = ouf.readLine();

    	ULL _lst = 0;

    	for( auto N : split( path, " " ) )
    	  { ULL _now = to_ULL( N );
    		if( _now != S and _now != T and MP[_now] )
			  { quitf( _wa, "Paths crossing" ); }
    	    if( !isPw2( _now ^ _lst ) )
			  { quitf( _wa, "Wrong path format" ); }
    	    _lst = _now; MP[_now] = true; }

    	if( _lst != T ) quitf( _wa, "Wrong path ending" );
	}

	quitf( _ok, "Accepted" );

    return 0;
}
```


title: [Cnoi2020] 四角链

type: P

background:
> 四角链图是一种常见的四角网络，属于仙人掌图，通常不会出现在重掺杂单晶尾部的横截面上，呈现的一组其外围是杂质富集条纹的封闭的不是四角环状网络。但因为其复杂的特点，所以常出现在描述社群联系的情景中，例如一些众所周知不可描述的......

作为一个聪明活泼的女孩子，Cirno 厌倦了教科书式冗长乏味的概念，直接给出了四角链图的图示。

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

description:
事实上四角链可以抽象为 $1\times (n - 1)$ 网格，每个格子被分别编号为 $1$, $2$, .... , $n-1$。

每个格子可以有两种选择 :
 - 不填数
 - 填入一个小于或等于自己编号的正整数

当一种填数方案 **不存在两个格子填的数相同** 时，Cirno 称之为合法方案。

Cirno 想知道有且仅有 $k$ 个格子填入了数字的合法方案数对 $998244353$ 取模后的结果。

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

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

hint:
### 数据范围约定

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

 - Subtask1( $20\%$ ) : $n,k \le 10$
 - Subtask2( $20\%$ ) : $n,k \le 1000$
 - Subtask3( $60\%$ ) : 无特殊限制

对于 $100\%$ 的数据 : $0 \le k < n \le 10^6$。

### 说明

 - 以下文献没有阅读必要。

### Reference

 - [1] 中国知网 - 四角链的一些极值问题 - 厦门大学 - 曾艳秋
http://kns.cnki.net/KCMS/detail/detail.aspx?dbcode=CMFD&filename=2007056552.nh
 - [2] 中国知网 - 关于四角仙人掌图的海明优美性 - 吉林工程技术师范学院教育技术中心;海南大学理工学院 - 李秀芬;潘伟
http://www.cnki.com.cn/Article/CJFDTotal-CCYD200806009.htm


title: [Cnoi2020] 领域极限

description:
Cirno 有 $n$ 个整数，分别记作 $a_1,a_2,a_3,...,a_n$。

对于每一个数 $a_i$ 都有一个限制二元组 $(l_i,r_i)$。

Cirno 想知道：

$$\min_{\forall t, a_t \in [l_t,r_t]}\big\{\sum_{i=1}^{n}\sum_{j=1}^{n}\left| a_i - a_j \right|\big\}$$

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

以下 $n$ 行，每行一个限制二元组 $(l_i,r_i)$。

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


title: 【模板】回滚莫队&不删除莫队

background: 这是一道模板题。

description:
给定一个序列，多次询问一段区间 $[l,r]$，求区间中**相同的数的最远间隔距离**。

序列中两个元素的**间隔距离**指的是**两个元素下标差的绝对值**。

inputFormat:
第一行一个整数 $n$，表示序列长度。

第二行 $n$ 个整数，描述这个序列。

第三行一个整数 $m$，表示询问个数。

之后 $m$ 行，每行两个整数 $l,r$ 表示询问区间。

outputFormat: 共 $m$ 行，每行一个整数表示答案。如果区间内不存在两个数相同，则输出 $0$。

hint:
记 $a_i$ 表示序列元素。

对于 $40\%$ 的数据，满足 $1\leq a_i \leq 400$，$1\leq n,m\leq 60000$。

对于 $100\%$ 的数据，满足 $1\leq n,m\leq 2\cdot 10^5$，$1\leq a_i\leq 2\cdot 10^9$。


title: [Ynoi2010] Brodal queue

background:
题目背景和题意无关，可以跳过

## 1.前言：
Brodal queue 在 1996 年由 Brodal 提出，是第一个满足每个操作都 worst case 而且达到了基于比较的堆的下界的数据结构

这里给出的 Brodal queue 是一个小根堆

该数据结构的一些特性：

1. 维护了两棵树。

2. Brodal queue 是一种 violation heap，即允许存在一些节点不满足堆性质。

3. 实现真的很复杂，常数真的很大。

## 2.一些记号：
Brodal queue 维护了两棵树 $T1$ , $T2$，他们的根是 $t1$ 和 $t2$。

定义：

$p(x)$：$x$ 的父亲节点，默认 $x \neq t1$ 且 $x \neq t2$。

$rank(x)$：和 $log( subtree\;size )$ 相关的一个权值。

$n(x,i)$：$x$ 的孩子中满足其 $rank$ 为 $i$ 的个数。

$w(x,i)$：$W(x)$ 中 $rank$ 为 $i$ 的元素个数。

$V$ 和 $W$ 列表：维护所有违反堆性质的节点。

## 3.概述：
每个曾经作为 $T1$ 的根的点都维护 $V$ 和 $W$，我们用 $V(x)$ 表示 $x$ 节点的 $V$ 集合，$W(x)$ 表示 $x$ 节点的 $W$ 集合。

$V$ 维护的是 $rank \ge rank(t1)$ 的节点，$W$ 维护的是 $rank<rank(t1)$ 的节点，这个是对插入当时的情况成立的，也就是说在经过结构修改操作之后不一定还满足这个性质。

$V$ 是只加不删的， $W$ 是需要维护平衡的，所以只需要保证 $t1$ 的 $W$ 中的点的 $rank<rank(t1)$。

有以下的一些性质：

$rank$ 的性质：

S1. 叶子节点的 $rank$ 为 $0$。

S2. $rank(x) < rank( p(x) )$。

S3. 如果 $rank(x) > 0$，则 $n(x,rank(x)-1) \ge 2$。

S4. $n(x,i)$ 只可能为 ${0,2,3,4,5,6,7}$ 中的元素。

S5. 当 $T2 \neq null$ 时 $rank(t1) \leq rank(t2)$。

解释：

S1. 边界定义。

S2. $rank$ 构成大根堆。

S3. 一个点有至少两个孩子的 $rank$ 是其 $rank-1$，所以 $x$ 的子树大小关于 $x$ 的 $rank$ 至少是指数级的，所以 $rank$ 最多是 $O( \log n )$ 的。

S4. $n(x,i)$ 有 $O(1)$ 上界，非 $1$ ，而总共有 $O( \log n )$ 种 $rank$，所以每个节点的度数都是 $O(\log n )$ 的。

S5. 要么 $T1$ 比 $T2$ 小，要么 $T2$ 为空。

$V$ 和 $W$ 列表的性质：

O1. $t1$ 是所有元素中的最小元。

O2. 如果 $y$ 在 $V(x)$ 或者 $W(x)$ 中，则 $x \leq y$，即这个元素在被插入列表时是违背了堆性质的。

O3. 如果 $y<p(y)$ ，那么存在一个 $x$ 使得 $x \neq y$，$y$ 属于 $V(x)$ 或 $W(x)$，即所有违背堆性质的节点都在某个节点的 $V$ 或 $W$ 列表中。

O4. 对于所有 $x$，有 $w(x,i) \leq 6$。

O5. 记 $V(x) = (y_|V(x)|,...,y_2,y_1)$ , 则 $rank(y_i) \ge floor((i-1)/α)$，$α$ 是一个常数。

解释：

O1. 我们要 $O(1)$ 求出最小值，所以规定了最小元是 $t1$。

O2. $x$ 被插入的时候是被插到 $V(t1)$ 或者 $W(t1)$ 中。

O3. 违反堆性质的点一定在另一个点的 $V$ 或者 $W$ 集合中。

O4. $w(x,i)$ 有常数上界，所以 $V$ 和 $W$ 列表的大小是 $O( \log n )$ 的。

O5. $V$ 列表中的 $rank$ 有一个阶梯的下界。

对于 $t1$，$t2$ 的额外性质：

R1. 对 $i = 0 \sim rank(tj) - 1$，有 $n(tj,i) \ne 0$。

R2. $|V(t1)| \leq α \times rank(t1)$ ，和前面提到的是同一个 $α$。

R3. 如果 $y$ 属于 $W(t1)$ 则 $rank(y)<rank(t1)$。

解释：

R1. 对于 $t1$，$t2$，每个 $rank$ 的孩子至少有 $2$ 个。

R2. $V(t1)$ 的大小 $|V(t1)|$ 有 $α \times rank(t1)$ 的上界。

R3. 属于 $W(t1)$ 的点比 $t1$ 小。

R2+O5可以推出如果 $t1$ 的 $rank$ 增大 $1$ ，我们就可以增加 $α$ 个大的违反堆性质的节点，把他们加入 $V(t1)$，并且不违反 $O5$。

每次 DECREASEKEY 时 ，我们直接加一个新的违反堆性质的点到 $V(t1)$ 或者$W(t1)$。

为了避免有太多的违反堆性质的节点，我们递增地做两种不同的变换，主要为了维护 R2 和 O4 性质。

第一种：把 $t2$ 的儿子移动进入 $T1$ ，变成 $t1$ 的孩子，使得 $rank(t1)$ 变大。

第二种：通过把 $2$ 个 $rank$ 为 $k$ 的违反堆性质的节点换成了 $\leq 1$个$rank$ 为 $k+1$ 的违反堆性质的节点，从而减少 $W(t1)$ 的大小。

Note：我们这里用到了很多可变长数组，默认可变长数组是严格 $O(1)$ 的，这个是平凡的所以不详细讲怎么实现了。

这里给出了一个作者称为 guide 的数据结构的实现。

## 4.Guide Data Structure：

用途：维护 $R1$，$O4$ 性质，即对 $n(t1,i),n(t2,i),w(t1,i)$ 的上界进行维护，大概是一个维护 $O(1)$ 进位的东西。

抽象出这部分要维护的东西，也就是我们这里讲的 guide 数据结构是要维护什么：

维护：一个长为 $k$ 的 int 数组，$x_k,x_{k-1},...x_1$ （这里我们从右往左写序列）。

需要满足：$max(x_i) \leq T$ , $T$ 是预设的一个阈值常数。

我们只能在这个数组上实现 REDUCE(i) 的操作，即 $x_i$ 至少减少 $2$，$x_{i+1}$ 至多增加 $1$（实际上这里我们 $x_i$ 只能减少 $2$ 或者 $3$，$x_{i+1}$ 只能增加 $0$ 或者 $1$）。

每次可能发生对一个任意位置 $i$ 的 $x_i$ 的 $+1$ 或者 $-1$ 操作，每次操作之后我们被允许通过 $O(1)$ 次 REDUCE 操作，使得我们需要维护的数组仍旧满足性质。

guide 干的事情就是 guide（向导） ，也就是说告诉我们要做什么样的 REDUCE 操作使得这个数组仍旧满足性质。

定义 $x'$ 是 $[T-2,T]$ ，当 $x_i$ 碰到进入 $x'$ 的范围之前我们不考虑对其进行调整。

不妨设 $T=2$，我们对 $T=2$ 维护这个 guide 即可。

把原序列分成一些块，考虑形如 $2$ $1*$ $0$ 这样的连续段，不在段内的元素只可能是单独的 $0$ 或 $1$。

对每个块我们新建一个节点，然后段内的每个元素都指向这个节点。

每个节点上记录块的开头位置。

不在块内的节点直接指向一个 null。

这里我们多个点共用一个 null ，存在多个 null。

有两个重要的性质：

1. 给一个位置 $x$ ，我们可以最坏复杂度 $O(1)$ 找到 $x$ 所属于的块内最左边的元素，
并且——

2. 我们可以最坏复杂度 $O(1)$ 销毁掉一个给定的块，直接把那个存有值的点改成 null 即可。

这里写一下变换是如何实现的，由于是按照自己的理解写的，所以可能和原论文
有出入。

注意到我们可以 $O(1)$ 拆掉一个块。

前驱不在块内：

```
case1：

0 0

0 1

trivial
```
```
case2：

0 1

0 2

1 1

trivial

```
```
case3:

0 [2 1* 0]

0 [3 1* 0]

1 [1 1* 0]

拆掉这个块

1 1 1* 0
```
```
case4:

1 0

1 1

trivial
```
```
case5:

1 1

1 2

[2 0]

trivial
```
```
case6:

1 [2 1* 0]

1 [3 1* 0]

2 [1 1* 0]

[2 1 1* 0]
```
前驱是块尾：
```
case7:

[2 1* 0] 0

[2 1* 0] 1

trivial
```
```
case8:

[2 1* 0] 1

[2 1* 0] 2

[2 1* 1] 0

[2 1* 1 0]
```
```
case9:

[2 1* 0] [2 1* 0]

[2 1* 0] [3 1* 0]

[2 1* 1] [1 1* 0]

拆后面的块

[2 1* 1] 1 1* 0

拆前面的块

2 1* 1 1 1* 0

递归成块外的1加1的情况case 2,5,8
```
前驱在块内：
```
case10:

[2 1* 0]

[2 1* 1]

拆块

2 1* 1

递归成块外的1加1的情况case 2,5,8
```
```
case11:

[2 1* 1 1* 0]

[2 1* 2 1* 0]

拆部分块，通过把指针指到第二个2的位置

2 1* [2 1* 0]

递归成块外的1加1的情况case 2,5,8
```

注意到这里 $2$ 是单调向右走的，除了每次操作可能可以往左边走一格，所以把一个块端点往右移动一段，或者向左移动 $O(1)$ 个位置是可行的。

加个内存池，我们需要的空间不超过 $O(k)$。

（*可能可以四毛子优化一下？）

## 5.link 和 delink

这个是两个基本操作，用于调节 Brodal queue。

link：

假设我们有 $3$ 个节点 $x_1,x_2,x_3$ ，这三个节点不是根，且有相同的 $rank$。

经过 $O(1)$ 次比较之后，不妨我们设 $x_1$ 是这三个中最小的。

然后我们可以把 $x_2$，$x_3$ 变成 $x_1$ 的最左儿子（因为是链表，只能在头插入），并且 $x_1$ 的 $rank$ 自增 $1$。

然后 $x_2$ 和 $x_3$ 都不是违反堆性质的节点，并且 $x_1$ 仍然满足所有 S1-S5 和 O1-O5 的性质。

delink：

对一个点 $x$ ，如果 $n(x,rank(x)-1)$ 是 $2$ 或者 $3$，那么把 $x$ 的 $rank$ 为 $rank(x)-1$ 的孩子和父亲的边断开，把它"切出来"，然后 $rank(x)$ 变成剩余孩子中的 $max(rank)+1$，这里切出来之后怎么办需要特殊说明。

如果 $n(x,rank(x)-1) \ge 4$，那么把 $2$ 个 $rank$ 为 $rank(x)-1$ 的孩子切出来。

delink 一个根节点的 $rank$ 为 $k$ 的树总是会得到 $2$ 或者 $3$ 个根节点的$rank$ 为 $k-1$ 的树，和一个额外的根节点的 $rank \leq k$ 的树（这个树根节点的 $rank$ 可以是 $[0,k]$ 的任意数）。

考虑如何维护 $t1$ 的孩子，使其满足R1（ $t1$ 对于 $[0,rank(t1)-1]$ 中每个 $rank$ 有$[2,7]$个孩子）。

对 $[0,rank(t1)-3]$ 中每个 $rank$ 的孩子个数，使用两个guide，一个处理个数在 $[2,4]$ 的孩子保证其个数 $ \ge 2$，一个处理个数在 $[5,7]$ 的孩子保证其个数 $\leq 7$。

对于 $rank$ 为 $rank(t1)-1$ 和 $rank(t1)-2$ 的孩子需要特判处理。

对 $t1$ 的孩子用两个 guide 来维护,设其为 guide1 和 guide2。

guide1 维护的是 $rank$ 在 $[T-2,T]$ 中的孩子，guide2 维护的是 $rank$ 在$[2,4]$ 中的孩子，这里我们令 $T=9$，是一个常数。

我们用 guide 中的元素 $a_k$ 代指这个 guide 里面 $rank$ 为 $k$ 的节点个数。

link 操作会让 guide1 里面的一个元素 $a_k$ 减少 $3$ , 另一个元素 $a_{k+1}$ 增加 $1$ ，注意到这里我们维护的是一个上界的形式，所以减少 $3$ 和减少 $2$是类似的。

delink 操作会让 guide2 里面的一个元素 $a_k$ 减少 $1$, $a_{k-1}$ 增加 $2$ 或 $3$ , 还会多出一个 $rank$ 在 $[0,k]$ 中的元素，这里维护的是下界形式，所以只用考虑 $+2$。

注：这里其实 $-3$ 会比 $-2$ 容易破坏下界，$+3$ 会比 $+2$容易破坏上界，把 $T$ 改成 $10$ ，或者加一些特判之后这个问题可以被解决，所以不专门讨论这两种情况了。

注：这里原论文给的界是 $T=7$ ，但是我们不知道如何达成，所以在这里讲$T=9$ 的情况。

$t1$ 新增孩子：

如果导致同 $rank$ 的孩子数 $=9$ ，则从处理上界的 guide 得到需要执行的 $O(1)$ 次 reduce 操作（这导致了 guide 的实现的微小变化），对应于用 link 合并 $3$ 个 $rank$为 $k$ 的孩子，得到 $1$ 个 $rank$ 为 $k+1$ 的孩子。

注意此时孩子数减少 $3$ 后变成 $6 > 4$ ，不影响处理下界的 guide。

如果这导致 $rank$ 为 $rank(t1)-2$，$rank(t1)-1$ 的孩子过多，同样用 link 操作进行调整，这时就可能需要增加 $t1$ 的 $rank$ 了。

这里由于我们每次都是把"切出来"的节点变成 $t1$ 的孩子，所以不产生额外的违反堆性质的节点。

$t1$ 删除孩子：

类似于新增孩子，但此时 reduce 对应于 delink 操作（这里只考虑 $rank=k$ 的树变为 $rank=k-1$ 的 $2$ 或 $3$ 棵树），delink 产生的额外的 rank 不固定的树会在删除孩子完成之后被新增为 $t1$ 的孩子。

关于这里的常数 $T$ 的解释：

我们考虑一个 guide 中维护的元素到了和这个 guide 的界差 $1$ 的情况才需要
 REDUCE ，不然不需要。

对于 guide1，这个界限就是 $T-1$，对于 guide2，这个界限就是 $3$。

然后我们要让这次 REDUCE 之后不会导致另一个 guide 需要调整。

所以 $T-1\;-\;3 > 4$，$3 + 3 < T-2$，可以解出 $T > 8$，故取 $T=9$。

这里和原论文的 $T=7$ 不一样，但也只是常数差别，不会对复杂度和正确性产生影响，所以不仔细讨论这个了。

对于 $t2$ 的新增/删除孩子，情况和 $t1$ 类似，不同之处是 delink 产生了 $O(1)$ 个新的破坏堆性质的点，这部分的详细内容会在后面提到。

定义 $pv$ 集合为 $V$ 集合和 $W$ 集合的并集，即潜在的违反堆性质的点的集合。

设计一个变换，用于减少 $pv$：

这一段是 $W(t1)$ 的 guide 的 REDUCE 的方法，这个变换将 $pv$ 减少了至少 $1$：

假设 $x1,x2$ 是潜在的违反堆性质的点，满足 $k=rank(x1)=rank(x2)<rank(t1)$，且 $x1,x2$不是根或根的孩子。

首先检查 $x1,x2$ 是否满足堆性质，若满足则从 $V$ 或 $W$ 列表中移除，否则：

若 $x1,x2$ 不是兄弟：

不失一般性，设 $p(x1) \leq p(x2)$，交换 $x1$ 所在子树和 $x2$ 的某个$rank=k$ 的兄弟 $x3$（由 S4 性质可知这样的 $x3$ 一定存在）所在子树（此操作不会增加 $pv$，$x1$ 仍是 $pv$，$x3$ 可能从 $pv$ 变为非 $pv$ 也可能状态不变），之后可设 $y=p(x1)=p(x2)$。

若存在 $rank=k$ 的第三个兄弟，则将 $x1$ 移除并新增为 $t1$的孩子，这样 $y$ 的 $rank=k$ 的儿子减少了一个，而且至少为 $2$ 个，不违反 S4 性质。

若不存在 $rank=k$ 的第三个兄弟，则将 $x1,x2$ 移除并新增为 $t1$ 的孩子，这样 $y$ 的 $rank=k$ 的儿子个数变成 $0$ 了，不违反 S4 性质。

若 $rank(y)=k+1$ 则还需要移除 $y$，更新 $y$ 的 $rank$，并新增 $y$ 为 $t1$的孩子，$y$ 子树原先的位置被从 $t1$ 移除的一个 $rank=k+1$ 的子树代替。

（这可能增加一个违反堆性质的点（需要加入 $W(t1)$ 中），但同时 $x1,x2$
 由于父亲变成了 $t1$，所以将符合堆性质），这里还需要对 $W(t1)$ 的 guide 进行一个 $rank=k+1$ 的位置 $+1$ 的操作。

所以至少减少 $2$ 个 $pv$ 中的点，至多增加 $1$ 个点到 $pv$ 中。

（由于 S2 性质保证了等 $rank$ 替换时，被替换的点和用于替换的点没有祖先关系，因此不会成环）

避免过多的违反堆性质的点出现：

当新增一个违反堆性质的点 $x$ 时，若 $rank(x) \ge rank(t1)$ 则将其加入到 $V(t1)$ 中，否则加入到 $W(t1)$ 中。

对 $W(t1)$ 也开个 guide，里面第 $i$ 个元素就是 $w(t1,i)$。

向 $W(t1)$ 加点时，插入一个点 $k$ 时，让 guide 中的第 $k$ 个元素 $+1$，然后通过 guide 得到需要进行的 reduce(k) 操作。

在 $w(t1,k)=6$，且其中至少 $2$ 个不是 $t2$ 的孩子时，执行上述变换减少 $pv$。

若有超过 $4$ 个是 $t2$ 的孩子，则将多出的点切下并新增为 $t1$ 的孩子（这不影响 $W(t2)$ 的 guide）。

每次进行优先队列操作时：

若 $T2$ 非空，则通过将 $O(1)$ 个孩子从 $t2$ 移到 $t1$，使 $t1$ 的 $rank$ 增加至少 $1$，这使得我们可以支付 $V(t1)$ 新增的不超过 $α$ 个 $pv$。

具体地，若 $rank(t2) \leq rank(t1)+2$，则把 $t2$ 的 $rank$ 最大的孩子切下并新增为 $t1$ 的孩子，最终当 $t2$ 没有孩子的时候，把 $t2$ 新增为 $t1$ 的孩子。

若 $rank(t2)>rank(t1)+2$，则切下 $t2$ 的一个 $rank$ 为 $rank(t1)+2$ 的孩子，将其delink并新增为 $t1$ 的孩子。

若 $T2$ 为空，则 $V(t1)$ 不会有新增的 $pv$。

## 6.抽象数据结构
对于一个抽象数据结构——优先队列，我们可以使用 Brodal queue 实现，具体进行的操作为：
```
MakeQueue：T1=T2=null
```
```
FindMin(Q): return t1
```
```
Insert(Q,e): 转为Meld(Q,{T1=e,T2=null})
```

```
Meld(Q1,Q2):

不失一般性，设 $Q1.t1<Q2.t1$。

若 Q1.T1 的 rank 最大，则把其余的 $3$ 棵树新增为 Q1.t1 的孩子，Q1.T2 设为空，这个过程中不产生新的 $pv$

否则让 Q1.T2，Q2.T2 中 rank 最大的树成为新的 Q1.T2，其余的 $2$ 棵树新增为 Q1.t2 的孩子。
```

解释：如果 $min$ 所在的那个树的 $rank$ 是这四个里面最大的，那就把其他几个树都插入到 $min$ 所在的那个树的孩子里面，新的树里面 $T2$ 为空

否则 $rank$ 最大的那个树成为新的 $T2$，除了 $min$ 所在的树都插入这个的孩子里面，$min$ 所在的树成为 $T1$

```
DecreaseKey(Q,e,e'):

修改权值后检查是否违反堆性质

如果违反堆性质，则将其加入pv中，此时pv大小+1

然后按前文避免过多的违反堆性质的点出现的方法来让pv减少至少1，使得pv大
小平衡
```
```
DeleteMin(Q):

将 t2 的孩子（O(log n) 个）全部切下，新增为 t1 的孩子；将 t2 变为 t1 的孩子；

删除 t1 得到 t1 的孩子，总共有 O(log n) 个。

遍历 t1 的孩子，V(t1) 和 W(t1)，从而得到新的最小值t1'

若 t1' 不是 t1 的孩子，则与等 rank 的孩子交换，这可能产生 O(1) 个 pv。

然后将 V(t1),V(t1'),W(t1),W(t1') 合并为 W(t1')：

先将 V(t1') 置为空，然后使用变换令 w(t1',i)<=1，最后使 t1' 成为新的 t1
```

```
Delete(Q),e: 转为DecreaseKey(Q,e,-inf),DeleteMin(Q)
```

description:
给定一个长为 $n$ 的序列 $a$ ，每个位置有一种颜色，有 $m$ 次操作，支持：

`1 l r x`：区间 $[l,r]$ 的数都变成 $x$。

`2 l r`：查询有多少二元组 $(i,j)$ 满足 $l \leq i < j \leq r$ ，且 $a_i = a_j$。

本题强制在线，每次的 $l,r,x$ 需要 $\operatorname{xor}$ 上（上次答案 $\bmod 2^{32}$），也就是说使用 `unsigned int` 数据类型存储上次的答案即可，如果之前没有询问，则上次答案为 $0$。这里输出的答案不对 $\bmod 2^{32}$ 取模。

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

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

之后 $m$ 行，每行形如 `1 l r x` 或 `2 l r`，表示上述的操作。

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

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

注意：本题采用**捆绑测试**，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

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

对于另外 $9\%$ 的数据，没有修改操作。

对于另外 $19\%$ 的数据，$n,m\leq 500$。

对于另外 $19\%$ 的数据，每次修改的区间长度不超过 $5$。

对于另外 $19\%$ 的数据，保证数据随机。

对于 $100\%$ 的数据，$1\leq n,m\leq 2\times 10^5$，$1\leq a_{i},x\leq n$，$1\leq l\leq r\leq n$。


title: 「ACOI2020」修学旅行

background:
![T5](https://s2.ax1x.com/2020/01/12/loS0Wq.md.png)

第一学期开学没多久，E 班的各位就要去修学旅行了！

description:
现在，六个人 赤羽 業，杉野 友人，奧田 愛美，茅野 楓，神崎 有希子，潮田 渚 为一组，他们将在京都进行一次暗杀旅行。他们的目标仍然是狙击杀老师。政府同时派来了职业狙击手 赤红之眼。但是完成任务的同时，他们想让快乐度尽量的高。

聪明的神崎 有希子（Kanzaki Yukiko）终于求出了快乐度的表达式，令人感到震惊的是，快乐度竟然和旅行景点个数和暗杀杀老师次数有关！

假设他们经过了 $n$ 个景点，暗杀了 $m$ 次杀老师，且定义：

$$
\Gamma(a,b)=\left\{
    \begin{aligned}
    & 1,a>b&\\
    &  \prod_{i=a}^b i,a \le b&\\
    \end{aligned}
    \right.
$$

那么快乐度为：

$$
\sum_{i=0}^m \lgroup \frac{\sqrt{\sum_{j=0}^i (C_i^j)^2C_{n+2i-j}^{2i}}}{\Gamma(n+1,n+i)} \times \Gamma(n-i+1,n) \rgroup
$$

**我们保证** $\frac{\sqrt{\sum_{j=0}^i (C_i^j)^2C_{n+2i-j}^{2i}}}{\Gamma(n+1,n+i)} \times \Gamma(n-i+1,n)$ **是一个整数。**

现在他们有 $T$ 个问题想要问你，如果他们经过了 $n$ 个景点并且暗杀 $m$ 次杀老师，能否告诉他们快乐度呢？

**由于答案可能太大，请将答案对 $998244353$ 取模。**

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

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

对于每组数据：

只有一行两个整数 $n$ 和 $m$。

outputFormat:
对于每组数据，只有一行一个整数，表示他们经过了 $n$ 个景点，暗杀了 $m$ 次杀老师的快乐度对 $998244353$ 取模后的值。

#### 样例有更新

hint:
#### 数据范围

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

- Subtask 1（10 points）：$T \leq 10$，$n,m \leq 10$。
- Subtask 2（20 points）：$T \leq 100$，$n,m \leq 5 \times 10^4$。
- Subtask 3（30 points）：$T \leq 50$，$n,m \leq 9 \times 10^8$。
- Subtask 4（40 points）：数据无特殊限制。

对于 $100\%$ 的数据，$m \leq n$，$1 \leq T \le 10^2$，$1 \leq n,m \leq 9 \times 10^8$。

---
#### 提示

**第三个子任务中的测试点时限 2S，第四个子任务中的测试点时限 5S。**


title: [CTSC2007] 挂缀pendant

description:
“珠缀花蕊，人间几多酸泪”……

挂缀在很早就被人们作为一种装饰品，垂坠的风韵，华丽摇曳的摆动，展现出一种与众不同的优雅与高贵。而我们的主人公小 Q，正想买一条漂亮的挂缀放在寝室里作为装饰。

挂坠的构成，是由若干粒缀珠相互连接而成。每一个缀珠由三部分组成：分别是珠子、珠子上方的连接环与珠子下方的挂钩。我们可以简单的认为从上往下数的第 $i$ 个缀珠是将它的连接环套在其上方（也就是第 $i-1$ 个）缀珠的挂钩
之上（第 $1$ 个除外）。小 Q 想买一根足够长的挂缀，这样显得更有韵味。

然而商店的老板告诉小 Q，挂缀是不可能做到任意长的，因为每一个珠子都受到重力作用，对其上方的挂钩有一定的拉力，而挂钩的承受能力是有限的。老板还告诉小 Q，他一共拥有 $N$ 个珠缀（假设每一个珠缀都很漂亮，小 Q 都很喜欢），每个珠缀都有其各自的重量与承受能力。**一个挂缀是稳定的，当且仅当对于其上的每一个珠缀，它下方所有珠缀的重量和（不包含自身）不超过其挂钩的承受能力。**

小 Q 希望她的挂缀尽量长，你能帮她计算出最长可能的稳定挂缀么？当然，如果有多个可选方案，小 Q 希望总重量最小的。

inputFormat:
第一行包含一个正整数 $N$，表示商店拥有的珠缀数目。

接下来 $N$ 行，每行两个整数 $C_i$，$W_i$，分别表示第 $i$ 个珠缀的承受能力与重量。

outputFormat:
共两行。

第一行包含一个整数 $L$，表示可以找到的最长稳定挂缀长度。

第二行包含一个整数 $W$，表示可以找到的长度为 $L$ 的稳定挂缀中的最小重量和。


title: [CTSC2007] 矩阵Matrix 【征集 SPJ】

description:
给定一个整数 $D$，$n$ 行 $m$ 列的实数矩阵 $A$，其第 $i$ 行第 $j$ 列的元素是 $a_{ij}$，且 $0 \le a_{ij} \le D$（$1 \le i \le n$，$1 \le j \le m$）。希望你能由此提供一个 $n$ 行 $m$ 列的 $01$ 矩阵 $B$，第 $i$ 行 第 $j$ 列的元素是 $b_{ij}$（$1 \le i \le n$，$1 \le j \le m$），$b_{ij}$ 非 $0$ 即 $1$。

对于给定的 $A$ 矩阵和你提供的 $B$ 矩阵，可以求出

$$p_1=\max \begin{cases}\max\limits_{ 1 \le j \le m} \{ |\sum_{i=1}^n (b_{ij}-\frac{a_{ij}}{D})|\}\\\max\limits_{1 \le i \le n} \{ |\sum_{j=1}^m (b_{ij}-\frac{a_{ij}}{D})|\}\end{cases}$$

$$p_2=\max_{1 \le i \le n,1 \le j \le m} \{|b_{i,j}+b_{i-1,j}+b_{i,j-1}+b_{i-1,j-1}-\frac{a_{i,j}+a_{i-1,j}+a_{i,j-1}+a_{i-1,j-1}}{D}|\}$$

在不同的测试例子中，我们希望提供的 $B$ 矩阵能使 $p_1$ 或 $p_2$ 尽量小。

inputFormat:
第一行有一个整数 $c$，有两种取值：$c=1$ 表示我们的最小化目标是 $p_1$，$c=2$ 则表示希望 $p_2$ 尽量小。

第二行有3个整数 $D$，$n$，$m$，相邻的两个数字间用一个空格隔开，$D$ 的含义如上文所述，$n$ 和 $m$ 分别表示 $A$ 矩阵的行数和列数。

以下有 $n$ 行，每行 $m$ 个实数，描述 $A$ 矩阵。其中第 $i$ 行第 $j$ 列的实数表示 $a_{ij}$，相邻的数字用一个空格隔开。

outputFormat: 仅包含一个 $n$ 行 $m$ 列的 $01$ 矩阵 $B$，表示你求出的使 $p_c$ 尽量小的答案。其中第 $i$ 行第 $j$ 列的数字表示 $b_{ij}$。相邻的整数之间用一个空格隔开。


title: [CSGRound3] 仙人掌

background: ckw 是一个非常菜的菜鸡。

description:
ckw 有好多边仙人掌。边仙人掌是一个每条边至多在一个简单环里的简单无向连通图。

ckw 定义了无向图的度数序列，度数序列的长度为图中点的个数，度数序列中第 $i$ 个元素是图中编号为 $i$ 的节点的度数。

ckw 想知道，对于所有 $n$ 个点 $m$ 条边的边仙人掌，其不同的度数序列有多少种。

输出答案模 $998244353$ 之后的结果即可。（如果不存在合法仙人掌输出 $0$ 即可）

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

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

对于每组数据，一行两个整数 $n,m$，分别表示点数和边数。

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

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

对于第一组数据，这里给出其中四个合法的度数序列：$\{2,2,2,2\},\{1,2,2,3\},\{1,2,3,2\},\{2,1,3,2\}$。

---

**【数据范围】**

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

- Subtask 1（8 points）：$n \le 5$。
- Subtask 2（10 points）：$n \le 10 $。
- Subtask 3（18 points）：$n \le 35$。
- Subtask 4（12 points）：$n \le 90$。
- Subtask 5（8 points）：$m = n - 1$。
- Subtask 6（10 points）：$m = n$。
- Subtask 7（16 points）：$m = n + 1$。
- Subtask 8（18 points）：无特殊限制。

对于 $100\%$ 的数据，$1 \le T \le 10$，$0 \le n \le 2 \times 10^3$，$0 \le m \le 10^9$。


title: 「ACOI2020」音速

background:
![T1](https://s2.ax1x.com/2020/01/12/loSQJI.png)

防卫省的 乌间 惟臣（Tadaomi Karasuma）老师来到了椚丘中學给予了三年 E 班的同学们重大的任务：在一年内暗杀掉一个超生物（被 茅野 カエデ 取名为杀老师）。于是同学们开始努力地训练。但是很快的，杀老师展现了它的本领，可以以 20 马赫的超高速持久飞行，导致同学们根本碰不到杀老师。于是他们准备找乌间购买一个传送器。

description:
现在同学们在后山埋伏。同学们对后山足够熟悉，并且后山足够宽广，可以看做一个无限大的平面直角坐标系，而同学们在 $(0,0)$ 这个位置。这时候杀老师在 $(x,y)$ 这个位置捡到了 岡島 大河 所放置的小黄书认真地读了起来。同学们现在可以以自己为圆心，$r$ 为半径画一个圆然后把传送器抛出去，落在圆上一点 $S$，传送器可以在落点处作一条与刚才的圆相切的直线 $PQ$，现在这条直线就是我们的传送器了。

传送器的作用是：把同学们传送到他们所站的点关于 $PQ$ 的对称点。而且他们必须要**传送后移动**到杀老师的位置才能攻击它。现在，乌间看了他们的计划之后十分感叹，但是他有两个问题想问同学：

- 他们用了传送器之后，至少需要移动多远？

- 在保证移动距离最短的方案下，$PQ$ 与 $x$ 轴夹角的 $\tan$ 值为多少？我们认为夹角在 $[0,180]$ ° 。

inputFormat:
第一行两个实数 $x,y$，表示杀老师和小黄书的位置，自动抹去无意义的 $0$；
第二行一个实数 $r$，意义见题目描述。

outputFormat:
第一行请输出他们用了传送器之后，至少需要移动的距离，**保留六位小数**。

第二行请在保证移动距离最短的方案下输出 $PQ$ 与 $x$ 轴夹角的 $\tan$ 值，**保留二位小数**。

特殊地，当 $\tan$ 值无意义的时候，输出 ```Error```；否则，如果有多个角度都可以满足条件，输出 $\tan$ 值最小的一个，可以把 ```Error``` 视作无穷大。

**注意，$\tan$ 值为负数的时候，将这个 $\tan$ 值视作无穷大。夹角指的是那个锐角。**

hint:
#### 数据范围

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

- Subtask 1（10 points）：$x,y,r$ 满足 $x^2+y^2=r^2$。
- Subtask 2（20 points）：$x,y$ 中至少有一个为 $0$。
- Subtask 3（70 points）：数据无特殊限制。

对于 $100\%$ 的数据， $0 \leq |x|,|y|,r \leq 10^{10}$。

---
####  提示

1. **本题含有 SPJ**，如果第一个问题的答案与标准答案差的绝对值不大于 $10^{-6}$ 时就能获得该测试点的分数的 $50\%$。当第一个问题的答案正确时：
- 若第二个问题的答案不为 ```Error``` 时，当输出答案与标准答案差的绝对值不大于 $10^{-2}$ 时能得到该测试点的所有分数；
- 当第二个问题的答案为 ```Error``` 时，只有输出 ```Error``` 才能得到该测试点的所有分数。
**因为 SPJ 敏感，如果只能回答第一个问题，也请在第二行随意输出一些值，不要输出 `Error`**。

2. $\tan$ 值表示在一个 **直角三角形** 中，一个角相对的直角边与其相邻的直角边的比值，比如 $\tan\ 45°= 1$。特殊地，$90°$ 的 $\tan$ 值**无意义**。

3. 和圆只有一个公共交点的直线叫做圆的**切线**，连接切点与圆心的半径**垂直**于切线。


title: 「ACOI2020」布丁暗杀计划

background:
![T3](https://s2.ax1x.com/2020/01/12/lopanO.png)

茅野 カエデ（Kayano Kaede）制定了一个用布丁暗杀杀老师的计划。他们用剩余的鸡蛋加工制成一个布丁。为了外观和味道，他们会在里面加上一些用糯米纸包着的改变口味的食材。为了好看，这些食材从上至下排成了树的模样。在布丁的最底下铺满了 对老师炸弹 。杀老师吃到那里去之后就会引爆。

description:
终于，同学们把布丁做好了。最爱吃布丁的茅野开始想，这个布丁有多好吃呢？

一个布丁的好吃程度，取决于里面的改变口味的食材。材料不同的话，颜色和美味度也是不一样的。

布丁里面有 $n$ 种调味食材，有 $n-1$ 个东西连接着，第一种食材在最上面，相当于这一棵树的根。

现在，茅野制定一个布丁的好吃程度与指定的某两个值 $u,k$ 有关，这个好吃程度为，第 $u$ 种食材的 $k$ 级祖先 $v$ 食材的所有 $k$ 级儿子与 $v$ 食材颜色相同的那些 $k$ 级儿子的美味度之和。可以发现，$u$ 或者 $k$ 不同，一般情况下美味度是不同的。所以有 $q$ 个问题想要问你。

**特殊地，如果第 $u$ 种食材没有 $k$ 级祖先，直接输出 $0$ 即可。**

inputFormat:
第一行两个整数 $n,q$，表示有 $n$ 个食材，$q$ 个询问。

第二行 $n$ 个整数，第 $i$ 个整数表示食材 $i$ 的颜色 $color_i$。

第三行 $n$ 个整数，第 $i$ 个整数表示食材 $i$ 的美味值 $d_i$。

第四行 $n-1$ 个整数，第 $i$ 个整数表示食材 $i+1$ 的父节点 $fa_i$。

接下来 $q$ 行，每行两个整数 $u,k$ 表示询问。

outputFormat: 有 $q$ 行，每行一个整数，表示询问的结果。

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

食材 $2$ 的 $1$ 级祖先是食材 $1$，食材 $1$ 的 $1$ 级儿子有食材 $2$ 与食材 $3$，食材 $2$ 与食材 $3$ 的颜色都与食材 $1$ 的颜色相同，所以美味度之和为 $2+3=5$。

------------
#### 数据范围
**本题采用捆绑测试**。

- Subtask 1（30 points），鸡蛋缺乏，布丁不大：$n \leq 10^3$，$q \leq 10^4$。
- Subtask 2（20 points），食材构成了一条链：$n \leq 5 \times 10^5$，$q \leq 10^5$，$color_i \leq 10^2$。
- Subtask 3（50 points）：数据无特殊限制。

对于 $100\%$ 的数据，$1 \leq n,q,color_i \leq 5 \times 10^5$，$1 \leq d_i \leq 10^5$。

------------
#### 提示

**第二个子任务中的测试点与第三个子任务中的测试点时限 2S。**


title: 「ACOI2020」学园祭

background:
![T4](https://s2.ax1x.com/2020/01/12/lopWDS.md.png)

秋天，是学习之秋，食欲之秋，更是，学园祭之秋！随着时间流逝，学园祭也越来越近。终于等到这一天，可是没想到在冲绳岛上邂逅到女装的渚同学的勇次竟然来了！中村 莉櫻（Nakamura Rio）见到这个情况，忙给渚同学换上女装。没办法，勇次已经来了，于是渚同学鼓起勇气迈出了第一步。（为什么自顾自地加提示框啊喂！）

description:
莉櫻为了利用这个人傻钱多的少爷，尽全力提高消费额，努力地暗示渚同学。没办法，于是渚同学想了一下，提出了一个问题：

给出一个 $n$，定义：
$$
\Gamma(0)=1,\Gamma(n)={n!}
$$

$$
A_i^j=\frac{\Gamma(i)}{\Gamma(j)}
$$
求
$$
\sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^j \gcd(A_{i-j}^j \times \Gamma(j),A_{j-k}^k \times \Gamma(k))
$$

渚同学念着莉櫻举起的对话板上写的字：如果不能在规定时间回答出问题的话，就要把菜单全部买一遍哦！

尽管勇次钱多，但是他并不想吃得太多，因为这个问题有 $T$ 个小问题！

**由于答案可能太大，请将答案对 $10086001$ 取模。**

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

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

对于每组数据：

只有一行一个整数 $n$。

outputFormat: 对于每组数据，一行一个整数，表示问题的答案对 $10086001$ 取模后的值。

hint:
#### 数据范围
**本题采用捆绑测试**。

- Subtask 1（20 points）：$T \leq 10^3$，$n \leq 10^2$。
- Subtask 2（30 points）：$T \leq 10^6$，$n \leq 5 \times 10^3$。
- Subtask 3（50 points）：$T \leq 10^6$，$n \leq 10^6$。

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


title: 数列求和加强版 / SPOJ MOON4

background: [原题链接](https://www.luogu.com.cn/problem/P4948)

description:
给定 $n,a,k$，求：

$$\sum_{i=1}^n i^k a^i$$
答案对 $998244353$ 取模。

inputFormat: 输入一行三个正整数 $n,a,k$。

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


title: [RC-03] 记忆

background: 小 W 想写一个关于记忆的题目背景，但是他忘记了。

description:
有一个括号串 $S$，一开始 $S$ 中只包含一对括号（即初始的 $S$ 为 `()`），接下来有 $n$ 个操作，操作分为三种：

1. 在当前 $S$ 的末尾加一对括号（即 $S$ 变为 `S()`）；

2. 在当前 $S$ 的最外面加一对括号（即 $S$ 变为 `(S)`）；

3. 取消第 $x$ 个操作，即去除第 $x$ 个操作造成过的**一切影响**（例如，如果第 $x$ 个操作也是取消操作，且取消了第 $y$ 个操作，那么当前操作的实质就是恢复了第 $y$ 个操作的作用效果）。

每次操作后，你需要输出 $S$ 的能够括号匹配的非空子串（子串要求连续）个数。

一个括号串能够括号匹配，当且仅当其左右括号数量相等，且任意一个前缀中左括号数量不少于右括号数量。

inputFormat:
第一行：一个整数 $n$，表示操作的个数。

接下来 $n$ 行：每行先有一个整数 $op$，表示操作的种类：

若 $op=1$，则表示执行了操作 $1$；

若 $op=2$，则表示执行了操作 $2$；

若 $op=3$，接下来还有一个整数 $x$，表示执行操作 $3$，取消了第 $x$ 个操作（操作按 $1$ 到 $n$ 编号，保证第 $x$ 个操作已发生），注意取消操作**并不影响任何操作的编号**，编号只取决于输入顺序。

outputFormat: 共 $n$ 行：第 $i$ 行输出一个整数 $ans_i$，表示第 $i$ 次操作结束后整个括号串的括号匹配的非空子串个数。


title: [CSGRound3] 游戏

background: 小 Y 和小 Z 是一对好朋友，他们在玩一个游戏。**游戏只有一个回合**。

description:
有一个牌堆，一共有 $n$ 张牌，第 $i$ 张牌上有一个数 $a_i$，其中第一张牌是堆顶。

小 Z 先取牌，他可以从堆顶开始取连续若干张牌（**可以取 $0$ 张**），取完的牌拿在手上，也就是不在牌堆里了。

然后小 Y 取牌，同样，她也可以从堆顶开始取连续若干张牌（**可以取 $0$ 张**）。

如果一个人手上的牌的数字和大于 $X$，那么他的分数就是 $0$，否则分数就是数字和。

分数高的人获胜，**如果一样高，则无人获胜**。

小 Z 为了获胜，使用了透视挂，即他知道牌堆里每张牌上写的数。

现在问你对于满足 $1 \leq X \leq K$ 的所有整数 $X$，哪些可以使得小 Z 有必胜策略，即小 Z 取完后，不管小 Y 怎么取都一定会**输**。

inputFormat:
第一行一个整数 $n$，表示牌堆里有几张牌。

第二行 $n$ 个整数 $a_{1\dots n}$，表示每张牌上写的数。

第三行一个正整数 $K$，含义见题目描述。

outputFormat:
第一行一个整数，表示满足要求的 $X$ 的个数。

第二行从小到大依次输出满足要求的 $X$，用空格隔开。

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

$X=1,2,3$ 时，小 Z 取一张牌，小 Y 不管怎么取都是零分。

$X=4$ 时，小 Z 如果取 $1$ 张，那么小 Y 取 $1$ 张小 Y 就赢了；否则小 Z 只能是零分。

$X=5$ 时，小 Z 如果取 $1$ 张，那么小 Y 取 $1$ 张小 Y 就赢了；小 Z 如果取了 $2$ 张，小 Y 也取 $2$ 张，平局；否则小 Z 只能是零分。

---

**【数据范围】**

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

- Subtask 1（3 points）：$n = 1$。
- Subtask 2（14 points）：$K= 1$。
- Subtask 3（20 points）：$n,K \le 100$。
- Subtask 4（33 points）：$n , K \le 3333$。
- Subtask 5（30 points）：无特殊限制。

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


title: 猫猫和企鹅

description:
王国里有 $n$ 个居住区，它们之间有 $n-1$ 条道路相连，并且保证从每个居住区出发都可以到达任何一个居住区，并且每条道路的长度都为 $1$。

除 $1$ 号居住区外，每个居住区住着一个小企鹅，有一天一只猫猫从 $1$ 号居住区出发，想要去拜访一些小企鹅。可是猫猫非常的懒，它只愿意去距离它在 $d$ 以内的小企鹅们。

猫猫非常的懒，因此希望你告诉他，他可以拜访多少只小企鹅。

inputFormat:
第一行两个整数 $n, d$，意义如题所述。

第二行开始，共 $n - 1$ 行，每行两个整数 $u, v$，表示居民区 $u$ 和 $v$ 之间存在道路。

outputFormat: 一行一个整数，表示猫猫可以拜访多少只小企鹅。

hint: 对于 $100\%$ 的数据，满足 $1 \le n ,d \le 10^5$，保证所有居民区从 $1$ 开始标号。


title: [CSGRound3] 压岁钱

background:
祝大家庚子鼠年快乐！Best wishes!

也愿肺炎早日得到控制吧，中国加油！

新年到了，小 Z 总是能收到很多的压岁钱。

小 Z 是个非常喜欢氪金的玩家，所以时不时都会把压岁钱花掉一部分用来买皮肤和石头。

但是小 Z 又十分担心压岁钱没过几天就都被自己花完了。为此，小 Z 有封印大法，能够暂时的把自己的一部分钱封印起来（即无法花费），直到某一天解除封印后才能使用。

description:
一共存在有 $m$ 个事件，且事件分为以下的 $3$ 种类型。

1. 小 Z 得到了 $a$ 元压岁钱。
2. 小 Z 花掉了 $a$ 元压岁钱用于买皮肤。
3. 小 Z 把自己的 $a$ 元钱封印了起来，只有当第 $b$ 个事件发生前 $1$ 秒才会解除封印，并保证每次小 Z 现有的钱大于等于封印的钱。

当小 Z 的钱在某个事件不够花时，小 Z 会感到不开心，同时钱不够花时小 Z 便不会花钱。

请告诉小 Z ，他的钱在几个事件中会不够花。

inputFormat:
第一行一个整数 $m$，用于表示事件发生的总数。

接下来的 $m$ 行，首先一个整数 $t$，表示事件的类型。

如果 $t=1$ 或 $t=2$，则接下来一个整数 $a$。

如果 $t=3$，则接下来两个整数 $a,b$。

outputFormat: 一行一个整数，表示**钱不够花**的事件数。

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

第一天：收入 $10$ 元，余额 $10$ 元。

第二天：不够支出 $20$ 元，余额 $10$ 元。

第三天：支出 $10$ 元，余额 $0$ 元。

总计：$1$ 天。

**【样例 2 解释】**

第一天：收入 $10$ 元，余额 $10$ 元。

第二天：封印 $5$ 元，余额 $5$ 元。

第三天：不够支出 $10$ 元，余额 $5$ 元。

第四天：收入 $10$ 元，余额 $15$ 元。

第五天：封印解开，支出 $20$ 元，余额 $0$ 元。

总计：$1$ 天。

---

**【数据范围】**

对于 $50\%$ 的数据，满足 $m,a \leq 5\times 10^3$。

对于 $70\%$ 的数据，$t \ne 3$。

对于 $100\%$ 的数据，满足 $ 1 \leq b \le m \leq 10^6$，$1 \le t \le 3$，$1 \leq a \leq 10^7$。


title: Ryoku 爱学习

background: Ryoku 继承了 Riri 在学习方面的天赋，所以她非常热爱学习。但是，不管再怎么热爱学习，Ryoku 也会疲倦的。

description:
Ryoku 在第 $i$ 时刻会了解到有一个新知识 $i$，这个新知识的实际价值为 $w_i$，由于 Ryoku 爱学习，所以她不会选择不学习知识，但她只有 $p_i$ 的概率能成功掌握这个知识。

然而如果 Ryoku 同时掌握了太多知识，由于 Ryoku 内心的疲倦等因素，Ryoku 感受到的对知识的喜爱程度会改变，我们用一个数值 $R$ 来描述**喜爱程度**的大小。具体而言，设 $R=f(l,r)$ 代表 Ryoku **连续掌握**时刻 $l$ 至时刻 $r$ 的知识时对这些知识的喜爱程度的总和，有参数 $a, b$（$0 < a, b<1$），则有：

$$ f(l,r)=a^{b(r-l)}  \sum_{i=l}^r w_i$$

Ryoku 想要知道她期望能**掌握的每一段连续时刻的知识**的喜爱程度之和是多少（需要注意的是，这里所说的连续时刻的知识不能被一段更长的所包含）。你能帮帮她吗？

inputFormat:
输入包含三行。
第一行包含一个整数 $n$，两个实数 $a,b$。
第二行包含 $n$ 个整数，为 $w_i$。
第三行包含 $n$ 个实数，为 $p_i$。

outputFormat: 输出包含一行一个正实数，为答案。

hint:
**【样例 1 说明】**

掌握知识 $1$、知识 $2$、知识 $3$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 2}(2+3+3)=4$。

掌握知识 $1$、知识 $2$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 1}(2+3)=\dfrac {5\sqrt2}2\approx 3.536$。

掌握知识 $1$、知识 $3$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 0}\times 2 +\left(\dfrac 12\right)^{\frac12\times 0}\times 3  = 5$。

掌握知识 $2$、知识 $3$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 1}(3+3)=3\sqrt 2\approx 4.243$。

只掌握知识 $1$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 0}\times 2  = 2$。

只掌握知识 $2$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 0}\times 3  = 3$。

只掌握宝物 $3$ 时，每一段连续掌握知识的喜爱程度之和为 $\left(\dfrac 12\right)^{\frac12\times 0}\times 3  = 3$。

什么都不掌握时，每一段连续掌握知识的喜爱程度之和为 $0$。

以上 $8$ 种情况出现的概率均为 $\dfrac 18$，所以答案约为：

$$(4+3.536+5+4.243+2+3+3+0)\times \dfrac 18\approx3.0973$$

---

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

对于 $20\%$ 的数据，$n \le 18$。
对于另外 $15\%$ 的数据，$w_i = 1$。
对于 $55\%$ 的数据，$n \le 10^3$。
对于另外 $15\%$ 的数据，$w_i = 1$。
对于另外 $15\%$ 的数据，$b_i \le 0.2$。

此外，对于 $100\%$ 的数据，$0<n\le10^5$，$0<a,b,p_i<1$，$0<w_i\le10^3$。保证输入数据的精度不超过 $10^{-2}$。

**本题使用 Special Judge，如果某个测试点中你的答案与标准答案相差小于等于 $10^{-3}$，你就可以通过该测试点。**


title: [POI2004] PRZ

background: 一只队伍在爬山时碰到了雪崩，他们在逃跑时遇到了一座桥，他们要尽快的过桥。

description: 桥已经很旧了, 所以它不能承受太重的东西。任何时候队伍在桥上的人都不能超过一定的限制。 所以这只队伍过桥时只能分批过，当一组全部过去时，下一组才能接着过。队伍里每个人过桥都需要特定的时间，当一批队员过桥时时间应该算走得最慢的那一个，每个人也有特定的重量，我们想知道如何分批过桥能使总时间最少。

inputFormat:
第一行两个数:  $W$ 表示桥能承受的最大重量和 $n$ 表示队员总数。

接下来 $n$ 行：每行两个数: $t$ 表示该队员过桥所需时间和 $w$ 表示该队员的重量。

outputFormat: 输出一个数表示最少的过桥时间。


title: [POI2004] MOS

background: 一个夜晚一些旅行者想要过桥。

description:
他们只有一个火把。
- 火把的亮光最多允许两个旅行者同时过桥。
- 没有火把或者多于 $2$ 个人则不能过桥。

每个旅行者过桥都需要特定的时间，两个旅行者同时过桥时时间应该算较慢的那个。现在我们想知道所有旅行者最少要花费多少时间才能全部过桥?

inputFormat:
第一行一个数 $n$ 表示旅行者的总数。

接下来 $n$ 行表示所有旅行者的过桥时间，时间从小到大排列。

outputFormat: 输出一个数表示最少过桥时间。

hint:
对于 $100\%$ 的数据，$1\le n\le10^5$，过桥时间均不超过 $10^9$。

注：数据中 $n\ge 2$。


title: [POI2004] JAS

background: 在 Byteotia 有一个洞穴。

description:
 它包含 $n$ 个洞室和一些隧道连接他们。

每个洞室之间只有一条唯一的路径连接他们。Hansel 在其中一个洞室藏了宝藏，但是它不会说出它在哪。Gretel 知道，当她询问一个洞室是否有宝藏时，如果她猜对了 Hansel 会告诉她，如果猜错了他会告诉她哪个方向会有宝藏。 给出洞穴的信息，那么无论 Hansel 把宝藏藏在了哪，求出最少要询问多少次才能找到宝藏。

inputFormat:
输入一个数 $n$，表示洞室总数。

接下来 $n-1$ 行描述 $n-1$ 条边。

outputFormat: 输出一个数表示最少询问次数。


title: [POI2004] KAG

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

接下来描述每个数据开头两个数 $n$ 和 $m$，接下来 $m$ 行每行两个数表示一条边。

outputFormat: 输出共 $k$ 行，每行输出一个判定，如果该图为 c-algae 输出 `TAK`，否则输出 `NIE`。


title: [POI2004] MAK

description:
置换就是 $n$ 个元素 $1$ 对 $1$ 的函数映射$p:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$，一个置换 $p$ 的 `order` 等于最小的 $k\ge1$，且对所以的 $i=1,2,...,n$ 都满足：
$$p(p(...(p(i))...))=i$$
（共 $k$ 次）

举个例子，对于 $3$ 个元素的 `order` $p(1)=3,p(2)=2,p(3)=1$ 为 $ 2$，因为$p(p(1))=1,p(p(2))=2,p(p(3))=3$。

对于给定的 $n$ 我们想要一个长度为 $n$ 的置换的 `order` 尽量大。比如说长度为 $5$ 的置换的 order 最大为 $6$。

一个例子就是 $p(1)=4,p(2)=5,p(3)=2,p(4)=1,p(5)=3$。

对于所有使得 `order` 最大的置换中，我们要找到字典序最小的那个。

更精确来说，我们说置换 $p$ 小于置换 $r$，即存在一个 $i$，使得对于所有 $j<i$ 都满足 $p(j)=r(j)$ 且 $p(i)<r(i)$。那么对于长度为 $5$ 的置换中最小的那个为 $p(1)=2,p(2)=1,p(3)=4,p(4)=5,p(5)=3$。

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

接下来 $d$ 行表示长度为 $n_1,n_2,...,n_d$。

outputFormat: 输出 $d$ 行每行一个最优置换。


title: [FJOI2014] 病毒防护带

background: 众所周知，在国王胖哥的带领下， K 国国泰民安，空前繁荣，但今天 K 国却遇到了空前的危机。

description:
在 K 国境内同时发现了 $n$ 个未知的病毒，每个病毒会从它被发现的位置开始感染 K 国的土地， K 国可以看做是一个无限大的二维平面，而病毒的感染形状可以看做是一个不断扩大的圆形区域，即在 $t$ 时间这个病毒会感染半径为 $t$ 的圆形土地，这个圆形的圆心为发现这个病毒的位置。

但是万幸的是， K 国有独特的病毒防护带可以杀死这些病毒，所以 K 国国王胖哥在刚发现病毒之时就开始着手进行杀毒工作，所谓的病毒防护带可以看成是一条直线，可以选定建立在 K 国的任意位置，即可以放置在 K 国所表示的平面上的任意位置，一旦病毒在扩散的过程中接触到这个防护带，病毒就会死亡，它感染的土地面积就固定为这个病毒死亡时所占的土地面积。注意由于防护带的建立十分昂贵， K 国最多只能建立一条病毒防护带。

现在胖哥想知道要如何设立这个病毒防护带，才能使每个病毒感染的平均面积最小，即被感染的总土地面积除以病毒数 $n$，每个病毒可以独立看待，即任意一个病毒的死亡不会影响到其他的病毒。注意如果同一个区域被多个病毒感染，那么在计算被感染的土地面积时需要计算多次，即若有一个病毒在位置 $(0,0)$ 被发现，一个病毒在位置 $(1,1)$ 被发现，它们都在 $t=1$ 时接触到防护带死亡，那么此时 K 国被感染的面积为 $p_i\times2$，病毒感染的平均面积为 $p_i$。

由于 K 国有举世无双的安全监测系统和卫生防护系统，可以认为在病毒防护带建立完毕之后病毒才开始进行扩散。若病毒出现在病毒防护带上，他感染的土地面积可以看做 $0$。

请编程输出在最优决策下，这些病毒感染的平均面积。

inputFormat:
第 $1$ 行中给出正整数 $Q$，表示该组数据中有多少组测试样例。

每组样例首先输入一个整数 $n$，表示该组样例中病毒的个数。

之后一行输入两个正整数 $x,y$，表示第一个病毒的坐标。

之后一行输入三个正整数 $a,b,c$，如果第 $i$ 个病毒的坐标为 $(x, y)$，那么第 $i+1$ 个病毒的坐标为 $(x',y')$，其中$x'=(a\times x^2+b\times x+c)\bmod107$，$y'=(a\times y^2+b\times y+c)\bmod107$，其中 $\bmod$ 是取模运算符号。

outputFormat: 首先输出样例编号，之后输出在最优决策下，这些病毒会感染的K国的土地面积，答案保留 $5$ 位小数，详见输出示例，请严格按照输出实例中的格式输出。


title: 「ACOI2020」惊吓路径

background:
![T6](https://s2.ax1x.com/2020/01/12/lopZpq.png)

3 年 E 班的同学们赢得了去南方的冲绳小岛的机会，在渚打败了鹰冈之后，他们受杀老师的邀请参加“试胆大会”。

试胆大会在一个黑漆漆的洞窟里面进行。赤羽 業（Akabane Karma）现在和奧田 愛美站在洞窟的门口。突然，業想到了一个事情。。。

description:
杀老师告诉过他们，洞窟可以近似地看成 $n$ 个点的外向树，因为地形原因，所以一个点到另一个点的边是有方向的，且边的方向都是同向的。这棵树的树根为入度为 $0$ 的点。每个点都有一个惊吓值，给出每个点的惊吓值 $a_i$。

杀老师告诉他们，这个洞穴有很多惊吓路径。如果两个节点 $u,v$ 构成的路径是一条惊吓路径的话，满足以下条件：

- $v$ 一定在 $u$ 的子树中。

- $u, v$ 这条路径上的所有的点的惊吓值的或值 $\geq k$。

走过一条惊吓路径就会收到杀老师的惊喜大礼。杀老师已经提前准备好了惊喜大礼，但是業当然已经知道杀老师有一些下流的意图，更别说惊喜大礼的数量可能不够！杀老师已经承诺有多少条惊吓路径就有多少个惊喜大礼。業已经通过一些神奇的途径知道了杀老师准备的惊喜大礼的个数，现在他想知道有多少条惊吓路径，也就是杀老师最少需要准备惊喜大礼的个数。如果不够，他就会揭穿杀老师的意图。现在業当然想赚，好好捉弄一下杀老师。所以他~~作弊~~提前得到了杀老师的地图，想问这个图里面有多少条惊吓路径？

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

第二行 $n$ 个整数，表示每个点的惊吓值。

接下来 $n-1$ 行，每行有两个整数 $u,v$ 表示节点 $u,v$ 之间有一条有向边，节点 $u$ 可以到达节点 $v$，**节点 $v$ 不可以到达节点 $u$**。

outputFormat: 一行一个整数，表示这个洞穴的惊吓路径条数。

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

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

只有两条路径满足条件：

1. $3\to 1\to 2$，这条路径的所有点的惊吓值的或值是 $6\operatorname{or}5\operatorname{or}9=15$。

2. $1 \to 2$，这条路径的所有点的惊吓值的或值是 $5\operatorname{or}9=13$。

------------
#### 数据范围
**本题采用捆绑测试**。

- Subtask 1（10 points）：$n \leq 5 \times 10^3$，$k \leq 10^5$。
- Subtask 2（30 points）：对于任意一条边，$v=u+1$，$n \leq 10^6$，$k,a_i \leq 10^9$。
- Subtask 3（20 points）：$n \leq 10^5$，$k,a_i \leq 10^9$。
- Subtask 4（40 points）：$n \leq 5 \times 10^5$，$k,a_i \leq 10^9$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$1 \leq k,a_i \leq 10^9$。

------------
#### 提示
**第四个子任务中的测试点空间 256MB，其余子任务中的测试点空间 128MB。**


title: [IOI1995] 铺放矩形块

description:
给定 $ 4 $ 个矩形块，找出一个最小的封闭矩形将这 $ 4 $ 个矩形块放入，但不得相互重叠。所谓最小矩形指该矩形面积最小。

所有 $ 4 $ 个矩形块的边都与封闭矩形的边相平行。

可能存在满足条件且有着同样面积的各种不同的封闭矩形， 你应该输出所有这些封闭矩形的边长。

inputFormat: 输入文件共有 $ 4 $ 行。每一行用两个正整数来表示一个给定的矩形块的两个边长。矩形块的每条边的边长范围最小是 $ 1 $，最大是 $ 50 $。

outputFormat: 输出文件的总行数为解的总数加 $ 1 $。第一行是一个整数， 代表封闭矩形的最小面积（子任务 $ A $）。接下来的每一行都表示一个解，由数 $ P $ 和数$ Q $ 来表示，并且 $ P \leq Q $（子任务 $ B $）。这些行必须根据 $ P $ 的大小按升序排列，$ P $ 小的行在前，大的在后。且所有行都应是不同的。


title: [FJOI2015] 金币换位问题

description:
给定一个 $n$，最开始序列长这样：

$$
\underbrace{\tt 111\cdots11}_{n \text{ 个 } 1}\underbrace{\tt 000\cdots00}_{n \text{ 个 } 0}\verb!__!
$$

现在要求用最少的交换步数，使得最终的序列为

$$
\underbrace{\tt 101010\cdots 1010}_{2\times n \text{ 个 } 01 \text{ 交替排列}}\verb!__!
$$

所谓交换是指**将相邻两个非空格的数一起挪到两个空格上**。

例如，下面是 $n=4$ 时的一组合法解：

- 初始状态：$\verb!11110000__!$。
- 第 $1$ 步：$\verb!__11000011!$。
- 第 $2$ 步：$\verb!101__00011!$。
- 第 $3$ 步：$\verb!1010100__1!$。
- 第 $4$ 步：$\verb!10101__001!$。
- 第 $5$ 步：$\verb!10101010__!$。

可以证明，最少的操作次数就是 $5$ 步。

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

outputFormat:
第一行输出最少移动步数。

接下来一行为移动方案，只要输出被移动的两个非空格格子左边那个的编号。详见样例。


title: [IOI2005] gar

background: Byteman 拥有镇上最漂亮的花园。

description:
他在自己的花园里面种了 $N$ 朵玫瑰花。

夏天来了，所有的花都开的非常的漂亮。 Byteman 开始意识到自己没有能力看管自己花园里的所有的花，所以他决定雇佣两个园丁来帮助他。

他想在花园中选择两块矩形的区域分别交给两个园丁看管。而且这两个矩形区域必须不能相交或者重叠，并且每一个区域要恰好包含 $K$ 朵玫瑰花。

Byteman 想要给这两块矩形区域的周围安上栅栏，但是他现在手头比较紧，所以他希望自己花的钱尽量的少。你的任务就是帮助 Byteman 选择两块矩形的区域,使得它们在满足条件的情况下周长和最小。

Byteman 的花园有 $L$ 米长，$W$ 米宽。花园被分成了 $L\times W$ 个大小相同 $1\times1$ 的方格。我们以平行与花园的两边建立起一个坐标系。所有的方格的坐标 $(x,y)$ 满足 $1\leq x\leq L,1\leq y\leq W$。每个方格内可能会有任意数目的玫瑰。

所选的矩形区域的两边必须跟花园的两边平行，并且矩形区域的四个角的坐标必须是整数。对于 $1\le L_1\le L_2\le L$ 并且 $1\le W_1\le W_2\le W$，一个矩形区域的四个角为 $(L_1,W_1),(L_1,W_2)$，$(L_2,W_1)$ 和 $(L_2,W_2)$:

* 这个矩形内所包含的点的坐标 $(x,y)$ 满足$L_1\le x\le L_2$并且$W_1\le y\le W_2$。

* 这个矩形的周长是 $2\times (L_2-L_1+1)+2\times (W_2-W_1+1)$。所选的两块矩形不能重叠或者相交。也就是它们不能有公共的方格。即使它们有公共的边，计算周长的时候也要分别计算。

inputFormat:
第一行是 $L$ 和 $W$。

第二行是 $N$ 和 $K$。

接下来 $N$ 行为 $N$ 朵玫瑰的坐标。

outputFormat:
输出仅有一行，为最小周长。

如果不存在满足题意的矩形，则输出`NO`。


title: [POI1999] 原始生物

background: - 鸣谢 `@Jiangly` 提出错误，`@NaCly_Fish` 修改数据。

description:
原始生物的遗传密码是一个自然数的序列 $K=(a_1,...,a_n)$。

原始生物的特征是指在遗传密码中连续出现的数对 $(l,r)$，即存在自然数 $i$ 使得 $l=a_i$ 且 $r=a_{i+1}$。

在原始生物的遗传密码中不存在 $(p,p)$ 形式的特征。

### 求解任务：

请设计一个程序：
- 读入一系列的特征。
- 计算包含这些特征的最短的遗传密码。
- 将结果输出.

inputFormat:
第一行是一个整数 $n$ ，表示特征的总数。

在接下来的 $n$ 行里，每行都是一对由空格分隔的自然数 $l$ 和 $r$。

数对 $(l,r)$ 是原始生物的特征之一。

输入文件中的特征**可能会有重复**，请过滤掉。

outputFormat: 唯一一行应该包含一个整数，为包含了所有特征的遗传密码的最小长度。


title: [IOI2004] empodia 障碍段

background:
古数学及哲学家毕氏相信自然之本质为数学。

现代生物学家研究生物数列。

description:
生物数列为满足下列条件的 $M$ 个整数所成的数列：

- 包含从 $0, 1, …,$ 到 $M-1$ 的所有数字。
- 起始数字为 $0$， 最后一个数字为 $M - 1$。
- 数列中 $E+1$ 不可以紧接在 $E$ 之后。

生物数列的连续子数列称为数段。如果一个数段的：

- 起点为该数段最小的数字。

- 终点为该数段最大的数字且与起点不是同一个数字。

- 且介于这两个数字之间所有的整数都出现在这个数段中。

则称这个数段为框段。

如果框段中并不包含更短的框段，则称之为障碍段。

以`(0,3,5,4,6,2,1,7)`这个生物数列为例。

整个生物数列是一个框段， 可是它包含了另外一框段 `(3,5,4,6)` ，因此该生物数列不是障碍段。而框段 `(3,5,4,6)` 并不包含任何更短的框段，所以它是一个障碍段，而且是此生物数列中唯一的障碍段。请写一个程序， 在
输入生物数列后， 输出所有的障碍段。

inputFormat:
第一行为单一整数 $M$，代表生物数列的长度。

生物数列中的数字依序出现在接下来的 $M$ 行，每一行有一个整数。

outputFormat:
第一行为一整数 $H$，代表该生物数列中的障碍段的个数。

接下来的 $H$ 行，将每一个障碍段，依照起点在原输入生物数列中出现的顺序，依序输出。

每行以 $2$ 个整数 $A$ 与 $B$ 代表一个障碍段并以一个空格分开。

原输入生物数列第 $A$ 个元素为该障碍段的起点，而第 $B$ 个元素为该障碍段的终点。


title: [IOI2004] Phidias 菲迪亚斯神

background: 有名的希腊雕刻神菲迪亚斯正在为他下一座雄伟的雕像作准备。

description:
为了这座雕像他需要大小为 $W_1\times H_1,W_2\times H_2, ...,W_N \times H_N$ 的矩形大理石板。

最近菲迪亚斯获得一块矩形大理石块。菲迪亚斯想把这块石板切成所需要的大小。

石板或是石板所切割出的部分都可以由垂直(或水平)方向纵贯(或是横贯)加以切割到底成为两块矩形石板，同时切割出的这两块矩形石板都必须具有整数的宽度与高度。

石板只能以此种方法加以切割，同时石板不能粘合成较大石板。

因为石板具有花纹，所以石板也不能旋转。

如果菲迪亚斯切割出一块 $A\times B$ 的石板，则此石板不能被当成 $B\times A$ 的石板使用，除非 $A$ 等于 $B$。对每一种所需石板大小菲迪亚斯可切割出零或更多块石板。如果当所有的切割完成时，一块产生出的石板并不是任何所需要的大小，则此石板成为废料。

菲迪亚斯想知道如何切割最初的石板，才能让所产生的废料最少。

例如，下图中的原始石板宽度为 $21$ 且高度为 $11$，而所需石板大小为 $10\times4,6\times 2, 7\times5$ 及 $15\times 10$, 则最小废料总面积为 $10$。下图同时画出最小废料总面积为 $10$ 的切割方法：

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

你的工作是写一个程序由给定的原始石板大小及所需要的各种石板大小计算出最小的废料总面积。

inputFormat:
第一行为两个整数。

第一个整数 $W$ 为原始石板的宽度，第二个整数 $H$ 为原始石板的高度。

第二行为一个整数 $N$，代表所需石板种类数目。以下 $N$ 行为各种所需石板的大小。

每一行为两个整数，第一个整数为所需石板宽度 $W_i$，第二个整数为所需石板宽度 $H_i$ 。

outputFormat: 为一行且仅包含一个整数，代表最小废料总面积。


title: [POI2007] 天然气管道Gaz

background: Mary 试图控制成都的天然气市场。

description:
专家已经标示出了最好的天然气井和中转站在成都的地图。现在需要将中转
站和天然气井连接起来。

每个中转站必须被连接到正好一个钻油井，反之亦然。

Mary 特别指名，建设的天然气管道必须从某个天然气井开始，向南或者向东建设。

Mary 想知道怎么连接每个天然气井和中转站，使得需要的天然气管道的总长度最小。

inputFormat:
第一行为一个正整数 $n$，表示天然气井的数量（中转站的数量与之相等）。

接下来 $n$ 行，每行两个整数 $x_i$ 和 $y_i$，表示天然气井的坐标。向东走则 $x$ 坐标增加，向北走则 $y$ 坐标增加接下来 $n$ 行，每行两个数 $x_j$ 和 $y_j$，表示中转站的坐标。

outputFormat: 第一行包含一个数，表示最短的连接管道长度。

hint:
对于 $100\%$ 的数据，$2\le n\le50000$，$0\le x_i,y_i,x_j,y_j\le100000$

------

## 样例解释：
![](https://cdn.luogu.com.cn/upload/image_hosting/rwhyfbkm.png)


title: [JSOI2009] 面试的考验

description:
求区间最接近且不相等的两数之差的绝对值。

**注：最接近指数值上最接近**

inputFormat:
第一行输入两个整数 $N,Q$，分别代表序列的长度和询问的个数。

第二行包含 $N$ 个由一个空格分开的正整数，代表了整个序列，从左向右依次编号为 $A_1, A_2……A_n$。

接下来 $Q$ 行，每行两个整数 $i,j$ 表示了一个询问区间。

输入数据保证 $1\le i<j\le N$。

outputFormat: 对于每一个询问输出一行，为所问区间中最接近两个数之差的绝对值。

hint:
对于 $100\%$ 的数据，$1\le N,Q\le10^5,1\le A_i\le10^9$。

数据为全部**纯随机**生成。


title: [JSOI2010] 下棋问题

background: 有一个新的益智游戏。

description:
该游戏由 A 和 B 两人轮流在一个 $1000000\times1000000$ 的方格棋盘上的网格线交点下棋，网格线交点的坐标以 $(x,y)$ 表示，$(0, 0)$ 代表棋盘最左下角的点。

每一个棋子放置的位置不可以与任何其它棋子在同一 $X$ 坐标或 $Y$ 坐标上，棋盘上新增加一个棋子时，棋盘上的计数器会自动算出以目前棋盘上棋子所能够围成的 `无障碍四方形` 个数。

`无障碍四方形` 是指以任意两个棋子所定义出的四方形内部不含其它棋子，每下一个棋子后所算出的 `无障碍四方形` 个数即为下该棋子的得分数。每位下棋者的总分即是该下棋者每个所下棋子的得分数总和。

请写一个程序计算 A 和 B 两位下棋者的累计总分。

inputFormat:
第一行输入只有一个整数 $n$，代表此盘棋共下了 $n$ 个棋子。

接下来的 $n$ 行，每一行有两个整数，依序代表这 $n$ 个棋子所放置的位置。

outputFormat: 请输出两个整数，分别代表该盘棋两位下棋者的累计得分数。A 的分数在前，B 的分数在后，中间用一个空格隔开。


title: [CEOI1999] Parity Game

description: Alice 和 Bob 在玩一个游戏：他写一个由 $0$ 和 $1$ 组成的序列。Alice 选其中的一段（比如第 $3$ 位到第 $5$ 位），问他这段里面有奇数个 $1$ 还是偶数个 $1$。Bob 回答你的问题，然后 Alice 继续问。Alice 要检查 Bob 的答案，指出在 Bob 的第几个回答一定有问题。有问题的意思就是存在一个 $01$ 序列满足这个回答前的所有回答，而且不存在序列满足这个回答前的所有回答及这个回答。

inputFormat:
第 $1$ 行一个整数 $n$，是这个 $01$ 序列的长度。

第 $2$ 行一个整数 $m$，是问题和答案的个数。

第 $3$ 行开始是问题和答案，每行先有两个整数，表示你询问的段的开始位置和结束位置。然后是 Bob 的回答。`odd`表示有奇数个 $1$，`even` 表示有偶数个 $1$。

outputFormat: 输出一行，一个数 $x$，表示存在一个 $01$ 序列满足第 $1$ 到第 $x$ 个回答，但是不存在序列满足第 $1$ 到第 $x+1$ 个回答。如果所有回答都没问题，你就输出所有回答的个数。

samples:
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd


title: [POI1999] 地图

background: 一个人口统计办公室要绘制一张地图。

description:
由于技术的原因只能使用少量的颜色。两个有相同或相近人口的区域在地图应用相同的颜色。例如一种颜色 $k$，则 $A(k)$ 是相应的数，则有：
- 在用颜色$k$的区域中至少有一半的区域的人口不大于 $A(k)$。
- 在用颜色$k$的区域中至少有一半的区域的人口不小于 $A(k)$。

区域颜色误差是该区域的人口与 $A(k)$ 差的绝对值。累计误差是所有区域颜色误差的总和。我们要求出一种最佳的染色方案，使得累计误差最小。

inputFormat:
第一行有一个整数 $n$，表示区域数。

在第二行中的数 $m$ 表示颜色数。

在接下来的  $n$ 行中每行有一个非负整数，表示一个区域的人口。

人口都不超过 $2^{30}$。

outputFormat: 输出一个整数，表示最小的累计误差。


title: [清华集训2012] 串珠子

description:
铭铭有 $n$ 个十分漂亮的珠子和若干根颜色不同的绳子。现在铭铭想用绳子把所有的珠子连成一个整体。

现在已知所有的珠子互不相同，用整数 $1$ 到 $n$ 编号。对于第 $i$ 个珠子和第 $j$ 个珠子，可以选择不用绳子连接，或者在 $c_{i,j}$ 根不同颜色的绳子中选择一根将它们连接。如果把珠子看作点，把绳子看作边，将所有珠子连成一个整体即为所有点构成一个连通图。特别地，珠子不能和自己连接。

铭铭希望知道总共有多少种不同的方案将所有珠子连成一个整体。由于答案可能很大，因此只需输出答案对 $1000000007$ 取模的结果。

inputFormat: 输入第一行包含一个正整数 $n$，表示珠子的个数。接下来 $n$ 行，每行包含 $n$ 个非负整数，用空格隔开。这 $n$ 行中，第 $i$ 行第 $j$ 个数为 $c_{i,j}$。

outputFormat: 输出一行一个整数，为连接方案数对 $1000000007$ 取模的结果。


title: [POI1999] 降水

background: 遥远的地方有一块土地。

description:
它被划分成 $N\times M$ 个正方形小块，每块面积是一平方英寸，第 $i$ 行第 $j$ 列的小块可以表示成 $P(i,j)$ 。这块土地高低不平，每一小块地 $P(i,j)$ 都有自己的高度 $H(i,j)$ （单位是英寸）。

一场倾盆大雨后，这块地由于地势高低不同，许多低洼地方都积存了不少降水。假如你已经知道这块土地的详细信息，你能求出它最多能积存多少立方英寸的降水么？

inputFormat:
输入文件第一行有两个数 $N,M$，表示土地的规模是 $N\times M$ 平方英寸。

以下有 $N$ 行，每行有 $M$ 个整数，表示每块地的高低（每个整数在 $[1,10000]$ 内，以英寸为单位）。

outputFormat: 输出只有一行一个数，表示土地中最多能积存多少立方英寸的水。


title: [清华集训2012] 最小生成树

description: 给定一个边带正权的连通无向图 $G=(V,E)$，其中 $N=|V|,M=|E|$，$N$ 个点从 $1$ 到 $N$ 依次编号，给定三个正整数 $u,v$ 和 $L(u\ne v)$，假设现在加入一条边权为 $L$ 的边 $(u,v)$，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？

inputFormat:
第一行包含用空格隔开的两个整数，分别为 $N$ 和 $M$；

接下来 $M$ 行，每行包含三个正整数 $u,v$ 和 $w$ 表示图 $G$ 存在一条边权为 $w$ 的边 $u,v$。

最后一行包含用空格隔开的三个整数，分别为 $u,v$ 和 $L$；

数据保证图中没有自环。

outputFormat: 输出一行一个整数表示最少需要删掉的边的数量。

hint:
#### 样例解释
我们只需把边 $(1,2)$ 删除即可，删除并加入新边之后，图中的生成树唯一。

#### 数据规模与约定
对于 $20\%$ 的数据满足 $N\leqslant10,M\leqslant20,L\leqslant20$；

对于 $50\%$ 的数据满足 $N\leqslant300,M\leqslant3000,L\leqslant200$；

对于 $100\%$ 的数据满足 $N\leqslant20000,M\leqslant200000,L\leqslant20000$。


title: [清华集训2012] 攻占黄金乡

background: 《海猫鸣泣之时》EP8 终于在今年暑假的末尾出了汉化，作为整个作品中高人气人物古户绘梨花，自然也是在剧中大活跃。在攻占黄金乡的战役中担任了指挥官一职，而整个战役过程也都被记录在了图书之都中，方便后来人的复盘。

description:
当时的战况如下，黄金乡可以看做是一个长方体空间，我们用 $(0,0,0)\sim(n-1,m-1,k-1)$ 表示里面的每一个单位区域，绘梨花指挥了 $t$ 艘不同等级的战舰依靠魔法突然出现在了黄金乡的 $t$ 个不同的区域，之后从战舰上便源源不断地涌出山羊们。每一个单位时刻，山羊们会从自己所在的区域向四周 $6$ 个方向扩展一个区域（如果那个相邻的区域已经被占领了，就不扩展），如果两队山羊在同一时刻想占领同一区域，那么等级高的山羊优先占领。

没过多久，黄金乡就变成了一片山羊海，但是作为指挥官的绘梨花却因茫茫多的山羊而找不到战舰所在的位置了，于是她将问题交给了身边的你——山羊君，作为一个急于立下战功然后回故乡找山羊子的青年将领，你自然不会放弃这个机会，于是很快就找到了战舰所在的位置，你的这份功绩自然也会被记录到图书之都的文书之中。

inputFormat:
第一行一个数 $test$，表示数据组数，以下 $test$ 部分。

每部分第一行 $3$ 个数 $n,m,k$，以下 $n$ 部分，每部分为 $m$ 行 $k$ 列的字符矩阵。

第 $i$ 部分表示区域 $(i,0,0)\sim(i,m-1,k-1)$ 中的战况。

不同等级的山羊我们用不同的小写英文字母表示，字典序越小的字母表示山羊等级越高。

相邻部分之间用空行隔开。

outputFormat:
输出 $test$ 部分，每部分用空行隔开。

每部分有 $t$ 行，$t$ 为该组数据中战舰的数目，每行格式为
```plain
ch x y z
```
表示编号为 $ch$ 的战舰的位置为 $(x,y,z)$。

战舰输出顺序无关，如果有多解，输出任意解即可。

samples:
2
1 2 2
dd
gg

3 3 3
aaa
aaa
baa

aaa
aaa
baa

aaa
aaa
bcc

hint:
#### 数据规模和约定
测试点 $1\sim3$：$n=1,n\times m\times k\leqslant10$

测试点 $4\sim6$：$n=1,n\times m\times k\leqslant100$

测试点 $7\sim10$：$n=1,n\times m\times k\leqslant500$

测试点 $11\sim20$：$n\times m\times k\leqslant1500$

对于所有数据 $test\leqslant10,t\leqslant26$


title: [POI1999] 多边形之战

background: 多边形之战是一个双人游戏。

description:
游戏在一个有 $n$ 个顶点的凸多边形上进行，这个凸多边形的 $n-3$ 条对角线将多边形分成 $n-2$ 个三角形，这 $n-3$ 条对角线在多边形的顶点相交。

三角形中的一个被染成黑色，其余是白色。双方轮流进行游戏，当轮到一方时，他必须沿着画好的对角线，从多边形上切下一个三角形。切下黑色三角形的一方获胜。

- 注：如果连接一个多边形中任意两点的线段都完全包含于这个多边形，则称这个多边形为凸多边形。

inputFormat:
第一行是一个整数 $n$。表示多边形的顶点数，多边形的顶点从 $0$ 到 $n-1$ 顺时针标号。

接着的 $n-2$ 行描述组成多边形的三角形。第 $i+1$ 行， $1 \le i \le n-2$，有三个空格分隔的非负整数 $a, b, c$，它们是第 $i$ 个三角形的顶点编号，第一个给出的三角形是黑色的。

outputFormat:
唯一一行应包含一个单词：

- `TAK`，表示先走的一方有必胜策略。
- `NIE`，表示先走的一方没有必胜策略。


title: [POI1999] 飞弹

background: 一场战争在 U 国与 A 国之间爆发了。

description:
U国的负责情报的长官得知，A 国在边界上已经事先布置了 $N$ 个坚实的地堡，这些地堡组成的防御体系将对 U 国的士兵构成极大的威胁！ U 国国防部不得不在进攻之前先摧毁这些地堡！

为了出奇制胜， U 国国防部决定：布置在边界的每一个飞弹发射点负责消灭一个地堡。

为了给敌人一个措手不及，$N$ 个飞弹发射点将同时发射飞弹，每个飞弹均以直线全速前进，争取在短时间内给地堡群造成毁灭性的打击。

但是，由于这些飞弹是地对地电子制导型的，两颗飞弹的飞行路线如果相交，电子信号将会互相干扰，从而偏离预定目标。

作为军事顾问，国防部需要你来设计一个作战方案，事先确定每个飞弹点负责哪一个地堡，并且在所设计的方案中，飞弹的飞行线路不相交。

情报部门已经将飞弹发射点和地堡的位置明确标在地图上，并保证这 $2\times N$ 个坐标点不存在三点共线。

inputFormat:
第一行是一个数 $N$，表示飞弹发射点的个数，也是敌方地堡的个数。

以下 $N$ 行，每行两个整数 $x$ 和 $y$（在 $[-10000,10000]$ 内），第 $i+1$ 行表示第 $ i$ 个飞弹发射点的坐标。
再下面 $N$ 行，每行两个整数 $x$ 和 $y$ （在 $[-10000,10000]$ 内），第 $N+i+1$ 行表示第 $i$个地堡的坐标。

outputFormat: 输出文件有 $N$ 行，每行为一个整数。第 $i$ 行的整数 $P_i$ 表示，第 $i$ 个飞弹发射点负责消灭第 $P_i$ 个地堡。


title: [POI1999] 祭坛问题

background:
在中国民间，人们相信鬼只能沿直线移动。

在修建寺庙时，那是非常重要的。

description:
寺庙要修建在四边分别平行于南北西东的矩形位置之上。两个矩形不能有公共交点。

入口位于四堵墙中一堵的中间，门的宽度等于墙长度的一半。祭坛出现在寺庙的中间，矩形的对角线在那里相交。

鬼魂在这个点出现，那么寺庙被亵渎，当且仅当存在从祭坛射出的一束光线，通过入口到外面而且不与其他寺庙（位于建筑区域平行的地带）的墙壁相交或接触，这种情形才可能发生，也就是能在建筑区域从祭坛到无穷远处画一条直线而不碰到任何墙。

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

在接下来的 $n$ 行的每一行有一个寺庙的描述（在第 $i$ 行有第 $ i$ 个寺庙的描述）。

寺庙的描述由四个非负的不大于 $8000$ 的整数和字母 $E,W,S$ 和 $ N$ 组成。头两个数字是寺庙的西北角的坐标，接下来的两个是相对的东南角的坐标。

描述的第五个元素代表入口的墙`（E-东，W-西，S-南，N-北）`。寺庙的描述元素由单空格隔开。

outputFormat: 接下来的几行，你的程序应该按升序写下可能被鬼魂亵渎的寺庙编号。每一个编号占一行。如果没有编号则输出 `BRAK`。

hint:
对于 $100\%$ 的数据，$1 \le n \le 1000$。

----

### 样例解释：

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


title: [POI1998] 折线

description:
给定二维直角坐标系。

我们要求一条折线只能从左边到右边一笔画过去，并且折线的每一段和 $x$ 轴的夹角在 $[-45°, 45°]$ 之间。

一条满足上述要求的折线被称为：平直折线。

给定坐标系上的 $n$ 个格点，最少需要画多少条平直折线才能覆盖所有的点呢？

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

接下来的 $n$ 行为每个点的坐标 $(x, y)$ 。

outputFormat: 最少需要多少条平直折线。


title: [POI1997] 跳

background: 在一个无限长的棋盘上玩一种跳棋游戏。

description:
其中棋盘被划分成许多区域，每一个区域中可以放置多个的棋子。

规定某一个区域的编号为 $0$，在它开始往左边连续的区域编号为 $-1,-2,-3,…,$在它的右边连续区域编号为 $1,2,3,…,$ ，若区域 $P$ 有棋子，那么棋子有两种跳法：

- 向左跳：则方格 $P-1$ 和 $ P-2 $ 中应增加一枚棋子，方格 $P$ 中应减少一枚棋子。

- 向右跳：则方格 $P$ 和 $P+1$ 中应减少一枚棋子，方格 $P+2$ 中应增加一枚棋子。

对于给定的初始棋局，经过若干步跳棋后，总可以找到一种目标，就是任意两个相邻的区域棋子数目不超过 $1$ 。

你的任务是对给定的一种初始棋局，找到最终的目标棋局。

inputFormat:
第一行为一个正整数 $n$， 表示棋盘中放置棋子的状态数。

下面的 $n$ 行描述了每个状态，由两个用空格分隔的整数组成，第一个整数表示区域的位置（不超过 $10000$），第二个整数表示该区域放置的棋子数目（不超过 $100000000$）。

outputFormat: 输出最终的棋局，这一行包含若干个整数，其中每一个整数为有棋子的区域编号，所有的区域按从小到大排列。


title: [POI1997] ADDON

background: 科学家们发现了一种新的放射性元素——`ADDON`。`ADDON` 是已知的效率最高的核燃料，因此他们决定建立一个 `ADDON` 核反应堆。

description:
根据计划，一间燃料室是一根竖直的管子。燃料棒（即装有 `ADDON` 的圆筒）将一根叠一根的被放进燃料室里，搭建成一个圆柱。燃料棒具有不同的高度。

核反应循环开始于将燃料棒放进燃料室中。接下来的步骤才是点火。麻烦的是，圆柱的高度不能是任意的——只有某些特定的高度才能保证反应的安全。这样的高度被称作稳定高度。

现在，反应堆的设计师们面临着两个任务：确定燃料室的高度以及选择一个用于制造 `ADDON` 的燃料棒的高度集合。

我们说一个高度集合是安全的（对于一个特定高度的燃料室），则有：

- 对于任意一根由高度属于这个集合的燃料棒搭建而成的，且高度不超过燃料室的高度的圆柱，它的高度一定是稳定的。

我们说一个高度集合是完备的（对于一个特定高度的燃料室），则有：

- 对于任意一根高度是稳定的,并且其高度不超过燃料室高度的圆柱，都一定能够由高度属于该集合的燃料棒搭建而成。

现在要写一个程序：
- 1. 读入一个稳定高度的集合；
- 2. 找出存在一个安全且完备的高度集合的核燃料室的最大可能值；
- 3. 对于找到的核燃料室，找出一个元素个数最少的安全且完备的高度集合；
- 4. 将结果输出。

inputFormat:
第一行是一个自然数 $n$，代表所给的稳定高度的个数。

接下来的 $n$ 行，每行是一个不超过 $10000$ 的正整数。这些数按照升序给出，代表了稳定高度。

outputFormat:
第一行是找到的燃料室高度的最大可能值。

接下来的每行按照升序给出你所找到的高度集合中的一个元素。


title: [POI2002] 敌对球迷

background: 在一个信息王国里决定在两个敌对的球队： LINUKS 和 MICROSOFT 之间举行球赛。

description:
由于两个球队的球迷结怨甚深，所以要将他们安排在两个距离尽量遥远的城市里，而且只允许他们从电视中看球赛。

信息王国是个岛国，它所有的城市都建在海岸上。沿着海岛周边有一条双向的环行公路。有两种方法可以从每一个城市到达另一个城市：顺时针和逆时针方向。这种双向环行公路方案中较短的距离是城市之间的距离。

现在，你需要计算出把敌对球迷分隔的最大距离。

inputFormat:
第一行输入一个正整数 $n$，表示海岛上城市的数目。

在接下来的 $n$ 行中输入相邻城市间环行公路的长度。每一行中包含了一个整数。

第 $i+1$ 行为 $i$ 的城市和编号为 $i+1$ 的城市之间公路段的长度，第 $n+1$ 行为城市 $n$ 和城市 $1$ 之间路程的长度。
环行公路的总长度不超过 $10^9$。

outputFormat: 一行一个数表示可以将球迷分隔的最大距离。


title: [POI2002] 最大的园地

description: 在一个 $n\times n$ 的正方形内找到最大的由 `0` 组成的矩形，输出它的面积。

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

接下来的 $n$ 行，每行 $n$ 个数，描述这个正方形。

outputFormat: 输出其中最大的由 `0` 组成的矩形的面积。


title: [POI2002] 出圈游戏

description:
有编号从 $1$ 到 $n$ 的 $n$ 个小朋友在玩一种出圈的游戏,编号为 $i+1 $ 的小朋友站在编号为 $i $ 小朋友左边。编号为 $1 $ 的小朋友站在编号为 $n$ 的小朋友左边。首先编号为 $1$ 的小朋友开始报数，接着站在左边的小朋友顺序报数，直到数到某个数字 $K$ 时就出圈。直到所有的小朋友都出圈，则游戏完毕。

现在给出出圈的顺序，求最小的 $K$。

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

第二行有 $n$ 个整数 $a_i$。其中第 $i$ 个整数表示编号为 $i$ 的小朋友第 $a_i$ 个出圈。

outputFormat: 求最小的 $K$，如果不存在，则输出一个单词 `NIE`。

hint:
对于 $100\%$ 的数据，$2\le n\le 20$。

---

$\text{upd 2022.8.24}$：新增加一组 Hack 数据。


title: [POI2002] 协议

background: Z 在一个通讯公司工作。 目前他承担了公司的网络协议设计任务。

description:
目前他致力于通过一条电缆从一台电脑向另一台电脑发送数据。

在这条电缆中有 $k$ 种不同的电平， 每秒电平会变化 $\frac{1}{n}$ 次 (我们称 $\frac{1}{n}$ 秒为一个脉冲)。 一个数据包包含 $m$ 个连续的脉冲。(即每 $\frac{m}{n}$ 秒发送一个数据包)。

由于技术原因, 每个包里的电平不能一直稳定为一个常数, 而是需要多次改变。 严格地讲, 包含连续 $l$ 个电平相同的脉冲的数据包将不能被发送。 注意相邻两个数据包互不影响。

如果可能被发送的数据包共有 $x$ 种， 那么单个数据包会包含 $log_2x$ 位信息(可以为一个小数)。Z 想知道在 $1$ 秒内最多能发送多少位信息。

inputFormat: 输入一行四个整数：电平种类 $k$， 脉冲频率 $n$， 单个数据包大小 $m$， 在一个数据包中不能连续保持相同电平的脉冲的数目 $l$， 在这个范围内电平至少要改变一次。

outputFormat: 输出一个整数，为一秒内最大能发送信息的位数，答案向下取整。

hint: 对于 $100\%$ 的数据，$2 \le k \le 10$，$1 \le n \le 1000$，$ 1 \le m \le 100$，$2 \le l \le m$，$\frac{n}{m}$ 是一个不超过 $10$ 的整数。


title: [POI2002] B-Smooth 数

description:
$B$ 是一个正整数。

 如果一个自然数 $n$ 被称为 B-smooth 数,那么它的质因子中没有任何一个超过 $B$。

我们说和 $n$ 等价的一个 B-smooth 数是指它能够表示成小于或等于  $B$ 的正整数乘积。

你的任务是对给定的闭区间 $[n,n+m]$，求出他们中的 B-smooth 数的个数。

inputFormat: 第一行是三个整数 $n,m$ 和 $B$。

outputFormat: 求出 B-smooth 数的个数。


title: [POI2003] Trinomial

description: 求 $(x^2+x+1)^n$ 的第 $i$ 项系数。

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

接下来的 $k$ 行，每行两个整数 $n,i$。

outputFormat: 对于每组数据，输出 $x_i \bmod 3$ 之后的结果。


title: [POI2003] Chocolate

description:
有一块 $n\times m$ 的矩形巧克力，准备将它切成 $n\times m$ 块。

巧克力上共有 $n-1$ 条横线和 $m-1$ 条竖线，你每次可以沿着其中的一条横线或竖线将巧克力切开，无论切割的长短，沿着每条横线切一次的代价依次为 $y_1,y_2,…,y_{n-1}$，而沿竖线切割的代价依次为 $x_1,x_2,…,x_{m-1}$。

例如，对于下图 $6\times4$的巧克力：

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

我们先沿着三条横线切割，需要 $3$ 刀，得到 $4$ 条巧克力，然后再将这 $4$ 条巧克力沿竖线切割，每条都需要 $5$ 刀，则最终所花费的代价为 $y_1+y_2+y_3+4\times (x_1+x_2+x_3+x_4+x_5)$。

当然，上述简单切法不见得是最优切法，那么怎样切割该块巧克力，花费的代价最少呢？

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

接下来 $n-1$ 行，每行一个整数，分别代表 $x_1,x_2,…,x_{n-1}$。

接下来 $m-1$ 行，每行一个整数，分别代表 $y_1,y_2,…,y_{m-1}$。

outputFormat: 输出一整数，为切割巧克力的最小代价。


title: [BalticOI 2006] coin collector钱币收藏家

description:
有一个国家，流通着 $n$ 种面值的硬币，其中包括了1分硬币。另外，有一种面值为 $K$ 分的纸币，它超过了所有硬币的面值。 有一位硬币收藏家，他想收集每一种面值的硬币样本。他家里已经有一些硬币，但是现在他只带着一张 $K$ 分纸币去商店。 商店里总共有 $K-1$ 种商品，价格分别为 $1$ 分、$2$ 分…… $K-1$ 分。

这家商店使用以下算法找零：
1.假设总共需要找 $A$ 分；
2.寻找最高的不超过 $A$ 的硬币面值，设它为 $B$ 分硬币；
3.给顾客一枚 $B$ 分硬币，然后令 $A$ 为 $A-B$；
4.如果 $A=0$，算法结束；否则转2。

收藏家想用他的 $K$ 分纸币买一件商品。请你编写程序，计算：收藏家能够得到多少种他还没有过的硬币? 在满足上一问的前提下，他能够买的最贵的商品是什么?

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

以下 $n$ 行描述各种流通的硬币的面值和是否已收藏状态。第 $i+1$ 行包含整数 $C_i\ (1\le C_i<k)$ 和 $d_i$，$C_i$ 表示第 $i$ 种硬币的面值。若 $d_i=1$，收藏家已经有硬币 $C_i$，若 $d_i=0$，收藏家还没有硬币 $C_i$。输入按照硬币面值递增顺序，也就是 $C_1<C_2<…<C_n$，第一枚硬币是 $1$ 分硬币，也就是 $C_1=1$。

outputFormat:
输出第一行为一个整数，表示收藏家最多能获得多少种之前还没有的硬币。

第二行为一个整数，表示在前一问的前提下，收藏家能购买的最贵的商品价格。

hint: 对于所有数据，$1\le n\le 5\times 10^5$，$2\le k\le 10^9$。


title: [BalticOI 2000] Division expression

description:
除法表达式有如下的形式:

$X_1/X_2/X_3.../X_n$ ，其中 $X_i$ 是正整数且 $X_i\le 10^9$， 除法表达式应当按照从左到右的顺序求。

例如表达式 $1/2/1/2$的值为 $1/4$。

但可以在表达式中加入括号来改变计算顺序，例如 $(1/2)/(1/2)$ 的值为 $1$.现给出一个除法表达式 $E$，求是告诉是否可以通过增加括号来使其结果为整数。

inputFormat:
第一行一个整数 $D$，代表有 $D$ 组数据。

每组数据先给出一个数字 $N$，代表这组数据将有 $N$ 个数。

接下来每行有 $N$ 个数。

outputFormat: 如果能使得表达式的值为一个整数，则输出 `YES` ，否则为`NO`。


title: [BOI2000] Stickers

description:
Charles 在商店里买了很多很多盒装的不干胶，所有不干胶上都印着 $0-9$ 中的某个数字。

每个盒里装的各种不干胶数目都一样：有 $i_0$个数字 $0$，$ i_1$ 个数字 $1 ,…,i_9$ 个数字 $9$，且每盒中各种数字的不干胶数目都不超过 $9$。

最开始，所有的盒子都是关着的，Charles 每次打开一个新的盒子，然后从已经打开的盒子中取出需要的不干胶拼成一个数，第一次拼成 $1$ ，第二次拼成 $2$ …第N次拼成 $N$ 。为了拼成数 $N$，Charles需要为N的每一个数字使用一张不干胶。

例如，再打开第 $2070$ 的盒子以后，为了拼成数 $2070$ ，它需要从已经打开的盒子（无论是以前打开的还是这次打开的）中取出一个 $2$，两个 $0$ 和一个 $7$。

取出的不干胶可以在之后使用。如果某次打开了一个盒子以后无法拼成相应的数，Charles 就停止工作。给出 $i_0,i_1,i_2,…,i_9$ 的值，编程计算 Charles 一共能拼出多少个数。例如，如果每盒中有各种数字的不干胶恰一张，则 Charles 一共可以拼出 $199990$ 个数。

inputFormat: 输入包含 $10$ 个 $1$ 位整数：$i_0, i_1, i_2, i_3, i_4, i_5, i_6, i_7, i_8, i_9$，其中 $i_j$ 表示在每个盒子中，写着数字 $j$ 的不干胶的数目。

outputFormat: 输出能拼出多少个数。


title: [BalticOI 2004] ships 船

description:
有一个由 $n\times n$ 的正方形组成的“船”的游戏棋盘。每个单元格可能属于某艘船(黑色)或为空。如果两个边相邻的单元格都是黑色，那么这两个单元格属于同一艘船。不同船之间没有公共边。船的吨位是这些相邻的单元格数。

下边样例，棋盘中(黑色)的单元格属于船，共有一艘 $29$ 吨的船，三艘 $7$ 吨的船，二艘 $4$ 吨的船，三艘 $1$ 吨的船。

![样例](https://cdn.luogu.com.cn/upload/image_hosting/uk57lz80.png?x-oss-process=image/resize,m_lfit,h_170,w_225)

请写一个程序，对给定的游戏棋盘计算出每艘船的吨位和数量。

inputFormat:
第一行包含一个整数 $n$ 表示游戏棋盘的大小。

以下 $n$ 行，第 $i+1$ 行描述第 $i$ 行的列（船）的信息，中间用一个逗号分隔：
如果是单独一个数，那么这一列属于船，这列的左、右单元格是空的；
如果是```-```连接的两个数，表示这两列之间的所有格子（包含这两列）都属于船，则左侧和右侧是空的。
数据之间用逗号分隔，每行结尾的分号。行中没有空格。如果某行只有一个分号，则这行没有船的信息。

outputFormat: 你的程序必须输出船的信息。每行是一个空格分隔的两个整数。第一个数是船的吨位，第二个数是这个吨位的船只数量。必须以递减顺序输出船的吨位，并且至少有一艘船有此吨位。

hint: 对于所有的数据，$1\le n\le 3\times 10^4$，船舶总数和船舶吨位都不超过 $10^3$。


title: [BOI2003] Barrel

background: 大水池子。

description:
给定一个水池的底面积 $S$ 和高 $H$。

现在其中有体积为 $V$ 的水量，放入 $n$ 个立方体，给出每个立方体的棱长和密度，请你求出水池中水池的高度。

注：此处我们忽视空气的任何作用力， 认为正方体之间互不接触且不会在水中旋转， 且认为水的密度为 $1$。

inputFormat:
第一行三个整数 $S,H,V$。

第二行为一个整数 $n$。

接下来的 $n$ 行，每行两个实数，为这个立方体的棱长和密度。

outputFormat: 输出最终水面的高度。答案误差不超过 $10^{-7}$ 即可。


title: [BalticOI ?] Card 卡牌游戏【来源请求】

description:
你手上有 $n$ 张卡牌，要求将其填入框中，使得结果最小。

每张卡有两面：即每张卡有两个数字。$6$ 不能当作 $9$ 使用，同理，$9$ 也不能当作 $6$ 使用。

框与框之间有计算符号。计算符号以 `-` 和 `+` 间隔。

例如：当 $n=8$ 时，填入的框格式为：-O+O-O+O-O+O-O+O。

填入卡牌时，不一定需要按照卡牌和框的顺序进行填写（即可以进行位置的调换）。

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

接下来 $n$ 行：每行两个整数 $A_i$ 和 $B_i$，分别表示每张卡牌的正面和反面。

outputFormat: 一行一个整数，表示最小结果。

hint:
样例一的解释：

框的格式为：-O+O-O+O-O+O。

第一个框将第一张卡牌的 $4$ 填入；第二个框将第六张卡牌的 $-8$ 填入；
第三个框将第三张卡牌的 $7$ 填入；第四个框将第五张卡牌的 $-3$ 填入；
第五个框将第四张卡牌的 $5$ 填入；第六个框将第二张卡牌的 $-7$ 填入。

此时可以得到的结果为 $-34$ 是最小的。

---

对于 $30\%$ 的数据，满足 $n\leq 8$ 。
对于 $100\%$ 的数据，满足 $n\leq 528360$ 且 $|A_i|,|B_i|\leq 10^7$。


title: [POI2018]Plan metra

description:
有一棵 $n$ 个点的无根树，每条边有一个正整数权值，表示长度，定义两点距离为在树上的最短路径的长度。

已知 $2$ 到 $ n-1$ 每个点在树上与 $1$ 和 $n$ 的距离，请根据这些信息还原出这棵树。

inputFormat:
第一行包含一个正整数 $n$，表示点数。

第二行包含 $n-2$ 个正整数 $d(1,2),d(1,3),...,d(1,n-1)$，分别表示每个点到 $1$ 的距离。

第三行包含 $n-2$ 个正整数 $d(n,2),d(n,3),...,d(n,n-1)$，分别表示每个点到 $n$ 的距离。

outputFormat:
若无解，输出 `NIE`。

否则第一行输出`TAK`，接下来 $n-1$ 行每行三个正整数 $u,v,c$，表示存在一条长度为 $c$ 的连接 $u$ 和 $v$ 两点的树边。

若有多组解，输出任意一组即可。

**本题使用 Special Judge。**


title: [POI2018] 水箱

description:
在地面上有一个水箱，它的俯视图被划分成了 $n$ 行 $m$ 列个方格，相邻两个方格之间有一堵厚度可以忽略不计的墙，水箱与外界之间有一堵高度无穷大的墙，因此水不可能漏到外面。已知水箱内每个格子的高度只能是 $[0,H]$ 之间的整数，请统计有多少可能的水位情况。

因为答案可能很大，请对 $10^9+7$ 取模输出。

我们说两种情况是不同的当且仅当存在至少一个方格的水位在两个情况中不同。

inputFormat:
第一行包含三个正整数 $n,m,H$。
接下来 $n$ 行，每行 $m-1$ 个整数$ a[i][j](1\le a[i][j]\le H)$，表示 $(i,j)$ 和 $(i,j+1)$ 之间的墙的高度。

接下来 $n-1$ 行，每行 $m$ 个整数 $b[i][j](1\le b[i][j]\le H)$ ，表示 $(i,j)$ 和 $(i+1,j)$ 之间的墙的高度。

outputFormat: 输出一行一个整数，即方案数模 $10^9+7$ 的结果。

hint:
对于 $100\%$ 的数据，$n\times m\le500000$，$1\le H\le10^9$。

----

### 样例解释：

要么全部格子水位都是 $2$，要么全部格子水位都在 $[0,1]$ 之间，共 $1+2^6=65$ 种情况。


title: [POI2018] Różnorodność

description: 给定一个 $n$ 行 $m$ 列的矩阵，请对于每个长宽均为 $k$ 的连续子正方形，统计里面出现过的数值的种类数。

inputFormat:
第一行包含三个正整数 $n,m,k$
接下来 $n$ 行，每行 $m$ 个正整数 $a[i][j](1<=a[i][j]<=100000)$ ，表示矩阵中每个位置的数值。

outputFormat:
输出一行两个整数 $M$ 和 $ S$。
设 $f(i,j)$ 表示以 $(i,j)$ 为左上角的正方形内出现过的数值的种类数，则 $M$ 表示 $f$ 的最大值，$ S$ 表示 $f$ 的总和。


title: [POI2018] Pionek

description: 在无限大的二维平面的原点 $(0,0)$ 放置着一个棋子。你有 $n$ 条可用的移动指令，每条指令可以用一个二维整数向量表示。每条指令可以执行 $1$ 次或者不执行。棋子可以重复经过同一个点，两条指令的方向向量也可能相同。你的目标是让棋子最终离原点的**欧几里得距离**最远，请问这个最远距离是多少？

inputFormat:
第一行包含一个正整数 $n$，表示指令条数。

接下来 $n$ 行，每行两个整数 $x,y$，表示你可以从 $(a,b)$ 移动到 $(a+x,b+y)$。

outputFormat: 输出一行一个整数，即最大距离的平方。

hint:
对于 $100\%$ 的数据，$n\le 2 \times 10^5$，$|x|,|y| \le 10^4$。

-----

### 样例解释：

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


title: [POI2017] Flappy Bird

background: `《飞扬的小鸟》` 是一款风靡的小游戏。

description:
在游戏中，小鸟一开始位于 $(0,0)$ 处，它的目标是飞到横坐标为 $X$ 的某个位置上。

每一秒，你可以选择点击屏幕，那么小鸟会从 $(x,y)$ 飞到 $(x+1,y+1)$，或者不点击，那么小鸟会飞到 $(x+1,y-1)$。

在游戏中还有 $n$ 个障碍物，用三元组 $(x_i,a_i,b_i)$ 描述，表示在直线 $x=x_i$ 上，$y\le a_i$ 或者 $y\ge b_i$ 的部分都是障碍物，碰到或者擦边都算游戏失败。

现在，请你求出小鸟从 $(0,0)$ 飞到目的地最少需要点击多少次屏幕。

inputFormat:
第一行包含两个整数 $n,X$。
接下来 $n$ 行，每行三个整数 $x_i,a_i,b_i$。数据保证 $x_i<x_{i+1}$。

outputFormat: 如果无论如何都飞不到目的地，输出 `NIE`，否则输出点击屏幕的最少次数。

hint:
对于 $100\%$ 的数据，$0\le n\le 500000$，$1\le X\le10^9$，$0<x_i<X$，$-10^9\le a_i<b_i\le 10^9$。

-------

### 样例解释：
![](https://cdn.luogu.com.cn/upload/image_hosting/9lse80af.png)


title: [POI2017] Podzielno

description: $B$ 进制数，每个数字 $i \in [0,B)$ 有 $a_i$ 个。你要用这些数字组成一个最大的 $B$ 进制数 $X$(不能有前导零，不需要用完所有数字)，使得 $X$ 是 $B-1$ 的倍数。 $q$ 次询问，每次询问 $X$ 在 $B$进制下的第 $k$ 位数字是什么(最低位是第 $0$ 位)。

inputFormat:
第一行包含两个正整数 $B,q$。

第二行包含 $B$ 个正整数 $a_0,a_1,a_2,...,a_{B-1}$。

接下来 $q$ 行，每行一个整数 $k$，表示一个询问。

outputFormat: 输出 $q$ 行，每行一个整数，依次回答每个询问，如果那一位不存在，请输出 `-1`。


title: [POI2017] Sabotaż

description:
某个公司有 $n$ 个人, 上下级关系构成了一个有根树。其中有个人是叛徒(这个人不知道是谁)。

对于一个人, 如果他下属(直接或者间接, 不包括他自己)中叛徒占的比例超过 $x$，那么这个人也会变成叛徒，并且他的所有下属都会变成叛徒。你要求出一个最小的 $x$，使得最坏情况下，叛徒的个数不会超过 $k$。

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

接下来 $n-1$ 行，第 $i$ 行包含一个正整数 $p_{i+1}$，表示 $i+1$ 的父亲是 $p_{i+1}$。

outputFormat:
输出一行一个实数 $x$，误差在 $10^{-6}$ 以内都被认为是正确的。

**所以本题使用 SPJ。**

hint:
对于 $100\%$ 的数据，$1\le k\le n\le 500000$，$1\le p_{i+1}\le i$。

-----

### 样例说明：

答案中的 $x$ 实际上是一个无限趋近于 $\frac{2}{3}$ 但是大于 $\frac{2}{3}$ 的数。

因为当 $x$ 取 $\frac{2}{3}$ 时，最坏情况下 $3,7,8,9$ 都是叛徒，超过了 $k=3$。


title: [POI2017] Turysta

description:
给出一个 $n$ 个点的有向图，任意两个点之间有且仅一条有向边。

对于每个点 $v$，求出从 $v$ 出发的一条经过点数最多，且没有重复经过同一个点两次及两次以上的简单路径。

inputFormat:
第一行包含一个正整数 $n$，表示点数。

接下来的 $n-1$ 行，其中的第 $i$ 行有 $i-1$ 个数。

如果第 $j$ 个数是 $1$，那么表示有向边 $j\rightarrow i+1$ ，如果是 $0$，那么表示有向边 $j\leftarrow i+1$。

outputFormat:
输出 $n$ 行，第 $i$ 行首先包含一个正整数 $k$，表示从 $i$ 点出发的最优路径所经过的点数。

接下来 $k$ 个正整数，依次表示路径上的每个点。

若有多组最优解，输出任意一组。

**本题使用 SPJ （Claris 制作）**


title: [PA2019] A+B

description:
在列竖式计算两个十进制数的和的时候，人们可能会错算成这样：

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

在图里的左边，$248+208$ 被错算成了 $4416$。

给定正整数 $n$，问有多少对非负整数 $a,b$ 满足 $a+b$ 会被错算成 $n$。

请注意 $a$ 可以等于 $b$，且 $a=1,b=2$ 和 $a=2,b=1$ 是两种不同的方案。

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

outputFormat: 输出一个整数，即满足条件的 $a,b$ 的数量。


title: 【模板】线段树分裂

description:
给出一个可重集 $a$（编号为 $1$），它支持以下操作：

`0 p x y`：将可重集 $p$ 中大于等于 $x$ 且小于等于 $y$ 的值移动到一个新的可重集中（新可重集编号为从 $2$ 开始的正整数，是上一次产生的新可重集的编号+1）。

`1 p t`：将可重集 $t$ 中的数放入可重集 $p$，且清空可重集 $t$（数据保证在此后的操作中不会出现可重集 $t$）。

`2 p x q`：在 $p$ 这个可重集中加入 $x$ 个数字 $q$。

`3 p x y`：查询可重集 $p$ 中大于等于 $x$ 且小于等于 $y$ 的值的个数。

`4 p k`：查询在 $p$ 这个可重集中第 $k$ 小的数，不存在时输出 `-1`。

inputFormat:
第一行两个整数 $n,m$，表示可重集中的数在 $1\sim n$ 的范围内，有 $m$ 个操作。

接下来一行 $n$ 个整数，表示 $1 \sim n$ 这些数在 $a$ 中出现的次数 $(a_{i} \leq m)$。

接下来的 $m$ 行每行若干个整数，第一个数为操作的编号 $opt$（$0 \leq opt \leq 4$），以**题目描述**为准。

outputFormat: 依次输出每个查询操作的答案。

hint:
对于 $30\%$ 的数据，$1\leq n \leq {10}^3$，$1 \le m \le {10}^3$；
对于 $100\%$ 的数据，$1 \le n \le 2 \times {10}^5$，$1 \le x, y, q \le m \le 2 \times {10}^5$。保证数据合法。

不开 `long long` 见祖宗！！

---

题面 by @[Limit](https://www.luogu.com.cn/user/86625)

std by @[Limit](https://www.luogu.com.cn/user/86625)（线段树分裂）

验题 by @[Froggy](https://www.luogu.com.cn/user/100285)（平衡树，不过合并的复杂度假掉了，倒数第二个测试点就是 hack 数据）

数据 by @[Froggy](https://www.luogu.com.cn/user/100285)


title: [POI2017] Reprezentacje ró?nicowe

description:
给定一个数列 $a$：
- 当 $n\le 2$ 时，$a_n=n$。
- 当 $n>2$，且 $n$ 是奇数时， $a_n=2\times a_{n-1}$。
- 当 $n>2$，且 $n$ 是偶数时，$a_n=a_{n-1}+r_{n-1}$。

其中 $r_{n-1}= \operatorname{mex}(|a_i-a_j|)(1\le i\le j\le n-1)$， $\operatorname{mex} \left\{ S\right\}$ 表示最小的不在 $S$ 集合里面的非负整数。

数列 $a$ 的前若干项依次为：

$1,2,4,8,16,21,42,51,102,112,224,235,470,486,972,990,1980$。

可以证明，对于任意正整数 $x$，只存在唯一一对整数 $(p,q)$ 满足 $x=a_p-a_q$，定义为 $\operatorname{repr}(x)$。

比如 $\operatorname{repr}(17)=(6,3)$，$\operatorname{repr}(18)=(16,15)$。
现有 $n$ 个询问，每次给定一个正整数 $x$，请求出 $\operatorname{repr}(x)$。

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

接下来 $n$ 行，每行一个正整数 $x$，表示一个询问。

outputFormat: 输出 $n$ 行，每行两个正整数 $ p,q$，依次回答每个询问。


title: [POI2016] Hydrorozgrywka

description:
给定一个 $n$ 个点 $m$ 条边的无向连通图，保证每条边最多属于一个环。

两个人在这张图上玩游戏，一开始他们会在某个节点放一个棋子，然后依次移动这个棋子，已经走过的边不能再走，谁不能移动谁就输了。

请求出所有先手必胜的策略中游戏开始时放棋子的位置。

inputFormat:
第一行包含两个正整数 $ n,m$，表示点数和边数。

接下来 $m$ 行每行包含两个正整数 $a,b$，表示 $a$ 点到 $b$ 点之间有一条无向边。

outputFormat: 包含 $n$ 行，对于第 $i$ 行，如果在 $i$ 点放棋子先手必胜，输出 `1`，否则输出 `2`。

hint: 对于 $100\%$ 的数据，$3\le n,m\le 5 \times 10^5$，$1\le a,b\le n$，$a\ne b$。


title: [POI2016] Korale

description:
有 $n$ 个带标号的珠子，第 $i$ 个珠子的价值为 $a_i$。

现在你可以选择若干个珠子组成项链（也可以一个都不选），项链的价值为所有珠子的价值和。

给出所有可能的项链排序，先按权值从小到大排序，对于权值相同的，根据所用珠子集合的标号的字典序从小到大排序。

请输出第 $k$ 小的项链的价值，以及所用的珠子集合。

inputFormat:
第一行包含两个正整数 $n,k$。
第二行包含 $n$ 个正整数，依次表示每个珠子的价值 $a_i$。

outputFormat:
第一行输出第 $k$ 小的项链的价值。
第二行按标号从小到大依次输出该项链里每个珠子的标号。


title: [POI2016] Nadajniki

description:
比特镇一共有 $n$ 个房子，编号依次为 $1$ 到 $n$，这些房子通过 $n-1$ 条无向道路连通在一起，形成了一棵树的结构。

Bytesear 要在比特镇实施 Wifi 搭建计划，他要让 Wifi 覆盖到比特镇的每一条道路。

Bytesear 可以安置无限多个 Wifi 发射器，但是只能安置在树上的节点上，一个房子可以安置多个 Wifi 发射器。

对于一条道路 $(a,b)$，如果它满足以下两个条件之中的至少一个，那么这条边将被 Wifi 覆盖：
- $a$ 点放置了 Wifi 发射器或者 $b$ 点放置了 Wifi 发射器。
- 与 $a$ 点或 $b$ 点直接相邻的点中，至少放置了两个 Wifi 发射器。

请帮助 Bytesear 规划一个最优的放置方案，使得 Wifi 覆盖到比特镇的每一条道路，且放置的 Wifi 发射器总数尽可能少。

inputFormat:
第一行包含一个正整数 $n$，表示房子的总数。

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

outputFormat: 输出一行一个整数，即最少的 Wifi 发射器总数。

hint:
对于 $100\%$ 的数据，$2\le n\le2 \times 10^5$，$1\le a,b\le n$。

----

### 样例解释：

在 $3$ 号点放置两个 Wifi 发射器。


title: [POI2016] Nim z utrudnieniem

description:
A 和 B 两个人玩游戏，一共有 $m$ 颗石子，A 把它们分成了 $n$ 堆，每堆石子数分别为 $a_1,a_2,...,a_n$，每轮可以选择一堆石子，取掉任意颗石子，但不能不取。谁先不能操作，谁就输了。在游戏开始前，B 可以扔掉若干堆石子，但是必须保证扔掉的堆数是 $d$ 的倍数，且不能扔掉所有石子。

A 先手，请问 B 有多少种扔的方式，使得 B 能够获胜。

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

第二行包含 $n$ 个正整数 $a_1,a_2,...,a_n$。

outputFormat: 输出一行一个整数，即方案数对 $10^9+7$ 取模的结果。

hint: 对于 $100\%$ 的数据，$1\le n\le 5\times 10^5$，$1\le d\le 10$，$1\le a_i\le 10^6$，$m$ 不直接给出，但数据保证 $1\le m\le 10^7$。


title: [POI2016] Park wodny

description:
给出一个 $n\times n$ 的四连通的网格图，每个格子要么是 `A`，要么是 `B`，保证 `B` 的连通块的形状都是矩形。

现在你最多可以把两个 `A` 变成 `B`，问最大的 `B` 的连通块有多大。

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

接下来 $n$ 行，每行 $n$ 个字符，表示这个网格图。

outputFormat: 输出一行一个整数，即最大的 `B` 的连通块的大小。


title: [PA2019] Desant

description:
给定一个 $1$ 到 $n$ 的排列 $a_{1..n}$，它有 $2^n-1$ 个非空子序列。

请对于每个 $k$，找到一个长度为 $k$ 的子序列，使得这个子序列的逆序对数量最少，并输出逆序对数量最少的子序列的数量。

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

第二行包含 $n$ 个正整数 $a_1,a_2,...,a_n$。

outputFormat: 输出 $n$ 行，每行两个整数，第 $k$ 行输出长度为 $k$ 的子序列中逆序对数量的最小值以及满足这个最小值的子序列数量。

hint: 对于 $100\%$ 的数据，$1\le k\le n$，$1\le n\le 40$，$1\le a_i\le n,a_i\ne a_j$。


title: [PA2014] Druzyny

description:
体育课上，$n$ 个小朋友排成一行（从 $1$ 到 $n$ 编号），老师想把他们分成若干组，每一组都包含编号连续的一段小朋友，每个小朋友属于且仅属于一个组。

第 $i$ 个小朋友希望它所在的组的人数不多于 $d_i$，不少于 $c_i$，否则他就会不满意。

在所有小朋友都满意的前提下，求可以分成的组的数目的最大值，以及有多少种分组方案能达到最大值。

inputFormat:
第一行一个整数 $n$，表示小朋友的数目。

接下来 $n$ 行，每行两个整数 $c_i,d_i$，表示 $i$ 所在组的人数的最小值和最大值。

outputFormat:
如果不存在这样的方案，仅输出一行  `NIE`。

否则输出一行包含两个整数，组的数目的最大值、方案数量。（方案数量对 $10^9+7$ 取模）

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


title: [PA2019] Herbata

description:
你有无穷多个容量无限的杯子以及 $n$ 杯水，第 $i$ 杯水的体积为 $l_i$，温度为 $a_i$。

你可以做无限次操作，每次操作是下面两种操作之一：
1. 选择一杯水，假设它的体积为 $V$，温度为 $T$，那么你可以将其倒入若干个空杯中，使得每一杯的水的温度都为 $T$，且体积之和等于 $V$，注意体积可以是任意非负实数。

2. 选择两杯水，假设一杯的体积为 $V_a$，温度为 $T_a$，另一杯的体积为 $V_b$，温度为 $T_b$，那么你可以将这两杯水混合为一杯体积为 $V_a+V_b$，温度为 $\dfrac{V_a*T_a+V_b*T_b}{V_a+V_b}$的水。

你的目标进行若干次操作，使得操作完毕后，对于所有的 $i(1\le i\le n)$ 都有第 $i$ 杯水的体积等于 $l_i$，温度等于 $b_i$。请写一个程序判断是否有解。

inputFormat:
第一行包含一个正整数 $T$，表示测试数据的组数。
每组测试数据第一行包含一个正整数 $n$。
接下来 $n$ 行，每行三个正整数 $l_i,a_i,b_i$。

outputFormat: 对于每组数据输出一行，如果有解，输出 `TAK`，否则输出 `NIE`。


title: [PA2019] Iloczyny Fibonacciego

description:
定义斐波那契数列为 $F_1=1,F_2=2,F_i=F_{i-1}+F_{i-2}(i\ge 3)$。
对于任意一个正整数 $x$，我们总能将 $x$ 写成唯一的斐波那契表示 $(b_1,b_2,...,b_n)$，满足：

1. $b_1\times F_1+b_2\times F_2+...+b_n\times F_n=x$。
2. 对于任意的 $i(1\le i<n)$ 都有 $b_i=0$ 或 $b_i=1$；对于 $b_n$ 有 $b_n=1$。
3. 对于任意的 $i(1\le i<n)$ 都有 $b_i\times b_{i+1}=0$。

比如 $2=(0,1),4=(1,0,1),5=(0,0,0,1),20=(0,1,0,1,0,1)=F[2]+F[4]+F[6]=2+5+13$。

给定两个斐波那契表示的正整数 $A$ 和 $B$，请输出 $A\times B$ 的斐波那契表示。

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

每组测试数据包含两行，分别描述 $A$ 和 $B$ 的斐波那契表示。每行首先是一个正整数 $n$，然后 $n$ 个非负整数 $b_1,b_2,...,b_n$。

outputFormat: 对于每组数据输出一行，按照输入格式输出 $A\times B$的斐波那契表示。

hint: 对于 $100\%$ 的数据，$1\le T\le 10^3$，输入数据保证所有的 $n$ 加起来不超过 $10^6$。


title: [PA2019] Trzy kule

description:
对于两个长度为 $n$ 的 $01$ 串 $a_{1..n},b_{1..n}$，定义它们的距离 $\operatorname{d(a,b)}=|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|$。

给定三个长度为 $n$的 $01$ 串 $s_1,s_2,s_3$以及三个非负整数 $r_1,r_2,r_3(0\le r_i\le n)$，问有多少个长度为 $n$ 的 $01$ 串 $S$满足$\operatorname{d(S,s[1])}\le r_1,\operatorname{d(S,s[2])}\le r_2,\operatorname{d(S,s[3])}\le r_3$ 这三个不等式中至少有一个成立。

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

第二行一个非负整数 $r_1$，然后一个长度为 $n$ 的 $01$ 串 $s_1$。

第三行一个非负整数 $r_2$，然后一个长度为 $n$ 的 $01$ 串 $s_2$。

第四行一个非负整数 $r_3$，然后一个长度为 $n$  的 $01$ 串 $s_3$。

outputFormat: 输出一行一个整数，即满足条件的 $S$ 的数量模 $10^9+7$。


title: [PA2019] Osady i warownie 2

description:
$n\times m$ 的网格，从上到下依次为第 $0$ 到 $n-1$ 行，从左到右依次为第 $0$ 到 $m-1$ 列，每个点都不是障碍格。

定义一条从起点 $(0,0)$ 到终点 $(n-1,m-1)$ 的路径是合法的，当且仅当这条路径经过恰好 $n+m-1$ 个格子(包括起点和终点)，且每一步要么往右走一格，要么往下走一格。当然，这条路径不能经过障碍格(包括起点和终点)。

你有一个 $int$ 变量 $v=0$，你现在需要模拟 $k$ 次操作，每次操作会给出三个非负整数 $r,c,z$，令 $x=(r \operatorname{xor}
 v)\bmod n,y=(c \operatorname{xor}
 v)\bmod m$：
1. 如果 $(x,y)$ 是障碍格，那么忽略这次操作，输出 `NIE`。
2. 否则如果将 $(x,y)$ 变成障碍格后仍然存在合法路径，那么将 $(x,y)$ 变成障碍格，输出 `NIE`。
3. 否则如果将 $(x,y)$ 变成障碍格后不存在合法路径，那么输出 `TAK`，并将 $v $ 修改为 $v \operatorname{xor} z$。

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

接下来 $k$ 行，每行三个非负整数 $r,c,z$。

outputFormat: 对于每个操作输出一行 `TAK` 或 `NIE`。

hint:
对于 $100\%$ 的数据,$2\le n,m\le 10^5$， $1\le k\le 10^6$，$0\le r,c,z<2^{20}$。

----

### 解释：

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


title: [PA2019] Podatki drogowe

description:
给定一棵 $n$ 个点的无根树，点的编号为 $1$ 到 $n$。
定义 $u$ 到 $v$ 的距离 $\operatorname{d(u,v)}$ 为 $u$ 和 $v$在树上的简单路径经过的边的边权之和。

给定 $k$，请在 $\dfrac{n\times (n-1)}{2}$ 个 $\operatorname{d(u,v)}(1\le u<v\le n)$ 中找到第 $k$ 小的值。

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

接下来 $n-1$ 行，每行三个正整数 $x,y,z(1\le x,y,z\le n)$，表示一条连接 $x$ 和 $y$ 的树边，其边权为 $n$ 的 $z$ 次方。

outputFormat: 输出一行一个整数，即第 $k$ 小的值对 $10^9+7$ 取模的结果。


title: [PA2019] Muzyka pop

description:
给定 $ n$ 个整数 $a_{1..n}$，请找到 $n$ 个非负整数 $b_{1..n}$，使得 $a_1\times \operatorname{f(b_1)}+a_2\times \operatorname{f(b_2)}+...+a_n\times \operatorname{f(b_n)}$ 的值最大，其中 $\operatorname{f(x)} $ 为 $x$ 在二进制下的 $1$ 的个数。

你找到的这 $n$ 个非负整数 $b_{1..n}$ 需要满足 $0\le b_1<b_2<...<b_n\le m$。

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

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$。

outputFormat: 输出一行一个整数，即 $a_1\times \operatorname{f(b_1)}+a_2\times \operatorname{f(b_2)}+...+a_n\times \operatorname{f(b_n)}$ 的最大值。


title: [PA2019] Szprotki i szczupaki

description:
在湖中有 $n$ 条小鱼，第 $i$ 条小鱼的重量为 $w_i$。

共 $q$ 个操作，每个操作是下面 $3$ 种之一：

- `1 s k` 假如现在来了一条重量为 $s$ 的大鲨鱼，它的目标是让自己的重量达到至少 $k$ (包含 $k$)，问它至少需要吃掉多少条小鱼？如果鲨鱼当前的重量严格大于要吃掉的小鱼的重量 $w$，那么它可以吃掉这条小鱼，并使得自己的重量增加 $w$。
- `2 w` 添加一条重量为 $w$ 的小鱼。
- `3 w` 删除一条重量为 $w$ 的小鱼，保证存在至少一条这样的小鱼。

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

第二行 $n$ 个正整数 $w_1,w_2,...,w_n$。

第三行一个正整数 $q$。

接下来 $q$ 行，每行若干个整数，描述一个操作。

outputFormat: 对于每个询问，如果有解，输出一行一个整数，即最少需要吃掉的小鱼数量，如果无解，输出 `-1`。


title: [PA2019] Terytoria

description:
在二维平面直角坐标系上，有一个长度为 $X$，宽度为 $Y$ 的地图，注意这个地图的左边界和右边界是连通的，下边界和上边界也是连通的。

在这个地图里，有 $X\times Y$ 个格子以及 $n$ 个边平行坐标轴的矩形。你只知道每个矩形两个对顶点的坐标，请问在最好情况下，被所有 $n$ 个矩形都覆盖住的格子数量有多少？

outputFormat: 输出一行一个整数，即被所有 $n$ 个矩形都覆盖住的格子数量的最大可能值。

hint:
对于 $100\%$ 的数据，$1\le n\le 5\times 10^5$，$2\le X,Y\le 10^9$。

### 样例解释：

下图列举了一些情况，其中第3种情况是最优的：

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


title: [PA2019] Wyspa

description:
比特岛位于海上，在比特岛的中心有一个内陆湖。

在比特岛一共有 $n$ 个点，编号为 $1$ 到 $n$，其中 $1$ 到 $a$ 的点按照顺时针或者逆时针表示内陆湖边上的点， $a+1$ 到 $a+b$ 的点按照顺时针或者逆时针表示比特岛海岸线上的点， $a+b+1$ 到 $n$ 的点表示既不在湖边也不在海边的点。

这些点之间连着 $m$ 条单向或双向道路。每条道路不会经过湖、海或者任意一个点；任意两点间只会连着最多一条道路；这些道路中不存在“天桥”或者“地下隧道”，任意两条道路只可能在端点处相交。换言之，这是一张平面图。并且从任意一个湖边的点出发，都能沿着这些道路直接或间接地到达至少一个海边的点。

现在要在 $b$ 个海边点中选择若干个点作为港口，问有多少种选点的方案使得任意一个湖边的点都能到达至少一个港口？

inputFormat:
第一行四个正整数 $n,m,a,b$。

接下来 $m$ 行描述 $m$ 条道路，每行要么是 `u -- v` 要么是 `u -> v`($1\le
u,v\le n,u\ne v$)：

如果是“`u -- v`，表示这是一条连接 $u$ 和 $v$的双向道路。

如果是 `u -> v`，表示这是一条从 $u$出发到达 $v$的单向道路。

outputFormat: 输出一行一个整数，即满足条件的方案数模 $10^9+7$。

hint:
对于 $100\%$ 的数据，$2\le n\le 5\times 10^5$，$1\le m\le 10^6$，$1\le a,b\le n,2\le a+b\le n$。

---

### 样例解释：

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

$6$ 号点必选， $4$ 和 $5$ 可选可不选，因此有 $4$种方案。


title: [PA2019] Wina

description:
 $n$ 行 $\dfrac{n\times(n+1)}{2}$ 个数叠成了一个数塔。

给定 $k$，你需要从中拿走恰好 $k$ 个数，使得拿走的数的最小值最小。一个数能被拿走当且仅当它左上角和右上角都没有数或者那个数已经被拿走了。

inputFormat:
第一行两个正整数 $n,k$。
接下来 $n$ 行，第$i$行 $i$个正整数 $a[i][1],a[i][2],...,a[i][i](1\le a[i][j]\le 2019)$，表示从上往下第 $i$ 行从左往右第 $j$ 个数。

outputFormat: 输出一行一个整数，即拿走的数的最小值的最小值。

hint:
对于 $100\%$ 的数据，$1\le n\le 2000$，$1\le k\le \dfrac{n\times(n+1)}{2}$。

### 样例解释：

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


title: [PA2015] Kieszonkowe

description:
给定 $n$ 个数，请从中选出若干个数，使得总和为偶数。

请最大化这个总和。

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

第二行包含 $n$ 个正整数$a_1,a_2,...,a_n$。

outputFormat: 输出一个正整数，即最大的总和，若无解则输出 `NIESTETY`。


title: [PA2015] Równanie

description:
对于一个正整数 $n$，定义 $\operatorname{f}(n)$ 为它十进制下每一位数字的平方的和。

现在给定三个正整数 $k,a,b$，请求出满足 $a\le n\le b$ 且 $k\times \operatorname{f}(n)=n$ 的 $n$ 的个数。

inputFormat: 第一行包含三个正整数 $k,a,b$。

outputFormat: 输出一个整数，即满足条件的 $n$ 的个数。


title: [PA2015] Rozstaw szyn

description:
给定一棵有 $n$ 个点， $m$ 个叶子节点的树，其中 $m$ 个叶子节点分别为 $1$ 到 $m$ 号点，每个叶子节点有一个权值 $r_i$。

你需要给剩下 $n-m$ 个点各指定一个权值，使得树上相邻两个点的权值差的绝对值之和最小。

inputFormat:
第一行包含两个正整数 $n,m$，分别表示点数和叶子数。

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

接下来 $m$ 行，每行一个正整数，依次为 $r_1,r_2,...,r_m$，表示每个叶子的权值。

outputFormat: 输出一个整数，即树上相邻两个点的权值差的绝对值之和的最小值。

hint: 对于 $100\%$ 的数据，$2\le n\le 5\times 10^5$，$1\le m\le n$，$1\le u,v\le n$，$1\le r_i\le 5\times 10^5$。


title: [PA2014] Iloczyn

description:
斐波那契数列的定义为：

- $k=0$ 或 $1$ 时， $F_k=k$；

- $k>1$ 时，$F_k=F_{k-1}+F_{k-2}$。

数列的开头几项为 $0,1,1,2,3,5,8,13,21,34,55,…$。

你的任务是判断给定的数字能否被表示成两个斐波那契数的乘积。

inputFormat:
第一行包含一个整数 $T$，表示询问数量。

接下来的 $T$ 行，每行一个整数 $n_i$。

outputFormat: 输出共 $T$ 行，第 $i$ 行为 `TAK`（是）或 `NIE`（否），表示 $n_i$ 能否被表示成两个斐波那契数的乘积。


title: [PA2014] Kuglarz

description:
魔术师的桌子上有 $n$ 个杯子排成一行，编号为 $1,2,…,n$，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。

花费 $c_{ij}$ 元，魔术师就会告诉你杯子 $i,i+1,…,j$ 底下藏有球的总数的奇偶性。

采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？

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

第 $i+1$ 行（$1\le i\le n$）有 $n+1-i$ 个整数，表示每一种询问所需的花费。

其中 $c_{ij}$（对区间 $[i,j]$ 进行询问的费用，$1\le i\le j\le n$）为第 $i+1$ 行第 $j+1-i$ 个数。

outputFormat: 输出一个整数，表示最少花费。


title: [PA2014] Lustra

description:
Byteasar 公司专门外包生产带有镜子的衣柜。

刚刚举行的招标会上，有 $n$ 个工厂参加竞标。所有镜子都是长方形的，每个工厂能够制造的镜子都有其各自的最大、最小宽度和最大、最小高度。镜子不可以旋转。

如果存在某家工厂满足这样的条件：其他所有工厂能够制造的镜子，它都能够制造。那么这家工厂显然会胜出。若不存在，评判工作将会遇到麻烦。

Byteasar 想知道，是否存在某家工厂符合上述条件。

inputFormat:
第一行有一个整数 $t$，表示测试数据数量。

对于每一组测试数据，第一行有一个整数 $n$。

接下来 $n$行，每行有四个整数 $w1,w2,h1,h2$，表示这家工厂能够制造的镜子的宽度 $w$、高度 $h$ 需要满足 $w_1\le w\le w_2,h_1\le h\le h_2$。

outputFormat: 输出共有 $t$ 行，每行为 `TAK` (是)或 `NIE` (否)，表示是否存在某家工厂符合条件。


title: [PA2014] Muzeum

description:
吉丽的漫展有 $n$ 件手办和 $m$ 名警卫。

现在我们对其建立平面直角坐标系，每个手办和警卫都可以看做一个点。警卫们的目光都朝着 $y$ 轴负方向，且都有相同大小的视角。警卫可以看见自己视角内（包括边界上的点）的所有手办，不用考虑视线的遮挡。

你打算抢劫吉丽的漫展，但不想被警卫发现。为了实施这次抢劫计划，你可以事先贿赂某些警卫，让他们闭上眼睛。只要某件手办不在任何睁着眼睛的警卫的视野内，你就可以偷走它。你知道每件手办的价格，以及每位警卫需要接受多少钱的贿赂。你想知道自己的最大收益是多少。

inputFormat:
第一行两个整数 $n,m$，分别表示手办的数量和警卫的数量。

第二行两个整数 $w,h$，表示每个警卫的视角的一半的正切值是 $\dfrac{w}{h}$。（见配图）

接下来 $n$ 行，每行三个整数 $x_i,y_i,v_i$，表示手办的坐标为 $(x_i,y_i)$，价格为 $v_i$。

接下来 $m$ 行，格式同上，表示警卫的坐标为 $(x_i,y_i)$，需接受贿赂的金额为 $v_i$。

**保证每个点最多只有一个手办或一个警卫。**

outputFormat: 输出仅一行表示最大收益。

hint:
对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5$，$1\le w,h\le 10^9$，$-10^9\le x_i,y_i\le 10^9$，$1\le v_i\le 10^9$。

----

### 样例解释：

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

贿赂 售价为 $3+6=9$ 元的两个警卫，偷走 价值共$2+8+4+1=15$ 元的 $4$ 个手办，收益 $15-9=6$ 元。


title: [PA2014] Pakowanie

description: 你有 $n$ 个物品和 $m$ 个包。物品有重量，且不可被分割；包也有各自的容量。要把所有物品装入包中，至少需要几个包？

inputFormat:
第一行两个整数 $n,m$，表示物品和包的数量。

第二行有 $n$ 个整数 $a_1,a_2,…,a_n$，分别表示物品的重量。

第三行有 $m$个整数 $c_1,c_2,…,c_m$，分别表示包的容量。

outputFormat:
如果能够装下，输出一个整数表示最少使用包的数目。

若不能全部装下，则输出 `NIE`。


title: [PA2014] Plemiona

description:
远古时代，在吉丽王国的版图上分布着 $n$ 个部落。建立平面直角坐标系后，每个部落都是一个边平行于坐标轴的矩形。有些地盘可能同时属于多个部落。随着时间推移，部落之间会发生融合。具体来说，若两个部落的公共面积严格大于零，它们会合并成一个新的部落，新部落的形状是包含原来两个部落的最小矩形（边平行于坐标轴）。

数百万年后，部落之间终于达到了稳定状态（任两个部落都不能再合并了），然而吉丽也已经老了。他想知道最终还剩下几个部落，以及各个部落的位置。你能替他完成遗业吗？

inputFormat:
第一行一个整数 $n$，表示远古时代的部落数量。

接下来 $n$ 行，每行四个整数 $x_1,x_2,y_1,y_2$，表示部落的坐标。

outputFormat:
第一行输出一个整数 $m$，表示稳定后还剩下的部落数量。
接下来 $m$ 行，每行四个整数 $x_1,x_2,y_1,y_2$，表示部落的坐标。

请按照字典序（先比较 $x_1$，若 $x_1$ 相等则比较 $x_2$，以此类推）从小到大输出。


title: [CEOI2016] kangaroo

description:
有一个园子，里面有 $n$ 个草丛排成一排，标号 $1\sim n$，有一个袋鼠，从 $s$ 出发，每次跳一步跳到一个其他的草丛，经过每个草丛恰好一次，最终到达 $t$。显然他会跳跃 $n-1$次为了不被人类发现，袋鼠每次跳跃的方向必须与前一次不同。

具体地，如果他现在在 $now$，他是从 $prev $ 跳跃一次到达 $now$ 的，然后他跳跃一次到达 $next$：

- 那么如果 $prev<now$，就必须有 $next<now$；

- 如果 $now<prev$，就必须有 $now<next$。

问从 $s$ 到 $t$ 的方案数模 $10^9+7$的结果。

两个路线不同，当且仅当草丛被访问的顺序不同。

保证至少有一种方案初始时可以往任意方向跳。

inputFormat: 一行三个整数 $n,s,t$。

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

hint: 对于 $100\%$ 的数据，$2\le n\le 2\times 10^3$，$1\le s,t\le n$


title: [CEOI2016] match

description:
给你一个由小写字母组成的字符串 $s$，要你构造一个字典序最小的（认为左括号的字典序比右括号小）合法的括号序列与这个字符串匹配。

字符串和括号序列匹配定义为：首先长度必须相等，其次对于一对匹配的左括号和右括号 $i,j$，必须有 $s_i=s_j$。

无解输出 `-1`。

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

outputFormat: 一行一个括号序列或者 `-1`。

samples: abbaaa (()())


title: [CEOI2016] popeala

description:
你办了一场比赛，有 $n$ 个人参加，只有一道题，有 $m$ 个数据点，标号为 $1\sim m$，每个测试点都有一个分数 $a_i$。

现在所有选手已经提交了程序并且测评完了，你知道每个人都能通过哪些测试点。

你现在要安排捆绑测试的方式，把数据点划分为若干个连续的区间，每个区间至少有一个测试点。每个区间只要有一个测试点错误就不会得分，如果所有
点都正确得分为所有测试点的分数的和。

**你的目的是最小化所有人的得分和**。你需要对 $1\le i\le S$，输出当把所有测试点划分为 $i$ 组时，最小的所有人分数和。

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

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

接下来 $n$ 行每行一个长度为 $m$ 的 $01$ 串，代表第 $i$ 个人是否通过了第 $j$ 个测试点。

outputFormat: $S$ 行，每行一个整数，代表当划分为 $i$ 个捆绑测试点时所有人分数和的最小值。

hint: 对于 $100\%$ 的数据，$1\le n\le 50$，$1\le m\le 2\times 10^4$，$S\le \min(50,m)，1\le a_i \le 10^4$，$\Sigma a_i\times n\le 2\times10^9$。


title: [CEOI2018] Global warming

description: 给定 $n$，你可以将任意 $a_l$ 至 $a_r$($1\le l\le r\le n$)每一个元素加上一个 $d$($-x\le d\le x$), 求 $a$ 数组的最大严格上升子序列长度。

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

第二行 $n$ 个整数表示 $a_1$ 至 $a_n$。

outputFormat: 一个数,即 $a$ 数组的最大严格上升子序列长度。


title: [CEOI2008] Fence

description:
在一个大小为 $1000\times 1000$ 的区域中，有 $n$ 个固定点, $m$ 棵树 。

现在你要建一个围栏来保护树，建它的费用为你选用的固定点的个数 $\times 20$ +你没有圈进围栏的树 $\times 111$。

现在希望这个值越小越好，求最小值。

inputFormat:
第一行给出 $n,m$。

接下来的 $n$ 行，给出固定的坐标。

接下来的 $m$ 行，给出树的坐标。

outputFormat: 输出最小费用。

hint:
对于 $100\%$ 的数据，$3\le N,M\le 100$。

----

## 样例解释：

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


title: [CEOI2008] Dominance

description:
给出一个宽为 $W$，高为 $H$ 的矩形 。

在它上面有两种点， $black$ 及 $white$。 每个点都有自己的辐射范围。对于其它的点如果它受到白点的辐射多于黑色的，则为白点，反之亦然，如果相同的话则中立。

现给出白点及黑色的坐标及各自的辐射范围，问最后白色点一共有多少个，黑色点共有多少个 。

inputFormat:
第一行给出 $W$ 和 $H$，左下角坐标为 $(0,0)$, 右上角为 $(W-1,H-1)$。

第二行给出数字 $N$，代表有多少个点。

接下来 $N$ 行，每行先给出点的属性，再给出坐标，再给出辐射范围(在$[0, 5\times 10^8)$)

outputFormat: 两个数，分别代表白色点有多少个，黑色点有多少个 。

hint:
对于 $100\%$ 的数据，$1 \le  W,H \le 10^9$，$0 \le  N \le  3\times 10^3$。

-----

### 样例解释：

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


title: [CEOI2009] photo

description: 平面上有若干个点，现在要求用最少的底边在 $X$ 轴上且面积小于等于 $A$ 的矩形覆盖所有点，这些矩形可以重叠。

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

以下 $N$ 行输入点坐标。

outputFormat: 最少的矩形个数。

hint:
对于 $100\%$ 的数据，$1\le N\le 100$，$1\le A\le 2\times 10^6$。

------

## 样例解释：

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


title: [CEOI2006] ANTENNA

description: 给出 $N$ 个点的坐标，要求能够覆盖其中至少 $K$ 个点的圆的最小半径及圆心位置。

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

接下来的 $N$ 行，每行两个整数，为每个点的坐标。

outputFormat:
第一行为圆的半径。

第二行为圆心的坐标。

使用 SPJ，满足以下两个条件才正确：

- $R$ 误差不超过 $10^{-4}$。

- 虽然多组解可以输出任意一组，但以你输出的坐标为圆心的圆如果以 $R+0.0002$为半径至少应该覆盖 $K$个点。


title: [PA2013] Iloczyn

description: 给定正整数 $n$ 和 $k$，问能否将 $n$ 分解为 $k$ 个不同正整数的乘积。

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

接下来 $T$ 行每行两个数 $n,k$。

outputFormat: 输出 $T$ 行,若可以被分解,输出 `TAK` 否则输出 `NIE`。


title: 千年食谱颂

background:
$$\texttt{事在人    命在天}$$
$$\texttt{亘古滔滔转眼间}$$
$$\texttt{唯席上}$$
$$\texttt{千年丰盛永不变}$$

  “阿绫，今天是我的第 $15$ 个 $15$ 岁生日呀！”
  “哦……阿绫今天回不了家嗷。”
  早晨九点，迷迷糊糊睁开双眼的小灰毛悄悄用手戳了戳自己的身旁，却只感受到枕头的淡淡的温暖。
  “明明是人家的生日嘛，又要加班……”把手机扔在一边，叠好被子，走近床边，垂着手轻轻拨开窗帘，刺眼的阳光轻易地冲散了另一个人的温度。
  “好无聊啊！”
  就这样熬到了晚上，却发现冰箱已经空空如也。要不……去美食节转转？
  今天正好是魔都一年一度的美食节，本来以为阿绫会陪自己，天依可是做好了无比详细的攻略。但现在，阿绫不在，计划也随之落空。穿一身清凉的休闲装，带上钱包，天依还是决定，不能在食物上辜负自己！
  天依的手才刚刚搭上门把手，轻轻一拉，便猛然打开，竟被恋人拥入怀中……
  星光，灯火，美食，还有……天依小小的舌头轻轻舔着蓝莓味的甜筒，一边悄悄打量着身旁的恋人。修长的身段优雅从容地迈着步子，头顶标志性的红色呆毛就像那希望的烛光闪烁，漫天灯火，在那暗红色的明眸里缓缓流动……阿绫转过身，目光撞上那双碧绿的眼眸。
  “天依，天依。想什么呢？”
  看着恋人害羞地撇过脸，耳根子却不争气地红了起来，阿绫又动起了坏心思。她慢慢靠近恋人的脸庞，轻轻嘬了一口粉嫩的嘴唇。
  “干嘛啦阿绫，这里那么多人……”嘴上这么说着，天依却又不自觉地凑向阿绫。阿绫牵起恋人的手。“走，带你把这儿吃个遍！”

description:
美食节上一共有 $n$ 个店铺，初始 ( 第 $0$ 时刻 ) 时天依都没有品尝过。天依的 flag 是将它们尽数品尝。所以**从第一个时刻起**，天依会在每一个时刻**等概率地选取 $n$ 个店铺中的一个品尝**。不过，由于食客众多，许多店铺会出现食材短缺的情况而不得不中途撤场。**当一个店铺撤场后，会有一个新的 ( 以前从未出现的 ) 店铺立即进场**，我们称其为一次**撤场事件**。阿绫知道所有撤场事件会在**相邻两个时刻间**发生，且每个店铺在每个时刻间撤场的概率都是 $p$。

天依凑过毛茸茸的脑袋问阿绫：“期望在第几个时刻，在场的 $n$ 个店铺都被我品尝过呢？”

inputFormat: 一行三个整数 $n,a,b$，表示有 $n$ 个店铺，撤场概率 $p=\dfrac{a}{b}$。

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

**由于答案可能是一个小数，为了避免损失精度，请输出答案对 $998244353$ 模意义下的值。**

hint:
#### 数据范围
对于不同的测试点，我们约定如下数据规模及其性质：

|             测试点编号              | $n \leq$ | 特殊性质 1 | 特殊性质 2 |
| :---------------------------------: | :------: | :--------: | :--------: |
|           $1 \sim 2$            |  $500$   | $\sqrt{}$  |     $\times$      |
|  $3 \sim 8$   |  $500$   |     $\times$      |     $\times$      |
|         $9 \sim 11$          |  $3000$  |     $\times$      | $\sqrt{}$  |
| $12 \sim 25$ |  $3000$  |     $\times$      |     $\times$      |

**特殊性质 1**：$a=0$。

**特殊性质 2**：$a=1,b=2$。

对于 $100 \%$ 的数据，$1 \le n \le 3000,0 \le a<b<998244353$。

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

#### 题目背景 ( 续 )
  阿绫注视着丝毫不顾忌吃相的天依，又好气又好笑。但看着包里黑卡的钱少了一个又一个 $0$ ，脸色越来越沉……
  “喂，阴阳头，再送张卡来！”只好冲着哥哥发怒气的阿绫挂掉电话，又挂上了一副温柔的笑颜。
  “阿绫，阿绫你也尝尝吧。”天依可算想起了没怎么吃的阿绫。
  “不急，晚上回家，还有大餐等着我呢。”阿绫冲天依笑着，邪魅地笑着。
  “唔，所以大餐是什么呢？”天依想不明白，但总觉得有些不安。
        “你还是老样子呢，天依。”


title: 『MdOI R1』Group

background:
此题为比赛时的数据。

然鹅后来yummy觉得没这个必要，于是放弃加强。

**存在不使用`long double`和`__int128`的写法。**

description:
为了让我们团队的同学更加团结，我们需要让各个成员的水平尽量平均。这时，就需要有人对自己产生一些改变。

我们的团队有 $n$ 个同学，第 $i$ 个同学的水平值是一个整数 $a_i$。

我们认为当整组同学水平值的 **方差** **不超过 $m$** 的时候，这组同学就是团结的。

请问至少要让几个同学改变自己的水平值（可以改成任意一个 **实数**），这个团队才可以做到团结？

为避免读入时的精度误差，本题输入的 $m$ 是 **实际值的 $n$ 倍**，这个值是一个整数。

---

如果你不知道什么叫做方差，以下是方差的基本概念：

方差是衡量一组数据 **波动程度** 的指标。

设长度为 $n$ 的序列 $a_{1\dots n}$ 的平均数为 $p$，则该序列的方差 $S$ 为：

$$
S=\frac{1}{n} \sum_{i=1}^n(a_i-p)^2
$$

inputFormat:
第一行，整数 $n,m$，分别表示同学的人数和方差上限的 $n$ 倍。

第二行，$n$ 个整数 $a_{1\cdots n}$，表示每个同学的水平值。

outputFormat: 第一行，一个整数 $t$，表示最少要改变水平值的人数。


title: [USACO20JAN] Cave Paintings P

description:
Bessie 成为了一名艺术家，正在创作壁画！她现在正在创作的作品是一个高为 $N$ 的方阵，方阵的每行都由 $M$ 个方格组成（$1\le N,M\le 1000$）。每个方格是空的，画了石头，或者画了水。Bessie 已经画上了包含石头的方格，包括整幅画作的边界。她现在想要将某些空的方格画上水，使得如果这幅画是真实的，其中应当不存在水的净移动。定义从上到下第 $i$ 行的方格的高度为 $N+1-i$。Bessie 想要她的画作满足以下限制：

假设方格 $a$ 画的是水。那么如果存在一条从 $a$ 到方格 $b$ 的路径，由高度不超过 $a$ 的空的方格或是有水的方格组成，路径中每相邻两个方格都有一条公共边，那么 $b$ 画的也是水。

求 Bessie 可以创作的不同作品的数量模 $10^9+7$ 的余数。Bessie 可以将任意数量的空格画上水，包括不画以及全画。

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

以下 $N$ 行每行包含 $M$ 个字符。每个字符均为 `.` 或 `#`，分别表示一个空的方格和一个画有石头的方格。第一行和最后一行、第一列和最后一列仅包含 `#`。

outputFormat: 输出一个整数，为满足限制的作品的数量模 $10^9+7$ 的余数。

hint:
### 样例解释

如果第二行中的任意一个方格被画上水，那么所有空的方格必须都被画上水。否则，假设没有这样的方格画有水。那么 Bessie 可以选择画上第三行的空格组成的三个连续区域的任意子集。所以，画作的总数等于 $1+2^3=9$。

### 子任务

- 测试点 $1 \sim 5$ 满足 $N,M \leq 10$。
- 测试点 $ 6 \sim 15$ 没有额外限制。


title: [USACO20JAN] Non-Decreasing Subsequences P

description:
Bessie 最近参加了一场 USACO 竞赛，遇到了以下问题。当然 Bessie 知道怎么做。那你呢？

考虑一个仅由范围在 $1 \ldots K$（$1 \leq K \leq 20$）之间的整数组成的长为 $N$ 的序列 $A_1,A_2, \ldots ,A_N$（$1 \leq N \leq 5 \times 10^4$）。给定 $Q$（ $1 \leq Q \leq 2 \times 10^5$ ）个形式为 $[L_i,R_i]$（$1 \leq L_i \leq R_i \leq N$）的询问。对于每个询问，计算 $A_{L_i},A_{L_i+1}, \ldots ,A_{R_i}$ 中不下降子序列的数量模 $10^9+7$ 的余数。

$A_L,\ldots ,A_R$ 的一个不下降子序列是一组索引 （$j_1,j_2, \ldots ,j_x$），满足 $L\le j_1<j_2<\ldots<j_x\le R$ 以及 $A_{j_1}\le A_{j_2}\le \ldots \le A_{j_x}$。确保你考虑了空子序列！

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

第二行包含 $N$ 个空格分隔的整数 $A_1,A_2, \ldots ,A_N$。

第三行包含一个整数 $Q$。

以下 $Q$ 行每行包含两个空格分隔的整数 $L_i$ 和 $R_i$。

outputFormat: 对于每个询问 $[L_i,R_i]$，你应当在新的一行内输出 $A_{L_i},A_{L_i+1},\ldots, A_{R_i}$ 的不下降子序列的数量模 $10^9+7$ 的余数。

hint:
### 样例解释

对于第一个询问，不下降子序列为 $()$、$(2)$ 和 $(3)$。$(2,3)$ 不是一个不下降子序列，因为 $A_2\not \le A_3$。

对于第二个询问，不下降子序列为 $()$、$(4)$、$(5)$ 和 $(4,5)$。

### 子任务

- 测试点 $2 \sim 3$ 满足 $N \leq 1000$。
- 测试点 $4 \sim 6$ 满足 $K \leq 5$。
- 测试点 $7 \sim 9$ 满足 $Q \leq 10^5$。
- 测试点 $10 \sim 12$ 没有额外限制。


title: [USACO20JAN] Falling Portals P

description:
有 $N$（$2 \leq N \leq 2 \times 10^5$）个世界，每个世界有一个传送门。初始时，世界 $i$（对于 $1 \leq i \leq N$）位于 $x$ 坐标 $i$，$y$ 坐标 $A_i$（$1 \leq A_i \leq 10^9$）。每个世界里还有一头奶牛。在时刻 $0$，所有的 $y$ 坐标各不相同，然后这些世界开始坠落：世界 $i$ 沿着 $y$ 轴负方向以 $i$ 单位每秒的速度移动。

在任意时刻，如果两个世界在某一时刻 $y$ 坐标相同（可能是非整数时刻），传送门之间就会“同步”，使得其中一个世界的奶牛可以选择瞬间传送到另一个世界。

对于每一个 $i$，在世界 $i$ 的奶牛想要去往世界 $Q_i$（$Q_i \neq i$）。帮助每头奶牛求出如果她以最优方案移动需要多少时间。

每个询问的输出是一个分数 $a/b$，其中 $a$ 和 $b$ 为互质的正整数，或者 $-1$，如果不可能到达。

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

下一行包含 $N$ 个空格分隔的整数 $A_1,A_2,\ldots,A_N$。

下一行包含 $N$ 个空格分隔的整数 $Q_1,Q_2,\ldots,Q_N$。

outputFormat: 输出 $N$ 行，第 $i$ 行包含奶牛 $i$ 的旅程的时间。

hint:
### 样例解释

考虑原先在世界 $2$ 的奶牛的答案。在时刻 $2$ 世界 $1$ 和世界 $2$ 同步，所以奶牛可以前往世界 $1$。在时刻 $\frac{7}{2}$ 世界 $1$ 和世界 $3$ 同步，所以奶牛可以前往世界 $3$。

### 子任务

- 测试点 $2 \sim 3$ 满足 $N \leq 100$。
- 测试点 $4 \sim 5$ 满足 $N \leq 2000$。
- 测试点 $6 \sim 14$ 没有额外限制。


title: 快乐水

background: 小 W 要去买快乐水。

description:
他来到了一家商店门前。

这家商店为了吸引顾客来买快乐水，搞了这么一个活动：「$5$ 个瓶盖换一瓶快乐水」。于是，人们纷纷来他的店里买快乐水。

买完快乐水，他想到了一个问题：

如果一瓶快乐水有 $m$ 个附属品，对于第 $i$ 个附属品，每 $a_i$ 个可以换一瓶全新的快乐水，现在我有买 $n$ 瓶快乐水的钱，我最多能喝多少快乐水呢？

inputFormat:
第一行两个整数 $n,m$，意义如上。

接下来一行 $m$ 个整数 $a_1,a_2,\cdots,a_m$，意义如上。

outputFormat:
如果小 W 可以无限白嫖快乐水，那么输出一行一个字符串 `Inf`。

否则，输出一行一个整数 $s$，表示小 W 最多能喝的快乐水数量。


title: [USACO20JAN] Time is Mooney G

description:
Bessie 正在安排前往牛尼亚的一次出差，那里有 $N$（$2 \leq N \leq 1000$）个编号为 $1 \ldots N$ 的城市，由 $M$（$1 \leq M \leq 2000$）条单向的道路连接。Bessie 每次访问城市 $i$ 都可以赚到 $m_i$ 哞尼（$0 \leq m_i \leq 1000$）。从城市 $1$ 出发，Bessie 想要赚到尽可能多的哞尼，最后回到城市 $1$。为了避免争议，$m_1=0$。

沿着两个城市之间的道路移动需要消耗一天。出差的准备工作十分费钱；旅行 $T$ 天需要花费 $C \times T^2$ 哞尼（$1 \leq C \leq 1000$）。

Bessie 在一次出差中最多可以赚到多少哞尼？注意有可能最优方案是 Bessie 不访问城市 $1$ 之外的任何城市，在这种情况下结果应当为 $0$。

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

第二行包含 $N$ 个整数 $m_1,m_2,\ldots, m_N$。

以下 $M$ 行每行包含两个空格分隔的整数 $a$ 和 $b$（$a \neq b$），表示从城市 $a$ 到城市 $b$ 的一条单向道路。

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

hint: 最优的旅行方案是 $1 \to 2 \to 3 \to 1 \to 2 \to 3 \to1$。Bessie 总共赚到了 $10+20+10+20-1 \times 6^2=24$ 哞尼。


title: [USACO20JAN] Farmer John Solves 3SUM G

description:
Farmer John 相信他在算法设计上实现了一个重大突破：他声称他发现了一个 3SUM 问题的近似线性时间算法，这是一个有名的算法问题，尚未发现比运行速度比平方时间明显更优的解法。3SUM 问题的一个形式是：给定一个整数数组 $s_1,\ldots,s_m$，计算不同索引组成的无序不重三元对 $i,j,k$ 的数量，使得 $s_i+s_j+s_k=0$（$i, j, k$ 互不相同）。

为了测试 Farmer John 的断言，Bessie 提供了一个 $N$ 个整数组成的数组 $A$（$1 \leq N \leq 5000$）。Bessie 还会进行 $Q$ 次询问（$1 \leq Q \leq 10^5$），每个询问由两个索引 $1 \leq a_i \leq b_i \leq N$ 组成。对于每个询问，Farmer John 必须在子数组 $A[a_i \ldots b_i]$ 上求解 3SUM 问题。

不幸的是，Farmer John 刚刚发现了他的算法中的一个错误。他很自信他能修复这个算法，但同时，他请你帮他先通过 Bessie 的测试！

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

第二行包含空格分隔的数组 $A$ 的元素 $A_1,\ldots ,A_N$。

以下 $Q$ 行每行包含两个空格分隔的整数 $a_i$ 和 $b_i$，表示一个询问。

保证对于每个数组元素 $A_i$ 有 $-10^6 \leq A_i \leq 10^6$。

outputFormat: 输出包含 $Q$ 行，第 $i$ 行包含一个整数，为第 $i$ 个询问的结果。**注意你需要使用 64 位整数型来避免溢出。**

hint:
### 样例解释

对于第一个询问，所有的三元对为 $(A_1,A_2,A_5)$ 和 $(A_2,A_3,A_4)$。

### 子任务

- 测试点 $2 \sim 4$ 满足 $N \leq 500$。
- 测试点 $5 \sim 7$ 满足 $N \leq 2000$。
- 测试点 $8 \sim 15$ 没有额外限制。


title: [USACO20JAN] Springboards G

description:
Bessie 在一个仅允许沿平行于坐标轴方向移动的二维方阵中。她从点 $(0,0)$ 出发，想要到达 $(N,N)$（$1 \leq N \leq 10^9$）。为了帮助她达到目的，在方阵中有 $P$（$1 \leq P \leq 10^5$）个跳板。每个跳板都有其固定的位置 $(x_1,y_1)$，如果 Bessie 使用它，会落到点 $(x_2,y_2)$。

Bessie 是一个过程导向的奶牛，所以她仅允许她自己向上或向右行走，从不向左或向下。类似地，每个跳板也设置为不向左或向下。Bessie 需要行走的距离至少是多少？

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

以下 $P$ 行每行包含四个整数 $x_1,y_1,x_2,y_2$，其中 $x_1 \leq x_2$ 且 $y_1 \leq y_2$。

所有跳板的位置和目标位置均不相同。

outputFormat: 输出一个整数，为 Bessie 到达点 $(N,N)$ 需要行走的最小距离。

hint:
### 样例解释

Bessie 的最佳路线为：

- Bessie 从 (0,0) 走到 (0,1)（1 单位距离）。
- Bessie 跳到 (0,2)。
- Bessie 从 (0,2) 走到 (1,2)（1 单位距离）。
- Bessie 跳到 (2,3)。
- Bessie 从 (2,3) 走到 (3,3)（1 单位距离）。

Bessie 总共走过的路程为 3 单位距离。

### 子任务

- 测试点 $2 \sim 5$ 满足 $P \leq 1000$。
- 测试点 $6 \sim 15$ 没有额外限制。


title: [USACO20JAN] Berry Picking S

description:
Bessie 和她的妹妹 Elsie 正在 Farmer John 的浆果园里采浆果。Farmer John 的浆果园里有 $N$ 棵浆果树（$1 \leq N \leq 1000$）；树 $i$ 上有 $B_i$ 个浆果（$1 \leq B_i \leq 1000$）。Bessie 有 $K$ 个篮子（$1 \leq K \leq 1000$，$K$ 为偶数）。每个篮子里可以装同一棵树上采下的任意多个浆果，但是不能装来自于不同的树上的浆果，因为它们的口味可能不同。篮子里也可以不装浆果。

Bessie 想要使得她得到的浆果数量最大。但是，Farmer John 希望 Bessie 与她的妹妹一同分享，所以 Bessie 必须将浆果数量较多的 $K/2$ 个篮子给 Elsie。这表示 Elsie 很有可能最后比 Bessie 得到更多的浆果，这十分不公平，然而姐妹之间往往就是这样。

帮助 Bessie 求出她最多可以得到的浆果数量。

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

第二行包含 $N$ 个空格分隔的整数 $B_1,B_2,\ldots,B_N$。

outputFormat: 输出一行答案。

hint:
### 样例解释

如果 Bessie 在

- 一个篮子里装树 2 的 6 个浆果
- 两个篮子里每个装树 3 的 4 个浆果
- 一个篮子里装树 4 的 4 个浆果

那么她能够得到两个各装有 4 个浆果的篮子，总共 8 个浆果。

### 子任务

- 测试点 $1 \sim 4$ 满足 $K \leq 10$。
- 测试点 $5 \sim 11$ 没有额外限制。


title: [USACO20JAN] Loan Repayment S

description:
Farmer John 欠了 Bessie $N$ 加仑牛奶（$1 \leq N \leq 10^{12}$）。他必须在 $K$ 天内将牛奶给 Bessie。但是，他不想将牛奶太早拿出手。另一方面，他不得不在还债上有所进展，所以他必须每天给 Bessie 至少 $M$ 加仑牛奶（$1 \leq M \leq 10^{12}$）。

以下是 Farmer John 决定偿还 Bessie 的方式。首先他选择一个正整数 $X$。然后他每天都重复以下过程：

1. 假设 Farmer John 已经给了 Bessie $G$ 加仑，计算 $\frac{N-G}{X}$ 向下取整。令这个数为 $Y$。
2. 如果 $Y$ 小于 $M$，令 $Y$ 等于 $M$。
3. 给 Bessie $Y$ 加仑牛奶。

求 $X$ 的最大值，使得 Farmer John 按照上述过程能够在 $K$ 天后给 Bessie 至少 $N$ 加仑牛奶 （$1 \leq K \leq 10^{12}$）。

inputFormat: 输入仅有一行，包含三个空格分隔的正整数 $N,K,M$，满足 $K \times M<N$。

outputFormat: 输出最大的正整数 $X$，使得按照上述过程 Farmer John 会给 Bessie 至少 $N$ 加仑牛奶。

hint:
### 样例解释

在这个测试用例中，当 $X=2$ 时 Farmer John 第一天给 Bessie $5$ 加仑，后两天每天给 Bessie $M=3$ 加仑。

### 子任务

- 测试点 $2 \sim 4$ 满足 $K \leq 10^5$。
- 测试点 $5 \sim 11$ 没有额外限制。


title: [USACO20JAN] Wormhole Sort S

description:
Farmer John 的奶牛们已经厌倦了他对她们每天早上排好序离开牛棚的要求。她们刚刚完成了量子物理学的博士学位，准备将这一过程搞快点。

今天早上，如同往常一样，Farmer John 的 $N$ 头编号为 $1 \ldots N$ 的奶牛（$1 \leq N \leq 10^5$），分散在牛棚中 $N$ 个编号为 $1 \ldots N$ 的不同位置，奶牛 $i$ 位于位置 $p_i$。但是今天早上还出现了 $M$ 个编号为 $1 \ldots M$ 的虫洞（$1 \leq M \leq 10^5$），其中虫洞 $i$ 双向连接了位置 $a_i$ 和 $b_i$，宽度为 $w_i$（$1\le a_i,b_i\le N, a_i\neq b_i, 1\le w_i\le 10^9$）。

在任何时刻，两头位于一个虫洞两端的奶牛可以选择通过虫洞交换位置。奶牛们需要反复进行这样的交换，直到对于 $1 \leq i \leq N$，奶牛 $i$ 位于位置 $i$。

奶牛们不想被虫洞挤坏。帮助她们最大化被她们用来排序的虫洞宽度的最小值。保证奶牛们有可能排好序。

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

第二行包含 $N$ 个整数 $p_1,p_2,\ldots ,p_N$。保证 $p$ 是 $1 \ldots N$ 的一个排列。

对于 $1$ 到 $M$ 之间的每一个 $i$，第 $i+2$ 行包含整数 $a_i,b_i,w_i$。

outputFormat: 输出一个整数，为在排序过程中奶牛必须挤进的虫洞的最小宽度的最大值。如果奶牛们不需要用任何虫洞来排序，输出 $-1$。

hint:
### 样例解释 1

以下是一个仅用宽度至少为 9 的虫洞给奶牛排序的可能方案：

- 奶牛 1 和奶牛 2 使用第三个虫洞交换位置。
- 奶牛 1 和奶牛 3 使用第一个虫洞交换位置。
- 奶牛 2 和奶牛 3 使用第三个虫洞交换位置。

### 子任务

- 测试点 $3 \sim 5$ 满足 $N,M \leq 1000$。
- 测试点 $6 \sim 10$ 没有额外限制。


title: 『MdOI R1』GCD? GCD!

description:
灵喜欢 $\mathrm{gcd}$，也就是 **最大公约数**。如果你不知道什么叫做最大公约数，你可以访问 [最大公约数 - OI Wiki](https://oi-wiki.org/math/gcd/)。

灵给了你一个正整数 $n$，要你把它分成三个 **互不相等的** 正整数 $a,b,c$ 之和，使得 $\mathrm{gcd}(a,b,c)$ 最大。

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

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

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

outputFormat:
对于每组数据，一行一个整数，表示答案，即最大的 $\mathrm{gcd}(a,b,c)$ 。

特别地，如果 $n$ 无法分成三个互不相等的正整数之和，请输出 `-1`。


title: 机器人

background: 小 W 购买了一个机器人。

description:
现在，小 W 希望机器人去帮他完成 $n$ 个任务。

每个任务有两种属性：完成需要花的钱 $w_i$，成功率 $p_i$。

小 W 需要将任务按一定顺序排序，随后，机器人会按如下方式做任务：

- 从第一个任务开始做；
- 花费代价做完第 $i$ 个任务后，如果成功，则继续做第 $i+1$ 个任务，否则重新从第一个任务开始做；
- 成功做完第 $n$ 个任务后，流程结束。

例如，当 $n=2$ 时，一个可能的流程为：
- 做任务 $1$，失败；
- 做任务 $1$，成功；
- 做任务 $2$，失败；
- 做任务 $1$，成功；
- 做任务 $2$，成功；
- 流程结束，总花费为 $3w_1+2w_2$。

现在，小 W 希望学 OI 的你帮他找到一种排列顺序，使得他的期望花费最小。

inputFormat:
第一行一个整数 $n$，表示任务的数量。

接下来一行 $n$ 个整数 $w_1,w_2,\cdots,w_n$，意义如上。

接下来一行 $n$ 个整数 $P_1,P_2,\cdots,P_n$，其中 $P_i=p_i\times10^4$，
$p_i$ 的意义如上。

outputFormat:
如果无论如何也不可能完成任务，那么输出一行一个字符串`Impossible`。

否则，输出一行 $n$ 个整数 $c_1,c_2,\cdots,c_n$，其为 $1,2,\cdots,n$ 的一个排列，表示任务的安排顺序，安排的第 $i$ 件任务是输入中的第 $c_i$  件任务。

hint:
样例一解释：可以感性理解。既然任务 $2$ 一定成功，那放到最后做肯定不劣。

样例二解释：显然这个任务不可能完成，它的成功率为 $0$。

**注意：无论任务是否成功，总是要花费 $w_i$ 的代价去做。**
********
本题带有 $\text{SPJ}$。如果你的输出与答案的输出一样优（或者都是`Impossible`），那么你将在这个测试点获得满分，否则你将在这个测试点不获得任何分数。

由于某种原因，本题不提供 $\text{SPJ}$ 给选手。
********
数据范围：
对于 $10\%$ 的数据，$1\le n\le 10$。
对于另外 $20\%$ 的数据，所有 $w_i$ 相等。
对于另外 $20\%$ 的数据，所有 $p_i$ 相等。
对于所有数据，$1\le n\le 2\times10^5$，$1\le w_i\le 10^9$，$0\le P_i\le10^4$。


title: Ryoku 的逆序对

background: Ryoku 并不知道这题的背景是什么。

description:
Ryoku 有一个正整数 $\{1,2,\cdots,n\}$ 的排列 $A = \{a_i\}$。

她告诉你一个序列 $B = \{b_i\}$，表示对于每个数 $a_i$，对于所有 $j>i$ 有 $b_i$ 个数可以与 $a_i$ 组成逆序对（逆序对的定义是：满足 $i>j$ 且 $a_i < a_j$ 的一组 $(a_i, a_j)$ 称作一对逆序对）。

不幸的是，Ryoku 给你的序列 $B$ 有一些位置污损了，你想知道有多少个可能的排列 $A$ 能符合条件。

请你输出答案并构造一个**字典序最小**的排列 $A$（对于排列 $A = \{a_i\},\ A' = \{a'_i\}$ 若存在某个位置 $i$，使得 $\forall j < i, a_j = a'_j$ 且 $a_i < a'_i$，则 $A$ 的字典序小于 $A'$）。

inputFormat:
输入包含两行。
第一行包含一个整数 $n$。
第二行包含 $n$ 个整数，为序列 $B$。若给出的 $b_i = -1$，则代表这个位置被污损了。

outputFormat:
输出包含两行。
第一行包含一个整数，为可能的排列 $A$ 的方案数，对 $10^9 + 7$ 取模。
第二行包含 $n$ 个整数，为字典序最小的符合条件的排列。若第一行答案为 $0$，则第二行无需输出。


title: [SCOI2006] 动态最值

description:
有一个包含 $n$ 个元素的数组，要求实现以下操作：

- `DELETE k`：删除位置 $k$ 上的数。右边的数往左移一个位置。
- `QUERY i j`：查询位置 $i\sim j$ 上所有数的最小值和最大值。

例如有 $10$ 个元素：

| 位置 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $	10$ |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| 元素 | $1$ | $5$ | $2$ | $6$ | $7$ | $4$ | $9$ | $3$ | $1$ | $5$ |

`QUERY 2 8` 的结果为 `2 9`。依次执行 `DELETE 3` 和 `DELETE 6`（注意这时删除的是原始数组的元素 $7$）后数组变为：

| 位置 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| 元素 | $1$ | $5$ | $6$ | $7$ | $4$ | $3$ | $1$ | $5$ |

`QUERY 2 8` 的结果为 `1 7`。

inputFormat:
第一行包含两个数 $n,m$，表示原始数组的元素个数和操作的个数。
第二行包括 $n$ 个数，表示原始数组。
以下 $m$ 行，每行格式为 `1 k` 或者 `2 i j`，其中第一个数为 $1$ 表示删除操作，为 $2$ 表示询问操作。

outputFormat: 对每个询问操作输出一行，包括两个数，表示该范围内的最小值和最大值。


title: [加油武汉] 七步洗手法

background:
现在正处于疫情防控的关键时期，大家要经常洗手，防止接触感染。

[正确的洗手方法](https://dxy.com/column/4473)

description:
给定一张含有 $n$ 个点的无向完全图，其中 $m$ 条边是白边，其余是黑边。

现在需要你求出同色的三元环（或者说，三角形）的个数。

inputFormat:
第一行整数 $n,m$，意义如题。

剩下的 $m$ 行每行两个整数 $u,v$，代表白边的两个端点。保证给出的白边没有重边和自环。

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

hint:
 - 对于 $20\%$ 的数据，满足 $n \leq 200$；
 - 对于 $50\%$ 的数据，满足 $n \leq 2000$；
 - 对于 $100\%$ 的数据，满足 $1 \leq n \leq 10^5,1 \leq m \leq 3\times 10^5$。


title: 『MdOI R1』Epic Convolution

background:
小 Q 是神仙，尤其喜欢多项式。

这天小 K 问了道题：

给定长度 $n$ 的序列 $g,h$，求 $f$ 满足 $f_n=\sum\limits_{k=0}^{n}g_kh_{n-k}$。

小 Q 对小 K 说：你这个菜鸡，这不随便卷一下就行了吗，你 FFT 怎么学的了。

然后小 K 花了一个月学习 FFT 和 NTT。又跑过去问小 Q 一道题：

给定长度 $n$ 的序列 $g,h$，求 $f$ 满足 $f_n=\sum\limits_{k=0}^{n}\binom{n}{k}g_kh_{n-k}$。

小 Q 对小 K 说：你这个菜鸡，这不随便卷一下就行了吗，你 FFT 怎么学的了。

然后小 K 又花了一个月学习 FFT 和 NTT。又跑过去问小 Q 一道题：

给定长度 $n$ 的序列 $g,h$，求 $f$ 满足 $f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}$。

小 Q 对小 K 说：你这个菜鸡，这不随便卷一下就行了吗，你 FFT 怎么学的了。

然后他仔细看了一遍，傻眼了，发现他不会这道题。

为了吊打小 K，你需要告诉他 $4$ 个特殊情况的做法。

description:
给定特定的序列 $g,h$，求 $f_n$ 满足 $f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}$。

本题有五个子任务，前四个子任务给定不同形式的 $g,h$，需要求出 $f_n$，第五个子任务不依赖于这个等式，但是形式上与此相似。

**注意，本题所有输出请对 $998244353$（$119\times 2^{23}+1$，一个质数）取模。**

---

**Subtask 1（4 pts）：**

给定一个 $n$，你需要回答 $q$ 组询问，每组询问给定一个整数 $m$。

每组询问的 $g$ 和 $h$ 如下所示（$0\leq k\leq n$）：

$$g_k=\begin{cases}1,&k<m\\0,&k\geq m\end{cases}$$

$$h_k=1$$

你需要回答出 $f_n$ 的值。

---

**Subtask 2,3（16,16 pts）：**

这两个子任务给定的序列 $g,h$ 形式相同，但数据范围不同，请仔细阅读数据范围。

你需要回答 $q$ 组询问，每组询问给定两个整数 $n,m$。

每组询问的 $g$ 和 $h$ 如下所示（$0\leq k\leq n$）：

$$g_k=\frac{1}{(k+m+1)!}$$

$$h_k=\begin{cases}0,&k<m\\\frac{(-1)^{k-m}}{(k-m)!},&k\geq m\end{cases}$$

你需要回答出 $f_n$ 的值。

---

**Subtask 4（32 pts）：**

你需要回答 $q$ 组询问，每组询问给定两个整数 $n,m$。

每组询问的 $g$ 和 $h$ 如下所示（$0\leq k\leq n$）：

$$g_k=\frac{k^m}{k!}$$

$$h_k=\frac{(-1)^k}{k!}$$

你需要回答出 $f_n$ 的值。

---

**Subtask 5（32 pts）：**

你需要回答 $q$ 组询问，每组询问给定两个整数 $n,m$。

**注意下面 $n,m$ 的含义，不要看反。**

$$\sum\limits_{k=0}^{m}(k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\sum\limits_{i=0}^{m-k}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}$$

你需要回答出上面这个式子的值。

与前四个 Subtask 相似之处是，求和的一开始是幂的形式。

inputFormat:
第一行一个整数 $op$，表示子任务编号。

若 $op=1$：

第二行一个整数 $n$，第三行一个整数 $q$；

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

若 $op\in \{2,3,4,5\}$：

第二行一个整数 $q$；

接下来 $q$ 行：每行两个整数 $n,m$。

所有变量含义见题目描述。

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


title: [Ynoi2077] hlcpq

description:
平面上，给出 $n$ 条水平线段和 $n$ 条竖直线段，保证不同线段不在同一直线上。

若两线段有交点则它们连通，若 $a, b$ 连通且 $b, c$ 连通则 $a, c$ 连通。

一条线段 $a$ 是关键的，当且仅当存在另外两条线段 $b, c$，使得 $b, c$ 连通，且删去 $a$ 后 $b, c$ 不连通。

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

接下来 $n$ 行，第 $i$ 行有两个整数 $l, r$（$1 \le l < r \le n$），表示一条水平线段 $l \le x \le r$，$y=i$。

接下来 $n$ 行，第 $i$ 行有两个整数 $d, u$（$1 \le d < u \le n$），表示一条竖直线段 $x = i$，$d \le y \le u$。

outputFormat:
输出两行，每行是一个长度为 $n$ 的 $01$ 串。

第一行第 $i$ 位为 $1$ 当且仅当第 $i$ 条水平线段是关键的。

第二行第 $i$ 位为 $1$ 当且仅当第 $i$ 条竖直线段是关键的。

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

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


title: [SDOI2012] 走迷宫

description: Morenan 被困在了一个迷宫里。迷宫可以视为 $n$ 个点 $m$ 条边的有向图，其中 Morenan 处于起点 $s$，迷宫的终点设为 $t$。可惜的是，Morenan 非常的脑小，他只会从一个点出发随机沿着一条从该点出发的有向边，到达另一个点。这样，Morenan 走的步数可能很长，也可能是无限，更可能到不了终点。若到不了终点，则步数视为无穷大。但你必须想方设法求出 Morenan 所走步数的期望值。

inputFormat:
第一行四个整数，$n,m,s,t$。

接下来 $m$ 行，每行两个整数 $u, v$ ，表示有一条从 $u$ 到 $v$ 的边。

outputFormat: 一个浮点数，保留小数点后 $3$ 位，为步数的期望值。若期望值为无穷大，则输出`INF`。


title: 质数前缀统计

background: 这是洲阁筛和 Min_25 筛的重要前置知识。

description:
设 $S(n)$ 为 $n$ 以内质数的 $k$ 次方和。

给出 $N$，求下列式子的值。

$$\sum_{i=1}^{\lfloor\sqrt{N}\rfloor} i^2 S \!\left( \left\lfloor \frac{N}{i} \right\rfloor \right)$$

所有结果对给定的质数 $p$ 取模。

inputFormat: 一行三个整数 $N,k,p$，之间用空格隔开。

outputFormat: 一行一个整数，代表计算的结果。


title: 函数求值

description:
有两个长度均为 $n$ 的权值序列 $a,b$，常数 $p,k$，以及两个函数：

$$g(x) = \sum_{i=1}^x p^i \times a_i$$

$$f(x) = \sum_{i=1}^x g(i) ^ k \times b_i$$

有 $m$ 个操作，操作有以下三种：

*  $1\ x\ y$，表示将 $a_x$ 修改为 $y$。

*  $2\ x\ y$，表示将 $b_x$ 修改为 $y$。

*  $3\ x$，表示查询 $f(x)$ 对 $10 ^ 9 + 7$ 取模的值。

inputFormat:
第一行四个整数，$n,m,p,k$。

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

第三行 $n$ 个整数，表示序列 $b$。

接下来 $m$ 行，每行描述一个操作。

outputFormat: 对于每个 $3\ x$ 操作，输出答案。


title: [JSOI2010] 旅行

description:
WJJ 喜欢旅游，这次她打算去一个据说有很多漂亮瀑布的山谷玩。

WJJ 事先得到了一张地图，上面标注了 $N$ 个小动物的聚居地，也就是一个个的小村落。其中第 $1$ 个村庄是 WJJ 现在住的地方，第 $N$ 个村庄是 WJJ 打算去的地方。

这些村庄之间有 $M$ 条双向道路连接着，第 $i$ 条双向道路恰好直接连接两个小村庄 $A_i$，$B_i$，长度为 $C_i$。道路有的是隧道，有的是栈桥，地图上那些看起来在村庄之外交叉的路实际上并不相交——也就是说，如果把这些小村落和双向道路构成的道路网看作图论意义上的图，我们不保证它是平面图，也不保证它没有重边。不过，有一点还是可以保证的：WJJ  细心地验证过，从它居住的村落一定能走到她想去的那个山谷。

在 WJJ 所在的神奇世界中，每只小动物都可以借助仙人掌来施放魔法，其中之一是，交换世界中任意两条双向道路的长度，同时保持其他道路的长度不变。按 WJJ 目前的魔法水平，她最多能使用 $K$ 次这种道路长度交换魔法。可惜的是，由于仙人掌刺比较多，WJJ 并不打算带着它旅行，于是她会在家里完成想要的道路交换后再出门。

假设 WJJ 的旅行途中不会有其他小动物进行道路交换来破坏她设计好的路线。为了尽快达到目的地，WJJ 希望她需要走的总距离越短越好。也就是说，使用最多 $K$ 次魔法后，从村落 $1$ 到村落 $N$ 的最短距离是多少？

inputFormat:
第一行为 $3$ 个用空格隔开的整数 $N,M,K$。

接下来 $M$ 行，每行 $3$ 个整数，用空格隔开，分别表示 $A_i,B_i,C_i$。

outputFormat: 一个整数，表示使用最多 $K$ 次魔法后，村落 $1$ 和村落 $N$ 之间的最短距离。

hint:
### 样例解释

一个可行的方案是，对调第 $1$ 条边和第 $4$ 条边的长度，再对调第 $2$ 条边和第 $5$ 条边的长度。对调后的最短路径为 $1\rightarrow 2\rightarrow 5$，长度为 $3$。可以证明，没有比这更优的方案了。

### 数据范围

对于 $100\%$ 的数据，$1\leq N\leq 50$，$1\leq M\leq 150$，$1\leq K\leq 20$，$1\leq A_i,B_i\leq N$，$A_i\neq B_i$，$1\leq C_i\leq 1000$。


title: CF1278F Cards 加强版

background: [原题链接](https://www.luogu.com.cn/problem/CF1278F)

description:
有 $m$ 张牌，其中有一张是王牌。将这些牌均匀随机打乱 $n$ 次，设有 $x$ 次第一张为王牌，求 $x^k$ 的期望值。

答案对 $998244353$ 取模。

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

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

hint:
【数据范围】
对于 $20\%$ 的数据，$1\le k \le 5000$；
对于 $40\%$ 的数据，$1\le k \le 10^5$；
对于 $100\%$ 的数据，$1\le k \le 10^7$，$1\le n,m \le 998244352$。

Solution：iostream
Data：NaCly\_Fish


title: 回文匹配

description:
对于一对字符串 $(s_1,s_2)$，若 $s_1$ 的长度为奇数的子串 $(l,r)$ 满足 $(l,r)$ 是回文的，那么 $s_1$ 的“分数”会增加 $s_2$ 在 $(l,r)$ 中出现的次数。

现在给出一对 $(s_1,s_2)$，请计算出 $s_1$ 的“分数”。

答案对 $2 ^ {32}$ 取模。

inputFormat:
第一行两个整数，$n,m$，表示 $s_1$ 的长度和 $s_2$ 的长度。

第二行两个字符串，$s_1,s_2$。

outputFormat: 一行一个整数，表示 $s_1$ 的分数。


title: 后缀树

background: Eztsu 是一个可爱的女孩子，最近她学习了[后缀树](https://www.luogu.com.cn/blog/EternalAlexander/xuan-ku-hou-zhui-shu-mo-shu)，并打算用它来解决如下问题。

description:
对于一个字符串 $S$，我们定义 $|S|$ 表示 $S$ 的长度。

接着，我们定义 $S_i$ 表示 $S$ 中第 $i$ 个字符，$S_{L...R}$ 表示由 $S$ 中从左往右数，第 $L$ 个字符到第 $R$ 个字符依次连接形成的字符串。

给定 $n$，求有多少种不同的满足下列要求的串 $S$：

- $|S|=n$。
- $S$ 中仅包含小写字母。
- 不存在整数 $i \in [1,n)$ 使得 $S_{1...i}$ 是 $S_{i+1...n}$ 的子串。

对于第三个限制，用通俗一点的说法解释的话，就是不存在一种将这个串分成两段的方式，使得前面一段是后面一段的子串。

两个串 $S$ 和 $T$ 不同当且仅当 $|S|\neq|T|$ 或 $\exists i \in [1,|S|] S_i \neq T_i$。如果你不知道这是什么意思，你可以理解为它们看起来不同。

可怜的 Eztsu 不会做，所以你要帮她做这道题。

答案可能很大，你只需要输出答案对 $998244353$ 取模的值。

题面补充：

$S$ 是 $T$ 的子串当且仅当存在 $L,R \in [1,|T|]$ 使得 $T_{L...R}=S$.

inputFormat: 一行一个正整数 $n$，意义见题目描述。

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

hint:
#### 样例解释

对于第一组样例，不难发现，这个串符合题意当且仅当两个字符不同，因此答案为 $26 \times 26 - 26$，可以理解为两个字符任意的方案数减去两个字符相同的方案数。

---

#### 数据范围

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

对于所有测试点，保证 $1 \leq n \leq 10^9$。

$\text{Subtask 1 (17 pts)}$ $n \leq 4$。

$\text{Subtask 2 (78 pts)}$ $n \leq 2\times 10^3$。

$\text{Subtask 3 (5 pts)}$ 没有特殊限制。

---

#### 提示

小写字母一共有 $26$ 个。


title: 丝之割

background:
Pharloom 是一个神秘的王国，[丝线与歌](https://www.bilibili.com/video/av43623335)是那里最强大的力量。多弦琴是 Pharloom 的一种强大武器，正如多项式是 OI 中的强大武器。

因为你很讨厌多项式，你决定摧毁多弦琴。

description:
下面这部分题面只是为了帮助你理解题意，并没有详细的解释。更为严谨清晰的叙述见形式化题意。

多弦琴由两根支柱和连接两根支柱的 $m$ 条弦组成。每根支柱上都均匀安放着 $n$ 个固定点，第 $i$ 条弦连接上方支柱的第 $u_i$ 个固定点和下方支柱的第 $v_i$ 个固定点。

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

> 上图是一把多弦琴

为了摧毁多弦琴，你可以进行若干次切割操作。在一次切割操作中，你可以选择上方支柱的某一个固定点 $u$ 和下方支柱的一个固定点 $v$，所有被 $u$ 到 $v$ 的连线**从左到右**穿过的弦都将被破坏。但同时，你需要付出 $a_u \times b_v$ 的代价。

形式化题意：有 $m$ 条弦，一条弦可以抽象为一个二元组 $(u,v)$，你可以进行任意次切割操作，一次切割操作你将选择两个下标 $i$ 和 $j$ 满足 $i,j \in [1,n]$，然后所有满足 $u>i,v<j$ 的弦 $(u,v)$ 都将被破坏，同时你将付出 $a_i \times b_j$ 的代价。求破坏所有弦的最小代价和。

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

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

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

接下来 $m$ 行每行两个整数 $u,v$，表示有一条弦 $(u,v)$。

以上输入的意义见题目描述。

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

hint:
#### 样例解释

对于第一组样例，使用两次切割，分别为 $(1,3)$，$(3,5)$，花费代价 $3 \times 1 + 1 \times 3 = 6$。

对于第二组样例，注意切割 $(5,1)$ 不能使弦 $(3,3)$ 消失。

---

#### 数据范围

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

对于所有测试点，保证 $1 \leq n, m \leq 3\times 10^5$，$2 \leq u \leq n$，$1 \leq v \leq n-1$，$1 \leq a_i,b_i \leq 10^6$。

$\text{Subtask 1 (21 pts)}$ $n,m \leq 6$。

$\text{Subtask 2 (3 pts)}$ $m=1$。

$\text{Subtask 3 (1 pts)}$ $a_1=b_n = 1$。

$\text{Subtask 4 (25 pts)}$ $n,m \leq 100$。

$\text{Subtask 5 (29 pts)}$ $n,m \leq 10^3$。

$\text{Subtask 6 (21 pts)}$ 无特殊限制。

---
#### 提示

如果你认真观察了数据范围，你会发现这把多弦琴一定能够被破坏。


title: 燔祭

description:
计算满足如下条件的带标号有根树数量：

- 这棵树一共有 $n$ 个节点。
- 每个节点都有一个整数权值，且在区间 $[1,m]$ 内。
- 每个节点的权值都**不大于**其父节点的权值。

答案可能很大，只需输出答案对 $998244353$ 取模的值。

两棵树 $T_1$ 和 $T_2$ 不同当且仅当两棵树的节点数不同或者根节点不同或者存在一个编号 $i$ 使得 $T_1$ 和 $T_2$ 中 $i$ 号节点的父节点编号不同或者 $i$ 号节点的权值不同。

inputFormat: 一行两个正整数 $n,m$，意义见题目描述。

outputFormat: 一行一个整数，所求答案。

hint:
#### 样例解释

对于第一组样例，

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

六棵树如上图所示，其中圈内的数字是节点编号，圈外的数字是节点权值。

---

#### 数据范围

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

对于所有测试点，保证 $1 \leq n \leq 400$，$1 \leq m < 998244353$。

$\text{Subtask 1 (7 pts)}$ $n = 3,m=3 $。

$\text{Subtask 2 (11 pts)}$ $m=1$。

$\text{Subtask 3 (19 pts)}$ $n,m\leq 6$。

$\text{Subtask 4 (17 pts)}$ $n \leq 7$。

$\text{Subtask 5 (11 pts)}$ $n,m \leq 50$。

$\text{Subtask 6 (35 pts)}$ 无特殊限制。


title: 纯粹容器

background: 白王正在挑选容器。

description:
白王制造了 $n$ 个容器，并将它们排成了一队，从左到右依次编号为 $1 \sim n$。第 $i$ 个容器的**强度**为 $a_i$，保证 $a_i$ 互不相同。为了挑选出最纯粹的容器，白王会进行 $n-1$ 轮操作，每轮操作中，他会等概率随机挑选两个 **位置相邻** 且 **未被击倒** 的容器，令它们进行决斗，在一次决斗中，强度较小的容器将会被击倒并移出队列。

显然最后留下的是强度最大的容器，但是，可怜的容器们很想知道自己能够活多久，于是，它们请你对每个容器求出它存活轮数的期望。答案对 $998244353$ 取模。

一个容器的存活轮数为最大的非负整数 $x < n$ 满足它在第 $x$ 轮未被击倒。

两个容器 $i$ 和 $j$ 位置相邻当且仅当不存在 $k$ 满足 $i<k<j$ 且 $k$ 号容器未被击倒。

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

第二行 $n$ 个整数 $a_1, a_2,\cdots,a_n$，意义见题目描述。

outputFormat: 一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个容器的存活轮数的期望。为了避免浮点误差，保证答案可以表示为最简分数 $\frac{p}{q}$，你只需要输出一个 $x (0 \leq x < 998244353)$ 使得 $qx \equiv p \pmod {998244353}$。

hint:
#### 样例解释

在第一组样例中，第一个容器无论如何不可能被击倒，第二个容器在第一轮一定会被击倒，第三个容器第一轮一定不被击倒，第二轮一定被击倒。

第二组样例的真实答案为 $\frac{1}{2}$，$\frac{1}{2}$，$2$。

---

#### 数据范围

对于所有测试点，保证 $1 \leq n \leq 50$，$1 \leq a_i \leq n$，$a_i$ 两两不同。

$\text{Subtask 1 (2 pts)}$ $n \leq 2$。

$\text{Subtask 2 (23 pts)}$ $n \leq 6$。

$\text{Subtask 3 (31 pts)}$ $n \leq 18$。

$\text{Subtask 4 (19 pts)}$ $a_i = i$。

$\text{Subtask 5 (25 pts)}$ 无特殊限制。

---

#### 提示

如果你不知道怎么对分数取模，可以参考[这里](https://www.luogu.com.cn/problem/P3811)。


title: [EER1] 迫害

background:
"In Germany they first came for the Communists,

and I didn't speak up because I wasn't a Communist.

Then they came for the Jews,

and I didn't speak up because I wasn't a Jew.

Then they came for the trade unionists,

and I didn't speak up because I wasn't a trade unionist.

Then they came for the Catholics,

and I didn't speak up because I was a Protestant.

Then they came for me ,

and by that time no one was left to speak up."

-- Pastor Martin Niemöller

”起初他们迫害共产党员，我没有说话，因为我不是马克思的信徒。

后来他们迫害犹太人，我没有说话，因为我是日耳曼人。

再后来他们迫害天主教徒，我没有说话，因为我是新教牧师。

最后他们迫害到我头上，我环顾四周，却再也没有人能为我说话。”

description:
有 $k$ 个人，X 要对这 $k$ 个人进行迫害。

这 $k$ 个人，每一个人都拥有一个数字，分别从 $1$ 至 $k$。

X 拥有 $n+m$ 个数字，这些数字为 $n$ 个 $1$ 和 $m$ 个大小可由 X 决定的数字（每个数字定好之后不能更换）。

X 能对这些人进行迫害，当且仅当他能用手中若干个数的加和等于被迫害人的数字，一次迫害就成功了（不会消耗数字）。

由于 X 的权利极大，又十分邪恶，他想要从第 $1$ 个人开始**一个一个**进行迫害行动。

由于小 Z 也在这个被迫害的行列里，他十分的慌张，希望你来告诉他 X 能最多能从第一个人开始连续迫害多少个人。

由于被迫害的人太多了，所以请将答案对 $1000000007$ 取模。

inputFormat: 第一行两个整数 $n,m$，表示 X 有 $n$ 个 $1$，有 $m$ 个大小可自定的数。

outputFormat: 请你告诉小 Z，X 能迫害多少个人。

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

X 选取 $2$ 个数分别为 $2,4$，可知能连续迫害 $7$ 个人。

**【样例 2 解释】**

X 选取 $2$ 个数分别为 $3,6$，可知能连续迫害 $11$ 个人。

---

**【数据范围】**

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

- Subtask 1（50 points）：$1 \le n \le 5$，$1 \le m \le 5$。
- Subtask 2（30 points）：保证答案在取模前在 $10^{18}$ 之内。
- Subtask 3（20 points）：无特殊限制。

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