← 返回题目列表

Codeforces · 444/C

C. DZY 喜欢颜色

中文机器翻译题面 查看原题

DZY 热爱色彩,他喜欢绘画。

在一个色彩缤纷的日子里,DZY 获得了一条彩色丝带,该丝带由 n 个单元组成(从左到右编号为 1 到 n)。首先,第 i 个色带单元的颜色为 i。它已经足够丰富多彩了,但是我们仍然认为一开始每个单元的色彩度都是0。

DZY 热爱绘画,我们知道。他拿起一支颜色为 x 的画笔,在丝带上画了一条线。在这种情况下,会绘制一些连续的单元。想象一下单元 i 当前的颜色是 y。当用该画笔绘制时,该单元的颜色变为x,并且该单元的色彩度增加|x - y|。

DZY 想要执行 m 次操作,每个操作可以是以下操作之一:

1. 将所有编号在 l 和 r(含)之间的单元涂上颜色 x。
2. 求 l 和 r 之间(含)单位的色彩度之和。

你能帮助DZY吗?

输入

第一行包含两个空格分隔的整数 n, m (1 ≤ n, m ≤ 105)。

接下来的 m 行中的每一行都以整数类型 (1 ≤ type ≤ 2) 开头,它表示此操作的类型。

如果 type = 1,则该行中还会有 3 个整数 l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 108),描述操作 1。

如果 type = 2,则该行中还会有 2 个整数 l, r (1 ≤ l ≤ r ≤ n),描述操作 2。

输出

对于每个操作 2,打印一行包含答案 - 色彩总和。

示例

输入 #1

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

输出 #1

8

输入 #2

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

输出 #2

3
2
1

输入 #3

10 6
1 1 5 3
1 2 7 9
1 10 10 11
1 3 8 12
1 1 10 3
2 1 10

输出 #3

129

注意

在第一个样本中,每个单元的颜色初始为[1,2,3],色彩度为[0,0,0]。

第一次操作后,颜色变为 [4, 4, 3],色彩度变为 [3, 2, 0]。

第二次操作后,颜色变为[4,5,5],色彩度变为[3,3,2]。

所以类型 2 的唯一操作的答案是 8。