P13130 [Ynoi Easy Round 2019] Akane Kurokawa.


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.

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.

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

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