yl-9/probench huggingface dataset:
# 「Diligent-OI R1 C」DlgtRank

## 题目描述

给你一个长为 $n$ 的序列 $a_1\sim a_n$。这里定义 $a_i$ 的**排名**为 $a$ 中**严格大于** $a_i$ 的数的个数 $+1$。

现有一些操作来更改 $a$ 中的元素。所有操作之前会事先给你一个常量 $k$。每次操作前，定义 $a_i$ 是**可移动**的，当且仅当**仅将 $a_i$ 的值加上 $k$，其他值不变**后，$a_i$ 的排名不变。否则 $a_i$ 在这次操作是不可移动的。然后这次操作为：将序列中所有可移动的数加上 $k$。

可以证明经过若干次操作后，$a$ 中所有值都会变成可移动的，并且第一次达到这种状态时，后面的操作也会是这种状态。也就是说，无论做多少次操作，$a$ 中每个值为**不可移动**状态的次数是有限的。

现在询问，做足够多次这个操作后，$a$ 中每个值为**不可移动**状态的次数是多少。

## 输入格式

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

接下来一行，输入 $n$ 个整数 $a_1\sim a_n$ 表示初始时的 $a$ 数列。

## 输出格式

输出一行 $n$ 个整数。第 $i$ 个整数表示 $a_i$ 在操作过程中为**不可移动**状态的次数。

## 样例 #1

### 样例输入 #1

```
3 1
1 3 4
```

### 样例输出 #1

```
1 1 0
```

## 样例 #2

### 样例输入 #2

```
6 2
1 2 5 6 7 8
```

### 样例输出 #2

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

## 样例 #3

### 样例输入 #3

```
8 10
1 14 5 14 19 19 8 10
```

### 样例输出 #3

```
5 1 4 1 0 0 3 2
```

## 提示

#### 样例 #1 解释

初始的 $a_1=1,a_2=3,a_3=4$。

操作一次后 $a_1=2,a_2=3,a_3=5$。$a_2$ 不可移动，是因为如果仅将 $a_2$ 加上 $1$，它的排名会由 $2$ 变成 $1$。

操作两次后 $a_1=2,a_2=4,a_3=6$。$a_1$ 不可移动，是因为如果仅将 $a_1$ 加上 $1$，它的排名会由 $3$ 变成 $2$。

操作三次后 $a_1=3,a_2=5,a_3=7$。这次操作所有值都是可移动的了。可以证明再操作任意多次也不会再出现不可移动的状态了。

因此过程中 $a_1$ 有一次不可移动，$a_2$ 有一次不可移动，$a_3$ 没有不可移动的时候。

#### 数据范围与约定

对于 $100\%$ 数据，$1\le n\le2\times10^5$，$1\le k,a_i\le10^9$。

| Subtask 编号 | $n\le$ | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: | :----------: |
| $0$ | $1$ | ABC | $4$ |
| $1$ | $100$ | C | $14$ |
| $2$ | $100$ | 无 | $13$ |
| $3$ | $3000$ | C | $18$ |
| $4$ | $3000$ | 无 | $16$ |
| $5$ | $2\times10^5$ | A | $6$ |
| $6$ | $2\times10^5$ | BC | $8$ |
| $7$ | $2\times10^5$ | C | $7$ |
| $8$ | $2\times10^5$ | 无 | $14$ |

特殊性质 A：所有的 $a_i$ 都相等。

特殊性质 B：对于任意的 $i<n$ 满足 $a_{i+1}=a_i+k$。

特殊性质 C：对于任意的 $i\neq j$ 满足 $a_i\neq a_j$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛
Difficulty: 普及/提高−
# 「Diligent-OI R1 D」DlgtTemplate

## 题目背景

棋盘是用板子做成的。这题是棋盘的题，所以……

## 题目描述

有一个 $1$ 行 $n$ 个格子的棋盘编号 $1\sim n$，上面每个格子写着一个得分 $a_i$。

现在你需要**从左到右**依次地选择一些格子，可以不选。有些格子选了之后，会将当前选的最靠前的 $b_i$ 个格子清除为未选格子，但你**不能**回去把这些格子重新选上。特殊地，如果该格子之前的已选格子不到 $b_i$ 个，那么该格子以及该格子以后的格子**不会**被清除为未选格子。

请你找出一种从左到右选择的方案，使得已选格子的得分之和最大。

## 输入格式

第一行输入 $n$，表示棋盘有 $n$ 个格子。

接下来一行 $n$ 个整数，依次表示第 $1\sim n$ 个格子的得分 $a_1\sim a_n$。

接下来一行 $n$ 个非负整数，依次表示第 $1\sim n$ 个格子的清除个数 $b_1\sim b_n$。

## 输出格式

你需要给出具体方案。

第一行输出非负整数 $k$，表示你选了 $k$ 个格子。

第二行 $k$ 个从小到大排列的正整数，表示你从左到右依次选择的格子编号。如果不选格子输出一个空行。

第三行输出 $ans$，表示你的最终答案。

Ns6 是很善良的。如果你不会求方案但答案正确，你也能得到测试点 $40\%$ 的分数。但这种情况下你也需要输出 $k$ 和 $k$ 个从小到大排列的正整数。

## 样例 #1

### 样例输入 #1

```
6
1 1 4 5 1 4
1 0 0 2 1 1
```

### 样例输出 #1

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

## 样例 #2

### 样例输入 #2

```
13
-1 1 4 -5 -1 -4 1 9 -1 9 -8 -1 0
1 0 2 1 3 0 0 2 0 0 2 0 1
```

