#1301. 『MdOI R3』Yoshino

『MdOI R3』Yoshino

题目描述

Yoshino 给了你一个长度为 nn 的序列,第 ii 项为 aia_i。

现在 Yoshino 会对数列进行 mm 次操作。

操作分成两种:

  • 1 l r x1\ l\ r\ x Yoshino 把数列下标在 [l,r][l,r] 区间内的数修改为了一个从 xx 开始公差为 11 的等差数列。

  • 22 Yoshino 需要查询整个数列中的逆序对个数。逆序对的定义为数对 (i,j)(i,j) 满足 iajia_j。

输入格式

第一行两个整数 n,mn,m。

第二行 nn 个整数,第 ii 个为 aia_i。

接下来 mm 行,每行代表一个操作,含义见上。

输出格式

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

样例

3 3
3 2 1 
2 
1 1 3 1 
2 
3 
0 

题目来源:洛谷 P6749