yl-9/probench huggingface dataset:
# 『FLA - I』冲云霄

## 题目背景

**[English statement.](/problem/U458236) You must submit your code at the Chinese version of the statement.**

住在呼和浩特的小 R 很久以前就学会了异或。异或使用符号 $\oplus$ 表示，在 C++ 中可用符号 `^` 表示。非负整数 $x$ 和 $y$ 的异或是指对它们二进制表示中的每一位进行如下运算得到的结果：

- 若 $x$ 和 $y$ 的第 $k$ 个二进制位相同，结果的第 $k$ 个二进制位为 $0$；
- 若 $x$ 和 $y$ 的第 $k$ 个二进制位不同，结果的第 $k$ 个二进制位为 $1$。

使用 $(X)_{10}$ 表示十进制数 $X$，$(Y)_2$ 表示二进制数 $Y$，因为 $(12)_{10}=(1100)_2$，$(10)_{10}=(1010)_2$，所以 $(12)_{10} \oplus (10)_{10}=(1100)_2 \oplus (1010)_2=(0110)_2=(6)_{10}$。

住在银川的小 F 想用这道题难倒小 R 但失败了，现在小 F 又想用这道题为难你，不能让他的阴谋得逞！

## 题目描述

给定**整数** $n$ 和 $m$，判断是否存在满足下列条件的数列 $a$。本题中数列元素的下标从 $1$ 开始。

- 数列 $a$ 的长度为 $m$，数列 $a$ 的每一项都为**正整数**。

- $a_1 \oplus a_2 \oplus \cdots \oplus a_m = n$，即数列 $a$ 的所有项异或得到的结果等于 $n$。

- 数列 $a$ 中所有元素的值都相同。

## 输入格式

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

第一行输入一个正整数 $T$，表示测试数据组数。

对于每组测试数据，输入一行两个整数 $n,m$。

## 输出格式

对于每组测试数据，输出一行一个字符串。如果存在满足条件的数列 $a$，输出 `Yes`；否则输出 `No`。

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

```
Yes
Yes
No
No
```

## 提示

**「样例解释 #1」**

对于第一组测试数据，数列 $a$ 可以是 $[3,3,3]$，此时 $a_1 \oplus a_2 \oplus a_3 = 3 \oplus 3 \oplus 3 = 3$。

对于第二组测试数据，数列 $a$ 可以是 $[2,2,2,2,2]$，此时 $a_1 \oplus a_2 \oplus a_3 \oplus a_4 \oplus a_5 = 2 \oplus 2 \oplus 2 \oplus 2 \oplus 2 = 2$。

对于第三组和第四组测试数据，可以证明不存在满足条件的数列。

**「数据范围」**

|测试点编号|$T \leq$|$n \leq$|$m \leq$|
|:-:|:-:|:-:|:-:|
|$1 \sim 2$|$5$|$0$|$10^9$|
|$3 \sim 4$|$5$|$10^9$|$3$|
|$5$|$10^5$|$10^9$|$10^9$|

对于所有测试数据，$1 \leq T \leq 10^5$，$0 \leq n \leq 10^9$，$2 \leq m \leq 10^9$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 数学, 位运算, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及−
# 『FLA - I』歌静河

## 题目背景

**[English statement.](/problem/U458237) You must submit your code at the Chinese version of the statement.**

> You can cry
>
> Drinking your eyes
>
> Do you miss the sadness when it's gone
>
> And you let the river run wild
>
> And you let the river run wild

— _The River_ by _AURORA_

## 题目描述

秋有两个长度为 $n$ 且仅包含 `#` 和小写字母的字符串 $a,b$。

这两个字符串总共包含 $m$ 个 `#`，秋打算执行 $m$ 次操作，用小写字母把两个字符串中所有的 `#` 都替换掉。对于第 $i$ 次操作，他要在 $a,b$ 中选择一个字符串，将这个字符串中从左向右数第一个 `#` 替换为第 $(i-1) \bmod 26 +1$ 个小写字母。**他不能选择不包含 `#` 的字符串。**

秋有一位热爱艺术的好友，他想最小化执行完 $m$ 次操作后的字符串 $a$ 的字典序。秋想，编程也是一种艺术，这样的话，他们的心也会更近一些。

## 输入格式

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

第二行输入一个长度为 $n$ 的字符串 $a$。

第三行输入一个长度为 $n$ 的字符串 $b$。

## 输出格式

输出一行一个字符串，表示执行 $m$ 次操作后能够得到的字典序最小的 $a$。

## 样例 #1

### 样例输入 #1

```
8 2
th#nkyou
#estwish
```

### 样例输出 #1

```
thankyou
```

## 样例 #2

### 样例输入 #2

```
16 5
##soluteradian#e
your#awnwillcom#
```

### 样例输出 #2

```
absoluteradiance
```

## 样例 #3

### 样例输入 #3

```
40 45
hhuj#pzr#k#mmd#z##y#o####m##j##tga#k#t#g
m########be#######vf##a#j###ypuf###pr###
```

### 样例输出 #3

```
hhujapzrakbmmdczdeyfoghijmkljmntgaokptqg
```

## 提示

**「样例解释 #1」**

第一次操作选择字符串 $a$，将 $a$ 中的 `#` 替换为第 $(1-1) \bmod 26+1=1$ 个小写字母，即 `a`；第二次操作选择字符串 $b$，将 $b$ 中的 `#` 替换为第 $(2-1) \bmod 26+1=2$ 个小写字母，即 `b`。最终的字符串 $a$ 即为 `thankyou`，可以证明这是执行 $m$ 次操作后能得到的字典序最小的 $a$。

**「数据范围」**

|测试点编号|$n \leq$|特殊性质|
|:-:|:-:|:-:|
|$1 \sim 3$|$10$|无|
|$4 \sim 6$|$10^5$|有|
|$7 \sim 10$|$10^5$|无|

