[AdditionalFile5216.zip](file://AdditionalFile5216.zip?type=additional_file)

#5216. 「UOI 2024 Stage 4 Day2」英雄与怪物

标签: 传统 | 时间限制: 1500 ms | 内存限制: 1024 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2024 Stage 4 Day2 T3. Герої та Монстри

有 $n$ 名英雄和 $n$ 只怪物，英雄和怪物分别编号为从 $1$ 到 $n$ 的整数。第 $i$ 名英雄的力量为 $a_i$，第 $i$ 只怪物的力量为 $b_i$。保证所有值 $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$ 两两不同。

总共将进行 $n$ 场战斗。每场战斗中恰好有一名英雄和一只怪物参与，且每名英雄和每只怪物都恰好参与一场战斗。假设战斗中参与的英雄编号为 $i$，怪物编号为 $j$，如果 $a_i > b_j$，则编号为 $i$ 的英雄会感到高兴；否则，他会感到沮丧。

我们定义英雄集合 $S$ 是独特的，当且仅当存在一种战斗分配方式，使得集合 $S$ 中的所有英雄都感到高兴，而其他英雄都感到沮丧。记 $ans_k$ 为大小为 $k$ 的独特英雄集合 $S$ 的种类数。

给定 $q$ 个查询，每个查询形式为 $l, r$。对于每个查询，计算 $\left(\sum\limits_{i=l}^{r} ans_i\right) \bmod 998244353$。

输入格式

输入的第一行包含一个整数 $n$ $(1 \leq n \leq 5 \cdot 10^3)$，表示战斗的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 2 \cdot n)$，表示英雄的力量。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$ $(1 \leq b_i \leq 2 \cdot n)$，表示怪物的力量。

保证所有值 $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$ 两两不同。

第四行包含一个整数 $q$ $(1 \leq q \leq n+1)$，表示查询的数量。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$ $(0 \leq l \leq r \leq n)$，表示对应查询的参数。

输出格式

对于每个查询，单独输出一行一个整数，表示所求值 $\left(\sum\limits_{i=l}^{r} ans_i\right) \bmod 998244353$。

样例 1

输入

3
3 4 6
1 2 5
3
1 2
2 3
3 3

输出

2
3
1

在第一个样例中，英雄和怪物的力量如下图所示。英雄在上方，怪物在下方，方框内的数字表示对应英雄或怪物的力量。

在样例中，存在三种可能的快乐英雄集合：$\{1, 2, 3\}$、$\{2, 3\}$ 和 $\{1, 3\}$。以下是三种战斗分配方式，分别使对应的英雄集合感到快乐。注意，对于同一个英雄集合，可能存在多种战斗分配方式使其快乐。

数据范围与提示

详细子任务附加限制及分值如下表所示：