AquaMoon and Potatoes

题意翻译

### 题目描述 给你三个长度为 $n$ 的数组 $a,b,c$。 有 $m$ 次操作，每次操作为下面两种之一： + `1 k x`：将 $a_k$ 修改为 $x$。 + `2 r`：求出有多少个三元组 $(i,j,k)$，满足 $1\leq i<j<k\le r$ 且 $b_{a_i}=a_j=c_{a_k}$。 ### 输入格式 第一行两个整数 $n,m$。 接下来一行 $n$ 个数，第 $i$ 个数表示 $a_i$。 接下来一行 $n$ 个数，第 $i$ 个数表示 $b_i$。 接下来一行 $n$ 个数，第 $i$ 个数表示 $c_i$。 接下来 $m$ 行，为 $m$ 次操作。 ### 输出格式 对于每个询问操作，输出一行一个整数，表示满足条件的三元组个数。 ### 数据范围 对于所有数据，$1\leq n\leq2\times 10^5,1\leq m\leq 5\times 10^4,1\leq a_i,b_i,c_i,k,x,r\leq n$。

题目背景

# Subscribe to Technoblade

题目描述

Technoblade has three integer arrays $a$, $b$, $c$ of length $n$. We have $1 \leq a_i, b_i, c_i \leq n$ for all $i$. In order to accelerate his potato farming, he organizes his farm in a manner based on these three arrays. He is now going to complete $m$ operations to count how many potatoes he can get. Each operation will be in one of the two following forms: 1. Technoblade reorganizes his farm and makes the $k$-th element of the array $a$ equal to $x$. In other words, perform the assignment $a_k := x$. 2. Given a positive integer $r$, Technoblade receives a potato for each triplet $(i,j,k)$, such that $1\le i<j<k\le r$, and $b_{a_i}=a_j=c_{a_k}$. Count the number of potatoes that he receives; that is, the number of such triplets. Help Technoblade complete these operations.

输入输出格式

输入格式

The first line contains two integers $ n $ , $ m $ ( $ 1\le n\le 2\cdot10^5 $ , $ 1\le m\le 5\cdot10^4 $ ). The second line contains $ n $ integers $ a_1, a_2, \dots,a_n $ ( $ 1\le a_i\le n $ ). The third line contains $ n $ integers $ b_1, b_2, \dots,b_n $ ( $ 1\le b_i\le n $ ). The fourth line contains $ n $ integers $ c_1, c_2, \dots,c_n $ ( $ 1\le c_i\le n $ ). The next $ m $ lines describe operations, the $ i $ -th line describes the $ i $ -th operation in one of these two formats: - " $ 1\ k\ x $ " ( $ 1\le k,x\le n $ ), representing an operation of the first type. - " $ 2\ r $ " ( $ 1\le r\le n $ ), representing an operation of the second type. It is guaranteed that there is at least one operation of the second type.

输出格式

For each operation of the second type print the answer.

输入输出样例

输入样例 #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

说明

For the first operation, the triplets are: - $ i=1 $ , $ j=2 $ , $ k=3 $ - $ i=2 $ , $ j=3 $ , $ k=4 $ - $ i=3 $ , $ j=4 $ , $ k=5 $ There is no satisfying triplet for the third operation. For the fourth operation, the triplets are: - $ i=2 $ , $ j=4 $ , $ k=5 $ - $ i=3 $ , $ j=4 $ , $ k=5 $