出一道有趣的题目

普通版

1. 定义

1.1 位置与双出现模式

• 位置：对长度为 $n$ 的序列，用 $i\in[1,n]$ 表示下标。
• 双出现模式：长度为偶数 $n$，记 $m=n/2$。序列 $A=(A_1,\dots,A_n)$ 满足：对每个 $k\in\{1,\dots,m\}$，在 $A$ 中恰好出现两次。 对每个 $k$，记两次出现位置为 $L_k<R_k$，并记开区间 $(L_k,R_k)$。

1.2 规范翻译为置换

给定一个双出现模式 $A$，按下述唯一规则生成置换 $p$（即 $p$ 为 $\{1,\dots,n\}$ 的某个排列）：

按 $k=1,2,\dots,m$ 的递增顺序处理每个位置对 $(L_k,R_k)$。在处理 $k$ 时：

• 若 $s_k$ 为偶数，则令 $p_{L_k}=2k-1,\ p_{R_k}=2k$；
• 若 $s_k$ 为奇数，则令 $p_{L_k}=2k,\ \ p_{R_k}=2k-1$。

处理结束后得到的 $p$ 确定且唯一。

直观记忆：每个 $k$ 对应一对连续数 $(2k-1,2k)$，按其区间内“已赋值个数”的奇偶决定左右顺序。

2. 任务

你将同时拿到 $m_{\text{pat}}$ 个双出现模式（长度均为同一个 $n$），并需要回答 $q$ 个查询。每个查询属于以下两类之一：

• 类型 1（取值）：给定模式编号 $z$ 与位置 $i$，输出该模式经规范翻译所得置换 $p^{(z)}$ 的第 $i$ 项 $p^{(z)}_i$。

• 类型 2（最早强分离）：给定两个模式编号 $u,v$，设它们对应的置换分别为 $p^{(u)},p^{(v)}$。找出最小的位置 $c$，满足

  $$\bigl|\,p^{(u)}_c - p^{(v)}_c\,\bigr|\ \ge\ 2.$$

  若两个模式完全相同，从而不存在这样的 $c$，则输出 $-1$。

注：“强分离”指同列数值差至少 2；该性质在本规则下总是可检测的。

3. 输入与输出

输入

• 第一行：三个整数 $n,m_{\text{pat}},q$（$n$ 为偶数）。

• 接下来 $m_{\text{pat}}$ 行：第 $z$ 行给出一个长度为 $n$ 的双出现模式 $A^{(z)}$（每行单独合法：每个 $k\in[1,n/2]$ 恰出现两次）。

• 接下来 $q$ 行：每行一个查询：

  • 形如 1 z i：类型 1 查询（模式 $z$、位置 $i$）。
  • 形如 2 u v：类型 2 查询（比较模式 $u,v$）。

输出

• 对每个查询输出一行：

  • 类型 1：输出一个整数 $p^{(z)}_i$。

  • 类型 2：若存在强分离位置，输出三个整数

    $$c\ \ p^{(u)}_c\ \ p^{(v)}_c$$

    其中 $c$ 是最小满足条件的位置；若不存在，输出 $-1$。

4. 约束

• $2\le n\le 2\times 10^5$，$n$ 为偶数。
• $1\le m_{\text{pat}},q\le 2\times 10^5$。
• 总规模限制：读取所有模式的元素总数不超过给定上限（例如 $\sum n \le 10^6$）。
• 输入保证每个模式各自合法（每个值 $k$ 恰两次）。
• 评测为单组数据；建议实现目标：时间 1s / 内存 $\le 1$GB。

5. 样例

输入

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

解释与可能输出

• 模式 1 的规范置换为 1 4 2 6 3 5
• 模式 2 的规范置换为 1 6 4 2 3 5
• 模式 3 的规范置换为 1 4 6 2 5 3

对应查询输出：

2
2
2 4 6
3 2 6
2 6 4

进阶

1. 定义

1.1 双出现模式与规范翻译（回顾）

与普通版一致。对每个模式 $A$ 先做 1.2 的规范翻译，得到置换的结构编码：

• $J_i \in [1,m]$：位置 $i$ 属于哪一个“对号” $k$（即 $A_i$ 的标签）；
• $S_i \in \{0,1\}$：该位置在其对内取小值(0)还是大值(1)； 并有基准置换