### 样例输出 #2

```
5
1 2 7 8 10 
19
```

## 样例 #3

### 样例输入 #3

```
3
-1 -1 0
0 1 2
```

### 样例输出 #3

```
0

0
```

## 样例 #4

### 样例输入 #4

```
6
1 1 4 5 1 4
1 1 1 3 0 1
```

### 样例输出 #4

```
2
4 5
6
```

## 提示

#### 【样例 #1 解释】

先选择第一个数 $1$，这时虽然 $b_1=1$，但是因为前面没有数，所以不会清除。

再选择第二个数 $1$，这时因为 $b_2=0$，所以不会清除。

再选择第三个数 $4$，这时因为 $b_3=0$，所以不会清除。

再选择第四个数 $5$，这时因为 $b_4=2$，所以选择的第一个数和第二个数会被清除为未选的数。

此时答案 $4+5=9$。方法不唯一。

#### 【数据范围与约定】

对于 $100\%$ 的数据，满足 $1\le n\le3000$，$|a_i|\le10^8$，$0\le b_i\le n$。

| Subtask 编号 | $n\le$ | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: | :----------: |
| $0$ | $20$ | 无 | $25$ |
| $1$ | $500$ | 无 | $20$ |
| $2$ | $3000$ | $b_i>0$ | $5$ |
| $3$ | $3000$ | $b_i=0$ | $5$ |
| $4$ | $3000$ | $a_i=1$ | $15$ |
| $5$ | $3000$ | 无 | $30$ |

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 动态规划 DP, 背包 DP, 洛谷原创, 洛谷月赛, Special Judge
Difficulty: 普及+/提高
# 碧树

## 题目背景

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

小 T 不知道交流是什么。

是为了弄懂一串奇怪的符号，然后再把它放入他人的大脑吗？

是为了得到一些抽象的知识，然后再用它打破自己的习惯吗？

为了交流，小 T 最终决定接通了 $\text{220V}$ 的电压。

## 题目描述

> t1k1x1ww。

小 T 注视着这一串自己不能理解的符号，决定先和你交流一个 OI 题目。

小 T 有一棵有根树，它共有 $k$ 个叶子结点，同时他还告诉了你，其叶子结点的深度分别为 $a_1\dots a_k$。请你帮他计算，这棵树最少包含多少个结点。小 T 保证存在至少一棵这样的树。

如果您不熟悉题面中的若干定义，我们乐意提醒您：

- 图上的 **简单路径** 指一条经过顶点不重复、经过边不重复的路径。
- 一棵 **树** 是一张联通，且任意两点之间有且仅有一条简单路径的图。在一棵树里，我们会选择一个节点为根结点。
- 树上的 **叶子结点** 为不是根结点，且度数为 $1$ 的结点。
- 树上一个节点的 **深度** 是该结点到根结点的简单路径上结点的个数。

## 输入格式

第一行一个整数 $k$。

接下来一行 $k$ 个整数，描述 $a_1\dots a_k$。

## 输出格式

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

## 样例 #1

### 样例输入 #1

```
4
2 3 4 5
```

### 样例输出 #1

```
8
```

## 样例 #2

### 样例输入 #2

```
7
6 6 7 8 4 2 4
```

### 样例输出 #2

```
14
```

## 提示

### 样例解释

- 对于第一组数据，下面是一棵可能的树：

