题目背景

题目描述

给定一个数组 $a$ 和 $n$ 个集合，初始第 $i$ 个集合里面只有一个元素 $i$，集合里面的每个元素对应了数组的一个下标。

定义一个元素 $i$ 在集合 $S$ 中的相同数个数 $F(S,i)$ 为集合 $S$ 中元素 $j$ 的个数，满足 $a[i] = a[j]$。

定义一个集合 $S$ 的 $k$-权值为：$\forall i \in S,\forall j \in S$，有多少方案 $(i,j)$ 满足 $F(S,i)+F(S,j) \le k$，这里可以 $i=j$，并且 $(i,j)$ 与 $(j,i)$ 视为不同的方案。

要进行 $m$ 次操作，操作有两种：

1 x y : 将 $y$ 集合里面所有元素都放入 $x$ 集合，之后将 $y$ 集合清空，操作保证 $x$ 集合和 $y$ 集合操作前非空。

2 x l r k : 查询 $x$ 集合保留在 $[l,r]$ 内的所有元素时的 $k$-权值，查询是独立的，不对集合进行改变。

输入格式

第一行用空格隔开的两个数，表示 $n,m$。

第二行包含 $n$ 个数，表示这个数组。

之后 $m$ 行，每行格式如题目描述，表示一次操作。

输出格式

对于每个 $2$ 操作，输出一行一个数，表示查询的答案。

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

提示

Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477

对于 $10\%$ 的数据，满足 $n,m \le 100$

对于另外 $20\%$ 的数据，满足 $n,m \le 10000$

对于另外 $20\%$ 的数据，查询的 $k$ 不变。

对于 $100\%$ 的数据，满足 $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$。