# 算法社暑期集训第一次阶段测试
### 【选手须知】
- 比赛开始后，选手可通过线上在线评测系统提交代码。
- 比赛时长以比赛页面显示为准。请合理安排时间，注意保存代码，并在截止前完成提交。
- 本场比赛采用 **ACM赛制**。比赛期间不显示各题详细评测结果，不通过罚时20分钟，最后一小时封榜。
- 封榜期间，选手只可看到自己的评测结果，榜单将在滚榜结束后开放。
- 对同一道题，选手可以多次提交，最终以第一次最高分的提交的评测结果为准（罚时按首次通过的时间计算）。
- 本场比赛的所有题目都需要以程序形式或者文件形式提交到评测机。
- 题目均为常规程序设计题，**难度并不完全升序**，请选手合理规划做题顺序。
- 选手提交的程序必须能够对给定输入输出正确结果。评测时使用的数据与题面中的样例不一定相同，因此程序必须是通用解法，不能只针对样例通过。
- 选手提交的代码不得依赖图形界面、Win32 API、硬件操作或其他与操作系统强相关的接口。
- 对于 **C++** 选手，代码中允许使用 STL。所有依赖的头文件都必须在源文件中显式包含。
- 对于 **Python** 选手，所有依赖的标准库模块都必须在源文件中显式 import，请不要依赖本地额外安装的第三方模块。
- 对于 **Java** 选手，主类名必须为 Main；如使用类库，请将相应的 import 语句与程序正文一并提交。
- 所有源码应提交为单文件形式。提交前请再次确认代码版本、语言与编译器配置是否正确。
## A. 时间计数
### 题目背景:
桃花山上的桃花开了又谢，谢了又开。
陶眠拥有着无尽的寿元，却也背负着无法言说的孤独。他的徒弟在红尘中历经三世轮回，生老病死，恩怨情仇。
对于小陶而言，时间的流逝不再以春秋计算，而是变成了系统面板上那每年雷打不动、默默增加一层的炼气期层数。当徒弟在红尘中历经千般苦楚、浮沉百载时，小陶只是枯坐在桃花树下，自己的修为从第 $1$ 层，一年年地叠到了第 $n$ 层。
某一夜，月朗风清，小陶饮下一壶浊酒，突然想起了某一世徒弟临终前紧紧握住他的手，叮嘱他的那个神秘数字 $x$。在这漫长孤寂的、通往第 $n$ 层的修仙岁月里，这个数字究竟出现了多少次？每一次它的惊鸿一瞥，是否都对应着徒弟在某一个纪元里向他奔赴而来的身影？
### 题目描述:
小陶闭上双眼，神识扫过自己从修为第 $1$ 层到第 $n$ 层的全部修行记录。请你编写一个程序，帮小陶统计出在这一串代表着无尽岁月的整数层数中，数字 $x$（$0\le x\le9$）一共出现了多少次。
例如：当小陶修为叠到第 $11$ 层时，他的修行记录为 $1,2,3,4,5,6,7,8,9,10,11$。如果他想寻找的数字 $x=1$，则数字 $1$ 一共出现了 $4$ 次（分别在 1, 10, 11 中出现）。
### 输入格式:
输入共 $2$ 个整数 $n,x$，之间用一个空格隔开。$n$ 代表小陶当前的修为层数。$x$ 代表小陶想要追寻的那个数字。
### 输出格式:
输出共 $1$ 个整数，表示数字 $x$ 在小陶的记录中出现的总次数。
### 输入输出样例 #1:
#### 输入 #1
```
11 1
```
#### 输出 #1
```
4
```
### 说明/提示:
对于 $100\%$ 的数据，满足 $1\le n\le 10^6$，$0\le x \le 9$。
## B. 桃花长阶
### 题目背景
桃花山高耸入云，山顶的道观里，小陶道长已经独自枯坐了千载。
这一世，红尘流转，小陶的徒弟再度转世。虽失了前尘记忆，但冥冥之中的血脉与宿缘，依旧指引着他来到了桃花山脚下。
从凡俗的人间到清修的道观，一共有 $N$ 级古旧的石阶。徒弟驻足仰望，石阶没入云雾之中，隐约能嗅到山顶飘来的淡淡桃花酒香。为了寻回那一丝执念，徒弟毅然踏上了长阶。因缘际会之下，他每一步福至心灵，或迈 $1$ 级，或跨 $2$ 级，或 $3$ 级。
山顶上，小陶拂去衣襟上的落花，睁开双眼，神识早已锁定了那道正一步步坚定登阶的身影。万千步法，皆是因果。小陶拂袖推演，算着徒弟究竟有多少种不同的步法组合，能最终驻足在自己的身前。
### 题目描述
已知从山脚到小陶所在的道观共有 $N$ 级台阶。徒弟一开始在最底部的第 $0$ 级，每次向上可以迈 $1$ 级、 $2$ 级或 $3$ 级台阶。
请你编写一个程序，帮小陶算出一共有多少种不同的登阶方式，可以刚好到达第 $N$ 级台阶。由于天道无常，命运的轨迹繁复无穷，最终的方式数请对 $100003$ 取模。
### 输入格式
输入一个正整数 $N(1 \le N \le 10^5)$，代表桃花山的石阶总级数。
### 输出格式
输出一个正整数 $ans \pmod{100003}$，代表到达第 $N$ 级台阶的不同方式数对 $100003$ 取模后的结果。
### 输入输出样例 #1
#### 输入 #1
```
5
```
#### 输出 #1
```
13
```
## C. 小陶的位运算挑战
### 题目背景：
在桃花山下的桃花观里，活了一千年的长生者陶眠正在研究他的“共享修炼长生系统”。为了在云共享中永远比他的卷王徒弟们高出一筹，系统面板弹出了两个被加密的底层参数 $x$ 和 $y$。
若要完美触发被动效果，小陶道长需要找到一个“平衡因子” $n$。通过按位异或（XOR）运算改变这两个参数的二进制分布，使得变换后 $x$ 的二进制中 $1$ 的个数，popcount）严格大于变换后的 $y$ 的二进制中 $1$ 的个数。
### 题目描述：
给定两个非负整数 $x$ 和 $y$，你需要构造一个整数 $n（0 \le n < 2^{31}）$，使得：
$$\operatorname{popcount}(x \oplus n) > \operatorname{popcount}(y \oplus n)$$
其中 $\operatorname{popcount}(z)$ 表示 $z$ 在二进制表示中 $1$ 的个数。例如 $\operatorname{popcount}(3) = 2$（二进制为 $11$），$\operatorname{popcount}(4) = 1$（二进制为 $100$）。
$\oplus$ 表示按位异或运算。
题目保证在给定范围内一定有解。如果有多解，输出任意一个满足条件的 $n$ 即可。
### 输入格式:
第一行一个整数 $T（1 \le T \le 10^6）$，表示测试数据组数。
接下来 $T$ 行，每行两个整数 $x, y（0 \le x < y < 2^{31}）$。
### 输出格式:
对于每组数据，输出一行一个整数 $n$，满足上述不等式。
### 输入样例:
```
2
1 2
0 4
```
### 输出样例:
```
2
4
```
### 说明/提示：
本题数据量较大，请使用较快的读入方式。
```cpp
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << "答案" << '\n';
```
## D. 小陶的考验
### 题目背景:
小陶道长管理着一座声名远扬的道观。为了检验门下弟子的修行成果，小陶道长会定期考核他们的“道行值”（数值在 0 到 100 之间）。
根据道观的规矩，道行值达到 60 及以上（$\ge 60$）的弟子才算学成，具备下山历练、降妖除魔的资格。随着慕名而来的求道者越来越多，小陶道长精力和时间有限，他需要你帮他设计一个管理系统，在 $O(1)$ 的时间复杂度内动态维护和查询道观内的总人数，以及随时可以下山历练的弟子数量。
### 题目描述:
系统初始时为空，需要支持不超过 $10^5$ 次操作，操作共有四种类型：
1. **登记与更新**，格式为 `1 NAME SCORE`：
- 在系统中录入或修改名字为 $\texttt{NAME}$（由字母和数字组成、不超过 100 个字符的字符串，区分大小写），道行值为 $\texttt{SCORE}$（$0 \le \texttt{SCORE} \le 100$）的弟子信息。
- 如果该名字先前不存在，则录入数据并输出 `Added`。
- 如果该名字先前已存在，则更新其道行值为 $\texttt{SCORE}$，并输出 `Modified`。
2. **下山历练（移除）**，格式为 `2 NAME`：
- 在系统中删除名字为 $\texttt{NAME}$ 的弟子数据（表示该弟子已正式毕业，出师下山）。
- 如果找不到该名字，输出 `Not found`；否则将其移除并输出 `Removed`。
3. **查询可下山人数**，格式为 `3`：
- 输出当前系统中所有道行值大于等于 60 分（$\ge 60$）的弟子总人数。
4. **查询总人数**，格式为 `4`：
- 输出当前系统中登记的弟子总数量。
### 输入格式:
第一行输入一个正整数 $Q$（$1 \le Q \le 10^5$），表示操作的总次数。
接下来 $Q$ 行，每行先输入一个正整数 $op$（$op \in [1,4]$），表示操作类型：
- 若 $op = 1$，后随一个字符串 $\texttt{NAME}$ 和一个整数 $\texttt{SCORE}$。
- 若 $op = 2$，后随一个字符串 $\texttt{NAME}$。
- 若 $op = 3$ 或 $op = 4$，本行无其他输入。
### 输出格式:
共输出 $Q$ 行。每行对应一次操作的执行结果。
### 输入输出样例 #1:
#### 输入 #1
```
8
1 ZhangSan 58
1 LiSi 85
3
1 ZhangSan 62
3
2 LiSi
2 WangWu
4
```
#### 输出 #1
```
Added
Added
1
Modified
2
Removed
Not found
1
```
## E. Divisible Permutation
### 题目描述:
给定一个整数 $n$。请构造一个长度为 $n$ 的排列 $p$，使其满足以下条件：
- 对于每个 $1 \le i \le n-1$，都有 $|p_i - p_{i+1}|$ 能被 $i$ 整除。
可以证明，在本题的约束条件下，总是存在这样的一个排列。
排列指的是长度为 $n$、由 $1$ 到 $n$ 的 $n$ 个互不相同整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 时数组中出现了 $4$）。
### 输入格式:
每个测试包含多组测试数据。第一行为测试用例个数 $t$（$1\le t\le 100$）。接下来是 $t$ 组测试用例的描述。
每个测试用例仅一行，包含一个整数 $n$（$2\le n\le 100$）——表示要构造排列 $p$ 的长度。
### 输出格式:
对于每组测试用例，输出 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1\le p_i\le n$，所有 $p_i$ 互不相同），即你构造的排列。
若有多组满足条件的排列，输出任意一组均可。
### 输入输出样例 #1:
#### 输入 #1
```
2
2
3
```
#### 输出 #1
```
1 2
2 3 1
```
### 说明/提示:
在第一个测试用例中，$p = [1,2]$ 满足条件，因为 $|p_1-p_2| = |1-2| = 1$，能被 $1$ 整除。
在第二个测试用例中，$p = [2,3,1]$ 满足条件，因为：
- $|p_1 - p_2| = |2-3| = 1$，能被 $1$ 整除；
- $|p_2 - p_3| = |3-1| = 2$，能被 $2$ 整除。
## F. 路标设置
### 题目背景:
B 市和 T 市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，我们把公路上相邻路标的最大距离定义为该公路的“空旷指数”。
### 题目描述:
现在政府决定在公路上增设一些路标，使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。请注意，公路的起点和终点保证已设有路标，公路的长度为整数，并且原有路标和新设路标都必须距起点整数个单位距离。
### 输入格式:
第 $1$ 行包括三个数 $L,N,K(2 \leq N \leq 100000, 0 \leq K \leq100000, 0 < L \leq 10000000)$，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。
第 $2$ 行包括递增排列的 $N$ 个整数，分别表示原有的 $N$ 个路标的位置。路标的位置用距起点的距离表示，且一定位于区间 $[0,L]$ 内。
### 输出格式:
输出 $1$ 行，包含一个整数，表示增设路标后能达到的最小“空旷指数”值。
### 输入输出样例 #1:
#### 输入 #1
```
101 2 1
0 101
```
#### 输出 #1
```
51
```
### 说明/提示:
公路原来只在起点和终点处有两个路标，现在允许新增一个路标，应该把新路标设在距起点 $50$ 或 $51$ 个单位距离处，这样能达到最小的空旷指数 $51$。
## G. Karen and Coffee
### 题目描述
为了在上课时保持清醒和专注，Karen 需要喝点咖啡！
Karen 是一位咖啡爱好者，她想知道冲泡完美咖啡的最佳温度。实际上，她花了一些时间阅读了几本食谱，包括备受赞誉的《The Art of the Covfefe》。
她一共掌握了 $n$ 种咖啡配方。第 $i$ 个配方建议咖啡应在 $l_i$ 到 $r_i$ 度（包含端点）之间冲泡，以获得最佳口感。
Karen 认为，如果有至少 $k$ 个配方推荐某个温度，则该温度为可接受温度。
Karen 的想法总是变化多端，于是她总共提出了 $q$ 个问题。每个问题，她都会给定一个温度范围 $a$ 到 $b$，想让你告诉她，在这个范围内有多少个可接受的整数温度。
### 输入格式
输入的第一行包含三个整数 $n,\ k$（$1 \leq k \leq n \leq 200000$）、$q$（$1 \leq q \leq 200000$），分别表示配方数量、某个温度被判定为可接受所需的最少配方数，以及 Karen 提出的查询个数。
接下来的 $n$ 行描述每个配方。具体地，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq 200000$），表示第 $i$ 个配方推荐咖啡应在 $l_i$ 到 $r_i$ 度（包含端点）之间冲泡。
接下来的 $q$ 行描述各个问题。每行包含两个整数 $a$ 和 $b$（$1 \leq a \leq b \leq 200000$），表示她想知道在 $a$ 到 $b$（包含端点）度之间有多少个可接受的整数温度。
### 输出格式
对于每一个问题，输出一行一个整数，表示在 $a$ 到 $b$ 度之间有多少个可接受的整数温度。
### 输入输出样例 #1
#### 输入 #1
```
3 2 4
91 94
92 97
97 99
92 94
93 97
95 96
90 100
```
#### 输出 #1
```
3
3
0
4
```
### 输入输出样例 #2
#### 输入 #2
```
2 1 1
1 1
200000 200000
90 100
```
#### 输出 #2
```
0
```
### 说明/提示
在第一个测试点中，Karen 掌握了 $3$ 个配方。
1. 第一个推荐温度区间为 $91$ 到 $94$ 度（包含端点）。
2. 第二个推荐温度区间为 $92$ 到 $97$ 度（包含端点）。
3. 第三个推荐温度区间为 $97$ 到 $99$ 度（包含端点）。
只要某个温度区间内至少有 $2$ 个配方推荐，则该温度为可接受温度。
她一共提出了 $4$ 个问题。
在第一个询问中，她想知道在 $92$ 到 $94$ 度之间的可接受整数温度有多少。答案是 $3$，因为 $92,\ 93,\ 94$ 度都是可接受的。
在第二个询问中，她想知道在 $93$ 到 $97$ 度之间的可接受整数温度有多少。答案是 $3$，因为 $93,\ 94,\ 97$ 度都是可接受的。
在第三个询问中，她想知道在 $95$ 到 $96$ 度之间的可接受整数温度有多少。没有可接受的温度。
在最后一个询问中，她想知道在 $90$ 到 $100$ 度之间有多少个可接受的整数温度。答案是 $4$，分别是 $92,\ 93, 94, 97$ 度。
在第二个测试点中，Karen 掌握了 $2$ 个配方。
1. 第一个配方建议只在 $1$ 度冲泡咖啡。
2. 第二个配方建议只在 $200000$ 度冲泡咖啡。
只要某个温度区间内至少有 $1$ 个配方推荐，则该温度为可接受温度。
她有且仅有一个问题，询问在合理范围内有多少可接受整数温度。实际上没有。
## H. 数字排列
### 题目背景
小陶最近迷上了一个数字排列游戏。他手里有一叠卡牌，每天都在研究如何通过固定的规则将它们收拾整齐。
### 题目描述
小陶手里有 $n$ 张排成一排的卡牌，每张卡牌上都写着一个正整数，这些数字恰好是 $1$ 到 $n$ 的一个排列 $p_1, p_2, \dots, p_n$。
现在，小陶拿到了两个特殊的正整数 $x$ 和 $y$。小陶的目标是通过一系列的交换操作，将这叠卡牌变成升序排列（即 $[1, 2, \dots, n]$）。由于游戏规则限制，小陶每次只能选择一个位置 $i$，并执行以下两种交换之一：
1. 交换 $p_i$ 与 $p_{i+x}$ 的位置（要求 $i + x \le n$）；
2. 交换 $p_i$ 与 $p_{i+y}$ 的位置（要求 $i + y \le n$）。
小陶可以进行任意次操作（也可以不操作）。请你帮小陶判断一下，他最终是否有可能将这叠卡牌变成升序排列？
### 输入格式
每个测试文件均包含多组测试数据。
第一行输入一个整数 $T(1 \le T \le 2 \times 10^4)$ ，代表数据组数。
对于每组测试数据：
- 第一行包含三个整数 $n, x, y(4 \le n \le 2 \times 10^5 且 1 \le x < y < n)$。
- 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示小陶手里的卡牌初始排列。
### 输出格式
对于每组测试数据，输出一行。
如果小陶可以通过操作将卡牌排成升序，输出 `Yes`；否则输出 `No`。
### 输入输出样例
#### 输入样例 1
```in
2
4 1 2
4 3 2 1
5 2 4
1 3 2 4 5
```
#### 输出样例 1
```out
Yes
No
```
### 说明/提示
- 保证单个测试文件的所有 $n$ 之和不超过 $2 \times 10^5$。
- 输入的 $p$ 保证是一个长度为 $n$ 的排列（即由 $1, 2, \dots, n$ 这 $n$ 个整数按任意顺序组成，每个整数均恰好出现一次）。
## I. 吾有上将潘凤，可斩华雄！
### 题目背景:
“吾有上将潘凤，可斩华雄！”
盟主大帐内，韩馥的话音刚落，重生的潘凤心里就冷笑了一声。他知道，如果自己直接推脱，韩馥肯定会不高兴；但如果能把锅精准地甩给下一个人，下一个人为了保命再甩给再下一个人……直到甩给那个真正能打赢华雄的“战力天花板”，那自己不仅能保命，还能坐看联军内斗。
凭借重生多次经验，潘凤瞬间看穿了排成一排的 $N$ 位将领的武力值。他要计算的不再是简单的“下一个是谁”，而是整条“甩锅链”。
### 题目描述:
现在有 $N(1\le N\le10^5)$ 位将领排成一排，从左到右依次编号为 $1$ 到 $N$。第 $i$ 位将领的武力值是 $H_i(1\le H_i\le10^6)$。
甩锅规则如下：
1. 当华雄叫阵令下达给将领 $i$ 时，如果他右侧存在武力值严格大于他的将领，他会立刻把军令塞给右侧距离最近且比他强的将领 $j$。
2. 将领 $j$ 接到军令后，同样会依此规则继续向右甩锅，直到军令传到某位将领手上时，其右侧再也没有比他更强的人。这位最后的将领将退无可退，必须披挂上阵。
一条完整的“甩锅链”包含从发起者到最后出战者的所有将领。重生者潘凤想知道：对于每一位将领 $i$，如果从他开始发起甩锅，整条甩锅链上所有被卷入的将领的武力值之和是多少？
### 输入格式:
第 $1$ 行输入一个整数 $N(1\le N\le10^5)$，表示将领的数量。
之后 $N$ 行，第 $i+1$ 行输入一个整数 $H_i(1\le H_i\le10^6)$，表示第 $i$ 位将领的武力值。
### 输出格式:
共 $N$ 行，按顺序每行输出一个整数，表示从第 $i$ 位将领开始甩锅时，整条链上的武力值总和。
### 输入输出样例 #1:
#### 输入 #1
```
6
3
2
6
1
1
2
```
#### 输出 #1
```
9
8
6
3
3
2
```
### 说明/提示:
**【样例解释】**
$6$ 位将领的武力值分别为 $3, 2, 6, 1, 1, 2$。
- **将领 1**（武力 $3$）：传给右边最近更强者**将领 3**（武力 $6$）。将领 $3$ 右边没有更强者，甩锅结束。链上武力总和为 $3 + 6 = 9$。
- **将领 2**（武力 $2$）：传给**将领 3**（武力 $6$），结束。总和为 $2 + 6 = 8$。
- **...**
- **将领 4**（武力 $1$）：传给右边最近更强者**将领 6**（武力 $2$），结束。总和为 $1 + 2 = 3$。