AquaMoon and Potatoes
Contest: Codeforces Round 732 (Div. 1)
Difficulty rating: 3500
Tags: brute force, data structures, dp

AquaMoon has three integer arrays $$$a$$$, $$$b$$$, $$$c$$$ of length $$$n$$$, where $$$1 \leq a_i, b_i, c_i \leq n$$$ for all $$$i$$$.

In order to accelerate her potato farming, she organizes her farm in a manner based on these three arrays. She is now going to complete $$$m$$$ operations to count how many potatoes she can get. Each operation will have one of the two types:

1. AquaMoon reorganizes their 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$$$, AquaMoon 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 such triplets.

As AquaMoon is busy finding the library, help her complete all of their operations.

Input format:
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.

Output format:
For each operation of the second type print the answer.

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

Note:
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$$$

Example input:
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

Example output:
3
0
2

Editorial:
We seek a solution of roughly square root time complexity; the small constraint of $$$m$$$ hints at a solution in $$$O(m\sqrt n)$$$. This immediately rules out solutions based on square root decomposition on sequences, because of the overhead incurred with initializing such structures.
Instead of directly solving the problem, let us solve the following - equivalent - task: How can we solve $$$O(\sqrt n)$$$ queries in $$$O(n)$$$ time?
If we only consider $$$O(\sqrt n)$$$ queries, then there are at most $$$O(\sqrt n)$$$ positions that are modified throughout these queries. Call these positions "dynamic points", and the others "static points".
A note concerning notation: The following editorial was written when $$$X$$$ and $$$Y$$$ were permutations, and as such it uses $$$X^{-1}_i$$$ to denote the value $$$j$$$ such that $$$X_j=i$$$. It was later found that the solution can be easily modified to accomodate for $$$X$$$ and $$$Y$$$ that were not permutations. You can regard $$$X^{-1}_i$$$ as the set of $$$j$$$ such that $$$X_j=i$$$. In the following, we often count the number of dynamic or static elements in a prefix that equals a certain value. The number of elements in a multiset that equal $$$X^{-1}_i$$$ is the same as the number of elements in said multiset that satisfy $$$X_j=i$$$. In implementation, we can maintain the multiset $$$\{X_j:j\in\dots\}$$$ instead of the original multiset.
Call a triplet "good" if it satisfies $$$1\le i<j< k\le r$$$, and $$$X_{a_i}=a_j=Y_{a_k}$$$.
Hence, for each query, the good triplets fall under 8 categories, in roughly increasing order of difficulty:
1. $$$i,j,k$$$ are all static.  We can calculate for each $$$r$$$ in $$$O(n)$$$, through DP or the like, the number of good triplets in $$$[1,r]$$$ where $$$i,j,k$$$ are all static: we simply ignore the dynamic points. This is $$$O(n)$$$ preprocessing and $$$O(1)$$$ for each query.
2. We can calculate for each $$$r$$$ in $$$O(n)$$$, through DP or the like, the number of good triplets in $$$[1,r]$$$ where $$$i,j,k$$$ are all static: we simply ignore the dynamic points. This is $$$O(n)$$$ preprocessing and $$$O(1)$$$ for each query.
3. $$$i,j,k$$$ are all dynamic.  Similarly to 1, for each query, we do a brute force DP over all dynamic $$$i,j,k$$$ before $$$r$$$. This is $$$O(\sqrt n)$$$ for each query.
4. Similarly to 1, for each query, we do a brute force DP over all dynamic $$$i,j,k$$$ before $$$r$$$. This is $$$O(\sqrt n)$$$ for each query.
5. $$$i,j$$$ are dynamic, $$$k$$$ is static.  We iterate over all dynamic $$$j$$$, moving forward, and keep track of the amount of $$$X^{-1}_{a_j}$$$ currently seen. Then, for each $$$j$$$, we know the number of dynamic $$$i$$$ that can precede it through what we tracked; what remains is to count the number of static $$$a_k=Y^{-1}_{a_j}$$$ in $$$[j+1,r]$$$ in $$$O(1)$$$.  We offline all $$$O(n)$$$ intervals that we need to count in these $$$O(\sqrt n)$$$ queries and then re-process their contribution at the end of the block.
6. We iterate over all dynamic $$$j$$$, moving forward, and keep track of the amount of $$$X^{-1}_{a_j}$$$ currently seen. Then, for each $$$j$$$, we know the number of dynamic $$$i$$$ that can precede it through what we tracked; what remains is to count the number of static $$$a_k=Y^{-1}_{a_j}$$$ in $$$[j+1,r]$$$ in $$$O(1)$$$.
7. We offline all $$$O(n)$$$ intervals that we need to count in these $$$O(\sqrt n)$$$ queries and then re-process their contribution at the end of the block.
8. $$$j,k$$$ are dynamic, $$$i$$$ is static.  This is virtually the same as 3; we just iterate in reverse and we count the number of static $$$a_i=X^{-1}_{a_j}$$$ in $$$[1,j-1]$$$.
9. This is virtually the same as 3; we just iterate in reverse and we count the number of static $$$a_i=X^{-1}_{a_j}$$$ in $$$[1,j-1]$$$.
10. $$$j$$$ is dynamic, $$$i,k$$$ are static.  Using the same data structure as 3 and 4, we multiply the number of $$$a_i=X^{-1}_{a_j}$$$ in $$$[1,j-1]$$$ with the number of static $$$a_k=Y^{-1}_{a_j}$$$ in $$$[j+1,r]$$$.
11. Using the same data structure as 3 and 4, we multiply the number of $$$a_i=X^{-1}_{a_j}$$$ in $$$[1,j-1]$$$ with the number of static $$$a_k=Y^{-1}_{a_j}$$$ in $$$[j+1,r]$$$.
12. $$$i,k$$$ are dynamic, $$$j$$$ is static.   We iterate over all dynamic $$$k$$$. The number of good $$$i,j,k$$$ in this situation equals the number of $$$i,j$$$ where $$$1\le i,j<k$$$, $$$a_i=X^{-1}_{Y_{a_k}}$$$, and $$$a_j=Y_{a_k}$$$, minus the number of $$$i,j$$$ where $$$1\le j\le i<k$$$, $$$a_i=X^{-1}_{Y_{a_k}}$$$, and $$$a_j=Y_{a_k}$$$.  For the former, notice that $$$i,j$$$ are independent. As we iterate forwards through all dynamic $$$k$$$, we keep track of all dynamic values we have seen so far, and multiply the number of dynamic occurrences of $$$X^{-1}_{Y_{a_k}}$$$ with the number of static occurrences of $$$Y_{a_k}$$$ in $$$[1,k-1]$$$. As usual, to solve for static occurrences we offline them.  For the latter, observe, that when $$$a_i=s$$$ we must have $$$a_j=X_s$$$ in a good triplet. Hence during the iteration over $$$a$$$, for each dynamic $$$i$$$ we count the number of static $$$j$$$ before or on it such that $$$a_j=X_{a_i}$$$. We obtain this count for each dynamic $$$i$$$ and then, for each $$$k$$$, sum the count over all $$$a_i=X^{-1}_{Y_{a_k}}$$$.
13. We iterate over all dynamic $$$k$$$. The number of good $$$i,j,k$$$ in this situation equals the number of $$$i,j$$$ where $$$1\le i,j<k$$$, $$$a_i=X^{-1}_{Y_{a_k}}$$$, and $$$a_j=Y_{a_k}$$$, minus the number of $$$i,j$$$ where $$$1\le j\le i<k$$$, $$$a_i=X^{-1}_{Y_{a_k}}$$$, and $$$a_j=Y_{a_k}$$$.
14. For the former, notice that $$$i,j$$$ are independent. As we iterate forwards through all dynamic $$$k$$$, we keep track of all dynamic values we have seen so far, and multiply the number of dynamic occurrences of $$$X^{-1}_{Y_{a_k}}$$$ with the number of static occurrences of $$$Y_{a_k}$$$ in $$$[1,k-1]$$$. As usual, to solve for static occurrences we offline them.
15. For the latter, observe, that when $$$a_i=s$$$ we must have $$$a_j=X_s$$$ in a good triplet. Hence during the iteration over $$$a$$$, for each dynamic $$$i$$$ we count the number of static $$$j$$$ before or on it such that $$$a_j=X_{a_i}$$$. We obtain this count for each dynamic $$$i$$$ and then, for each $$$k$$$, sum the count over all $$$a_i=X^{-1}_{Y_{a_k}}$$$.
16. $$$k$$$ is dynamic, $$$i,j$$$ are static.   We iterate over all dynamic $$$k$$$; we seek the number of static $$$i,j$$$ in $$$[1,k-1]$$$ such that $$$a_j=X_{a_i}$$$, $$$i<j$$$, and $$$a_j=Y_{a_k}$$$.  We offline all $$$O(n)$$$ dynamic $$$k$$$ that we need to count in these $$$O(\sqrt n)$$$ queries. Then, we iterate forwards through $$$a$$$ in a manner similar to part 1, keeping track of the number of $$$i$$$ that can bind to each $$$j$$$, and a sum over all current $$$j$$$ where $$$a_j$$$ equals some value, answering offlined questions on the way.
17. We iterate over all dynamic $$$k$$$; we seek the number of static $$$i,j$$$ in $$$[1,k-1]$$$ such that $$$a_j=X_{a_i}$$$, $$$i<j$$$, and $$$a_j=Y_{a_k}$$$.
18. We offline all $$$O(n)$$$ dynamic $$$k$$$ that we need to count in these $$$O(\sqrt n)$$$ queries. Then, we iterate forwards through $$$a$$$ in a manner similar to part 1, keeping track of the number of $$$i$$$ that can bind to each $$$j$$$, and a sum over all current $$$j$$$ where $$$a_j$$$ equals some value, answering offlined questions on the way.
19. $$$i$$$ is dynamic, $$$j,k$$$ are static.   We iterate over all dynamic $$$i$$$; we seek the number of static $$$j,k$$$ in $$$[i+1,r]$$$ such that $$$a_j=Y_{a_k}$$$, $$$j<k$$$, and $$$a_j=X_{a_i}$$$.  We offline all $$$O(n)$$$ intervals that we need to count in these $$$O(\sqrt n)$$$ queries. Notice that the number of $$$j,k$$$ in an interval $$$[i+1,r]$$$ equals the number of $$$j,k$$$ where $$$j$$$ is in $$$[i+1,r]$$$ minus the number of $$$j,k$$$ where $$$j$$$ is in $$$[i+1,r]$$$ and $$$k$$$ is in $$$[r+1,n]$$$.  We calculate the former iterating backwards through $$$a$$$ to count the number of $$$k$$$ that can bind to each $$$j$$$, and then use a sum similar to part 3.  For the latter, we observe, that $$$j$$$ and $$$k$$$ are independent since we have fixed both the value of $$$a_j=X_{a_i}$$$ and $$$a_k=Y^{-1}_{X_{a_i}}$$$, so we simply multiply the possible $$$j$$$ in $$$[i+1,r]$$$ with the possible $$$k$$$ in $$$[r+1,n]$$$.
20. We iterate over all dynamic $$$i$$$; we seek the number of static $$$j,k$$$ in $$$[i+1,r]$$$ such that $$$a_j=Y_{a_k}$$$, $$$j<k$$$, and $$$a_j=X_{a_i}$$$.
21. We offline all $$$O(n)$$$ intervals that we need to count in these $$$O(\sqrt n)$$$ queries. Notice that the number of $$$j,k$$$ in an interval $$$[i+1,r]$$$ equals the number of $$$j,k$$$ where $$$j$$$ is in $$$[i+1,r]$$$ minus the number of $$$j,k$$$ where $$$j$$$ is in $$$[i+1,r]$$$ and $$$k$$$ is in $$$[r+1,n]$$$.
22. We calculate the former iterating backwards through $$$a$$$ to count the number of $$$k$$$ that can bind to each $$$j$$$, and then use a sum similar to part 3.
23. For the latter, we observe, that $$$j$$$ and $$$k$$$ are independent since we have fixed both the value of $$$a_j=X_{a_i}$$$ and $$$a_k=Y^{-1}_{X_{a_i}}$$$, so we simply multiply the possible $$$j$$$ in $$$[i+1,r]$$$ with the possible $$$k$$$ in $$$[r+1,n]$$$.
As such, we have solved $$$O(\sqrt n)$$$ queries in $$$O(n)$$$, and have solved the problem in $$$O(n+m\sqrt n)$$$.
We can prove that this problem is more difficult than calculating matrix multiplication of two matrices with size $$$\sqrt n\times \sqrt n$$$, when ignoring poly-logarithmic factors.
We construct a special arrangement of array: for $$$a_i=2,5,8,\dots$$$, the corresponding $$$b_{a_i}=1,4,7,\dots$$$, the corresponding $$$c_{a_i}=3,6,9,\dots$$$. For other $$$a_i$$$, $$$b_{a_i}=c_{a_i}=n$$$. We make sure that no $$$n$$$ exists in the array $$$a$$$.
Array $$$a$$$ is separated into three parts from left to right. The first part consists of $$$1,4,7,\dots$$$, each appears exactly one time. The second part consists of $$$2,5,8,\dots$$$, each may exist multiple times. The third part consists of $$$3,6,9,\dots$$$, each may exist multiple times.
Let $$$f_{k}$$$ be the number of triplets $$$(i,j,k)$$$ that $$$b_{a_i}=a_j=c_{a_k}$$$. For each $$$a_k$$$, there is exactly one $$$a_i$$$ and it appears exactly one time. Hence, $$$f_{k}$$$ is equal to the number of corresponding $$$a_j$$$. We only modify elements of $$$a$$$ in the second part. If we regard $$$k,a_k$$$ that $$$k$$$ is in the third part of array as a point in 2D space, let $$$x_k=k,y_k=a_k$$$, then inserting a corresponding $$$a_j$$$ into the second part means a ranged plus operation for any point that $$$y=a_k$$$. A query operation with value $$$r$$$ reports the sum of all point $$$i$$$ that $$$x_i\le r$$$. Because of our constructed array, only triplets where $$$k$$$ is in the third part can contribute to the answer. So we used an algorithm that can solve this problem to solve the two-dimensional $$$x=A$$$ add, $$$y=B$$$ sum problem, which is equivalent to $$$x<A$$$ add, $$$y<B$$$ sum when ignoring poly-logarithmic factors. This problem is further equivalent to the famous range inverse query problem, which was proven more difficult than calculating matrix multiplication of two matrices with size $$$\sqrt n\times \sqrt n$$$.
As currently the best matrix multiplication algorithm is $$$O(n^{2.373})$$$, seeking a $$$\tilde{O}(n)$$$ solution is not realistic, so the $$$O(n+m\sqrt n)$$$ solution described above is enough for competitive programming.
P.S. There is an easter egg in the problem statement, find it :)