P9998 [Ynoi2000] rfrqwq

Given a sequence $a$ of length $n$, each position contains an integer in $[1,n]$. Define $f(i,j)$ as the number of integers $x$ such that $i \le x < j$ and $a_x \ne a_{x+1}$. There are $m$ operations: `1 l r x`: Set all elements in the interval $[l,r]$ to $x$. `2 l r x`: Query, within the interval $[l,r]$, the sum of $f(i,j)$ over all pairs $l \le i < j \le r$ such that $a_i = a_j = x$.

The first line contains two integers $n, m$. The second line contains $n$ integers separated by spaces, representing the sequence $a$. Then follow $m$ lines, each containing four integers $opt, l, r, x$ separated by spaces, representing an operation.

For each operation of type $2$, output one line containing one integer, the answer.

Idea: nzhtl1477, Solution: nzhtl1477, Code: ccz181078, Data: ccz181078. For $20\%$ of the testdata, $1 \le n, m \le 1000$. For another $20\%$ of the testdata, there are no type $1$ operations. For another $10\%$ of the testdata, the operation types are in $[1,2]$, and $a_i, x$ are generated uniformly at random in $[1,100]$. The two endpoints of the interval $[l,r]$ are integers generated uniformly at random from $[1,n]$. If $l > r$ after generation, swap them. For another $30\%$ of the testdata, $1 \le n, m \le 10^5$. For $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^5$, $1 \le l \le r \le n$, $1 \le a_i, x \le n$, and all inputs are integers. Translated by ChatGPT 5