- 特殊性质：保证 $a,b$ 中存在一个不包含 `#` 的字符串。

对于所有测试数据，$1 \leq n \leq 10^5$，$1 \leq m \leq 2n$，字符串 $a,b$ 仅包含字符 `#` 和小写字母。

2024 年 8 月 4 日：添加了 1 组 hack 数据置于 Subtask #1。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 模拟, 字符串, 贪心, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及−
# 『FLA - I』云音泛

## 题目背景

**[English statement.](/problem/U458238) You must submit your code at the Chinese version of the statement.**

“……这些年来，过得可好？”

“……无所谓好或不好，人生一场空虚大梦，韶华白首，不过转瞬。惟有天道恒在，往复循环，不曾更改...”

## 题目描述

在梦中，秋种下了 $n$ 朵凋零玫瑰。他记得，第 $i$ 朵玫瑰是在时刻 $t_i$ 种植的。

凋零玫瑰在被种下的那个时刻就立即开放，但每一株玫瑰只会开放 $m$ 个时刻（在时刻 $T$ 种植的玫瑰会且仅会在从时刻 $T$ 到时刻 $T+m-1$ 的 $m$ 个时刻开放），在 $m$ 个时刻后便化作再也无法挽留的灰尘，飘散在凛冽的寒风中。

他问你，假如他可以改变不超过一朵玫瑰的种植时间（选定一个 $t_i$ 并将其修改为任意正整数），那么最多有多少个时刻有且仅有一株凋零玫瑰开放？

## 输入格式

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

第二行输入 $n$ 个正整数，第 $i$ 个正整数为 $t_i$。

## 输出格式

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

## 样例 #1

### 样例输入 #1

```
5 4
11 9 1 3 12
```

### 样例输出 #1

```
14
```

## 样例 #2

### 样例输入 #2

```
13 7
6 42 58 41 20 60 2 61 45 28 45 28 12
```

### 样例输出 #2

```
38
```

## 提示

**「样例解释 #1」**

如图，使用金色标记有且仅有一株凋零玫瑰开放的时刻，使用黑色和红色标记每朵凋零玫瑰开放的时刻。

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

将使用红色标记的玫瑰的种植时刻改为 $17$（将 $t_1$ 的值修改为 $17$，如下图）后有 $14$ 个时刻有且仅有一株凋零玫瑰开放。可以证明不存在能够使有且仅有一株凋零玫瑰开放的时刻数量大于 $14$ 的修改方案。

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

**「数据范围」**

|测试点编号|$n \leq$|$m \leq$|$t_i \leq$|
|:-:|:-:|:-:|:-:|
|$1 \sim 6$|$5000$|$5000$|$5000$|
|$7 \sim 12$|$2 \times 10^5$|$2 \times 10^5$|$2 \times 10^5$|
|$13 \sim 14$|$2 \times 10^5$|$1$|$10^9$|
|$15 \sim 20$|$2 \times10^5$|$10^9$|$10^9$|

对于所有测试数据，$1 \leq n \leq 2 \times 10^5$，$1 \leq m,t_i \leq 10^9$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 模拟, 离散化, 排序, 前缀和, 队列, 差分, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及+/提高
# 『FLA - I』庭中有奇树

## 题目背景

**[English statement.](/problem/U458239) You must submit your code at the Chinese version of the statement.**

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

某天晚上小 G 和小 Y 本打算激情 CF 但过掉两题就下班了，然后他们准备玩一个游戏。

## 题目描述

给定一棵有 $n$ 个节点的无根树，边带权，树上有一个起始节点 $S$ 和一个终止节点 $T$。

有一枚可以沿着边在节点之间移动的棋子，它每次移动花费的硬币数量等于经过的边的权值。

如果当前棋子所在节点为 $u$ 且节点 $v$ 与节点 $u$ 之间连有一条权值为 $w$ 的边，小 G 就能花费 $w$ 个硬币把棋子移动到节点 $v$。游戏开始时棋子位于节点 $S$，我们的小 G 要控制棋子移动到节点 $T$。

由于曾经有人告诉小 G 玩某游戏不开挂等于没玩，小 G 决定开挂。他的外挂可以花费 $k$ 个硬币把棋子从当前节点传送到任意一个**没有和当前节点连边**的节点，小 G 只能用这个外挂至多一次。

正义的小 Y 不能坐视不管，在小 G 开始行动之前，小 Y 可以封锁至多 $m$ 条可能的传送路线。假设小 Y 封锁了从节点 $x$ 向节点 $y$ 的传送路线，小 G 把棋子从节点 $x$ 传送到节点 $y$ 花费的硬币数量就会变成 $10^9$。由于外挂功能强大，小 G 知道小 Y 都封锁了哪些路线。**请注意传送路线是单向的，封锁节点 $x$ 向节点 $y$ 的传送路线不影响小 G 从节点 $y$ 向节点 $x$ 传送。**

有趣的是，游戏中小 G 不仅负责控制棋子移动到节点 $T$，还想**最小化**花费的硬币数量；而小 Y 想要**最大化**小  G 花费的硬币数量。

如果两人都采取最优策略，小 G 总共会花掉多少硬币？

## 输入格式

第一行输入五个整数 $n,m,k,S,T$。

接下来 $n-1$ 行，第 $i$ 行输入三个正整数 $u_i,v_i,w_i$ 表示节点 $u_i$ 和节点 $v_i$ 之间有一条边权为 $w_i$ 的边。

## 输出格式

输出一行一个整数，表示在两人都采取最优策略的情况下小 G 花费的硬币数量。

## 样例 #1

### 样例输入 #1

```
4 2 2 1 2
2 3 6
4 1 6
3 1 8
```

