Zily 和 Jily 喜欢在序列中跳跃。它们按照某种规则移动,在整个过程中,它们从当前位置对应的区间中汲取能量。他们利用这种能量来恢复逻辑稳定性。
给你两个排列$$$^{\text{*}}$$$ $$$a$$$ 和 $$$b$$$,长度为$$$n$$$。
对于任何 打开 区间 $$$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$$$。
您还将获得一个 $$$0$$$ 索引的非负序列 $$$p$$$,长度为 $$$n$$$。序列 $$$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{if } k=0 \text{ or } l+1\ge r \\ g(I) + f(\operatorname{next}(I), k-1) & \text{otherwise} \end{案例}$$$$$$^{\text{§}}$$$。
您需要执行$$$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 \lt k \lt r$$$) 使得 $$$a_k = \max\limits_{x \in (l, r)} a_x$$$。
$$$^{\text{‡}}$$$这里,$$$[1]^m$$$表示由所有$$$1$$$组成的长度为$$$m$$$的序列。
$$$^{\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$$$ ($$$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$$$) — 将 $$$y$$$ 分配给 $$$p_x$$$。
保证所有测试用例的 $$$n$$$ 和 $$$m$$$ 之和不分别超过 $$$4 \cdot 10^5$$$。
输出
对于 $$$1$$$ 类型的每个操作,在一行中输出答案。
示例
输入复制
35 43 4 1 5 22 3 5 1 42 3 2 5 31 0 4 11 1 4 21 3 6 11 0 6 25 43 5 1 2 41 4 3 2 50 2 0 3 01 2 5 11 4 6 21 0 5 11 3 5 210 3010 1 7 3 2 8 4 9 6 51 7 3 2 8 9 5 4 10 64 0 6 3 0 2 1 5 2 41 10 11 101 10 11 31 4 11 101 10 11 91 1 4 102 4 51 0 7 41 9 10 42 6 31 5 7 61 6 7 91 2 7 41 4 7 21 1 2 11 5 7 82 0 31 2 7 51 7 10 61 6 8 71 3 4 31 8 9 92 4 51 1 4 41 0 9 42 1 21 6 11 101 5 9 101 2 4 71 1 11 11 2 11 3
输出复制
235200030000040206502653000335626
注意
在第一个测试用例中:
- $$$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}$$$