Sequence Transition Sum Queries

You are given a sequence \(a\) of length \(n\), where each \(a_i\) is an integer in \([1, n]\). Define the function \(f(i,j)\) for indices \(i,j\) with \(1 \le i < j \le n\) as:

\(f(i,j)=\#\{x \mid i \le x < j \text{ and } a_x \neq a_{x+1}\}\).

There are \(m\) operations. Each operation is one of the following two types:

• Update Operation: 1 l r x which means set every element in the subarray \(a_l, a_{l+1}, \dots, a_r\) to \(x\).
• Query Operation: 2 l r x which asks you to compute the following sum over all pairs \((i,j)\) with \(l \le i < j \le r\) and \(a_i = a_j = x\):

\(\displaystyle \sum_{{l \le i < j \le r \atop a_i=a_j=x}} f(i,j) \)

Hint: Note that for any index \(k\) in \([l, r-1]\) where \(a_k\neq a_{k+1}\), its contribution to \(f(i,j)\) for those \(i,j\) is \(\text{(number of occurrences of }x\text{ in }a_l \ldots a_k)\times(\text{number of occurrences of }x\text{ in }a_{k+1} \ldots a_r)\). Use this observation to handle the query.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the length of the sequence and the number of operations respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where \(1 \leq a_i \leq n\).

Then \(m\) lines follow. Each line represents an operation in one of the following formats:

• 1 l r x: update operation, which means assign value \(x\) to all elements in the segment \([l, r]\).
• 2 l r x: query operation, which means query the sum of \(f(i,j)\) for all \(l \leq i < j \leq r\) such that \(a_i = a_j = x\).

outputFormat

For each query operation (type 2), print the corresponding answer in a new line.

sample

5 5
1 2 2 3 1
2 1 5 2
1 2 4 2
2 1 5 2
2 1 3 1
2 3 5 1

0
0
0
0