P6749 "MdOI R3" Yoshino

"Becoming a Spirit did make me go through many painful things, and many sad things. But—I've also gained far more happiness and joy than all that pain and sorrow." "—I think that although Mio wanted to use my life, in exchange, didn't she also let me live for a longer time?" "By the way—almost forgot. Yotsuba, ... can you spare a little while?" "Then, let me introduce you properly—Mom." "This is Natsumi, my—most important friend." "This is Shido, the person I—like the most." 

Yoshino gives you a sequence of length $n$, where the $i$-th term is $a_i$. Now Yoshino will perform $m$ operations on the sequence. There are two types of operations: - $1\ l\ r\ x$: Yoshino changes the numbers with indices in the interval $[l,r]$ into an arithmetic progression starting from $x$ with common difference $1$. - $2$: Yoshino needs to query the number of inversion pairs in the entire sequence. An inversion pair is a pair $(i,j)$ such that $ia_j$.

The first line contains two integers $n,m$. The second line contains $n$ integers; the $i$-th one is $a_i$. The next $m$ lines each describe an operation, with the meaning as stated above.

For each query, output one integer per line as the answer.

[Sample Explanation] The first operation is a query. At this time there are three inversion pairs: $(1,3),(2,3),(1,2)$, so the answer is $3$. After the second operation (the modification), the sequence becomes $1\ 2\ 3$. The third operation is a query. At this time there are no inversion pairs in the sequence, so the answer is $0$. You can get more samples [here](https://www.luogu.com.cn/paste/j4nq14ov). --- [Constraints] **This problem uses bundled testdata.** | Subtask ID | $n,m\le$ | Special Condition | Score | Time Limit | | ---------- | -------------- | ----------------------------------------------------------- | ----- | ---------- | | $1$ | $500$ | None | $10$ | $1s$ | | $2$ | $3\times 10^3$ | None | $10$ | $1s$ | | $3$ | $3\times 10^4$ | The modification length is $1$ | $15$ | $2s$ | | $4$ | $3\times 10^4$ | The maximum value in the sequence never exceeds $15$ | $20$ | $2s$ | | $5$ | $3\times 10^4$ | The odd-numbered operation $1$ is guaranteed to be $1\ 1\ n\ 1$ | $20$ | $2s$ | | $6$ | $3\times 10^4$ | No special restrictions | $25$ | $2s$ | For all testdata, $1\le n,m,a_i\le 3\times 10^4$, $1\le l\le r\le n$, $1\le x\le 3\times 10^4-r+l$. Translated by ChatGPT 5