### 样例输出 #1

```
14
```

## 样例 #2

### 样例输入 #2

```
9 7 4 1 6
3 8 7
6 8 6
6 7 4
2 5 3
3 2 2
3 9 12
2 1 2
8 4 11
```

### 样例输出 #2

```
12
```

## 提示

**「样例解释 #1」**

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

给出一种可能发生的情况：小 Y 封锁节点 $1$ 向节点 $2$ 的传送路线和节点 $4$ 向节点 $2$ 的传送路线。

小 G 控制棋子从初始节点到达节点 $4$，从节点 $4$ 传送到节点 $3$ 后再到达终止节点，总共花费 $14$ 个硬币。

**「数据范围」**

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

|Subtask|$n\leq$|$m \leq$|特殊性质|分值|
|:---:|:---:|:---:|:---:|:---:|
|**#1**|$1000$|$10^5$|无|$10$|
|**#2**|$10^5$|$0$|无|$10$|
|**#3**|$10^5$|$10^5$|无|$10$|
|**#4**|$10^5$|$10^9$|A|$15$|
|**#5**|$10^5$|$10^9$|B|$15$|
|**#6**|$10^5$|$10^9$|无|$40$|

- 特殊性质 A：保证 $k=10^9$。
- 特殊性质 B：保证 $k=0$。

对于所有测试数据，$2 \leq n \leq 10^5$，$0 \leq m,k \leq 10^9$，$1 \leq S,T,u_i,v_i \leq n$，$1 \leq w_i \leq 10^9$，$S \neq T$，$u_i \neq v_i$。节点的编号是从 $1$ 到 $n$ 的整数。

2024 年 8 月 4 日：将样例置于 Subtask #0。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 图论, 贪心, 二分, 树论, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及+/提高
# 「CROI · R2」在相思树下 I

## 题目背景

>年年桃树下
>
>常看一个变成俩
>
>小小心愿常比划
>
>快快实现吧
>
>却没看到他也在树下
>
>相逢二字纵使隔天涯
>
>转角总会遇上他
>
>缘分缘分啊

## 题目描述

**本题采用多组数据测试。**

现在欣欣有一个从 $1$ 到 $n$ 的序列，并想对这个序列进行如下两种操作。

操作一：删去所有的奇数项。

操作二：删去所有的偶数项。

欣欣发现她在进行 $k$ 次操作后，最后只剩下一个数，但她不知道这个数是多少，于是欣欣来找你求助，她会给你她所进行的 $k$ 次操作的种类，希望你告诉她最后的那个数是多少。

## 输入格式

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

对于每组数据：

第一行两个整数 $n$ 和 $k$，含义如题面所示。

第二行 $k$ 个整数，代表欣欣依次进行的操作种类，其中 $1$ 代表操作一，$2$ 代表操作二。

## 输出格式

共 $T$ 行，每行一个数代表每组数据对应的答案。

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

```
4
1
8
6
```

## 提示

**【样例解释】**

对于第一组数据，序列的变化如下：

$\{1,2,3,4,5\} \to \{2,4\} \to \{4\}$。

**【数据范围】**

对于 $30\%$ 的数据， $n\le 5\times10^5$。

对于 $100\%$ 的数据，$1\le T \le 10$，$1\le n\le 10^{18}$。

保证对于所有的数据，操作 $k$ 次后均仅剩下一个数。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及−
# 「CROI · R2」01-string

## 题目描述

给定两个长度为 $n$ 的 $01$ 串 $S,T$，你可以对串 $S$ 执行无限次操作，每次都可以从以下操作中任选一个执行：

- 选择两个正整数 $l,r(1\le l\le r\le n)$，将 $S_l\dots S_r \ 01$ 反转。

- 选择两个正整数 $l,r(1\le l\le r\le n)$，将 $S_l\dots S_r $ 全部改为 $0$。

- 选择两个正整数 $l,r(1\le l\le r\le n)$，将 $S_l\dots S_r $ 全部改为 $1$。

你需要回答最少使用几次操作才能把 $S$ 变成 $T$。

## 输入格式

**本题采用多组数据测试。**

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

对于每组数据：

第一行一个 $01$ 串，表示串 $S$。

第二行一个 $01$ 串，表示串 $T$。

## 输出格式

一共 $T$ 行，第 $i$ 行一个整数，表示第 $i$ 组数据的答案。

## 样例 #1

### 样例输入 #1

```
3
00000
11111
10101
01010
11100101
11110000
```

### 样例输出 #1

```
1
1
2
```

## 提示

**【样例解释】**

以下提供样例三组数据的合法方案之一：

对于第一组数据，选取 $l=1,r=5$，将 $S_l\dots S_r$ 全部变成 $1$。

对于第二组数据，选取 $l=1,r=5$，将 $S_l\dots S_r \ 01$ 反转。

对于第三组数据，先选取 $l=4,r=8$，将 $S_l\dots S_r$ $01$ 反转，再选取 $l=5,r=8$，将 $S_l\dots S_r$ 全部变成 $0$。

**【数据范围】**

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

- Sub 0（10 points）：$n\le 5$。
- Sub 1（10 points）：$n\le 18$。
- Sub 2（30 points）：$n\le 2000$。
- Sub 3（50 points）：无特殊限制。

对于所有的数据，$1\le T \le 10$，$1\le n\le 5\times 10^5$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 动态规划 DP, 洛谷月赛, O2优化
Difficulty: 提高+/省选−
# 「CROI · R2」在相思树下 II

## 题目背景

真的要继续吗？

真的不想放弃吗？

真的有用吗？

## 题目描述

狐妖们在涂山上举办了一场淘汰制比赛，现在已知第 $i$ 名参赛者实力为 $i$，每场比赛都会有两名选手决出胜负，胜者进入下一轮，为了尽量让实力较强和较弱的参赛选手均有获胜的可能，涂山雅雅设计了一种特殊的比赛规则。

