CF2223E Zhily and Permutation

Zhily 和 Jily 喜欢在一个数列上跳来跳去。他们根据某种规则移动，在整个过程中，他们会从当前所在区间汲取能量。这些能量用于恢复逻辑稳定性。 给定长度为 $n$ 的两个排列 $a$ 和 $b$。 对于任意开区间 $I = (l, r)$，其中 $0 \le l < r \le n+1$ 并且 $l + 1 < r$，我们定义 $\operatorname{next}(I) = (\min(i, j), \max(i, j))$，其中 - $i = \operatorname*{argmax}\limits_{k \in (l, r)} a_k$； - $j = \operatorname*{argmax}\limits_{k \in (l, r)} b_k$。 还给定了一个长度为 $n$ 的 $0$ 下标、非负整数序列 $p$。定义序列 $g(I)$ 为 $g(I) = \begin{cases} [0] & (p_l = 0) \\ [1]^{p_l} & (p_l > 0) \end{cases}$。 再定义序列 $f(I, k)$ 为 $f(I, k) = \begin{cases} [~] & \text{若 } k=0 \text{ 或 } l+1\ge r \\ g(I) + f(\operatorname{next}(I), k-1) & \text{否则} \end{cases}$。 你需要执行 $m$ 个操作： - 1 l r k：输出 $f((l, r), k)$ 中最大连续 $1$ 的数量。 - 2 x y：将 $y$ 赋值给 $p_x$。 $ ^{\text{∗}} $ 一个长度为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个不同整数组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 在数组中出现两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中有 $4$）。 $ ^{\text{†}} $ $\operatorname*{argmax}\limits_{k \in (l, r)} a_k$ 表示唯一的下标 $k$（$l < k < r$），使得 $a_k = \max\limits_{x \in (l, r)} a_x$。 $ ^{\text{‡}} $ 这里，$[1]^m$ 表示长度为 $m$ 的全 $1$ 序列。 $ ^{\text{§}} $ 这里，$[~]$ 表示空序列，两个序列的 $+$ 表示按顺序拼接。

每组测试包含多组数据。第一行包含测试组数 $t$（$1 \le t \le 10^4$）。接下来是各组测试数据。 每组数据第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5$），分别表示排列的长度和操作数。 第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示排列 $a$。 第三行包含 $n$ 个互不相同的整数 $b_1, b_2, \ldots, b_n$，表示排列 $b$。 第四行包含 $n$ 个整数 $p_0, p_1, \ldots, p_{n-1}$（$0 \le p_i \le 10^9$），表示序列 $p$。 接下来 $m$ 行每行描述一次操作，格式如下： - 1 l r k（$0 \le l < r \le n+1, 1 \le k \le n$）：输出 $f((l, r), k)$ 中最大连续 $1$ 的数量。 - 2 x y（$0 \le x < n$，$0 \le y \le 10^9$）：将 $y$ 赋值给 $p_x$。 保证所有测试组中 $n$ 与 $m$ 的总和分别不超过 $4 \cdot 10^5$。

对于每个操作类型为 $1$ 的操作，输出一行答案。

在第一组测试中： - $f((0,4),1) = g(0,4) + f((2,3),0) = [1,1] + [~] \to \mathbf{2}$ - $f((1,4),2) = g(1,4) + f((2,3),1) = [1,1,1] + [~] \to \mathbf{3}$ - $f((3,6),1) = g(3,6) + f((4,5),0) = [1,1,1,1,1] + [~] \to \mathbf{5}$ - $f((0,6),2) = g(0,6) + f((3,4),1) = [1,1] + [~] \to \mathbf{2}$ 在第二组测试中： - $f((2,5),1) = g(2,5) + f((3,4),0) = [0] + [~] \to \mathbf{0}$ - $f((4,6),2) = g(4,6) + f((5,5),1) = [0] + [~] \to \mathbf{0}$ - $f((0,5),1) = g(0,5) + f((2,2),0) = [0] + [~] \to \mathbf{0}$ - $f((3,5),2) = g(3,5) + f((4,4),1) = [1,1,1] + [~] \to \mathbf{3}$ 由 ChatGPT 5 翻译