![](https://cdn.luogu.com.cn/upload/image_hosting/kh6cgtyp.png?x-oss-process=image/resize,m_lfit,h_400,w_400)

其大小为 $8$，其中叶子 $3, 5, 6, 8$ 的深度分别为 $2, 3, 4, 5$。容易证明没有大小 $\leq 7$ 的树符合题意。

### 数据规模与约定

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

- Subtask 0（0 pts）：样例。
- Subtask 1（30 pts）：$k = 2$。
- Subtask 2（30 pts）：$a_1 = a_2 = \dots = a_k$。
- Subtask 3（40 pts）：无特殊限制。依赖于子任务 $0 \sim 2$。

对于所有数据，保证 $1 \leq k \leq 10^5$，$2 \leq a_i \leq 10^5$，且保证存在至少一棵这样的树。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 数学, 树论, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及−
# 繁花

## 题目背景

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

我已经知道，在设置好循环播放时就已经知道，我是在麻痹自己，在逃避问题。

我承认如此，可捞起那些沉于水底的细节时，却一瞬间突然和所有所有真实的心跳共鸣。

那时总想的太少，现在常想得太多，不知所措似荒塘里的绿藻蔓延着。

然而这世间情感太多，小 R 也只能体会更开心和更难过。

## 题目描述

小 R 想对上面的问题进行探究，她想先做一些统计，于是她抽象了这个问题。

小 R 有 $n$ 个未知量 $a_1\dots a_n$，对每个 $1 \leq i < n$，她都比较了 $a_i$ 和 $a_{i+1}$ 并写下了一个字符 $c_i \in \{\texttt <, \texttt >, \texttt =\}$，表示两个未知量之间的比较结果。具体地：

- 若 $c_i = \texttt >$，则 $a_i > a_{i+1}$；
- 若 $c_i = \texttt <$，则 $a_i < a_{i+1}$；
- 否则（$c_i = \texttt =$），表示 $a_i = a_{i+1}$。

小 R 称 $\bm{a_i}$ **比** $\bm{a_j}$ **更开心**，当且仅当对任何 **满足上述 $\bm{n - 1}$ 条约束的** $[a_1, \dots, a_n] \in \mathbb R^n$，都有 $a_i < a_j$。请你帮她数出 $1 \leq i, j \leq n$ 且 $a_i$ 比 $a_j$ 更开心的整数数对 $(i, j)$ 个数。

因为要循环播放，所以有多组数据。

## 输入格式

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

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

- 第一行一个整数 $n$。
- 接下来一行，一个长度为 $n - 1$ 的字符串 $c_1c_2\dots c_{n-1}$。

## 输出格式

对于每组数据，输出仅一行一个整数，表示符合条件的整数数对个数。

## 样例 #1

### 样例输入 #1

```
5
5
<<<<
7
<=><=<
9
=<<><==<
11
>=<<=>>>=>
13
=><<=<=>=><>
```

### 样例输出 #1

```
10
9
13
29
25
```

## 提示

### 样例解释

- 对于第一组数据，$a_i$ 比 $a_j$ 开心当且仅当 $1 \leq i < j \leq n$，故共有 $\frac{5\times 4}{2} = 10$ 对合法的 $(i, j)$。
- 对于第二组数据，合法的 $(i, j)$ 分别为：$(1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (4, 6), (4, 7), (5, 7), (6, 7)$，共 $9$ 对。
- 对于其他几组数据，聪明的读者可以自行验证。

### 数据规模与约定

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

- Subtask 0（0 pts）：样例。
- Subtask 1（10 pts）：$n \leq 8$，$T \leq 8$。
- Subtask 2（20 pts）：$n \leq 5000$，$T \leq 8$。依赖于子任务 $0, 1$。
- Subtask 3（20 pts）：$c_i \neq \texttt =$。
- Subtask 4（50 pts）：无特殊限制。依赖于子任务 $0 \sim 3$。

对于所有数据，保证 $2 \leq n \leq 2\times 10^5$，$1 \leq T \leq 10^4$，$c_i \in \{\texttt <, \texttt >, \texttt =\}$，$\sum n \leq 5\times 10^5$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 递推, 双指针 two-pointer, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及/提高−
# 吻秋

## 题目背景

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

秋雨刚刚亲吻过大地，白云便卷起赤橙黄绿青蓝紫。

波长在可见光范围内自由落体，让蒸腾的水汽都带上了递进的旋律。

渐变色模糊的印象总被晴天匆匆带过，但往往反常的极差让我们更加记忆犹新。

所以有序，真的最优吗？

## 题目描述

小 C 有 $m$ 个整数序列 $a_1\dots a_m$，每个序列的长度都为 $n$。

小 C 想要把自己的序列按照整数大小排序。于是小 C 有 $q$ 次操作，每次操作：

- 要么，小 C 给出 $x, y\ (x \neq y)$，他想把 $a_x, a_y$ 拼接在一起形成长度为 $2n$ 的序列 $b$，将 $b$ 升序排序后取 $b_1\dots b_n$ 作为新的 $a_x$，$b_{n+1}\dots b_{2n}$ 作为新的 $a_y$；
- 要么，小 C 给出 $i, j$，细心的小 C 想要询问你，经过前面的若干次操作后，$a_{i,j}$ 的值，你需要准确回答他的问题。

## 输入格式

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

接下来 $m$ 行，每行 $n$ 个整数，第 $i$ 行 $j$ 个整数表示 $a_{i,j}$。

接下来 $q$ 行，每行三个整数，描述一次操作或询问。其格式为下述两种之一：

- $\verb!1 x y!$ 表示对 $a_x, a_y$ 进行排序，其中 $1 \leq x \neq y \leq m$；
- $\verb!2 i j!$ 表示查询 $a_{i,j}$，其中 $1 \leq i \leq m$，$1 \leq j \leq n$。

## 输出格式

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

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

```
6
7
2
```

## 样例 #2

### 样例输入 #2

```
6 5 20
5 14 13 1 15 17
7 7 19 3 8 6
16 13 13 6 14 2
12 5 4 17 12 3
19 19 4 6 3 3
2 5 3
1 4 3
2 1 1
1 2 5
2 4 6
2 2 2
1 4 2
1 2 4
2 1 1
2 3 3
2 3 3
1 4 2
1 4 1
2 3 5
1 3 4
1 4 1
1 1 4
1 5 1
2 2 4
2 4 2
```

### 样例输出 #2

```
4
5
12
3
5
13
13
16
6
14
```

## 提示

### 数据规模与约定

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

因为最后两个 Subtask 的极限输入数据大小分别达到 18MB、50MB 以上，C++ 选手可以选择使用下面的 **快速输入输出模板**：

```cpp
namespace FastIO {
	char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
	template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
	template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
}; using namespace FastIO;
#undef getchar()
```

**不保证除了 C++ 以外的语言一定能够通过，但保证对于 C++ 语言有充足的时限。**

---

- Subtask 0（0 pts）：样例。
- Subtask 1（9 pts）：$n \leq 10^4$，$q \leq 3000$。依赖于子任务 $0$。
- Subtask 2（23 pts）：$q \leq 3000$。依赖于子任务 $0, 1$。
- Subtask 3（20 pts）：$m \leq 5$，$q \leq 4\times 10^5$。依赖于子任务 $0$。
- Subtask 4（28 pts）：$q \leq 4\times 10^5$。依赖于子任务 $0 \sim 3$。
- Subtask 5（20 pts）：无特殊限制。依赖于子任务 $0 \sim 4$。

对于所有数据，满足 $1 \leq n\cdot m \leq 2\times 10^6$，$1 \leq m \leq 20$，$1 \leq q \leq 5\times 10^6$，$1 \leq a_{i,j} \leq 10^7$；对于操作或询问，$1 \leq x \neq y \leq m$，$1 \leq i \leq m$，$1 \leq j \leq n$。

## 时空限制



时间限制
900ms

内存限制
512.00MB

Tags: 模拟, 暴力数据结构, 枚举, 排序, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及+/提高
# 残雪

## 题目背景

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

如果我再和你走在同一条路上的话，我也会把远方的星星讲过无限的话再跟你说一遍吧。

你微笑着把竖起的手指放在嘴角，似乎是在暗示我，原来你就是远方的 Polestar 罢了。

令人伤感的事情是，这个世界上没有了小王子，也没有了去年今日的那位飞行员。

试问闲愁都几许？一川烟草，满城风絮，梅子黄时雨。

![](https://pic.imgdb.cn/item/670fd597d29ded1a8c604148.png)

## 题目描述

给出集合 $S$。我们定义一个 $\tt 01$ 串 $t$ 是不好的，当且仅当存在 $k \in S$，使得 $t$ 包含一个长度为 $2k$ 的子串 $t'$，且 $t'$ 恰好包含 $k$ 个 $\tt 0$ 和 $k$ 个 $\tt 1$。对立地，一个 $\tt 01$ 串如果不是不好的，那么它就是好的。

小 Y 有 $q$ 组询问，每次给出 $L, R, m, n$，表示 $S = \{x \in \N_+ \mid L \leq x \leq R\}$，判断是否存在一个好的字符串 $t$ 满足 $t$ 恰好包含 $m$ 个 $\tt 0$ 和 $n$ 个 $\tt 1$。

## 输入格式

第一行，一个整数 $q$，表示询问个数。对于每组询问：

- 仅一行，四个整数 $L, R, m, n$。

## 输出格式

输出共 $q$ 行。对于每组询问，一行一个字符串 `Yes` 或 `No` 表示你的答案：你应当输出 `Yes`，当且仅当你对小 Y 的问题的回答是肯定的。

本题中字符串大小写不敏感，即 `yEs`、`yes`、`Yes`、`YES` 等都被认为是 `Yes`；`No` 同理。

## 样例 #1

### 样例输入 #1

```
5
1 2 3 5
3 3 4 6
5 6 11 13
10 15 33 22
10 13 11 11
```

### 样例输出 #1

```
No
Yes
No
Yes
No
```

## 提示

### 样例解释

- 对于第一组数据，因为包含 $\tt 0, 1$ 但 $L = 1$，所以一定不合法。
- 对于第二组数据，存在 $t = \tt 0011111100$。容易证明这是合法的。
- 对于第三组数据，事实确实如此。
- 对于其它数据，暂时不能给你一个明确的答复。

### 数据规模与约定

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

- Subtask 0（0 pts）：样例。
- Subtask 1（13 pts）：$q \leq 10^3$，$n + m \leq 14$，$R \leq 14$。
- Subtask 2（20 pts）：$\sum \max(n, m, L, R) \leq 5\times 10^3 + 5$。依赖于子任务 $0$。
- Subtask 3（13 pts）：$\sum \max(n, m, L, R) \leq 10^7 + 100$。依赖于子任务 $0 \sim 2$。
- Subtask 4（13 pts）：$L = R$。
- Subtask 5（41 pts）：无特殊限制。依赖于子任务 $0 \sim 4$。

对于所有数据，保证 $1 \leq q \leq 10^5$，$1 \leq L \leq R \leq 10^{18}$，$0 \leq n, m \leq 10^{18}$，$n + m \geq 1$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 贪心, 构造, 洛谷原创, 洛谷月赛, Special Judge, O2优化
Difficulty: 省选/NOI−
# 「KDOI-10」商店砍价

## 题目背景

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

您可以点击 [这里](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/3jbtilzv) 下载本场比赛的选手文件。

You can click [here](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/5fzhd8sk) to download all tasks and examples of the contest.

密码 / Password：`rAnHoUyaSuoBaoMimaNijuEdefAngsHa2)2$1)0(2@0!`

**本场比赛所有题目从标准输入读入数据，输出到标准输出。**

## 题目描述

有一个正整数 $n$，保证其只由数字 $1\sim 9$ 构成。

你可以做任意多次如下操作：

- 选择 $n$ 的一个数位 $x$，花费 $v_x$ 的代价删除它，注意，此时 $n$ 的数位个数会减少 $1$，$n$ 的值也会发生相应的变化；
- 或者，花费 $n$ 的代价把剩余的所有数位删除。

求把整个数删除的最小代价。

## 输入格式

从标准输入读入数据。

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

输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含一个正整数 $t$，表示测试数据组数。

对于每组测试数据：

- 第一行一个正整数 $n$，表示这个数的初始值。
- 第二行九个正整数 $v_1,v_2,\dots,v_9$，表示删除每个数位的代价。

## 输出格式

输出到标准输出。

对于每组测试数据：

- 输出一行一个正整数，表示最小代价。

## 样例 #1

### 样例输入 #1

```
0
3
123
10 10 10 10 10 10 10 10 10 
1121
2 1 2 2 2 2 2 2 2
987654321
1 2 3 4 5 6 7 8 9
```

### 样例输出 #1

```
21
6
45
```

## 提示

**【样例 1 解释】**

对于第一组测试数据，最优操作方案如下：

- 删除数位 $2$，代价为 $10$，此时 $n$ 变为 $13$；
- 删除数位 $3$，代价为 $10$，此时 $n$ 变为 $1$；
- 删除 $n$ 的剩余所有数位，代价为 $1$。

总代价为 $10+10+1=21$，可以证明，这是代价的最小值。

对于第二组测试数据，一种最优操作方案如下：

- 删除第一个数位 $1$，代价为 $2$，此时 $n$ 变为 $121$；
- 删除最后一个数位 $1$，代价为 $2$，此时 $n$ 变为 $12$；
- 删除数位 $2$，代价为 $1$，此时 $n$ 变为 $1$；
- 删除 $n$ 的剩余所有数位，代价为 $1$。

总代价为 $2+2+1+1=6$。

**【样例 2】**

见选手目录下的 `bargain/bargain2.in` 与 `bargain/bargain2.ans`。

这个样例满足测试点 $3\sim 6$ 的约束条件。

**【样例 3】**

见选手目录下的 `bargain/bargain3.in` 与 `bargain/bargain3.ans`。

这个样例满足测试点 $11$ 的约束条件。

**【样例 4】**

见选手目录下的 `bargain/bargain4.in` 与 `bargain/bargain4.ans`。

这个样例满足测试点 $17,18$ 的约束条件。

**【样例 5】**

见选手目录下的 `bargain/bargain5.in` 与 `bargain/bargain5.ans`。

这个样例满足测试点 $23\sim 25$ 的约束条件。

***

**【数据范围】**

对于全部的测试数据，保证：

- $1\le t\le 10$；
- $1\le n< 10^{10^5}$；
- 对于任意 $1\le i\le 9$，$1\le v_i\le 10^5$；
- $n$ 由数字 $1\sim 9$ 构成。

|   测试点    |   $n<$    | $v_i\le$ |        特殊性质        |
| :---------: | :---------: | :------: | :--------------------: |
|     $1$     |    $100$     |  $10^5$  |           无           |
|     $2$     |    $10^3$    |  $10^5$  |           无           |
|  $3\sim 6$  |  $10^{18}$  |  $10^5$  |           无           |
| $7\sim 9$  |  $10^{40}$  |  $10^5$  |           无           |
|    $10$    | $10^{10^5}$ |  $10^5$  | $n$ 由至多一种数字构成 |
|    $11$     | $10^{10^5}$ |  $10^5$  | $n$ 由至多两种数字构成 |
| $12,13$ | $10^{10^5}$ |  $10^5$  | $n$ 由至多三种数字构成 |
| $14\sim 16$ | $10^{10^3}$ | $10^5$ | $v_1=v_2=v_3=\dots =v_9$ |
| $17,18$ | $10^{10^5}$ | $10^5$ | $v_1=v_2=v_3=\dots =v_9$ |
| $19,20$ | $10^{100}$ | $100$ | 无 |
| $21,22$ | $10^{10^3}$ | $10^3$ | 无 |
| $23\sim 25$ | $10^{10^5}$ | $10^5$ | 无 |

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 动态规划 DP, 洛谷原创, 洛谷月赛, O2优化, 2024
Difficulty: 普及+/提高
# 「KDOI-10」水杯降温

## 题目背景

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

**本场比赛所有题目从标准输入读入数据，输出到标准输出。**

## 题目描述

小 S 有一棵包含 $n$ 个节点的有根树，且根为节点 $1$。节点 $i$ $(1\le i\le n)$ 上放置了一个初始水温为 $a_i$ 的水杯。

在不知道水温的情况下拿起水杯喝水并被烫了 inf 次的小 S 决定将这些水杯的水温全部变为 $0$ 后再喝它们。

现在，小 S 可以分别进行以下两种操作任意次：

* 使用一个在节点 $i$ 的加热装置。这会使以 $i$ 为根的子树内所有水杯里的水温均增加 $1$；
* 或者，从某个**叶子**节点 $i$ 向根方向吹一阵风。这会使 $i$ 到根所有水杯里的水温均减少 $1$。

请你帮小 S 判断：能否将所有节点上的水杯的水温都变为 $0$。

## 输入格式

从标准输入读入数据。

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

输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含一个正整数 $t$，表示测试数据组数。

对于每组测试数据：

- 第一行包含一个正整数 $n$，表示节点数量。
- 第二行 $n-1$ 个正整数 $f_2,\dots,f_n$，$f_i$ 表示 $i$ 节点的父亲节点编号。保证 $f_i<i$。
- 第三行 $n$ 个整数 $a_i$，表示初始水温。

## 输出格式

输出到标准输出。

对于每组测试数据：

- 如果可以将水温变为 $0$，输出一行一个字符串 `Huoyu`；
- 如果无法将水温变为 $0$，输出一行一个字符串 `Shuiniao`。

## 样例 #1

### 样例输入 #1

```
0
5
5
1 1 2 3
6 5 2 2 1
5
1 1 2 2
6 5 1 2 1
5
1 1 2 2
4 -1 5 -2 -2
5
1 1 2 2
6 -4 8 -3 -3
5
1 1 2 2
-1 -1 -1 -4 -1
```

### 样例输出 #1

```
Shuiniao
Huoyu
Shuiniao
Shuiniao
Huoyu
```

## 提示

**【样例 1 解释】**

记 $A_u$ 表示在节点 $u$ 使用加热装置的操作，$B_u$ 表示从节点 $u$ 吹一阵风的操作，$(S)^k$ 表示将操作序列 $S$ 重复 $k$ 次。

- 对于第一、三、四组测试数据，可以证明，小 S 无法将所有水杯的水温都变为 $0$；
- 对于第二组测试数据，一种可能的操作序列为：$B_3(A_4)^2(B_4)^4B_5$；
- 对于第五组测试数据，一种可能的操作序列为：$(A_4)^3A_1$。

**【样例 2】**

见选手目录下的 `water/water2.in` 与 `water/water2.ans`。

这个样例满足测试点 $3$ 的约束条件。

**【样例 3】**

见选手目录下的 `water/water3.in` 与 `water/water3.ans`。

这个样例满足测试点 $7,8$ 的约束条件。

**【样例 4】**

见选手目录下的 `water/water4.in` 与 `water/water4.ans`。

这个样例满足测试点 $12$ 的约束条件。

**【样例 5】**

见选手目录下的 `water/water5.in` 与 `water/water5.ans`。

这个样例满足测试点 $13,14$ 的约束条件。

**【样例 6】**

见选手目录下的 `water/water6.in` 与 `water/water6.ans`。

这个样例满足测试点 $15\sim 17$ 的约束条件。

**【样例 7】**

见选手目录下的 `water/water7.in` 与 `water/water7.ans`。

这个样例满足测试点 $18\sim 21$ 的约束条件。


***

**【数据范围】**

记 $\sum n$ 为单个测试点内所有测试数据中 $n$ 的和。

对于全部的测试数据，保证：

- $1\leq t\leq 1\,000$；
- $2\leq n\leq 10^5$，$\sum n\le 10^6$；
- 对于任意 $2\le i\le n$，$1\le f_i<i$；
- 对于任意 $1\le i\le n$，$-10^{12}\leq a_i\leq10^{12}$。

| 测试点 | $n\leq$ | $\sum n\le $ | $\lvert a_i\rvert\leq$ | 特殊性质 |
| :----: | :-----: | :----------: | :--------------------: | :------: |
| $1$ | $5$ | $50$ | $5$ | 无 |
| $2$ | $5$ | $200$ | $5$ | 无 |
| $3$ | $5$ | $5\,000$ | $5$ | 无 |
| $4,5$ | $50$ | $500$ | $50$ | 无 |
| $6$ | $50$ | $500$ | $10^{8}$ | 无 |
| $7,8$ | $200$ | $2\,000$ | $200$ | 无 |
| $9$ | $200$ | $2\,000$ | $10^{8}$ | 无 |
| $10,11$ | $1\,000$ | $10^4$ | $1\,000$ | 无|
| $12$ | $1\,000$ | $10^4$ | $10^{8}$ | 无 |
| $13,14$ | $10^5$ | $3\times 10^5$ | $10^{12}$ | A |
| $15\sim 17$ | $10^5$ | $3\times 10^5$ | $10^{12}$ | B |
| $18\sim 21$ | $10^5$ | $3\times 10^5$ | $10^{12}$ | C |
| $22,23$ | $3\times 10^4$ | $10^5$ | $10^{8}$ | 无 |
| $24,25$ | $10^5$ | $10^6$ | $10^{12}$ | 无 |

- 特殊性质 A：对于任意 $2\le i\le n$，$f_i=i-1$；
- 特殊性质 B：对于任意 $1\le i\le n$，$a_i\le \left(\sum_{f_j=i}a_j\right)+5$，其中设 $f_1=0$；
- 特殊性质 C：树的深度不超过 $2$，其中深度指所有节点到根的边数中的最大值。

***

**【提示】**

本题输入输出量较大，请使用适当的 I/O 方式。

## 时空限制



时间限制
2.00s

内存限制
512.00MB

Tags: 动态规划 DP, 贪心, 二分, 洛谷原创, 洛谷月赛, O2优化, 2024
Difficulty: 省选/NOI−
# 「KDOI-10」超级演出

## 题目背景

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

**本场比赛所有题目从标准输入读入数据，输出到标准输出。**

## 题目描述

巡准备了一场超级演出。舞台和候场室可以看作一个包含 $n$ 个点 $m$ 条边的有向图，并且这个图当中没有环，也就是说，这是一张有向无环图（DAG）。

舞台为 $1$ 号节点，**保证所有节点均有到达节点 $\bm 1$ 的路径**。其余的节点均为候场室，每个候场室恰有一个剧团进行等待。

巡可以对一个候场室 $u$ 发布出场命令：

- 如果这个候场室的剧团还没有出场，并且存在一条 $u\to 1$ 的路径上没有其余候场的剧团。那么这个剧团就会沿着这条路径到达舞台进行演出，随后退场。注意：**一个剧团退场后不会重新回到候场室。**
- 否则，这个命令被认为是无效的。

巡有一个命令序列 $a_1,a_2,\dots,a_k$ 和 $q$ 次询问，每次给出一个区间 $[l,r]$。巡想要知道如果依次对候场室 $a_l,a_{l+1},\dots,a_r$ 发布出场命令后，候场室还会剩下多少剧团等待演出。

注意：每次询问相互独立，也就是说，每次询问之前，每个候场室都恰有一个剧团进行等待。

## 输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含四个正整数 $n,m,k,q$，表示图的点数，边数，序列长度，和询问次数。

接下来 $m$ 行，每行两个正整数 $u,v$，表示一条从 $u$ 到 $v$ 的有向边。保证无自环，无重边。

接下来的一行，$k$ 个正整数 $a_1,a_2,\dots,a_k$。

接下来 $q$ 行，每行两个正整数 $l,r$，表示一次询问的区间。

## 输出格式

输出到标准输出。

$q$ 行，每行一个非负整数，表示一次询问的答案。

## 样例 #1

### 样例输入 #1

```
0
5 5 5 4
2 1
3 1
5 1
4 2
4 3
2 4 4 3 5
1 2
1 5
3 5
2 3
```

### 样例输出 #1

```
2
0
2
4
```

## 提示

**【样例 1 解释】**

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

如图：

- 当询问 $l=1,r=2$ 时：
	- 发布出场命令 $a_1=2$。$2$ 沿着 $2\to 1$ 出场。
   - 发布出场命令 $a_2=4$。$4$ 沿着 $4\to 2\to 1$ 出场。
   
   此时余下 $3,5$ 两个剧团，输出 $2$。
   
- 当询问 $l=2,r=3$ 时：
	- 发布出场命令 $a_2=4$。找不到 $4\to 1$ 的且路上没有别的剧团的路线，该指令被认为无效。
   - 发布出场命令 $a_3=4$。找不到 $4\to 1$ 的且路上没有别的剧团的路线，该指令被认为无效。
   
   此时余下 $2,3,4,5$ 四个剧团，输出 $4$。
  
**【样例 2】**

见选手目录下的 `show/show2.in` 与 `show/show2.ans`。

这个样例满足测试点 $1,2$ 的限制条件。

**【样例 3】**

见选手目录下的 `show/show3.in` 与 `show/show3.ans`。

这个样例满足测试点 $5\sim 8$ 的限制条件。

**【样例 4】**

见选手目录下的 `show/show4.in` 与 `show/show4.ans`。

这个样例满足测试点 $9\sim 11$ 的限制条件。

**【样例 5】**

见选手目录下的 `show/show5.in` 与 `show/show5.ans`。

这个样例满足测试点 $12,13$ 的限制条件。


**【样例 6】**

见选手目录下的 `show/show6.in` 与 `show/show6.ans`。

这个样例满足测试点 $18,19$ 的限制条件。

***

**【数据范围】**

对于全部的测试数据，保证：

- $1\leq n,k,q\leq2\times10^5$；
- $1\leq m\leq4\times10^5$；
- $1\leq v<u\leq n$，且不存在两组相同的 $(u,v)$；
- 对于任意 $1\le i\le k$，$2\leq a_i\leq n$；
- 对于每组询问，$1\leq l\leq r\leq k$；
- 输入构成一张有向无环图，且所有节点均存在到达节点 $1$ 的路径。

| 测试点 | $n,k,q\leq$ | $m\leq$ | 特殊性质 |
|:--:|:--:|:--:|:--:|
| $1,2$ | $300$ | $600$ | 无 |
| $3,4$ | $2\,000$ | $4\,000$ | A |
| $5\sim 8$ | $2\,000$ | $4\,000$ | 无 |
| $9\sim 11$ | $2\times10^5$ | $4\times10^5$ | A |
| $12,13$ | $2\times10^5$ | $4\times10^5$ | BC |
| $14,15$ | $2\times10^5$ | $4\times10^5$ | C |
| $16,17$ | $2\times10^5$ | $4\times10^5$ | BD |
| $18,19$ | $2\times10^5$ | $4\times10^5$ | D |
| $20\sim 22$ | $2\times10^5$ | $4\times10^5$ | B |
| $23\sim 25$ | $2\times10^5$ | $4\times10^5$ | 无 |

- 特殊性质 A：图退化为一棵内向树，也就是说，除节点 $1$ 外，每个点恰有一条出边，节点 $1$ 没有出边；
- 特殊性质 B：保证对于每组询问，$r=k$；
- 特殊性质 C：保证对于任意 $1\leq i< j\leq k$，$a_i\neq a_j$；
- 特殊性质 D：保证每个点的入度和出度均不超过 $30$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 线段树, 扫描线, 根号分治, 洛谷原创, 洛谷月赛, O2优化, 2024
Difficulty: 省选/NOI−
# 带余除法

## 题目背景

**注意：提交至洛谷时，请使用标准输入输出，而非文件输入输出。**

**NOTICE: When submitting your code on Luogu site, please use standard IO instead of file IO.**

[点我（或在本题底部）下载中文试题 PDF。](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/asjh3my3?contestId=200686)

[Click here (or at the bottom  of this page) to download the English version of statements (PDF).](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/lkux3617?contestId=200686)

**注意：本次比赛所有题目的大样例均为 Linux 换行符格式，在 Windows 系统内可能无法正常显示换行。**

## 题目描述

我们已经学过带余除法。对于两个正整数 $n,q$，如果 $n$ 除以 $q$ 的商为 $k$，余数为 $r$，我们可以写出带余除法算式 $n\div q = k \cdots\cdots r$，或被记为 $n\div q = k (\text{r. } r)$。本题中，为了简化，哪怕 $r=0$，我们也要写出这个余数。

现在有一个带余除法，然而你只知道被除数 $n​$ 和商 $k​$，而并不知道除数 $q​$ 和余数 $r​$。你想知道余数有多少种可能。

## 输入格式

**本题有多组测试数据**。输入的第一行有一个正整数 $T$，表示数据组数。

之后 $T$ 行，每行有一个正整数 $n$ 和自然数 $k$，分别表示带余除法的被除数和商。

## 输出格式

对于每组测试数据，输出一行一个自然数，表示余数的不同可能性数量。

## 样例 #1

### 样例输入 #1

```
2
10 2
1 0
```

### 样例输出 #1

```
2
1
```

## 样例 #2

### 样例输入 #2

```
参见 division/division2.in
```

### 样例输出 #2

```
参见 division/division2.ans
```

## 提示

【样例 1 解释】

对于第一组数据，被除数为 $10$，商为 $2$。

- 如果除数是 $1,2,3$，那么商分别是 $k=10,5,3$，不符合题意。
- 如果除数是 $4$，那么商为 $2$，余数为 $r=2$。
- 如果除数是 $5$，那么商为 $2$，余数为 $r=0$。
- 如果除数是 $6,7,8,9,10$，那么商都是 $1$，不符合题意。
- 如果除数 $>10$，那么商为 $0$，不符合题意。

对于第二组数据，被除数为 $1$，商为 $0$。

只要除数 $q>1$，那么 $1\div q = 0 \cdots\cdots 1$ 一定是正确的带余除法算式。余数只有 $1$ 这一种可能。

【数据范围】

对于前 $30\%$ 的数据，保证 $1\le n\le 1000$，$0\le k\le 1000$。

另有 $20\%$ 的数据，保证 $k\le 10^5$。

另有 $20\%$ 的数据，保证 $k\ge 10^9$。

对于全体数据，保证 $1\le T\le 10$，$1\le n\le 10^{14}$，$0\le k\le 10^{14}$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛
Difficulty: 普及−
# 奖牌排序

## 题目描述

有 $n$ 个小朋友参加了若干场比赛，其中第 $i$ 个小朋友获得了 $g_i$ 枚金牌、$s_i$ 枚银牌和 $b_i$ 枚铜牌。老师希望**每个小朋友**制作一张**所有小朋友**的排行榜。

然而小朋友们为了让自己的排名尽量靠前，自然是可以动一些小心思的，体现在排序标准上——每个小朋友可以选择按照金牌数从大到小排序，也可以选择按照银牌数从大到小排序，也可以选择按照铜牌数从大到小排序。在小朋友自制的排行榜里，如果自己和别的小朋友并列，那么他可以把自己写在最前面。

给出每个小朋友获得的金牌数、银牌数和铜牌数，请对于每个小朋友 $i$，计算他在他自己的排行榜里最好能排第几名。

## 输入格式

输入的第一行有一个正整数 $n$，表示小朋友的个数。

之后 $n$ 行，每行有三个自然数 $g_i,s_i,b_i$ 表示一个小朋友的金牌、银牌和铜牌数量。

## 输出格式

输出 $n$ 行，每行一个正整数，其中第 $i$ 行的正整数表示第 $i$ 个小朋友的最好排名。

## 样例 #1

### 样例输入 #1

```
4
8 5 0
4 5 3
4 1 2
2 1 1
```

### 样例输出 #1

```
1
1
2
3
```

## 样例 #2

### 样例输入 #2

```
参见 medal/medal2.in
```

### 样例输出 #2

```
参见 medal/medal2.ans
```

## 样例 #3

### 样例输入 #3

```
参见 medal/medal3.in
```

### 样例输出 #3

```
参见 medal/medal3.ans
```

## 提示

【样例 1 解释】

下面给出一种可能得情况，其中加粗的一列表示这个小朋友的排序依据。

第一个小朋友制作的排行榜如下：

|小朋友编号|金牌数|银牌数|铜牌数|
|:-:|:-:|:-:|:-:|
|$1$|$\bf{8}$|$5$|$0$|
|$2$|$\bf 4$|$5$|$3$|
|$3$|$\bf 4$|$1$|$2$|
|$4$|$\bf 2$|$1$|$1$|

第二个小朋友制作的排行榜如下：

|小朋友编号|金牌数|银牌数|铜牌数|
|:-:|:-:|:-:|:-:|
|$2$|$4$|$\bf 5$|$3$|
|$1$|$8$|$\bf 5$|$0$|
|$3$|$4$|$\bf 1$|$2$|
|$4$|$2$|$\bf 1$|$1$|

第三个小朋友的排行榜如下（按照金牌排序，也可以获得第二名）：

|小朋友编号|金牌数|银牌数|铜牌数|
|:-:|:-:|:-:|:-:|
|$2$|$4$|$5$|$\bf 3$|
|$3$|$4$|$1$|$\bf 2$|
|$4$|$2$|$1$|$\bf 1$|
|$1$|$8$|$5$|$\bf 0$|

第四个小朋友的排行榜如下：

|小朋友编号|金牌数|银牌数|铜牌数|
|:-:|:-:|:-:|:-:|
|$2$|$4$|$\bf 5$|$3$|
|$1$|$8$|$\bf 5$|$0$|
|$4$|$2$|$\bf 1$|$1$|
|$3$|$4$|$\bf 1$|$2$|

【样例 2 解释】

该样例符合测试点 $8$ 的性质。

【样例 3 解释】

该样例符合测试点 $10$ 的性质。

【数据范围】

对于全体数据，保证 $1\le n\le 2\times 10^5$，且 $0\le g_i,s_i,b_i\le 10^9$。

|测试点编号|$n\le$|特殊性质|
|:-:|:-:|:-:|
|$1\sim 2$|$3$||
|$3\sim 4$|$100$||
|$5\sim 7$|$1000$|A|
|$8\sim 9$|$1000$||
|$10\sim 12$|$2\times 10^5$|A|
|$13\sim 15$|$2\times 10^5$|B|
|$16\sim 20$|$2\times 10^5$||

- 特殊性质 A：$g_i$ 互不相同，$s_i$ 互不相同，$b_i$ 互不相同。
- 特殊性质 B：$1\le g_i,s_i,b_i\le 2\times 10^5$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛
Difficulty: 普及−