loj#P6780. 「2021 营员交流」数串
「2021 营员交流」数串
题目背景
小 F 喜欢字符串。
小 S 喜欢后缀数组。
有 只鼠,它们被绳子依次串起来,顺次排成一排。每只鼠有一个体型大小 。小 F 定义一个后缀为从某一只鼠开始,到最后一只鼠构成的序列。
对于两个鼠的序列 ,我们称 当且仅当存在一个位置 ,满足 和 中前 只鼠的体型大小对应相同,且 的第 只鼠不存在或者比 的第 只鼠小。
小 S 给予了这些鼠一个排列 $\boldsymbol p = \left[ p_1, p_2, \ldots, p_n \right]$,满足对于 ,从第 只鼠开始的后缀小于从第 只鼠开始的后缀。
小 F 观察了这一列鼠后,发现它们中有非常多的鼠具有相同的体型大小。于是,她问小 S:这列鼠有多少种不同的大小呢?
鼠在不停地挣扎,想要挣脱绳子的束缚。小 S 还没有看清这些鼠的大小,鼠便把绳子都咬断了,开始四处乱窜。
小 S 有些气恼,但是她还是想要知道答案。她带着已经得到的排列问小 F:对于所有满足 “给予它的排列为 的” 鼠的序列,答案 (鼠的大小的种类数) 的最小值可以是多少?
鼠在不停地挣扎,想要逃离这阴暗的房间。小 S 还没有计算出来,鼠便把小 S 得到的排列中的若干数字也咬掉了,带着碎片纷纷逃离房间。
小 S 有些气恼,但是她还是想要知道答案。她带着那残缺的排列问小 F:对于剩下的数的所有 种排列方案 ( 为被鼠咬掉的数的数量),答案 (鼠的大小的种类数的最小值) 的总和是多少?
小 S 哭了。
题目描述
本题包含三个问题:
- 问题 0:给定一个长度为 的序列以及它的后缀数组 ,求这个序列中有多少个不同的数。
- 问题 1:给定一个长度为 的排列 ,对于所有满足后缀数组为 的长度为 的序列,求不同的数的数量的最小值。
- 问题 2:给定一个长度为 的残缺的排列 (有 个位置未知),对于所有 种完整的排列,求问题 1 的答案之和。
在不同的测试点中,你将可能需要回答不同的问题。我们将用 来指代你需要回答的问题编号 (对应上述 )。
在问题 2 中,由于答案可能很大,因此你只需要输出答案对 取模的结果即可。
输入格式
第一行包含两个非负整数 ,分别表示鼠的数量和子问题的类型。
如果 ,则第二行包含 个正整数 ,表示每只鼠的体型大小;第三行包含 个正整数 ,表示小 S 得到的排列。
如果 ,则第二行包含 个正整数 ,表示小 S 得到的排列。
如果 ,则第二行包含 个非负整数 ,表示小 S 的残缺的排列。 表示这一个值被鼠 "咬掉" 的,否则 表示排列中第 位的值。
每行中的两个整数之间均用一个空格隔开,鼠的编号是从 开始的。
输出格式
输出一行一个整数,表示对应问题的答案对 取模的结果。
3 0
10 20 30
1 2 3
3
3 1
1 2 3
2
3 2
0 0 3
5
样例 4
见附加文件中的 ex_suffix4.in
与 ex_suffix4.out
。
该组样例满足 。
样例 5
见附加文件中的 ex_suffix5.in
与 ex_suffix5.out
。
该组样例满足 。
样例 6
见附加文件中的 ex_suffix6.in
与 ex_suffix6.out
。
该组样例满足 。
数据范围与提示
对于所有的测试点,均满足 $1 \leq n \leq 5 \times 10^5; 1 \leq a_i \leq 10^9; 1 \leq p_i \leq n; 0 \leq \tilde p_i \leq n$,当 时存在至少一个 使得 。
问题类型 () | 测试点编号 | 其它性质 | |
---|---|---|---|
0 | 1 | 无 | |
2 | |||
3 | |||
1 | 4 | ||
5 | |||
6 | |||
7 | |||
8 | |||
9 | |||
10 | |||
11 | |||
12 | |||
13 | 无 | ||
14 | |||
2 | 15 | ||
16 | |||
17 | |||
18 | 满足 的 不超过 个 | ||
19 | 无 | ||
20 | 满足 的 不超过 个 | ||
21 | 无 | ||
22 | 所有 | ||
23 | 存在整数 (),满足 $\tilde p_i = \begin{cases} i & i \leq t \\ 0 & i > t \end{cases}$ | ||
24 | 存在整数 (),满足 当且仅当 | ||
25 | 无 |