← 返回题目列表

Codeforces · 1545/F

F. AquaMoon 和土豆

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

AquaMoon 有三个整数数组 $$$a$$$、$$$b$$$、$$$c$$$,长度为 $$$n$$$,其中 $$$1 \leq a_i、b_i、c_i \leq n$$$ 代表所有 $$$i$$$。

为了加速她的马铃薯种植,她按照这三个数组的方式组织她的农场。她现在将完成 $$$m$$$ 操作来计算她可以获得多少个土豆。每个操作都有以下两种类型之一:

1. AquaMoon 重新组织他们的农场,并使数组 $$$a$$$ 的第 $$$k$$$ 元素等于 $$$x$$$。换句话说,执行赋值 $$$a_k := x$$$。
2. 给定一个正整数 $$$r$$$,AquaMoon 会为每个三元组 $$$(i,j,k)$$$ 接收一个土豆,使得 $$$1\le i<j<k\le r$$$,并且 $$$b_{a_i}=a_j=c_{a_k}$$$。计算这样的三元组的数量。

由于AquaMoon正忙于寻找图书馆,请帮助她完成所有操作。

输入

第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$1\le n\le 2\cdot10^5$$$、$$$1\le m\le 5\cdot10^4$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots,a_n$$$ ($$$1\le a_i\le n$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots,b_n$$$ ($$$1\le b_i\le n$$$)。

第四行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots,c_n$$$ ($$$1\le c_i\le n$$$)。

接下来的 $$$m$$$ 行描述操作,第 $$$i$$$ 行以以下两种格式之一描述第 $$$i$$$ 操作:

- "$$$1\ k\ x$$$" ($$$1\le k,x\le n$$$),表示第一类操作。
- "$$$2\ r$$$" ($$$1\le r\le n$$$),表示第二类操作。

保证至少有一个第二类型的操作。

输出

对于第二种类型的每个操作,打印答案。

示例

输入 #1

5 4
1 2 3 4 5
2 3 4 5 1
5 1 2 3 4
2 5
1 2 3
2 4
2 5

输出 #1

3
0
2

注意

对于第一个操作,三元组是:

- $$$i=1$$$, $$$j=2$$$, $$$k=3$$$
- $$$i=2$$$, $$$j=3$$$, $$$k=4$$$
- $$$i=3$$$, $$$j=4$$$, $$$k=5$$$

第三次操作没有令人满意的三元组。

对于第四个操作,三元组是:

- $$$i=2$$$, $$$j=4$$$, $$$k=5$$$
- $$$i=3$$$, $$$j=4$$$, $$$k=5$$$