RDOI Round #1

下发文件：

RDOI Round #1

不保证安全喵

题目名称	猫树	记忆余晖	乘积,欧拉函数,求和	重逢之时
文件名称	catree.cpp/.in/.out	memory.cpp/.in/.out	phi.cpp/.in/.out	reunion.cpp/.in/.out
时间限制	1s	1s	1.5s	2s
空间限制	256MB	512MB	512MB	512MB
题目类型	传统题	传统题	传统题	传统题

快读随下发文件一同下发，你最好使用。

注意事项：

1. 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。
2. 程序可使用的栈内存空间限制与题目的内存限制一致。
3. C++ 语言编译选项开启 -O2 -std=c++14​。
4. 不要带会产生刺激性气味的食品参加比赛，虽然你可能并不被允许带食品进入考场。
5. 请牢记比赛时间为 4h，并合理分配时间。
6. 本场比赛前三名可以找非 RDOI 成员领取奖励。
7. 不要盯着注意事项看 4h。
8. 本场比赛提供暗色题面。

$\;$
$\;$
$\;$
$\;$

猫树 (Catree)

文件名 catree.cpp/.in/.out​，时间限制 $1$ 秒，空间限制 $256 \text{MB}$。

题目背景

‍We’re gonna ri-ri-ri-ri-rise 'til we fall

No they don’t speak our language

They say we’re too savage yeah

No no we don’t give a anymore

这里本来有一个关于猫和树和猫粮和异或的感人小故事，但是删掉了。

cat & tree = t。

题目描述

给定一条 $n$ 条边，$n+1$ 个点的树，第 $i$ 条边连接点 $i$ 和点 $i+1$，下标从 $1$ 开始，你也从点 $1$ 出发。

经过第 $i$ 条边所需的时间为 $t_i$，你需要在 $m$ 时刻前（包含 $m$ 时刻）到达点 $n+1$。

初始你有 $0$ 枚金币，同时每一个点 $i$ 上都有一只可以摸的猫 $i$，有二元组 $(a_i,b_i)$ 来描述这只猫，对于每只猫，你可以多次进行如下操作：

• 花费 $1$ 单位时间摸这只猫，如果这是你第 $k$ 次摸这只猫，获得 $a_i-(k-1)b_i$ 金币。

点 $n+1$ 并没有猫，当你到达点 $n+1$ 时，就不能进行操作了。

求在规定时间内到达点 $n+1$ 时的最大金币数。

输入格式

第一行输入两个正整数 $n$ 和 $m$，分别表示猫的只数和规定时间。

第二行输入 $n$ 个正整数 $t_i$，表示经过第 $i$ 条边需要的时间。

接下来 $n$ 行每行输入两个整数 $a_i$ 和 $b_i$，用来描述猫 $i$。

输出格式

输出一个整数，表示最大金币数。

样例

样例输入 #1

3 10
1 1 1
10 1
20 9
25 15

样例输出 #1

93

样例输入 #2

10 15
1 1 1 1 1 1 1 1 1 1
6 2
7 5
1 1
8 6
4 4
4 2
5 5
7 6
10 3
6 3

样例输出 #2

39

样例 #3

见下发文件 ex_catree3.in/out，该样例满足测试点 5 的限制。

样例 #4

见下发文件 ex_catree4.in/out，该样例满足测试点 10 的限制。

说明提示

测试点编号	$n$	$m$	特殊性质
$1\sim2$	$\leq 3 \times 10^5$	$\leq 10^5$	无
$3\sim4$	$\leq 10^3$	$\leq 10^8$	无
$5$	$\leq 3 \times 10^5$	$<2^{32}$	$A$
$6\sim10$	$\leq 3 \times 10^5$	$<2^{32}$	无

特殊性质 $A$：保证对于所有 $i$，$a_i \leq b_i$。

保证对于 $100\%$ 的测试点，$1 \leq n \leq 3 \times 10^5$，$1 \leq m < 2^{32}$，$1 \leq t_i \leq 10^9$，$1 \leq a_i,b_i \leq 10^{12}$。

保证存在一种方案，使得你可以在规定时间内从点 $1$ 走到点 $n+1$。

$\;$
$\;$
$\;$
$\;$

