CF2223E.Zhily and Permutation

Zhily and Jily enjoy jumping around on a sequence. They move according to some rule, and throughout the process, they draw energy from the interval corresponding to their current positions. They use this energy to restore logical stability.

You are given two permutations$^{\text{∗}}$ $a$ and $b$ of length $n$.

For any open interval $I = (l, r)$ where $0 \le l \lt r \le n+1$ and $l + 1 \lt r$ holds, we define $\operatorname{next}(I) = (\min(i, j), \max(i,j))$, where

• $i = \operatorname*{argmax}\limits_{k \in (l, r)} a_k$$^{\text{†}}$;
• $j = \operatorname*{argmax}\limits_{k \in (l, r)} b_k$.

You are also given a $0$-indexed non-negative sequence $p$ of length $n$. The sequence $g(I)$ is defined as $g(I) = \begin{cases} [0] & (p_l = 0) \\ [1]^{p_l} & (p_l \gt 0) \end{cases}$$^{\text{‡}}$.

The sequence $f(I, k)$ is defined as $f(I, k) = \begin{cases} [~] & \text{if } k=0 \text{ or } l+1\ge r \\ g(I) + f(\operatorname{next}(I), k-1) & \text{otherwise} \end{cases}$$^{\text{§}}$.

You need to perform $m$ operations:

• 1 l r k: Output the maximum number of consecutive $1$s in $f((l, r), k)$.
• 2 x y: Assign $y$ to $p_x$.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

$^{\text{†}}$$\operatorname*{argmax}\limits_{k \in (l, r)}$ $a_k$ denotes the unique index $k$ ($l \lt k \lt r$) such that $a_k = \max\limits_{x \in (l, r)} a_x$.

$^{\text{‡}}$Here, $[1]^m$ represents a sequence of length $m$ consisting of all $1$s.

$^{\text{§}}$Here, $[~]$ represents the empty sequence, and the operator $+$ between two sequences indicates their concatenation.

芝莉和吉莉喜欢在一个序列上跳跃。她们根据某种规则移动，在整个过程中，她们从当前所在位置对应的区间中汲取能量。她们利用这些能量来恢复逻辑稳定性。

给定两个长度为 $n$ 的排列$^{\text{∗}}$ $a$ 和 $b$。

对于任意开区间 $I = (l, r)$，其中 $0 \le l \lt r \le n+1$ 且满足 $l + 1 \lt r$，我们定义 $\operatorname{next}(I) = (\min(i, j), \max(i,j))$，其中

• $i = \operatorname*{argmax}\limits_{k \in (l, r)} a_k$$^{\text{†}}$；
• $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 \gt 0) \end{cases}$$^{\text{‡}}$。

序列 $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}$$^{\text{§}}$。

你需要执行 $m$ 次操作：

• 1 l r k：输出 $f((l, r), k)$ 中最长连续 $1$ 的个数。
• 2 x y：将 $p_x$ 赋值为 $y$。

$^{\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$ 表示唯一满足 $l \lt k \lt r$ 且 $a_k = \max\limits_{x \in (l, r)} a_x$ 的下标 $k$。

$^{\text{‡}}$ 这里，$[1]^m$ 表示一个长度为 $m$、全部由 $1$ 组成的序列。

$^{\text{§}}$ 这里，$[~]$ 表示空序列，而两个序列之间的运算符 $+$ 表示它们的拼接（连接）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the length of the permutations and the number of operations.

The second line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the permutation $a$.

The third line contains $n$ distinct integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$) — the permutation $b$.

The fourth line contains $n$ integers $p_0, p_1, \ldots, p_{n - 1}$ ($0 \le p_i \le 10^9$) — the sequence $p$.

Each of the next $m$ lines contains an operation in one of the following formats:

• 1 l r k ($0\le l \lt r \le n + 1, 1\le k\le n$) — Output the maximum number of consecutive $1$s in $f((l, r), k)$.
• 2 x y ($0 \le x \lt n$, $0 \le y \le 10^9$) — Assign $y$ to $p_x$.

It is guaranteed that the sums of $n$ and $m$ over all test cases do not exceed $4 \cdot 10^5$, respectively.

每个测试包含多个测试用例。第一行包含测试用例数量 $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$（$1 \le b_i \le 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 \lt r \le n + 1$, $1\le k\le n$）—— 输出 $f((l, r), k)$ 中连续 1 的最大个数。
• 2 x y（$0 \le x \lt n$, $0 \le y \le 10^9$）—— 将 $p_x$ 赋值为 $y$。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和分别不超过 $4 \cdot 10^5$。

For each operation of type $1$, output the answer in one line.

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

In the first test case:

• $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}$

In the second test case:

• $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}$

在第一个测试用例中：

• $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}$