P15103 [ICPC 2025 LAC] Infinite Arrays

一个数组 $B$ 的**子数组**是指从 $B$ 中取出的一段连续元素序列。例如，如果 $B = [3, 1, 4, 1, 5]$，那么 $[3, 1, 4]$、$[4, 1]$、空数组 $[]$ 和整个数组 $B$ 都是 $B$ 的子数组（还有其他子数组），而 $[3, 4, 5]$ 和 $[1, 3]$ 不是 $B$ 的子数组。 我们还定义 $C^m$ 为将数组 $C$ 连接 $m$ 份所得到的数组。例如，如果 $C = [3, 2]$，那么 $C^1 = [3, 2]$，$C^2 = [3, 2, 3, 2]$，且 $C^\infty = [\dots, 3, 2, 3, 2, 3, 2, \dots]$。 在这个问题中，你被给定一个不包含重复数字的数组 $P$，并且你需要按顺序处理一系列事件。事件可以分为三种类型： - **删除**：必须从 $P$ 中删除一个存在的数字。例如，如果 $P = [2, 3, 4]$ 且数字 $3$ 需要被删除，处理完该事件后 $P$ 将变为 $[2, 4]$。 - **插入**：必须将一个不存在于 $P$ 中的数字插入到 $P$ 中，并位于 $P$ 中某个现有数字之前。例如，如果 $P = [4, 3, 2, 1]$ 且数字 $9$ 需要插入到数字 $1$ 之前，处理完该事件后 $P$ 将变为 $[4, 3, 2, 9, 1]$。 - **查询**：必须计算 $P^\infty$ 和 $A^\infty$ 之间的最长公共子数组的长度，其中 $A$ 是查询中给出的数组。例如，如果 $P = [1, 2, 3, 4]$ 且 $A = [3, 2]$，那么 $P^\infty$ 和 $A^\infty$ 之间的最长公共子数组是 $[2, 3]$，因此查询的答案是 $2$。 你准备好迎接这个挑战了吗？

第一行包含一个整数 $N$（$1 \le N \le 5 \cdot 10^5$），表示 $P$ 的初始长度。 第二行包含 $N$ 个不同的整数 $P_1, P_2, \dots, P_N$（对于 $i = 1, 2, \dots, N$，有 $1 \le P_i \le 10^6$）。 第三行包含一个整数 $E$（$1 \le E \le 5 \cdot 10^5$），表示需要处理的事件数量。 接下来的 $E$ 行按顺序描述每个事件。每行的内容取决于事件类型，如下所示： - **删除**：该行包含字符 “-”（减号）和一个整数 $X$（$1 \le X \le 10^6$，且 $X \in P$），表示必须从 $P$ 中删除 $X$。保证删除后 $P$ 不会变为空。 - **插入**：该行包含字符 “+”（加号）和两个整数 $Y$ 和 $Z$（$1 \le Y, Z \le 10^6$，$Y \notin P$，且 $Z \in P$），表示必须将 $Y$ 插入到 $P$ 中，紧邻 $Z$ 的左侧。 - **查询**：该行包含字符 “?”（问号）、一个正整数 $K$ 以及 $K$ 个整数 $A_1, A_2, \dots, A_K$（对于 $i = 1, 2, \dots, K$，有 $1 \le A_i \le 10^6$），表示必须计算 $P^\infty$ 和 $A^\infty$ 之间的最长公共子数组的长度。保证输入中至少包含一个查询，并且所有查询的 $K$ 值之和不超过 $10^6$。

对每个查询输出一行，包含一个整数，表示 $P^\infty$ 和 $A^\infty$ 之间的最长公共子数组的长度；或者，如果最长公共子数组的长度大于 $10^{18}$，则输出字符 “*”（星号）。

翻译由 DeepSeek V3 完成