yl-9/probench huggingface dataset:
# 三目运算

## 题目描述

三目运算是一种比较特殊的运算，功能类似于 `if` 语句，其语法格式如下：

`条件?数值1:数值2`，三目运算得到的结果也是数值。当条件成立时得到的结果是数值 1，不成立时得到的结果为数值 2。

例如，`x>5?8:6` 就是一种三目运算表达式（也是分段常数表达式，见下文）。当 $x=7$ 时，该表达式的结果为 $8$，而 $x=3$ 时，该表达式的结果为 $6$。

---

本题中，称满足下列条件中**至少一条**的字符串 $S$ 是**分段常数表达式**：

- 十进制正整数 $a$，如 `243`，是分段常数表达式。
- 如果 $a$ 为一个十进制正整数，$p,q$ 为两个分段常数表达式，则 $\texttt{x>}a\texttt{?}p\texttt{:}q$ 是分段常数表达式。
- 如果 $a$ 为一个十进制正整数，$p,q$ 为两个分段常数表达式，则 $\texttt{x<}a\texttt{?}p\texttt{:}q$ 是分段常数表达式。

（后两条条件中， $x>a$ 和 $x<a$ 是条件，$p,q$ 为数值，该表达式是三目运算表达式。）

例如，`x>154?220:x<37?16:10` 是一个分段常数表达式，因为 `220` 和 `x<37?16:10` 都是分段常数表达式，从而整个表达式由第 2 条规则也是分段常数表达式。

---

给出一个分段常数表达式 $S$，保证出现的正整数均不超过 $m$。

yummy 有 $q$ 个询问，每次给出一个自然数 $x$ 的值，希望你求出分段常数表达式的值。

## 输入格式

输入的第一行有两个正整数 $m,q$，分别表示表达式出现数字的最大可能值和询问个数。

第二行有一个字符串 $S$，表示这个分段常数表达式。

之后有 $q$ 行，每行有一个自然数 $x$，表示一次询问。

## 输出格式

对于每个询问输出一行一个正整数，表示表达式的结果。

## 样例 #1

### 样例输入 #1

```
20 5
x>12?x<15?4:10:x<12?14:7
15
12
14
7
1000000
```

### 样例输出 #1

```
10
7
4
14
10
```

## 样例 #2

### 样例输入 #2

```
参见 expr/expr2.in
```

### 样例输出 #2

```
参见 expr/expr2.ans
```

## 样例 #3

### 样例输入 #3

```
参见 expr/expr3.in
```

### 样例输出 #3

```
参见 expr/expr3.ans
```

## 样例 #4

### 样例输入 #4

```
参见 expr/expr4.in
```

### 样例输出 #4

```
参见 expr/expr4.ans
```

## 提示

【样例 1 解释】

如果我们进行适当的换行和缩进可以得到：

```cpp
x>12?    //如果 x>12
  x<15?  //那么判断 x<15 是否成立
    4    //如果是则得到 4
    :10  //如果不是则得到 10
  :x<12? //否则（如果 x<=12) 判断 x<12 是否成立
    14   //如果是则返回 14
    :7   //如果不是则返回 7
```

按照这个思路模拟即可得到样例输出。

【样例 2 解释】

该样例满足测试点 $6$ 的性质。

【样例 3 解释】

该样例满足测试点 $10$ 的性质。

【样例 4 解释】

该样例满足测试点 $19$ 的性质。

【数据范围】

设 $n$ 为 $S$ 中三目运算符的个数。（选手可以通过 $n$ 来估计 $S$ 的串长。）

对于全体数据，保证 $0\le n\le 10^5$，$1\le m\le 10^5$，$1\le q\le 10^5​$，$1\le x\le 10^9$，且 $S$ 是分段常数表达式。

| 测试点编号  | $n\le$ | $m\le$ | $q\le$ |
|:-:|:-:|:-:|:-:|
| $1$         | $0$    | $10^5$ | $10$   |
| $2$         | $1$   | $10^5$ | $10$   |
| $3\sim 5$   | $100$ | $9$    | $10$   |
| $6\sim 9$   | $100$ | $10^5$ | $10$   |
| $10\sim 12$ | $10^5$ | $9$    | $10$   |
| $13\sim 16$ | $10^5$ | $10^5$ | $10$   |
| $17\sim 18$ | $10^5$ | $9$    | $10^5$ |
| $19\sim 25$ | $10^5$ | $10^5$ | $10^5$ |

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛
Difficulty: 普及+/提高
# 配对序列

## 题目描述

一个序列 $s_1,\ldots s_{2k}$ 是**配对的**，当且仅当：

- 对于任意 $1\le i \le k$，$s_{2i}=s_{2i-1}$。
- 对于任意 $1\le i<k$，$s_{2i}\ne s_{2i+1}$。

注意，配对的序列长度必然为偶数。

例如，$3,3,5,5,2,2$ 是配对的，而 $2,2,2,2,5,5$（$s_2=s_3$ 不满足第二条要求）或者 $1,2,3,3,1,1$（$s_1\ne s_2$ 不满足第一条要求）都不是配对的。

给出一个数列 $a_1,\ldots, a_n$，求所有配对的子序列长度的最大值。

## 输入格式

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

第二行有 $n$ 个正整数 $a_1,\ldots,a_n$，表示这个序列。

## 输出格式

输出一行一个自然数，表示最长的配对子序列长度。特别地，如果不存在非空的配对子序列，那么输出 $0$。

## 样例 #1

### 样例输入 #1

```
8
1 2 2 2 2 1 2 2
```

### 样例输出 #1

```
4
```

## 样例 #2

### 样例输入 #2

```
11
1 1 4 1 1 2 1000 2 5 5 4
```

