E. Жили и перестановка
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Жили и Джили любят прыгать по последовательности. Они движутся по определенному правилу и на протяжении всего процесса черпают энергию из интервала, соответствующего их текущему положению. Эту энергию они используют для восстановления логической стабильности.

Даны две перестановки$$$^{\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$$$.

Также задана последовательность $$$p$$$ неотрицательных чисел длиной $$$n$$$ в $$$0$$$-индексации. Последовательность $$$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)$$$.
  • 2 x y: Присвоить $$$p_x$$$ значение $$$y$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$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$$$ представляет собой последовательность длины $$$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$$$) — последовательность $$$q$$$.

Каждая из следующих $$$m$$$ строк содержит операцию в одном из следующих форматов:

  • 1 l r k ($$$0\le l \lt r \le n + 1, 1\le k\le n$$$) — Выведите максимальное количество последовательных единиц в $$$f((l, r), k)$$$.
  • 2 x y ($$$0 \le x \lt n$$$, $$$0 \le y \le 10^9$$$) — Присвойте $$$p_x$$$ значение $$$y$$$.

Гарантируется, что суммы $$$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}$$$