具体而言，一共有 $2^n$ 位选手报名参加淘汰赛，每场比赛一定按照两种规则之一进行。

- 规则一：参加比赛的两名选手实力较强者胜出。
- 规则二：参加比赛的两名选手实力较弱者胜出。

现在涂山雅雅会对你进行 $m$ 次询问，对于一个每场比赛规则确定但选手分布未知的签表，每次询问第 $a$ 名选手能否闯入第 $b$ 轮比赛，若能则输出 `Yes`，否则输出 `No`。特殊地，若某位选手夺得了冠军，则我们称其闯入了第 $n+1$ 轮比赛。

下图展示了一张每场比赛规则确定，但选手分布未知的签表示例。其中，每场比赛下标注 $\max$ 表示该场比赛按照规则一进行，实力较强者胜出；标注 $\min$ 表示该场比赛按照规则二进行，实力较弱者胜出。

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

## 输入格式

第一行两个整数 $n,m$，含义如题面所示。

接下来 $n$ 行描述签表，其中第 $i$ 行有 $2^{i-1}$ 个整数，代表第 $n-i+1$ 轮中从左往右的每场比赛的比赛规则，其中 $1$ 代表该场比赛按照规则一进行，$2$ 代表该场比赛按照规则二进行。

接下来 $m$ 行每行两个整数 $a,b$，代表一次询问。

## 输出格式

共 $m$ 行，每行一个字符串 `Yes` 或 `No` 代表每次询问的答案。

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

```
Yes
Yes
No
```

## 提示

**【样例解释】**

样例中的签表与题目描述中的图示一致。

若要使第六位选手进入第二轮，或使第七位选手进入第三轮，均可按照如下顺序安排选手位置：$\{1,2,3,4,7,8,5,6\}$。具体比赛情况如下图所示。

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

显然不存在一种可能的情况使得第八位选手进入第四轮（即夺得冠军）。

**【数据范围】**

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

- Subtask 0（20 points）：$n \leq 3$，$m \leq 20$。
- Subtask 1（10 points）：对于所有询问，$b \leq 2$。
- Subtask 2（10 points）：保证每场比赛的规则均为规则一。
- Subtask 3（20 points）：保证第 $i$ 轮中的所有比赛比赛规则均相同。
- Subtask 4（40 points）：无特殊限制。

对于所有数据，$1\leq a\leq 2^n$，$1\leq b\leq n+1$，$1 \leq 2^n,m \leq 10^6$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 树形 DP, 洛谷原创, 洛谷月赛
Difficulty: 提高+/省选−
# 「CROI · R2」落月摇情

## 题目背景

>昨夜闲潭梦落花，\
可怜春半不还家。\
>江水流春去欲尽，\
江潭落月复西斜。
>
>斜月沉沉藏海雾，\
碣石潇湘无限路。\
>不知乘月几人归，\
落月摇情满江树。

## 题目描述

小烟是住在月亮上的仙女。为了和人间保持联系，小烟在江边种了一棵树。每当月光透过枝叶洒在江面上，形成特定的图案时，小烟就能与那个人产生心灵感应。为了让形成的图案更加美观，小烟用魔法让树的枝条互相交错成他喜欢的样子。你可以认为这棵树是一个**有 $n$ 个节点、$m$ 条边且无重边、无自环的无向连通图**。

某次小烟出差回到月亮上，发现这棵树上所有的枝条都被破坏了。为了快速恢复和人间的联系，小烟需要施加魔法将 $n$ 个节点重新连接起来。施加魔法生成一条边的代价与这条边对月光投影的影响程度有关。由于小烟忘记了原本树的形态，所以她希望花费最小的代价将这棵树恢复到任意一个可能的原先形态。也就是说，她需要这 $n$ 个节点之间形成一张有 $m$ 条边且无重边、无自环的无向连通图。

考虑到你不是仙女，很难计算每条边对投影的影响程度，善良的小烟给出了一个简单的计算方法：给你每个点的影响程度 $a_i$，则用魔法生成一条边 $(u,v)$ 的代价为 $a_u\times a_v$。请你帮小烟找到一组花费代价最小的施加魔法的方案。

**形式化地**，给出 $n$ 个点，每个点有点权 $a_i$，你需要构造一张有 $m$ 条边，且无重边、无自环的无向图，使得这 $n$ 个点连通。设边 $(u,v)$ 的权值为 $a_u\times a_v$，你需要最小化图中所有边的权值和。

## 输入格式

输入共两行。

第一行两个非负整数 $n,m$。

第二行 $n$ 个由空格隔开的整数 $a_i$。

## 输出格式

输出 $m+1$ 行。

第一行一个整数 $ans$，表示你构造的图中，所有边的权值和。

接下来的 $m$ 行每行两个正整数 $u,v$，表示你构造的图中存在一条边 $u,v$。你需要保证 $u\neq v$，且不存在两个无序二元组 $(u,v)$ 相同，且所有输出能表示一张 $n$ 个点的连通图。**如有多解，输出任意一组合法解即可**。

## 样例 #1

### 样例输入 #1

```
4 5
1 2 -2 -3
```

### 样例输出 #1

```
-13
1 2
1 3
1 4
2 3
2 4
```

## 样例 #2

### 样例输入 #2

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

### 样例输出 #2

```
-36
1 6
2 6
3 6
4 6
5 6
```

## 提示

**【Special Judge】**

本题采用 Special Judge。只要你输出的图满足无重边、无自环且连通，同时其边权和与你输出的答案一致且输出的答案与标准答案一致，你就可以通过对应的测试点。

需要注意的是，请确保你的输出符合输出格式中的要求，否则你得到的结果可能不确定。

