← 返回题目列表

Codeforces · 2223/E

E. 直和排列

中文机器翻译题面 查看原题

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$$$ 类型的每个操作,在一行中输出答案。

示例

输入
复制

3
5 4
3 4 1 5 2
2 3 5 1 4
2 3 2 5 3
1 0 4 1
1 1 4 2
1 3 6 1
1 0 6 2
5 4
3 5 1 2 4
1 4 3 2 5
0 2 0 3 0
1 2 5 1
1 4 6 2
1 0 5 1
1 3 5 2
10 30
10 1 7 3 2 8 4 9 6 5
1 7 3 2 8 9 5 4 10 6
4 0 6 3 0 2 1 5 2 4
1 10 11 10
1 10 11 3
1 4 11 10
1 10 11 9
1 1 4 10
2 4 5
1 0 7 4
1 9 10 4
2 6 3
1 5 7 6
1 6 7 9
1 2 7 4
1 4 7 2
1 1 2 1
1 5 7 8
2 0 3
1 2 7 5
1 7 10 6
1 6 8 7
1 3 4 3
1 8 9 9
2 4 5
1 1 4 4
1 0 9 4
2 1 2
1 6 11 10
1 5 9 10
1 2 4 7
1 1 11 1
1 2 11 3

输出
复制

2
3
5
2
0
0
0
3
0
0
0
0
0
4
0
2
0
6
5
0
2
6
5
3
0
0
0
3
3
5
6
2
6

注意

在第一个测试用例中:

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