1.2 偏置翻译

对每个模式引入一个可变偏置数组 $B=(B_1,\dots,B_m)\in\{0,1\}^m$，初始全为 0。 当前（受偏置后的）置换定义为

含义：当且仅当 $B_k=1$ 时，对号 $k$ 的两格 $(2k-1,2k)$ 在当前状态中被整体翻转。

1.3 强分离（回顾）

给定两个置换 $p^{(u)},p^{(v)}$，称位置 $c$ 强分离，若

若对所有 $c$ 都不成立，则称二者无强分离。

等价表述（判定帮助）：记 $\Pi^{(z)}_i$ $=$ $(J^{(z)}_i,$ $S^{(z)}_i$ $\oplus$ $B^{(z)}_{J^{(z)}_i})$。 两模式在列 $i$ 不强分离 当且仅当满足其一：

1. $J^{(u)}_i=J^{(v)}_i$ 且第二分量相等（同号同位 → 数值相等）；
2. $|J^{(u)}_i-J^{(v)}_i|=1$ 且二者第二分量恰为 $(1,0)$ 或 $(0,1)$（相邻号、形成相邻整数）。 否则为强分离。

2. 任务

你拿到 $m_{\text{pat}}$ 个双出现模式 $A^{(1)},\dots,A^{(m_{\text{pat}})}$（长度均为同一个 $n$，令 $m=n/2$）。 对每个模式先求 $(J^{(z)},S^{(z)})$，并维护可变偏置 $B^{(z)}$。需要在线处理 $q$ 个操作：

1. 取值

1  z  i

输出当前 $p^{(z)}_i$。

2. 最早强分离

2  u  v  l  r

在区间 $[l,r]$ 内找最小 $c$，使 $\bigl|p^{(u)}_c-p^{(v)}_c\bigr|\ge 2$。若不存在输出 -1。

3. 偏置区间翻转

3  z  a  b

对所有对号 $k\in[a,b]$ 执行 $B^{(z)}_k \gets B^{(z)}_k \oplus 1$。

3. 输入输出

输入

• 第一行：三个整数 $n,m_{\text{pat}},q$（$n$ 为偶数）。
• 接下来 $m_{\text{pat}}$ 行：第 $z$ 行给出模式 $A^{(z)}$ 的 $n$ 个整数（双出现合法）。
• 接下来 $q$ 行：每行一个操作，格式如上三类之一。

输出

• 类型 1：输出一行当前的 $p^{(z)}_i$。

• 类型 2：若存在强分离位置，输出

  $$c\ \ p^{(u)}_c\ \ p^{(v)}_c$$

  为最小满足位置及两值；否则输出 $-1$。

• 类型 3：无输出。

4. 约束

• $2\le n\le 2\times 10^5$，$n$ 为偶数，记 $m=n/2$。
• $1\le m_{\text{pat}},q\le 2\times 10^5$。
• 总规模限制：$m_{\text{pat}}\cdot n \le 10^6$。
• 输入保证每个模式各自合法。
• 单组数据；建议目标：时间 2s / 内存 $\le 1$GB。

5. 样例

输入

6 3 8
1 2 1 3 2 3
1 3 2 1 2 3
1 2 3 1 3 2
1 1 3
2 1 2 1 6
3 2 1 2
2 1 2 1 6
1 2 4
3 1 1 1
2 1 3 2 6
2 2 3 1 3

一种可能输出

3
2 4 6
2 6 4
2
3 2 6
2 6 4

（注：偏置区间翻转会改变后续查询的列内左右次序，样例仅示交互效果。）

6. 判定等价（便于实现）

将每列视作二元对 $\Pi^{(z)}_i$ $=$ $(J^{(z)}_i,$ $S^{(z)}_i$ $\oplus$ $B^{(z)}_{J^{(z)}_i})$。

• 不强分离 $\Leftrightarrow$ (i) 同号且同位；或 (ii) 号相邻且位为 $(1,0)$ 或 $(0,1)$。
• 其余情形为强分离。类型 2 查询就是在 $[l,r]$ 内寻找首个使上述判定不成立的列。