CF323C Two permutations

给定两个长度为 $n$ 的排列 $p$ 和 $q$，以及 $m$ 个询问。每个询问形如：$l_1, r_1, l_2, r_2$，其中 $l_1 \leq r_1$，$l_2 \leq r_2$。对于每个询问，回答满足以下条件的整数 $v$（$1$ 到 $n$ 之间）：该数在第一个排列中的位置在区间 $[l_1, r_1]$ 内（包含边界），且在第二个排列中的位置在区间 $[l_2, r_2]$ 内（同样包含边界）的数量。 一个长度为 $n$ 的排列是包含 $n$ 个互不相同整数的序列，每个整数都在 $1$ 到 $n$ 之间。 数 $v$（$1 \leq v \leq n$）在排列 $g_1, g_2, ..., g_n$ 中的位置是满足 $g_i = v$ 的 $i$。

第一行包含一个整数 $n\ (1 \leq n \leq 10^6)$，表示排列的长度。 第二行包含 $n$ 个用空格隔开的整数 $p_1, p_2, ..., p_n\ (1 \leq p_i \leq n)$，表示第一个排列。 第三行包含第二个排列 $q_1, q_2, ..., q_n$，格式同上。 接下来一行包含一个整数 $m\ (1 \leq m \leq 2 \cdot 10^5)$，表示询问个数。 接下来 $m$ 行，每行四个整数 $a,b,c,d\ (1 \leq a,b,c,d \leq n)$，为一次询问的描述。询问参数 $l_1, r_1, l_2, r_2$ 由下述算法得到： 1. 定义变量 $x$。如果为第一个询问，则 $x=0$，否则 $x$ 等于上一个询问的答案加 $1$。 2. 定义函数 $f(z) = ((z-1+x) \bmod n) + 1$。 3. 设 $l_1 = \min(f(a), f(b))$，$r_1 = \max(f(a), f(b))$，$l_2 = \min(f(c), f(d))$，$r_2 = \max(f(c), f(d))$。

每个询问输出一行答案。

由 ChatGPT 5 翻译