Background

The background is not related to the task and can be skipped.

Problem Description

Given a sequence $a$ of length $n$, each position has a color. There are $m$ operations. You need to support:

1 l r x: Set all numbers in the interval $[l,r]$ to $x$.

2 l r: Query how many pairs $(i,j)$ satisfy $l \leq i < j \leq r$ and $a_i = a_j$.

This problem is forced online. For each operation, the input $l,r,x$ must be $\operatorname{xor}$-ed with (the last answer $\bmod 2^{32}$). That is, you can store the last answer using the unsigned int data type. If there has been no query before, the last answer is $0$. The output answer is not taken $\bmod 2^{32}$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers representing the sequence $a$.

Then follow $m$ lines. Each line is in the form 1 l r x or 2 l r, representing the operations above.

Output Format

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

10 12
6 9 9 4 7 8 10 4 9 2
2 1 4
1 0 5 0
2 3 6
2 10 9
1 7 9 2
2 7 9
1 2 7 1
1 2 11 4
2 6 10
1 3 12 0
1 14 14 15
2 7 12

1
3
0
3
6
16

Hint

Idea: nzhtl1477, Solution: nzhtl1477&ccz181078, Code: ccz181078, Data: nzhtl1477.

Note: This problem uses bundled tests. You can get the score for a subtask only after you pass all test points in that subtask.

For $1\%$ of the testdata, it is Sample 1.

For another $9\%$ of the testdata, there are no modification operations.

For another $19\%$ of the testdata, $n,m\leq 500$.

For another $19\%$ of the testdata, the length of each modified interval does not exceed $5$.

For another $19\%$ of the testdata, the testdata is guaranteed to be random.

For $100\%$ of the testdata, $1\leq n,m\leq 2\times 10^5$, $1\leq a_{i},x\leq n$, $1\leq l\leq r\leq n$.

Translated by ChatGPT 5