Problem Description

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

Input Format

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.

Output Format

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

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

2
20
20
2
4
30
0
9
0

Hint

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