本题开启子任务依赖。你可以得到一个子任务对应的分数，当且仅当你通过了当前子任务，同时你也通过了当前子任务依赖的所有子任务。具体的依赖情况见“数据范围”部分的表格。

**【数据范围】**

对于所有数据，满足 $1\leq n\leq 10^6$，$n-1\leq m\leq \min(10^6,\frac{n(n-1)}{2})$，$0\leq |a_i|\leq 10^6$。

本题开启捆绑测试、开启子任务依赖。

|  子任务编号  | $n \le$ | $m \le$ | 特殊性质 | 分值 |子任务依赖|
| :----------: | :-----: | :--------------: | :------------: | :-----: | :-----: |
|$1$ |$7$ | $21$ | 无 |$10$| 无 |
| $2$ | $16$ |  $120$ | 无 |$15$| $1$ |
|  $3$  | $1000$ | $3\times 10^5$| 无 |$15$|$1,2$|
| $4$ | $2\times 10^5$ | $3\times 10^5$ | 保证 $a_i$ 为非负整数 |$15$|无|
| $5$ | $2\times 10^5$ | $3\times 10^5$ | 保证 $m=n-1$ |$10$|无|
| $6$ | $2\times 10^5$ | $3\times 10^5$ |  无  | $15$|$1,2,3$|
| $7$ | $10^6$ | $10^6$ |  无  | $20$|$1,2,3,6$|

**【样例解释】**

- 对于样例一，构造出的图如下图所示。边权和为 $2+-2+-4+-3+-6=-13$。该样例的构图方式是唯一的。

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

- 对于样例二，构造出的图如下图所示。边权和为 $-3+-6+-12+-15+0=-36$。该样例还存在其它正确的构图方式，比如你可以把边 $(5,6)$ 改为边 $(5,3)$。
  
   ![](https://cdn.luogu.com.cn/upload/image_hosting/6fm944rj.png)

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 贪心, 二分, 堆, 生成树, 构造, 洛谷原创, 洛谷月赛, Special Judge, O2优化
Difficulty: 提高+/省选−
# 「CROI · R2」夏风与树

## 题目背景

刺眼的阳光把大地烤得炽热，小 B 走在街上，迎面吹来一阵清风，路旁郁郁葱葱的树叶沙沙地摇晃着。

“夏风扫过树叶的声音就像下雨一样呢。”

## 题目描述

Alice 和 Bob 在种树，同时，他们决定玩一个游戏。

Alice 拥有 $1\sim n$ 号结点，Bob 拥有 $(n+1)\sim 2n$ 号结点，这 $2n$ 个结点的权值恰好构成一个**排列** $a$，其中 $a_i$ 为 $i$ 号点上的权值。

首先，他们约定 $1$ 号点为树根。

然后，由 Alice 为 $2\sim n$ 号点决定父亲，其中 $i$ 号点的父亲只能在 $1\sim(i-1)$ 中选择。

接下来，由 Bob 为 $(n+1)\sim 2n$ 号点决定父亲，其中 $i$ 号点的父亲只能在 $0\sim(i-1)$ 中选择。$0$ 号点不在他们的树上，也就是说，Bob 的结点不一定要与这颗树连通。

最后，Alice 会从 $1$ 号点开始，对这棵树进行深度优先搜索，同时她会维护一个序列，搜索过程中，每遇到一个没访问过的点就将它上面的**权值**加入序列末尾。

Alice 希望最终序列的字典序尽可能小，Bob 希望最终序列的字典序尽可能大，并且他们二人都会采取最优策略。现在 Bob 请求你告诉他，最终序列会是什么样。

以下是关于字典序的定义：

- 对于一个长度为 $n$ 的序列 $a$，若 $i>n$，约定 $a_i=-\infty$。
- 对于两个序列 $a, b$，我们定义 $a$ 的字典序小于 $b$ 当且仅当存在 $i\ge 1$，使得 $\forall 1 \leq j < i$，$a_j = b_j$，且 $a_i < b_i$。

## 输入格式

**在本题的部分测试点中，Bob 会把 Alice 在第一步中决定好的 $2\sim n$ 号结点的父亲告诉你。**

第一行一个整数 $t$，表示子任务编号。特别地，样例的子任务编号为 $0$。

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

第三行 $2n$ 个正整数，表示排列 $a$。

第四行 $(n-1)$ 个整数，若该子任务拥有特殊性质 A，则表示 $2\sim n$ 号结点的父亲，否则这 $(n-1)$ 个整数都为 $0$。

## 输出格式

一行，表示最终序列。

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

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

## 样例 #2

### 样例输入 #2

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

### 样例输出 #2

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

## 样例 #3

### 样例输入 #3

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

### 样例输出 #3

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

## 提示

样例 #1 中，一种可能的最终树，数字为编号，括号内为权值：

![](https://cdn.luogu.com.cn/upload/image_hosting/gqt4od8n.png)
### 数据范围

| 子任务 | 分值 | $n$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------:  |
| $1$ | $10$ | $\le 4$ |无 |
| $2$ | $10$ | $\le 10^5$ |B|
| $3$ | $30$ | $\le 10^5$ |A |
| $4$ | $20$ | $\le 3000$ |无 |
| $5$ | $30$ | $\le 10^5$ |无 |

特殊性质 A：输入中给定一种 Alice 的最优决策中 $2\sim n$ 号结点的父亲。

特殊性质 B：$a_{n+1}\sim a_{2n}$ 构成 $1\sim n$ 的一个排列。 

对于 $100\%$ 的数据，$1\le n\le 10^5$，保证序列 $a$ 是一个 $1\sim 2n$ 的排列。

## 时空限制



时间限制
1.00s

内存限制
128.00MB

Tags: 贪心, 博弈论, 线段树, 洛谷原创, 洛谷月赛
Difficulty: NOI/NOI+/CTSC
# 小S按按钮

## 题目描述

> $\hspace{15pt}$小 S 想要忘记一切，可是她已身无分文。一天晚上她做了个梦，梦里她只需要按按钮，钱就会自动到账。 

$\hspace{15pt}$一开始小 S 没有钱。当小 S 第奇数次（ $1,3,5,\cdots$ ）次按按钮时，她可以得到 $1$ 元；第偶数次（ $2,4,6,\cdots$ ）次按按钮时，她可以得到 $x$ 元。  
$\hspace{15pt}$她想知道，最少需要按几次按钮，才可以赚到 $y$ 元钱或更多。  
  
$\hspace{15pt}$**本题有多组独立的询问，请你对每组询问的 $x,y$ 分别求出结果。**

## 输入描述:
    
    
    $\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 10^4\right)$ 代表数据组数，每组测试数据描述如下：  
      
    $\hspace{15pt}$在一行上输入两个整数 $x,y \left(0 \le x,y \le 10^9\right)$ 代表偶数次按按钮时得到的金额、目标金额。

## 输出描述:
    
    
    $\hspace{15pt}$对于每一组测试数据，在单独的一行上输出一个整数代表答案。

示例1 

## 输入
    
    
    3
    0 0
    1 1
    11 45

## 输出
    
    
    0
    1
    8

## 说明
    
    
    $\hspace{15pt}$对于第一组测试数据，不需要按按钮也可以达到目标。  
    $\hspace{15pt}$对于第二组测试数据，按一次按钮可以得到 $1$ 元，达到目标。  
    $\hspace{15pt}$对于第三组测试数据，按七次按钮可以得到 $4 \times 1 + 3 \times x = 37$ 元，未达到目标；按八次按钮可以得到 $4 \times (1 + x) = 48$ 元，超过目标。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# 小R排数字

## 题目描述

$\hspace{15pt}$小 R 是一只小猫。有一天她得到了一个正整数 $n$，且 $n$ 在十进制表示下没有 $0$（不考虑前导零）。  
$\hspace{15pt}$小 R 太顽皮了，以至于她将这个正整数 $n$ 的数位重新排列为一个数（也可以不做排列，这样这个数依旧是 $n$ ）。  
$\hspace{15pt}$现在小 R 的主人 T 想问问你，小 R 重组的数字是否有可能是 $4$ 的倍数。  
  
$\hspace{15pt}$**本题有多组询问，你需要对每个询问都求出相应的结果。**

## 输入描述:
    
    
    $\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq  10^4\right)$ 代表数据组数，每组测试数据描述如下：  
      
    $\hspace{15pt}$在一行上输入一个正整数 $n \left(1 \le n \le 10^9\right)$ 代表初始数字。保证 $n$ 在十进制下没有 $0$ 数位。

