『MdOI R3』Yoshino

『变成了精灵确实是遭遇了许多难过的事情，也遭遇了许多悲伤的事情。但是——我也得到了比这些难过和悲伤多得多的快乐与开心。』 『——我觉得，虽然澪小姐想要使用我的生命，但是作为交换，她不是也让我活了更长的时间了吗？』 『对了——差点忘了。四糸奈，……稍微一会儿，可以吗。』 『那么，正式介绍一下呢，——妈妈。』 『这位是七罪小姐，我——最重要的朋友。』 『这位是士道先生，是我——最喜欢的人。』 

Yoshino 给了你一个长度为 $n$ 的序列，第 $i$ 项为 $a_i$。 现在 Yoshino 会对数列进行 $m$ 次操作。 操作分成两种： - $1\ l\ r\ x$ Yoshino 把数列下标在 $[l,r]$ 区间内的数修改为了一个从 $x$ 开始公差为 $1$ 的等差数列。 - $2$ Yoshino 需要查询整个数列中的逆序对个数。逆序对的定义为数对 $(i,j)$ 满足 $i<j$ 且 $a_i>a_j$。

第一行两个整数 $n,m$。 第二行 $n$ 个整数，第 $i$ 个为 $a_i$。 接下来 $m$ 行，每行代表一个操作，含义见上。

对于每次询问，一行一个整数输出答案。

3 3
3 2 1 
2 
1 1 3 1 
2 

3 
0 

【样例解释】 第一次操作为询问操作，此时有 $(1,3),(2,3),(1,2)$ 三组逆序对，答案为 $3$。 第二次操作修改完成后，数列变为 $1\ 2\ 3$。 第三次操作为询问操作，此时数列中没有逆序对，故答案为 $0$。 更多样例请[到这里](https://www.luogu.com.cn/paste/j4nq14ov)领取。 --- 【数据范围】 **本题采用捆绑测试** | 子任务编号 | $n,m\le$ | 特殊条件 | 分值 | 时限 | | ---------- | -------------- | -------------------------------------- | ----- | ----- | | $1$ | $500$ | 无 | $10 $ | $1s$ | | $2$ | $3\times 10^3$ | 无 | $10$ | $1s $ | | $3$ | $3\times 10^4$ | 修改长度为 $1$ | $15$ | $2s $ | | $4$ | $3\times 10^4$ | 保证任何时刻序列中的最大值不超过 $15$ | $20 $ | $2s $ | | $5$ | $3\times 10^4$ | 保证第奇数次操作 $1$ 为 $1\ 1\ n\ 1$ | $20$ | $ 2s$ | | $6$ | $3\times 10^4$ | 无特殊限制 | $25 $ | $2s$ | 对于所有的数据，$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$。