loj#P6780. 「2021 营员交流」数串

「2021 营员交流」数串

题目背景

小 F 喜欢字符串。

小 S 喜欢后缀数组。

nn 只鼠,它们被绳子依次串起来,顺次排成一排。每只鼠有一个体型大小 aia_i。小 F 定义一个后缀为从某一只鼠开始,到最后一只鼠构成的序列。

对于两个鼠的序列 σ,π\sigma, \pi,我们称 σ<π\sigma < \pi 当且仅当存在一个位置 ii,满足 σ\sigmaπ\pi 中前 i1i - 1 只鼠的体型大小对应相同,且 σ\sigma 的第 ii 只鼠不存在或者比 π\pi 的第 ii 只鼠小。

小 S 给予了这些鼠一个排列 $\boldsymbol p = \left[ p_1, p_2, \ldots, p_n \right]$,满足对于 i<j\forall i < j,从第 ii 只鼠开始的后缀小于从第 jj 只鼠开始的后缀。

小 F 观察了这一列鼠后,发现它们中有非常多的鼠具有相同的体型大小。于是,她问小 S:这列鼠有多少种不同的大小呢?

鼠在不停地挣扎,想要挣脱绳子的束缚。小 S 还没有看清这些鼠的大小,鼠便把绳子都咬断了,开始四处乱窜。

小 S 有些气恼,但是她还是想要知道答案。她带着已经得到的排列问小 F:对于所有满足 “给予它的排列为 p\boldsymbol p 的” 鼠的序列,答案 (鼠的大小的种类数) 的最小值可以是多少?

鼠在不停地挣扎,想要逃离这阴暗的房间。小 S 还没有计算出来,鼠便把小 S 得到的排列中的若干数字也咬掉了,带着碎片纷纷逃离房间。

小 S 有些气恼,但是她还是想要知道答案。她带着那残缺的排列问小 F:对于剩下的数的所有 k!k! 种排列方案 (kk 为被鼠咬掉的数的数量),答案 (鼠的大小的种类数的最小值) 的总和是多少?

小 S 哭了。

题目描述

本题包含三个问题:

  • 问题 0:给定一个长度为 nn 的序列以及它的后缀数组 p\boldsymbol p,求这个序列中有多少个不同的数。
  • 问题 1:给定一个长度为 nn 的排列 p\boldsymbol p,对于所有满足后缀数组为 p\boldsymbol p 的长度为 nn 的序列,求不同的数的数量的最小值
  • 问题 2:给定一个长度为 nn残缺的排列 p~\tilde {\boldsymbol p} (有 kk 个位置未知),对于所有 k!k! 种完整的排列,求问题 1 的答案之和

在不同的测试点中,你将可能需要回答不同的问题。我们将用 op\mathrm{op} 来指代你需要回答的问题编号 (对应上述 0,1,20, 1, 2)。

在问题 2 中,由于答案可能很大,因此你只需要输出答案对 998244353998244353 取模的结果即可。

输入格式

第一行包含两个非负整数 n,opn, \mathrm{op},分别表示鼠的数量和子问题的类型。

如果 op=0\mathrm{op} = 0,则第二行包含 nn 个正整数 a1,a2,,ana_1, a_2, \ldots, a_n,表示每只鼠的体型大小;第三行包含 nn 个正整数 p1,p2,,pnp_1, p_2, \cdots, p_n,表示小 S 得到的排列。

如果 op=1\mathrm{op} = 1,则第二行包含 nn 个正整数 p1,p2,,pnp_1, p_2, \ldots, p_n,表示小 S 得到的排列。

如果 op=2\mathrm{op} = 2,则第二行包含 nn 个非负整数 p~1,p~2,,p~n\tilde p_1, \tilde p_2, \ldots, \tilde p_n,表示小 S 的残缺的排列。p~i=0\tilde p_i = 0 表示这一个值被鼠 "咬掉" 的,否则 p~i\tilde p_i 表示排列中第 ii 位的值。

每行中的两个整数之间均用一个空格隔开,鼠的编号是从 11 开始的。

输出格式

输出一行一个整数,表示对应问题的答案对 998244353998244353 取模的结果。

3 0
10 20 30
1 2 3

3

3 1
1 2 3

2

3 2
0 0 3

5

样例 4

见附加文件中的 ex_suffix4.inex_suffix4.out

该组样例满足 op=0\mathrm{op} = 0

样例 5

见附加文件中的 ex_suffix5.inex_suffix5.out

该组样例满足 op=1\mathrm{op} = 1

样例 6

见附加文件中的 ex_suffix6.inex_suffix6.out

该组样例满足 op=2\mathrm{op} = 2

数据范围与提示

对于所有的测试点,均满足 $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$,当 op=2\mathrm{op} = 2 时存在至少一个 ii 使得 p~i=0\tilde p_i = 0

问题类型 (op=\mathrm{op} =) 测试点编号 nn 其它性质
0 1 10\leq 10
2 5×105\leq 5 \times 10^5
3
1 4 =3= 3
5 =5= 5
6 10\leq 10
7 500\leq 500
8 5000\leq 5000
9
10 50000\leq 50000
11
12 5×105\leq 5 \times 10^5 pi=ip_i = i
13
14
2 15 =3= 3
16 =5= 5
17 10\leq 10
18 500\leq 500 满足 p~i=0\tilde p_i = 0ii 不超过 55
19 5000\leq 5000
20 满足 p~i=0\tilde p_i = 0ii 不超过 55
21 50000\leq 50000
22 所有 p~i=0\tilde p_i = 0
23 5×105\leq 5 \times 10^5 存在整数 tt (1t<n1 \leq t < n),满足 $\tilde p_i = \begin{cases} i & i \leq t \\ 0 & i > t \end{cases}$
24 存在整数 tt (1t<n1 \leq t < n),满足 p~i=0\tilde p_i = 0 当且仅当 i>ti > t
25