## 输出描述:
    
    
    $\hspace{15pt}$对于每一组测试数据，如果小 R 重组的数字有可能是 $4$ 的倍数，在单独的一行上输出 $\rm YES$ ；否则，直接输出 $\rm NO$（都是大写字母）。  
    

示例1 

## 输入
    
    
    3
    32123432
    1354
    552122

## 输出
    
    
    YES
    NO
    YES

## 说明
    
    
    $\hspace{15pt}$对于第一组测试数据，$32\,123\,432$ 本身就是 $4$ 的倍数。  
    $\hspace{15pt}$对于第二组测试数据，我们可以证明，$1\,354$ 无法通过重排数位变成 $4$ 的倍数。  
    $\hspace{15pt}$对于第三组测试数据，$552\,122$ 可以重排成 $122\,552$，它是 $4$ 的倍数。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# 小T数星星

## 题目描述

> $\hspace{15pt}$小 T 和她的朋友小 U 在看天文台看星星。  
> 

$\hspace{15pt}$天上有 $n$ 颗星星，第 $i$ 颗星星的亮度为 $a_i$ 。现在小 T 想把这些星星分组。  
$\hspace{15pt}$具体地，她每次可以选取若干颗还未分组的星星（任意选取，不需要连续），如果它们满足：  
$\hspace{23pt}\bullet\,$记一共选取了 $m$ 颗星星，它们的亮度分别是 $c_1,c_2,...,c_m$ ；  
$\hspace{23pt}\bullet\,$ $c_1 \oplus c_2 \oplus \cdots \oplus c_m \neq 0$ ；  
$\hspace{23pt}\bullet\,$ $\operatorname{lcm}(c_1,c_2,\cdots,c_m) + (c_1 \oplus c_2 \oplus \cdots \oplus c_m) = 2 \times \min(c_1,c_2,\cdots,c_m)$ ；  
$\hspace{15pt}$那么小 T 就可以将这些星星分为一组。  
$\hspace{15pt}$小 T 想要让每颗星星都被分到某一组里，请问她最少需要分多少组？  
  
$\hspace{15pt}$**本题有多组数据，你需要对每组数据都求出对应的结果。**  
  
