{"problem":{"name":"「DTOI-5」进行一个排的重 (Maximum Version)","description":{"content":"小 L 有一个长为 $n$ 的序列 $a$，其中每一项 $a_i$ 都是一个 pair $(p_i, q_i)$。 为了让 $a$ 看起来规整一些，他钦定 $p, q$ 分别均为长为 $n$ 的排列。 为了对 $a$ 的规整程度进行量化计算，他给出了一个权值函数 $f(a) = \\displaystyle\\sum_{i = 1}^n ([p_i > \\max_{j = 1}^{i - 1} p","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":819200},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9307"},"statements":[{"statement_type":"Markdown","content":"小 L 有一个长为 $n$ 的序列 $a$，其中每一项 $a_i$ 都是一个 pair $(p_i, q_i)$。\n\n为了让 $a$ 看起来规整一些，他钦定 $p, q$ 分别均为长为 $n$ 的排列。\n\n为了对 $a$ 的规整程度进行量化计算，他给出了一个权值函数 $f(a) = \\displaystyle\\sum_{i = 1}^n ([p_i > \\max_{j = 1}^{i - 1} p_j] + [q_i > \\max_{j = 1}^{i - 1} q_j])$。**注意 $i = 1$ 时两个方括号都能取到值，因为我们认为 $\\displaystyle\\max_{j = 1}^0 p_j = \\displaystyle\\max_{j = 1}^0 q_j = -\\infty$。**\n\n为了让 $a$ 看起来更加规整，他决定分别以某种方式重排 $a$ 得到 $a'$ 使得 $f(a')$ 最大。**注意重排时必须将 $a'_i = (p'_i, q'_i)$ 视为整体。**\n\n他希望你求出 $f(a')_{\\max}$ 的值，以及分别有多少个 $a'$ 可以取到 $f(a')_{\\max}$。\n\n由于方案数可能很大，你只需要求出结果对 $998244353$ 取模的值。\n\n## Input\n\n第一行，一个整数 $n$；\n\n第二行，$n$ 个整数 $p_1, p_2, \\cdots, p_n$；\n\n第三行，$n$ 个整数 $q_1, q_2, \\cdots, q_n$。\n\n## Output\n\n一行，两个整数，表示所求的值。\n\n[samples]\n\n## Background\n\n**本题与 Minimum Version 的区别是所求最值和数据范围不同。**\n\n小 L 热衷于重排数列使之规整。\n\n## Note\n\n**【数据范围】**\n\n$$\n\\def\\or{\\operatorname{or}}\n%\\def\\arrayscretch{1.5}\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|}\\hline\n\\textbf{Subtask}&n\\le &\\textbf{Points}\\cr\\hline\n\\sf1&10&10 \\operatorname{pts}\\cr\\hline\n\\sf2&50&20 \\operatorname{pts}\\cr\\hline\n\\sf3&500&20 \\operatorname{pts}\\cr\\hline\n\\sf4&2\\times 10^3&20 \\operatorname{pts}\\cr\\hline\n\\sf5&/&30 \\operatorname{pts}\\cr\\hline\n\\end{array}\n$$\n对于 $100\\%$ 的数据，$1 \\leq n \\leq 10^4$，$1 \\leq p_i, q_i \\leq n$，保证 $p, q$ 均为**排列**。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9307","tags":["动态规划 DP","2023","洛谷原创","O2优化","排列组合","前缀和","构造"],"sample_group":[["5\n1 5 2 4 3\n1 4 2 5 3","9 2"]],"created_at":"2026-03-03 11:09:25"}}