### 样例输出 #2

```
6
```

## 样例 #3

### 样例输入 #3

```
参见 pairing3.in
```

### 样例输出 #3

```
参见 pairing3.out
```

## 样例 #4

### 样例输入 #4

```
参见 pairing4.in
```

### 样例输出 #4

```
参见 pairing4.out
```

## 提示

【样例 1 解释】

取 $1,1,2,2$ 这个子序列即可。

【样例 2 解释】

取 $1,1,2,2,5,5$ 这个配对子序列即可。

【样例 3 解释】

该样例符合测试点 $3$ 的限制。

【样例 4 解释】

该样例符合测试点 $12$ 的限制。

【数据范围】

对于全体数据，保证 $2\le n\le 5\times 10^5$，$1\le a_i\le 5\times 10^5$。

|测试点编号|$n\le$|$a_i\le$|特殊性质|
|:-:|:-:|:-:|:-:|
|$1\sim 2$|$18$|$5\times 10^5$||
|$3\sim 5$|$500$|$500$||
|$6\sim 7$|$5000$|$5000$||
|$8\sim 9$|$5000$|$5\times 10^5$||
|$10$|$5\times 10^5$|$5\times 10^5$|每个数最多出现 $1$ 次|
|$11$|$5\times 10^5$|$5\times 10^5$|$a_i\le a_{i+1}$ 恒成立|
|$12\sim 14$|$5\times 10^5$|$5\times 10^5$|每个数最多出现 $2$ 次|
|$15\sim 20$|$5\times 10^5$|$5\times 10^5$||

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛
Difficulty: 普及+/提高
# 「SFMOI Round I」Strange Cake Game

## 题目背景