记忆余晖 (Memory)

文件名 memory.cpp/.in/.out​，时间限制 $1$ 秒，空间限制 $512\text{MB}$。

题目背景

It won’t be long now, it won’t be long now

When I get back on land

Well I’ll never get my chance

Be ready to live and it’ll be ripped right out of my hands

开篇的线索看似简单，结局到来前，故事展现了其复杂的一面。

单点空间不可大于 512MB，如有需要请联系管理员。

题目描述

给定一个长度为 $m$ 的序列 $b$。

求满足最长上升子序列之一为 $b$ 的长度为 $n$ 的排列 $p$ 的数量。

输入格式

第一行输入两个正整数 $n$ 和 $m$，分别表示排列 $p$ 的长度和序列 $b$ 的长度。

第二行输入 $m$ 个正整数 $b_i$，含义见题目描述。

输出格式

输出一个整数，表示排列 $p$ 的数量，对 $10^9 + 9$ 取模。

样例

样例输入 #1

4 2
1 4

样例输出 #1

4

样例解释 #1

满足条件的排列 $p$ 有 $(1,4,3,2)$，$(2,1,4,3)$，$(3,1,4,2)$，$(3,2,1,4)$，共 $4$ 个。

样例输入 #2

6 3
2 3 5

样例输出 #2

47

样例输入 #3

10 4
2 4 7 9

样例输出 #3

30300

样例输入 #4

15 7
2 4 5 7 9 10 13

样例输出 #4

81734510

样例输入 #5

21 12
1 3 5 7 9 10 11 13 15 18 19 20

样例输出 #5

565973512

提示说明

测试点编号	$n$	特殊性质
$1$	$n\leq 3$	无
$2 \sim 4$	$n\leq 10$	无
$5\sim8$	$n\leq 20$	A
$9\sim10$	$n\leq 15$	无
$11\sim15$	$n\leq 19$	无
$16\sim20$	$n\leq 20$	无
$21\sim25$	$n\leq 21$	无

特殊性质 $A$：保证 $n-4\leq m\leq n$。

保证对于 $100\%$ 的测试点，$1 \leq m,\;b_i \leq n \leq 21$。

$\;$
$\;$
$\;$
$\;$

乘积,欧拉函数,求和 (phi)

文件名 phi.cpp/.in/.out​，时间限制 $1.5$ 秒，空间限制 $512\text{MB}$。

题目背景

Running through this strange life

Chasing all them green lights

Throwing off the shade

For a little bit of sunshine

题目描述

维护一个集合 $S$，求该集合中所有元素两两之间的乘积的 $φ$ 值之和。

形式化的，求 $\sum\limits_{u \in S,v \in S,u < v} φ(uv)$。

其中，$φ$ 表示欧拉函数。

输入格式

第一行输入两个整数 $n$ 和 $m$，$n$ 表示操作次数，$m$ 表示集合中元素可能的最大值。

第二行输入 $n$ 个整数 $x_i$，表示一次操作。

我们这样定义一次操作：

• 当 $x_i \notin S$ 时，将 $x_i$ 加入集合 $S$。
• 否则，当 $x_i \in S$ 时，将 $x_i$ 从集合 $S$ 中删去。

输出格式

输出 $n$ 行，每行一个整数，第 $i$ 行的整数表示操作 $i$ 后集合 $S$ 的答案，对 $998244353$ 取模。

样例输入 #1

5 4
1
2
3
4
3

样例输出 #1

0
1
5
15
7

样例解释 #1

当第四次操作后，$S=\{1,2,3,4\}$，所以 $ans=φ(1 \times 2) + φ(2 \times 3)+φ(3 \times 4)+φ(1 \times 3)+ φ(2 \times 4)+φ(1\times 4) = 1 + 2 + 4 + 2 + 4 + 2 = 15$。

样例输入 #2

10 10
5
3
4
6
2
6
4
1
10
9

样例输出 #2

0
8
20
42
56
30
14
21
61
139

样例 #3

见下发文件 ex_phi3.in/out，该样例满足测试点 4 的限制。

样例 #4

见下发文件 ex_phi4.in/out，该样例满足测试点 12 的限制。

样例 #5

