P13130 [Ynoi Easy Round 2019] 黑川赤音


给定一个数组 $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$ 操作，输出一行一个数，表示查询的答案。

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$。