[English statement](https://www.luogu.com.cn/problem/T510646). **You must submit your code at the Chinese version of the statement.**

小 $\mathcal{W}$ 和 小 $\mathcal{M}$ 在 CF 庄园里分蛋糕。

## 题目描述

有一块面积为 $n\times m$ 的矩形蛋糕。记其左上角顶点为 $(0,0)$，右下角顶点为 $(n,m)$，右上角顶点为 $(0,m)$。

蛋糕上分布着 $k$ 块巧克力，第 $i$ 块的位置为 $(x_i-0.5,y_i-0.5)$。**一个点上可能有不止一块巧克力。**

小 M 和 小 W 要切蛋糕。蛋糕刀起初在 $(0,0)$，小 W 先手，轮流移动蛋糕刀。设蛋糕刀在 $(x,y)$，则它可以被移动到 $(x,y+1)$ 或 $(x+1,y)$。

在若干步后，蛋糕会被切割轨迹完全分成两个部分——右上角的部分归小 W，左下角的部分归小 M。小 W 和小 M 都想吃到最多的巧克力，请帮他们计算：如果双方都按照最优策略行动，小 W 能分到几块巧克力。

如下是蛋糕的示例和一种可能的切蛋糕的方式。

![蛋糕示例](https://cdn.luogu.com.cn/upload/image_hosting/er9wuv91.png?x-oss-process=image/resize,m_lfit,h_500)
![切蛋糕示例](https://cdn.luogu.com.cn/upload/image_hosting/9o6ntvlb.png?x-oss-process=image/resize,m_lfit,h_500)

## 输入格式

第一行，两个正整数 $n,m$，含义见题面。

第二行，一个整数 $k$ ，表示巧克力块数。

接下来 $k$ 行，每行两个正整数 $x_i,y_i$，表示第 $i$ 块巧克力的坐标为 $(x_i-0.5,y_i-0.5)$。

注意：第 $i$ 块巧克力的坐标为 $(x_i-0.5,y_i-0.5)$。**一个格子上可能有多块巧克力。**

## 输出格式

输出一个整数，代表小 W 最多能拿到的巧克力块数。

## 样例 #1

### 样例输入 #1

```
3 3
1
1 3
```

### 样例输出 #1

```
1
```

## 提示

### 数据范围

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

- Subtask 1（5 pts）：$n=m=1$；
- Subtask 2（10 pts）：$1 \le n \times m \le 60$；
- Subtask 3（15 pts）：$1 \le n \times m \le 10^5$；
- Subtask 4（20 pts）：$k=1$；
- Subtask 5（50 pts）：无特殊限制。


对于 $100\%$ 的数据，保证：

- $0 \le k \le 2 \times 10^5$；
- $1 \le n,m \le 10^{18}$；
- $1 \le x_i \le n$，$1 \le y_i \le m$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 贪心, 博弈论, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及−
# 「SFMOI Round I」Strange Madoka Game

## 题目背景

[English statement](https://www.luogu.com.cn/problem/T510969). **You must submit your code at the Chinese version of the statement.**

> いつも君の側にいるから / 无论何时我都与你同在 \
> 儚すぎて / 世界如此虚幻 \
> 消えて行きそうな世界 / 似乎随时随地都会消失 \
> だけど君がいる / 然而只要有你 \
> それだけで守りたいと思った / 我就心甘情愿将它守护

## 题目描述

**本题和 B2 是不同的问题，请分别仔细阅读两题题面。**

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

**提示**：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

圆和焰在玩游戏。

圆在心中想了一个非负整数 $m$，让焰猜出 $m$ 的值。当然，圆不会为难焰，所以 $\textcolor{red}{0}\le m\le 10^{17}$。圆不会作弊，也就是说，**圆不会悄悄更换想好的数字。**

焰可以问圆：对于**正**整数 $x$，$m\bmod x$ 的值是多少。焰需要用最少的询问次数来猜出 $m$ 的值。（为了得到全部分数，最多只能使用 $2$ 次询问。）

圆一共和焰玩了 $T$ 次游戏。然而，焰的数学很差，于是她找来了你，来帮她猜出这 $T$ 次游戏的答案。



**形式化地**：有一个隐藏的非负整数 $m\in [\textcolor{red}{0},10^{17}]$。每次询问给定**正**整数 $x$，回答 $m\bmod x$。用最少的询问次数找出 $m$。共有 $T$ 组测试数据。$m$ 的数值在事先确定，不会根据询问变化，也就是说，**交互库是非适应性的**。

【实现细节】

对于每个测试点，输入一行一个正整数 $T$，表示游戏次数。

对于每组测试数据，你可以用以下的格式发起一次询问：

- $\texttt{? }x$：询问 $m\bmod x$ 的值。你需要保证 $x$ 是**正**整数，且 $x \in \textcolor{red} {[1,4\times 10^8]}$。

	从标准输入流读入一个整数表示答案。特别地，若整数是 $\texttt{-1}$，你的程序已经被判定为 $\texttt{Wrong Answer}$，此时你需要立刻终止程序。

你可以用以下的格式回答答案：

- $\texttt{! }m$：回答 $m$ 的值。

在发起询问后，需要刷新缓冲区，否则可能导致 TLE。

- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。 特别地，利用 `std::endl` 来换行也会刷新缓冲区。
- 在 Pascal 中，使用 `flush(output)`。  
- 在 Python 中，使用 `stdout.flush()`。  
- 对于其它语言，可自行查阅文档。

## 输入格式

见【实现细节】。

## 输出格式

见【实现细节】。

## 样例 #1

### 样例输入 #1

```
1

1

2
```

### 样例输出 #1

```
? 2

? 3

! 5
```

## 提示

#### 数据范围

对于 $100\%$ 的数据，保证 $1\le T\le 100$，$m$ 为非负整数，$\textcolor{red}{0}\le m\le 10^{17}$。

#### 评分方式

记单个测试点中，你的询问次数的最大值为 $Q$。则得分 $\mathrm{score}$ 如下所示：

$$
\begin{aligned}
\mathrm{score}=\begin{cases}
0, & Q\in [81,+\infty) \\
10, & Q\in [11,81) \\
25, & Q\in [3,11) \\
50, & Q\in [0,3) \\
\end{cases}
\end{aligned}
$$

本题得分为所有测试点得分的最小值。

本题数据点的范围是非严格单调递增的。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 数论, 不定方程, 洛谷原创, 洛谷月赛, 交互题, Special Judge, O2优化
Difficulty: 普及/提高−
# 「SFMOI Round I」Strange Homura Game

## 题目背景

[English statement](https://www.luogu.com.cn/problem/T514577). **You must submit your code at the Chinese version of the statement.**

> 伝えたいコトバは たったひとつ / 想要传达的言语 唯有一个 \
> キミがいたから 強くなれた / 因有你在 我变坚强了 \
> 2 人ならどんな空も飛べるね / 只要两人一起就能任意飞翔 \
> キミをいつでも 信じてるから / 因为一直都 坚信着你 \
> ずっとずっと夢を見ていよう / 能同做此梦不复醒吧

## 题目描述

**本题和 B1 是不同的问题，请分别仔细阅读两题题面。**

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


**提示**：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

焰和圆在玩游戏。

焰在心中想了一个正整数 $m$，让圆猜出 $m$ 的值。当然，焰不会为难圆，所以 $\textcolor{red}{2}\le m\le 10^{17}$。焰不会作弊，也就是说，**焰不会悄悄更换想好的数字。**

圆可以问焰：对于**非负**整数 $x$，$x\bmod m$ 的值是多少。圆需要用最少的询问次数来猜出 $m$ 的值。（为了得到全部分数，最多只能使用 $2$ 次询问。）

焰一共和圆玩了 $T$ 次游戏。圆的数学很好，在 $\varepsilon $ 秒内就秒了这题，但是她在军训，于是她找来了你，来帮她猜出这 $T$ 次游戏的答案。



**形式化地**：有一个隐藏的正整数 $m\in [\textcolor{red}{2},10^{17}]$。每次询问给定**非负**整数 $x$，回答 $x\bmod m$。用最少的询问次数找出 $m$。共有 $T$ 组测试数据。$m$ 的数值在事先确定，不会根据询问变化，也就是说，**交互库是非适应性的**。

【实现细节】

对于每个测试点，输入一行一个正整数 $T$，表示游戏次数。

对于每组测试数据，你可以用以下的格式发起一次询问：

- $\texttt{? }x$：询问 $x\bmod m$ 的值。你需要保证 $x$ 是**非负**整数，且 $x \in \textcolor{red}{ [0,10^{18}]}$。
	
    从标准输入流读入一个整数表示答案。特别地，若整数是 $\texttt{-1}$，你的程序已经被判定为 $\texttt{Wrong Answer}$，此时你需要立刻终止程序。

你可以用以下的格式回答答案：

- $\texttt{! }m$：回答 $m$ 的值。

在发起询问后，需要刷新缓冲区，否则可能导致 TLE。

- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。 特别地，利用 `std::endl` 来换行也会刷新缓冲区。
- 在 Pascal 中，使用 `flush(output)`。  
- 在 Python 中，使用 `stdout.flush()`。  
- 对于其它语言，可自行查阅文档。

## 输入格式

见【实现细节】。

## 输出格式

见【实现细节】。

## 样例 #1

### 样例输入 #1

```
1

0

1
```

### 样例输出 #1

```
? 5

? 1

! 5
```

## 提示

#### 数据范围

对于 $100\%$ 的数据，保证 $1\le T\le 100$，$m$ 为正整数，$\textcolor{red}{2}\le m\le 10^{17}$。

#### 评分方式

记单个测试点中，你的询问次数的最大值为 $Q$。则得分 $\mathrm{score}$ 如下所示：

$$
\begin{aligned}
\mathrm{score}=\begin{cases}
0, & Q\in [101,+\infty) \\
30, & Q\in [3,101) \\
50, & Q\in [0,3) \\
\end{cases}
\end{aligned}
$$

本题得分为所有测试点得分的最小值。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: Ad-hoc, 洛谷原创, 洛谷月赛, 交互题, Special Judge, O2优化
Difficulty: 普及/提高−
# 「SFMOI Round I」Strange Train Game

## 题目背景

[English statement](https://www.luogu.com.cn/problem/T512993). **You must submit your code at the Chinese version of the statement.**

SFM 团队又断网了，于是玩起了 Mini Metro，结果发现游戏更新了，列车要自己组装，于是有了这题。

## 题目描述

**提示**：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

SFM 号列车由 $n$ 节车厢组成，编号为 $1\sim n$。每节车厢有一个舒适度 $a_i\in \{0,1\}$，$0$ 代表不舒适，$1$ 代表舒适。管理组想要让舒适的车厢的编号尽量小，也就是说，让 $a$ 的字典序最大。

为此，管理组运来了一辆 $n$ 节车厢的备用车，舒适度表示为 $b_i\in \{0,1\}$。共有 $m$ 个可进行的操作，第 $i$ 个操作的操作参数为 $l_i,r_i$，表示 $\forall l_i\le k\le r_i$，交换 $a_k,b_k$。

可以**从小到大依次**决定是否执行每个操作，但是一共有 $2^m$ 种方案，于是，管理组找来了你，帮忙选出一种最优的方案，最大化 $a$ 的字典序。只需要输出最终得到的 $a$ 即可。

**形式化地**：给定长度为 $n$ 的 $01$ 串 $a,b$，给定 $2m$ 个正整数 $l_i,r_i$。对于 $i=1,2,\cdots,m$，**依次**执行以下操作：
- 选择是否执行第 $i$ 次操作。
    - 如果执行，则对于 $k=l_i,l_{i}+1,\cdots,r_i$，交换 $a_k,b_k$。

最大化 $a$ 的字典序并输出最终的结果。

## 输入格式

第一行，两个正整数 $n,m$，表示字符串的长度和操作次数。

第二行，一个长度为 $n$ 的 $01$ 串 $a$。

第三行，一个长度为 $n$ 的 $01$ 串 $b$。

接下来 $m$ 行，每行两个正整数 $l_i,r_i$，描述第 $i$ 个操作。

## 输出格式

输出一行长度为 $n$ 的 $01$ 串，表示最优操作后的 $a$。

## 样例 #1

### 样例输入 #1

```
10 5
0101011001
0101001110
5 10
2 6
1 10
6 6
3 4
```

### 样例输出 #1

```
0101011110
```

## 提示

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

- Subtask 1（20 pts）：$1\le n,m\le 20$；
- Subtask 2（30 pts）：$l_i$ 互不相同，$a_i \ne b_i$；
- Subtask 3（30 pts）：$1 \le n ,m \le 10^3$；
- Subtask 4（20 pts）：无限制；

对于 $100\%$ 的数据，保证：
- $1\le n,m\le 2\times 10^5$；
- $1\le l_i\le r_i\le n$。

## 时空限制



时间限制
1.00s

内存限制
500.00MB

Tags: 贪心, 并查集, 图论建模, 线性基, 随机化, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 提高+/省选−
# 「FSLOI Round I」单挑

## 题目背景

**[English statement](https://www.luogu.com.cn/problem/T491159). You must submit your code at the Chinese version of the statement.**

小 F 和小 S 经常进行篮球单挑，但小 S 总是被盖帽。

## 题目描述

每次单挑的结果一定是小 F 获胜或者小 S 获胜，不存在平局的情况。

由于小 F 和小 S 实力不均衡，于是他们制定规则如下：

给定两个整数 $x,y$，若小 F 先赢 $x$ 场，则小 F 获胜。若小 S 先赢 $y$ 场，则小 S 获胜。

现在已经进行了 $n$ 场单挑，这 $n$ 场单挑的结果由一个字符串 $s$ 给出。若 $s$ 的第 $i$ 位为 `F`，则小 F 赢了第 $i$ 场。若 $s$ 的第 $i$ 位为 `S`，则小 S 赢了第 $i$ 场。

小 F 想知道，为了取得胜利，后续的比赛中他**最多连续胜利的场数最少是多少**。

你总共需要回答 $T$ 组询问。

## 输入格式

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

每组数据共两行。

第一行三个整数 $n,x,y$，含义与题目描述一致。

第二行一个长度为 $n$ 的字符串 $s$，含义与题目描述一致。

## 输出格式

共 $T$ 行。

每行一个整数，表示小 F 在后续的比赛中最多连续胜利的场数的最小值。

## 样例 #1

### 样例输入 #1

```
1
5 6 4
SFSFS
```

### 样例输出 #1

```
4
```

## 样例 #2

### 样例输入 #2

```
1
3 7 3
FFF
```

### 样例输出 #2

```
2
```

## 样例 #3

### 样例输入 #3

```
1
29 1000 20
FFFSFFFFSFFFFFSFFFSFFFFFFSFFF
```

### 样例输出 #3

```
66
```

## 提示

**【样例 1 解释】**

为了让小 F 获胜，后续的比赛结果只能为 $ \texttt {FFFF}$，此时最多连续胜利场数为 $4$。

**【样例 2 解释】**

为了让小 F 获胜，一种可能的后续的比赛结果为 $ \texttt {FFSFSF}$，此时最多连续胜利场数为 $2$。

请注意，您只需考虑**后续**的比赛中的最多连续胜场数，而不需要考虑前 $n$ 场。

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

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

对于 $100 \%$ 的数据，保证：
- $1 \leq T \leq 20$
- $1 \leq n \leq 2\times10^5$
- $1 \leq x,y \leq 10^9$
- $\forall i \leq n$，保证第 $i$ 场比赛结束后小 S 没有获胜。
- $\forall i < n$，保证第 $i$ 场比赛结束后小 F 没有获胜。

|子任务|分值|特殊性质|
|:-----:|:-----:|:-----:|
|$1$|$10$|$n=1$|
|$2$|$15$|$x,y\leq n$|
|$3$|$15$|$A$|
|$4$|$30$|$T=1$|
|$5$|$30$|无|

- 特殊性质 $A$：第 $n$ 场比赛结束后，小 S 总共获胜 $y-1$ 场。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 数学, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 入门
# 「FSLOI Round I」石子

## 题目背景

**[English statement.](https://www.luogu.com.cn/problem/T500971) You must submit your code at the Chinese version of the statement.**

小 F 和小 L 正在玩一种古老的博弈游戏的改版。

## 题目描述

给定 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子。设序列 $a_1,a_2,\cdots,a_n$ 的平均数为 $x$。此外，还会给定一个不大于 $x$ 的数字 $k$。小 F 和小 L 将轮流进行以下操作直至一方胜出，小 F 先手：

- 选定两堆石子 $i,j$，满足 $a_i < x < a_j$。若无法选出这样的两堆石子，则对方获胜。

- 从第 $j$ 堆石子中拿出 $k$ 个石子放到第 $i$ 堆中。

小 F 和小 L 都将用最优策略进行操作。

若游戏会无限进行下去，输出 `Draw`。若小 F 将获胜，输出 `F`。否则，输出 `L`。

小 F 一共会进行 $T$ 场游戏，你需要告诉他每场游戏的结果。

## 输入格式

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

每组数据共两行。

第一行输入两个整数 $n,k$。

第二行输入 $n$ 个整数 $a_i$。

## 输出格式

共 $T$ 行。

每行应为 `Draw`，`F`，`L` 中的一种。

## 样例 #1

### 样例输入 #1

```
1
5 2
1 5 7 9 13
```

### 样例输出 #1

```
L
```

## 样例 #2

### 样例输入 #2

```
2
6 3
4 7 5 3 1 16
7 2
2 6 4 8 12 4 6
```

### 样例输出 #2

```
Draw
L
```

## 提示

**【样例 1 解释】**

平均数为 $7$。

小 F 可以选择 $i=1,j=5$ 进行操作，使得石子数分别为 $3,5,7,9,11$。

小 L 可以选择 $i=1,j=4$ 进行操作，使得石子数分别为 $5,5,7,7,11$。

小 F 可以选择 $i=2,j=5$ 进行操作，使得石子数分别为 $5,7,7,7,9$。

小 L 可以选择 $i=1,j=5$ 进行操作，使得石子数分别为 $7,7,7,7,7$。

小 F 无法进行操作。小 L 获胜。可以证明无论小 F 如何操作，小 L 都有必胜策略。

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

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

设 $x$ 为序列 $a$ 的平均值。

对于 $100 \%$ 的数据，保证：
- $1 \leq T \leq 10$
- $1 \leq n \leq 2\times10^5$
- $0 \leq a_i \leq 10^9$
- $1 \leq k \leq x$
- $x$ 为整数

|子任务|分值|特殊性质|
|:-----:|:-----:|:-----:|
|$1$|$5$|$A$|
|$2$|$10$|$k = 1$|
|$3$|$15$|$n \leq 5, T =1$|
|$4$|$25$|$n \leq 1000$|
|$5$|$45$|无|

特殊性质 $A$：$a_1=a_2=a_3=\cdots=a_n$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 博弈论, Ad-hoc, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及−
# 「FSLOI Round I」迷雾

## 题目背景

**[English statement.](https://www.luogu.com.cn/problem/T500989) You must submit your code at the Chinese version of the statement.**

小 F 来到了迷雾之森。

## 题目描述

整个迷雾之森可以由一个 $n \times m$ 的矩阵表示，`X` 代表有迷雾的地块，`.` 代表空地。从上到下给每行标号为 $1,2,\cdots,n$，从左到右给每列标号为 $1,2,\cdots,m$。除此之外，还会给定一个迷雾系数 $k$。

小 F 进行了 $q$ 次移动。第 $i$ 次移动由一个字符 $c_i$，两个数字 $a_i,b_i$ 描述，更具体地说：

- $c_i$ 为 `U` 时，向上走 $a_i$ 步。
- $c_i$ 为 `D` 时，向下走 $a_i$ 步。
- $c_i$ 为 `L` 时，向左走 $a_i$ 步。
- $c_i$ 为 `R` 时，向右走 $a_i$ 步。

当然，小 F 不可以走出这个 $ n \times m $ 的范围。换句话说，若走到边界处，立即结束此次移动。

若第 $i$ 次移动**结束**后小 F 停留在有迷雾的地块上，则小 F 会对从 $i+k$ 开始，之后每 $k$ 次移动的 $c$ 进行一次修改，一共修改 $b_i$ 个移动。也就是说，小 F 会对 $c_{i+k},c_{i+2\times k},\cdots,c_{i+b_i \times k}$ 进行一次**修改**（保证 $i+b_i\times k \leq q$）。若 $b_i=0$ 则相当于不做修改。**注意所有操作的 $k$ 是一样的**。

修改 $c_x$ 即为按照以下规则替换 $c_x$：

- 若 $c_x$ 为 `U`，则替换为 `D`。
- 若 $c_x$ 为 `D`，则替换为 `U`。
- 若 $c_x$ 为 `R`，则替换为 `L`。
- 若 $c_x$ 为 `L`，则替换为 `R`。

初始时小 F 在点 $(1,1)$ 处，请输出 $q$ 次移动后小 F 所在的位置 $(x,y)$。

## 输入格式

第一行四个整数 $n,m,q,k$。

接下来 $n$ 行，每行一个长度为 $m$，由 `.` 和 `X` 构成的字符串，描述整个迷雾之森。

接下来 $q$ 行，每行先是一个字符 $c_i$，然后依次是两个整数 $a_i,b_i$，描述每次移动。

## 输出格式

共一行。

两个整数 $x,y$，表示小 F 最终的位置。

## 样例 #1

### 样例输入 #1

```
3 3 4 1
..X
.XX
XXX
D 1 2
R 1 2
D 2 0
L 1 0
```

### 样例输出 #1

```
1 3
```

## 样例 #2

### 样例输入 #2

```
10 10 8 2
XX.XX.X...
XXX..XXX.X
XXX.X.XXXX
XXXXXXX.X.
.XX...XX.X
.XXX.X.X.X
...XXX.XXX
XX...XX...
X..XX....X
XXXXX...XX
U 2 1
L 1 3
R 3 1
L 1 2
D 2 1
R 5 1
L 4 0
D 3 0
```

### 样例输出 #2

```
1 10
```

## 提示

**【样例 1 解释】**

小 F 的位置变化如下：

$(1,1) \rightarrow (2,1) \rightarrow (2,2)\rightarrow (1,2) \rightarrow (1,3)$

序列 $c$ 的变化如下：

$ \lbrace \texttt{D,R,D,L} \rbrace \rightarrow \lbrace \texttt{D,R,D,L} \rbrace \rightarrow \lbrace \texttt{D,R,U,R} \rbrace \rightarrow \lbrace \texttt{D,R,U,R} \rbrace \rightarrow \lbrace \texttt{D,R,U,R} \rbrace$

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

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

对于 $100 \%$ 的数据，保证：
- $1 \leq n,m \leq 500$
- $1 \leq k \leq 20$
- $1\leq q \leq 2 \times 10^5$
- $1 \leq a_i,b_i \leq 10^6$
- $c_i$ 为 `L`，`R`，`U`，`D` 四个字符中的一个。

|子任务|分值|特殊性质|
|:-----:|:-----:|:-----:|
|$1$|$5$|$q=1$|
|$2$|$15$|$n,m,q\leq 100$|
|$3$|$20$|$k=1$|
|$4$|$30$|$n=1$|
|$5$|$30$|无|

## 时空限制



时间限制
500ms

内存限制
512.00MB

Tags: 线段树, 差分, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及/提高−
# 「FSLOI Round I」山峦

## 题目背景

**[English statement.](https://www.luogu.com.cn/problem/T501030) You must submit your code at the Chinese version of the statement.**

山峦是造物主弃的酒杯。

## 题目描述

如果一个长度至少为三的序列 $a$ 满足以下条件，则称其为一个**山峰**：

- 设其长度为 $m$。存在一个 $x$，满足 $2\leq x \leq m-1$，并且使得 $a_1,a_2,\cdots,a_x$ 严格单调递增，$a_x,a_{x+1},\cdots,a_m$ 严格单调递减。

特别地，称 $a_x$ 为这个山峰的高度。

如果一个序列 $b$ 满足以下任一条件，则称其为一个**山峦**：

- $b$ 序列是一个**山峰**。

- 可以拆成至少两个连续的子序列，使得每个子序列都是**山峰**，且从左到右**山峰的高度**严格单调递增。

比如，序列 $\lbrace 2,4,3,1,5,2,1 \rbrace$ 是山峦，因为其可以拆分为 $\lbrace 2,4,3 \rbrace,\lbrace 1,5,2,1 \rbrace$ 两个山峰，且山峰高度严格递增。而序列 $\lbrace 2,4,3,5,2,1 \rbrace$ 不是山峦，因为其无法拆分成至少两个连续的子序列，使得每个子序列都是山峰。

现在给定一个长度为 $n$ 的序列 $a$，小 F 想知道，在 $a$ 的所有子序列中，有多少个是**山峦**。由于答案可能很大，请输出其对 $998244353$ 取余后的结果。

请注意，在本题中，即使子序列的元素相同，只要子序列的元素在 $a$ 中的位置不同，仍算作不同的子序列。

## 输入格式

共两行。

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

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示 $a$ 序列。

## 输出格式

共一行。

一个整数，表示是山峦的子序列数量对 $998244353$ 取余的结果。

## 样例 #1

### 样例输入 #1

```
4
1 2 2 1
```

### 样例输出 #1

```
2
```

## 样例 #2

### 样例输入 #2

```
7
2 4 3 1 5 2 1
```

### 样例输出 #2

```
35
```

## 样例 #3

### 样例输入 #3

```
20
2 3 5 6 8 7 6 5 6 7 8 8 8 8 4 3 5 6 7 4
```

### 样例输出 #3

```
15085
```

## 提示

**【样例 1 解释】**

由 $a_1,a_2,a_4$ 构成的子序列是山峦，由 $a_1,a_3,a_4$ 构成的子序列是山峦。

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

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

对于 $100 \%$ 的数据，保证：
- $1 \leq n \leq 500$
- $1 \leq a_i \leq 10^6$

|子任务|分值|特殊性质|
|:-----:|:-----:|:-----:|
|$1$|$10$|$n \leq 18$|
|$2$|$15$|$n \leq 80$|
|$3$|$15$|$A$|
|$4$|$20$|$B$|
|$5$|$40$|无|

特殊性质 $A$：序列 $a$ 是山峰。

特殊性质 $B$：序列 $a$ 中的元素互不相同。

## 时空限制



时间限制
500ms

内存限制
512.00MB

Tags: 动态规划 DP, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 提高+/省选−
# 「LAOI-6」[太阳]] 请使用最新版手机 QQ 体验新功能

## 题目背景

**[English statement](https://www.luogu.com.cn/problem/U481351). You must submit your code at the Chinese version of the statement.**

「」

---

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

## 题目描述

你的 QQ 收到了一条新消息！但是你很生气，因为你看不到别人发送的超级表情。

消息形如一个字符串 $S$，包含且仅包含一个超级表情。具体地，$S$ 的拼音被采用驼峰命名法处理，因此其形如：

```plain
[AaaBbbCcc......]]QingShiYongZuiXinBanShouJiQQTiYanXinGongNeng
```

也就是说，将 $\texttt [w\texttt{]]请使用最新版手机QQ体验新功能}$ 中的每个汉字替换为其拼音，其中 $w$ 为表情的实际中文名称，保证其包含至少一个音节，**其中每个音节包含一个大写英文字母和至少一个小写英文字母**。

你想在电脑上也能发出这个表情。为此，你需要键入一个正斜杠（$\texttt /$）加它的「拼音缩写」。**具体地，表情 $\bm w$ 的「拼音缩写」即为 $\bm w$ 的每个音节的首字母转为小写后拼接的结果**。例如，`TaiYang` 的「拼音缩写」为 $\texttt{/ty}$，而 `YueLiang` 的「拼音缩写」为 $\texttt{/yl}$。

请你输出在电脑端表示发送这个表情的字符串。

请注意：这个字符串可能在 QQ 中实际上不能表示这个表情，例如 `NiZhenBangBang`（一个超级表情） 不能在 QQ 中用 $\texttt{/nzbb}$ 来打出，但是在本题中，我们认为其是合法的。

## 输入格式

输入仅一行：一个字符串 $S$。

## 输出格式

输出一行一个字符串，表示答案。

## 样例 #1

### 样例输入 #1

```
[TaiYang]]QingShiYongZuiXinBanShouJiQQTiYanXinGongNeng
```

### 样例输出 #1

```
/ty
```

## 样例 #2

### 样例输入 #2

```
[LiuLei]]QingShiYongZuiXinBanShouJiQQTiYanXinGongNeng
```

### 样例输出 #2

```
/ll
```

## 提示

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

对于 $100 \%$ 的数据，保证给出的字符串 $S$ 满足题目中所写的 `[AaaBbbCcc......]]QingShiYongZuiXinBanShouJiQQTiYanXinGongNeng` 的格式，且保证 $\lvert S\rvert \leq 100$；给出的 $S$ 描述一个真实存在的 QQ 超级表情。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 模拟, 字符串, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 入门
# 「LAOI-6」Radiation

## 题目背景

[English statement](https://www.luogu.com.cn/problem/T503655). You must submit your code at the Chinese version of the statement.

## 题目描述

小 T 和 小 U 在一个 $n \times m$ 的初始为空的棋盘上玩游戏。小 T 先在上面摆 $k$ 个石头，然后小 U 会使用宇宙射线毁掉所有石头。但是小 U 的宇宙射线威力有限，只能每次销毁一行或一列的石头。

小 U 不想过多用他的宇宙射线发射器，所以他会按照最优策略销毁石头。反之，小 T 偏偏想让小 U 发射最多的宇宙射线，所以他会摆放石头以做到这一点。问题来了：小 T 不会摆放了。你能够找到一种方法帮助小 T 达到目标吗？

## 输入格式

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

第一行一个整数 $T$。

然后 $T$ 行，每行 $n,m,k$ 三个整数，表示这组数据的游戏设定。

## 输出格式

对于每组数据，输出 $n$ 行 $m$ 列共 $nm$ 个字符，第 $i$ 行第 $j$ 个字符如果为 `S` 那么代表棋盘的第 $i$ 行第 $j$ 列有石头；如果为 `.` 那么代表棋盘的第 $i$ 行第 $j$ 列没石头。

你需要保证每组数据中输出的字符 `S` 的个数为 $k$。

## 样例 #1

### 样例输入 #1

```
2
3 5 2
5 4 7
```

### 样例输出 #1

```
S....
....S
.....
S..S
...S
S.S.
...S
.S..
```

## 提示

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

子任务 1（$20$ 分）：保证 $k \leq \min(n,m)$。

子任务 2（$12$ 分）：保证 $n = 2$。

子任务 3（$18$ 分）：保证 $T,n,m \leq 10$。

子任务 4（$20$ 分）：保证 $T \leq 10$，$n,m \leq 300$。依赖子任务 $3$。

子任务 5（$30$ 分）：无特殊限制。依赖子任务 $1 \sim 4$。

对于所有数据，保证 $1 \leq T \leq 10^4$，$1 \leq n,m \leq 2 \times 10^3$，$0 \leq k \leq nm$，$\sum nm \leq 5 \times 10^6$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 贪心, 构造, 洛谷原创, 洛谷月赛, Special Judge, O2优化
Difficulty: 普及−
# 「LAOI-6」区间测速

## 题目背景

[English statement](https://www.luogu.com.cn/problem/T503704). You must submit your code at the Chinese version of the statement.

## 题目描述

小 A 正在一条笔直的公路上行驶（可以随时掉头，掉头的时间和路程忽略不计），这条公路可以被抽象为一条数轴。

你现在得到了 $n$ 个监控的信息，第 $i$ 条信息记录到：小 A 在 $t_i$ 时刻经过了坐标为 $x_i$ 之处。

有 $m$ 次询问，第 $i$ 次询问给定 $u_i$ 和 $v_i$，表示：假如将第 $u_i$ 个监控记录到小 A 经过 $x_i$ 的时间改为 $v_i$，小 A 所有可能的行驶过程中，最快时速的最小值是多少（答案向下取整）？**询问之间互相独立，即每次询问的改动是暂时的**。

### 形式化题意

给定 $n,m$，有长度为 $n$ 的数组 $x$ 与 $t$。进行 $m$ 次独立的修改，第 $i$ 次会将 $t_{u_i}$ 修改为 $v_i$，并询问：

$$\max_{i=1}^{n}\max_{j=i+1}^n \left\lfloor\frac{|x_i-x_j|}{|t_i-t_j|}\right\rfloor$$

**前一次修改不会影响后一次修改，即询问结束后会撤销修改**。

## 输入格式

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

接下来 $n$ 行，每行两个整数 $x_i,t_i$。

接下来 $m$ 行，每行两个整数 $u_i,v_i$。

## 输出格式

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

## 样例 #1

### 样例输入 #1

```
5 3
10 3
-10 1
0 5
-5 0
10 7
1 2
2 2
3 100
```

### 样例输出 #1

```
20
20
10
```

## 提示

样例解释：

第 $1$ 次询问：

小 A 第 $0$ 时刻位于 $-5$，第 $1$ 时刻位于 $-10$，第 $2$ 时刻位于 $10$，第 $5$ 时刻位于 $0$，第 $7$ 时刻位于 $10$，最快时速最慢是 $20$（$1$ 时刻到 $2$ 时刻，从 $-10$ 移动到 $10$ 的时候）。

---

本题共有 $10$ 个测试点，每个测试点分值均为 $10$ 分。

| 测试点编号 | 特殊性质 |
| :----------: | :----------: |
| $1 \sim 3$ | $n,m\leq 10^3$ |
| $4 \sim 5$ | $-10^5\leq x_i\leq 10^5$ |
| $6 \sim 7$ | $m\leq 100$ |
| $8 \sim 10$ | N/A |

对于 $100\%$ 的数据，$2\leq n\leq 10^5$，$1\leq m\leq 10^5$，$-10^9\leq x_i\leq 10^9$，$0\leq t_i,v_i\leq 10^9$，$1\leq u_i\leq n$，保证任意时刻不存在两个监控记录的时间相同。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 数学, 贪心, 二分, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及+/提高
# 「LAOI-6」Yet Another Graph Coloration Problem

## 题目背景

[English statement](https://www.luogu.com.cn/problem/U477166). You must submit your code at the Chinese version of the statement.

## 题目描述

小 R 有一张 $n$ 个节点和 $m$ 条的边简单无向图，节点的编号依次为 $1 \sim n$。她想要为图中的每个节点分配黑色或白色的颜色，使得：

- 有至少 $1$ 个黑色节点；
- 有至少 $1$ 个白色节点；
- 对于任何一对点对 $(u, v)$，只要 $u$ 和 $v$ 的颜色不同，就存在至少 $2$ 条从 $u$ 到 $v$ 的不同的简单路径。
	- 简单路径是图上指不重复经过同一点的路径。
	- 若两条简单路径不同，要么其长度不同，要么至少存在一个正整数 $i$ 使两条路径经过的第 $i$ 个点不同。

或者，报告解不存在。

## 输入格式

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

第一行，一个整数 $T$，表示数据组数。对于每组数据：

- 第一行，两个整数 $n, m$，表示图的节点数和边数。
- 接下来 $m$ 行，每行两个整数 $u, v$，表示有一条 $u, v$ 之间的边。

保证给出的图无重边、无自环。

## 输出格式

对于每组数据：

- 若有解，输出一行长为 $n$ 的字符串，第 $i$ 个字符为 `B` 表示 $i$ 号节点为黑色，为 `W` 表示 $i$ 号节点为白色；
- 若无解，仅输出一行一个整数 $-1$。

如果有多种合法的解，你只需要输出任意一种即可。

## 样例 #1

### 样例输入 #1

```
3
4 5
1 2
1 3
1 4
2 3
3 4
5 6
1 2
1 3
1 5
2 3
2 4
3 4
6 10
1 2
1 3
1 5
2 3
2 4
2 5
2 6
3 5
3 6
4 6
```

### 样例输出 #1

```
BWBW
BBWWB
BWBWBW
```

## 样例 #2

### 样例输入 #2

```
1
4 3
1 2
1 3
2 3
```

### 样例输出 #2

```
-1
```

## 提示

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

- Subtask 0（15 pts）：$\sum 2^n \leq 2^{16}$。
- Subtask 1（25 pts）：$n \leq 3\times 10^3$，$m \leq 3\times 10^3$，$\sum n \leq 10^4$，$\sum m \leq 2\times 10^4$。
- Subtask 2（5 pts）：保证图不连通。
- Subtask 3（10 pts）：保证每个点的度数均为 $2$。
- Subtask 4（20 pts）：保证 $n = m$。
- Subtask 5（25 pts）：无特殊限制。

对于所有数据，保证 $1 \leq T \leq 10^5$，$2 \leq n \leq 2 \times 10^5$，$0 \leq m \leq 2 \times 10^5$，$\sum n \leq 2\times 10^6$，$\sum m \leq 2\times 10^6$，保证给出的图无重边、无自环。

## 时空限制



时间限制
1.50s

内存限制
512.00MB

Tags: 图论, 深度优先搜索 DFS, 拓扑排序, Tarjan, 双连通分量, 构造, 圆方树, 洛谷原创, 洛谷月赛, Special Judge, O2优化
Difficulty: 普及+/提高