见下发文件 ex_phi5.in/out，该样例满足测试点 20 的限制。

提示说明

测试点编号	$n$	$m$	特殊性质
$1\sim2$	$\leq 10$	$\leq 10$	无
$3\sim4$	$\leq 10^3$	$\leq 10^3$	无
$5\sim6$	$\leq 10^5$	$\leq 3 \times 10^3$	$无$
$7\sim12$	$\leq 10^5$	$\leq 3 \times 10^5$	$A$
$13\sim16$	$\leq 10^5$	$\leq 3 \times 10^5$	无
$17 \sim 20$	$\leq 3 \times 10^5$	$\leq 5 \times 10^5$	无

特殊性质 $A$：保证对于进行每一个操作 $i$ 时，$x_i \notin S$。

保证对于 $100\%$ 的测试数据，$1 \leq n \leq 3 \times 10^5$，$1 \leq x_i \leq m \leq 5 \times 10^5$。

保证对于没有特殊性质 $A$ 的测试数据，$x_i$ 在 $1$ 至 $m$ 的范围内均匀随机生成。

$\;$
$\;$
$\;$
$\;$

重逢之时 (reunion)

文件名 reunion.cpp/.in/.out​，时间限制 $2$ 秒，空间限制 $512 \text{MB}$。

题目背景

从夜晚走向清晨。
从清晨走向夜晚。
从现实走向梦境。
从梦境走向现实。
终有一天，我们会在梦中，邂逅那片未经观测的星空。

于太阳西斜之时重逢吧,此时此刻的光辉,盼君勿忘。

题目描述

浩瀚的星云中有着无数的星球，由于宇宙的不断降维，不同的星球处在同一直线上，也就是你可以把星球看做数轴上的点。同时，没有任意两个星球处于同一位置。Chtholly 和你将在两颗不同的星球上，你已经迫不及待的想和她重逢，所以你想知道在不同情况下你们两的最短距离是多少。

具体地，有 $n$ 个星球，给出每个星球的位置 $a_i$ ，$q$ 次询问。

对于两个编号下标 $l,r$ ，定义 $f(l,r)$ 表示：从 $l$ 到 $r$ 选两个数使他们的差的绝对值最小。

形式化地，$f(l,r)=min_{l \le i < j \le r}{|a_i-a_j|}$。

$q$ 次询问，每次给出一对 $L,R$，求 $\sum_{i=L}^{R-1} f(i,R)$。

输入格式

第一行两个由空格分隔的整数 $n,q$；

第一行 $n$ 个由空格分隔的整数 $a_i$；

接下来 $q$ 行，每行两个整数 $L,R(L<R)$。

输出格式

输出 $q$ 行，每行一个整数表示答案，对 $10^9+7$ 取模。

样例输入 #1

3 3
6 2 8
1 3
1 2
2 3

样例输出 #1

8
4
6

样例解释 #1

$f(1,2)=6-2=4,\;f(2,3)=8-2=6,\;f(1,3)=8-6=2$。

查询一的答案为 $f(1,3)+f(2,3)=2+6=8$。

查询二的答案为 $f(1,2)=4$。

查询三的答案为 $f(2,3)=6$。

样例输入 #2

5 5
733533103 809174366 611619313 711218266 130639620
2 4
2 3
3 4
2 3
1 5

样例输出 #2

197555053
197555053
99598953
197555053
800448536

样例 #3

见下发文件 ex_reunion3.in/out，该样例满足测试点 1 的限制。

样例 #4

见下发文件 ex_reunion4.in/out，该样例满足测试点 4 的限制。

样例 #5

见下发文件 ex_reunion5.in/out，该样例满足测试点 7 的限制。

样例 #6

见下发文件 ex_reunion6.in/out，该样例满足测试点 10 的限制。

提示说明

对于 $100\%$ 的数据，$1\le l<r\le n,\;0\le a_i\le 10^9$ 。

测试点编号	$n$	$q$
$1$	$\leq 100$	$\leq 100$
$2\sim4$	$\leq 3\times10^3$	$\leq3\times 10^3$
$5\sim7$	$\leq 10^4$	$\leq 10^5$
$8\sim10$	$\leq 10^5$	$\leq 10^6$