Background

Problem Description

You are given an array $a$ and $n$ sets. Initially, the $i$-th set contains only one element $i$. Each element in a set corresponds to an index of the array.

Define the number of equal values of an element $i$ in a set $S$ as $F(S,i)$, which is the number of elements $j$ in $S$ such that $a[i] = a[j]$.

Define the $k$-weight of a set $S$ as: for all $i \in S$ and for all $j \in S$, count how many ordered pairs $(i,j)$ satisfy $F(S,i) + F(S,j) \le k$. Here, $i$ may equal $j$, and $(i,j)$ and $(j,i)$ are considered different.

You need to perform $m$ operations of two types:

1 x y: Move all elements in set $y$ into set $x$, then clear set $y$. It is guaranteed that both set $x$ and set $y$ are non-empty before the operation.

2 x l r k: Query the $k$-weight of set $x$ when only keeping the elements whose indices are in $[l,r]$. Each query is independent and does not modify any set.

Input Format

The first line contains two integers separated by spaces, denoting $n,m$.

The second line contains $n$ integers, denoting the array.

The next $m$ lines each describe one operation in the format given above.

Output Format

For each operation of type $2$, output one line with one integer, denoting the answer to the query.

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

1
0
0
1
0
1
0
1
1
0
0
0
0
1
0
1
0
9
4
0
0

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477.

For $10\%$ of the testdata, $n,m \le 100$.

For another $20\%$ of the testdata, $n,m \le 10000$.

For another $20\%$ of the testdata, the queried $k$ does not change.

For $100\%$ of the testdata, $n \le 10^5$, $m \le 2 \times 10^5$, $0 \le a_i,k \le m$, $1 \le l \le r \le n$, $1 \le x,y \le n$.

Translated by ChatGPT 5