$\hspace{15pt}$在本题中，$\min$ 指最小数，例如 $\min(4,6,8)=4$ ；$\text{lcm}$ 指最小公倍数，例如 $\text{lcm}(2,3,4)=12$ ；$\oplus$ 表示按位异或运算。  
$\hspace{15pt}$如果您需要更多最小公倍数相关的知识，请参考 [**OI-Wiki：最小公倍数**](https://oi-wiki.org/math/number-theory/gcd/#%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0) ；如果您需要更多位运算相关的知识，请参考 [**OI-Wiki：与、或、异或**](https://oi-wiki.org/math/bit/#%E4%B8%8E%E6%88%96%E5%BC%82%E6%88%96) 。

## 输入描述:
    
    
    $\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T \left(1 \le T \le 10^4\right)$ 代表数据组数，每组测试数据描述如下：  
      
    $\hspace{15pt}$第一行输入一个整数 $n \left(1 \le n \le 10^5\right)$ 代表星星的数量。  
    $\hspace{15pt}$第二行输入 $n$ 个整数 $a_1,a_2,...,a_n \left(1 \le a_i \le 10^9\right)$ 代表每颗星星的亮度。  
      
    $\hspace{15pt}$除此之外，保证单个测试文件的 $n$ 之和不超过 $10^5$ 。

## 输出描述:
    
    
    $\hspace{15pt}$对于每一组数据，在单独的一行上输出一个整数，代表最少需要分出的组数。

示例1 

## 输入
    
    
    2
    2
    1 2
    5
    1 1 4 5 1

## 输出
    
    
    2
    3

## 说明
    
    
    $\hspace{15pt}$对于第一组测试数据：  
    $\hspace{23pt}\bullet\,$$1 \oplus 2 = 3$ ，第一个条件满足；  
    $\hspace{23pt}\bullet\,$等式左边 $\operatorname{lcm}(1,2) + (1 \oplus 2) = 2 + 3 = 5$ ；等式右边 $2 \times \min(1,2) = 2$ ，第二个条件不满足。  
    $\hspace{15pt}$综上，这两个数字不能分配到同一组，所以至少需要分出 $2$ 组。  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# 小A弹吉他

## 题目描述

> $\hspace{15pt}$小 A 不想成为不被需要的人，所以她决定要努力练习吉他。但是她现在被一个作业题卡着了，为了珍惜练习时间，她现在向你求助。  
> 

$\hspace{15pt}$对于给定的正整数 $m$，小 A 需要选一个正整数 $n$，并构造一个长度为 $n$ 的正整数序列 $\\{a_1,a_2,\dots,a_n\\}$ 使得它们的和等于 $m$ 。  
$\hspace{15pt}$小 A 想知道，对于所有可能的构造，令 $t_i$ 表示 $a_1,a_2,\dots,a_n$ 中等于 $i$ 的元素个数，最大的 $\operatorname{mex}\big\\{t_1,t_2,\dots,t_{114^{514}}\big\\}$ 是多少。请你求出这个值。  
  
$\hspace{15pt}$**本题有多组数据，请你对每组数据的 $m$ 都求出相应的结果。**  
  
$\hspace{15pt}$整数序列的 $\operatorname{mex}$ 定义为没有出现在序列中的最小非负整数。例如 $\operatorname{mex} \\{1,2,3 \\} =0$ 、$\operatorname{mex} \\{0,2,5\\} =1$ 。

## 输入描述:
    
    
    $\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T \left(1 \le T \le 10^5\right)$ 代表数据组数，每组测试数据描述如下：  
      
    $\hspace{15pt}$在一行上输入一个正整数 $m \left(1 \le m \le 10^{18}\right)$ 代表规定的数组和。

## 输出描述:
    
    
    $\hspace{15pt}$对于每一组测试数据，在单独的一行上输出一个整数，表示最大的 $\operatorname{mex}$ 。

示例1 

## 输入
    
    
    3
    1
    5
    12

## 输出
    
    
    2
    3
    4

## 说明
    
    
    $\hspace{15pt}$对于第一组数据，其唯一可能的构造是选取 $n=1$ 且 $a=\{1\}$，这样 $t_1=1;\ t_2=t_3=\cdots=t_{114^{514}}=0$，因此 $\operatorname{mex}\big\{t_1,t_2,\dots,t_{114^{514}}\big\} =2$。  
    $\hspace{15pt}$对于第二组数据，其中一种可能的构造是选取 $n=3$ 且 $a=\{1,2,2\}$，这样 $t_1=1;\ t_2=2;\ t_3=t_4=\cdots=t_{114^{514}}=0$，因此 $\operatorname{mex}\big\{t_1,t_2,\dots,t_{114^{514}}\big\} =3$。可以证明这是更优的。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# 小M种树

## 题目描述

> $\hspace{15pt}$小 M 出身于贵族学校，擅长园艺。除了会给黄瓜浇水，她还会给一棵树上色。  
> 

$\hspace{15pt}$这棵树的形态与图论中描述的有根树相同，是以 $1$ 为根节点的 $n$ 个节点、$n-1$ 条边的简单连通图。   
$\hspace{15pt}$一开始，树上每个节点染上了红色或蓝色。定义以节点 $i$ 为根的子树的差异 $D(i)$ 为该子树中红色点数与蓝色点数的**差的绝对值** ；而一棵树的不平均程度，等于 $\sum\limits_{i=1}^n D(i)$。  
$\hspace{15pt}$现在小 M 有机会，可以修改其中一个节点的颜色（原来是红色就染成蓝色，反之同理）。小 M 想问你，有哪些修改的方案，可以让这棵树的不平均程度相比修改前更小。  
  
$\hspace{15pt}$**本题有多组数据，你需要对每组数据都求出对应的答案。**

## 输入描述:
    
    
    $\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T \left(1 \le T \le 10^4\right)$ 代表数据组数，每组测试数据描述如下：  
      
    $\hspace{15pt}$第一行输入一个整数 $n \left(1 \le n \le 5 \times 10^5\right)$ 代表树上的点数。   
    $\hspace{15pt}$第二行输入一个长度为 $n$ 、仅由 $\rm{R}$ 和 $\rm{B}$ 组成的字符串 $s$ ，代表树上的节点颜色。其中，如果 $s_i = \rm{R}$，那么代表节点 $i$ 是红色的；反之，如果 $s_i = \rm{B}$，代表节点 $i$ 是蓝色的。  
    $\hspace{15pt}$此后 $n-1$ 行，第 $i$ 行输入两个正整数 $u_i,v_i \left(1 \le u_i,v_i \le n;\ u_i \neq v_i\right)$ ，代表树上第 $i$ 条边连接节点 $u_i$ 和 $v_i$ 。保证这 $n-1$ 条边一定可以形成一棵大小为 $n$ 的树。  
      
    $\hspace{15pt}$除此之外，保证单个文件的 $n$ 之和不超过 $5 \times 10^5$ 。

## 输出描述:
    
    
    $\hspace{15pt}$对于每一组测试数据，在单独的一行上输出一个长度为 $n$ 的 $\rm{01}$ 字符串，代表每一个节点修改后，树的不平均程度是否变小。其中，如果 $s_i=\rm{1}$ ，那么代表修改第 $i$ 个节点后可以让不平均程度变小；反之，输出 $s_i=\rm{0}$。

示例1 

## 输入
    
    
    3
    4
    BRBB
    3 2
    4 2
    1 3
    7
    RRRRBRR
    2 3
    7 3
    4 2
    5 2
    1 5
    6 3
    7
    BRBBBRB
    2 7
    4 7
    1 2
    3 2
    6 2
    5 4

## 输出
    
    
    1010
    1111011
    1011101

## 说明
    
    
    $\hspace{15pt}$对于第一组测试数据，树的形态如下图所示。  
    
    
    ![](https://uploadfiles.nowcoder.com/images/20241129/0_1732869384749/DA59326B09E72E852FF7A1773C34582B)
    
    $\hspace{15pt}$初始时，树的不平均度为 $2+0+1+1=4$ 。  
    $\hspace{23pt}\bullet\,$如果修改了第一个节点的颜色，那么 $D(1)=0$ ，其余不变，新的不平均度为 $0+0+1+1=2$ ，变小了；  
    $\hspace{23pt}\bullet\,$如果修改了第二个节点的颜色，不平均度变为 $10$ ；  
    $\hspace{23pt}\bullet\,$如果修改了第三个节点的颜色，不平均度变为 $2$ ；  
    $\hspace{23pt}\bullet\,$如果修改了第四个节点的颜色，不平均度变为 $4$ ；  
    $\hspace{15pt}$因此，修改第一、三个点，不平均度会比原来小，输出 $\texttt{"1010"}$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# 小H算数

## 题目描述

> $\hspace{15pt}$小 H 是哪个角色？小 H 自己也不知道，但小 H 已经学会弹标题以 H 开头的一首歌了，望周知。  
> 

$\hspace{15pt}$小 H 有一个由 $n$ 个正整数组成的序列 $\\{a_1,a_2,...,a_n\\}$ ，对于其全部的区间 $[i,j] \left(1 \le i<j \le n\right)$ ，定义函数 $c(i,j)$ 和 $d(i,j)$ 如下：  
$\hspace{15pt}$下面是函数 $c$ 的定义：  
$\hspace{23pt}\bullet\,$若 $a_i=a_j$ ，则 $c(i,j)$ 等于区间中比两端（即 $a_i$ ）大的元素个数；  
$\hspace{23pt}\bullet\,$若 $a_i \neq a_j$ ，则 $c(i,j) = 0$。  
$\hspace{15pt}$下面是函数 $d$ 的定义：  
$\hspace{23pt}\bullet\,$若区间长度（即 $j-i+1$ ）是奇数，则 $d(i,j)=1$ ；  
$\hspace{23pt}\bullet\,$若区间长度（即 $j-i+1$ ）是偶数，则 $d(i,j)=2$ 。  
$\hspace{15pt}$你需要帮小 H 求出序列 $a$ 中所有区间的 $c(i,j) \times d(i,j)$ 之和。

## 输入描述:
    
    
    $\hspace{15pt}$第一行输入一个整数 $n \left(2 \le n \le 10^6\right)$ 代表序列中的元素个数。   
    $\hspace{15pt}$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n \left(1 \le a_i \le n\right)$ 代表序列中的元素。

## 输出描述:
    
    
    $\hspace{15pt}$在一行上输出一个整数，代表所有 $c(i,j) \times d(i,j)$ 之和。

示例1 

## 输入
    
    
    6
    1 1 4 5 1 4

## 输出
    
    
    8

## 说明
    
    
    $\hspace{15pt}$在这个样例中，除 $c(1,5)=2;\ c(2,5)=2;\ c(3,6)=1$ ，其余 $c(i,j)$ 均为 $0$ 。  
    $\hspace{15pt}$故我们只关心非 $0$ 的 $c(i,j)$ ，即 $d(1,5)=1;\ d(2,5)=2;\ d(3,6)=2$。  
    $\hspace{15pt}$最终，计算答案是 $2\times 1+2 \times 2+1 \times 2=8$ 。  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# Cidoai的吃饭

## 题目描述

Cidoai 喜欢吃饭。  
它的饭卡中一开始有 $n$ 元钱。假设某次吃饭前，它的饭卡中剩下 $x$ 元钱，则他会做出如下选择：  
1\. 若 $x \ge a$，花费 $a$ 元购买套餐一；  
2\. 若不满足条件 1 且 $x \ge b$，花费 $b$ 元购买套餐二；  
3\. 若不满足条件 1、2 且 $x \ge c$，花费 $c$ 元购买套餐三；  
4\. 若上述三个条件都不满足，则吃不了饭。  
给定 $n,a,b,c$，请问 Cidoai 一共能吃几顿饭。  


## 输入描述:
    
    
    一行四个正整数 $n,a,b,c$。  
      
    $1 \le n,a,b,c \le 10^6$  
    

## 输出描述:
    
    
    一行一个整数，表示吃饭的次数。

示例1 

## 输入
    
    
    50 16 12 10

## 输出
    
    
    3


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld