← 返回题目列表

Codeforces · 855/F

F. 纳吉尼

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

纳吉尼是神秘人因谋杀伯莎·乔金斯而创造的魂器,它已经集结了蛇大军,正在对霍格沃茨学校发动攻击。

霍格沃茨的入口可以想象为一条从 1 到 105 的直线(x 轴)。纳吉尼正在霍格沃茨入口处发射各种蛇。每条蛇平行于入口着陆,覆盖从 x = l 到 x = r 距离为 k 的一段。形式上,每条蛇可以想象为点 (l, k) 和 (r, k) 之间的线段。请注意,k 可以为正值,也可以为负值,但不能为 0。

设,在某个 x 坐标 x = i 处,点 (i, y1) 和点 (i, y2) 处存在蛇,使得 y1 > 0 且 y2 < 0。那么,如果对于包含蛇的任何点 (i, y3),使得 y3 > 0,则 y1 ≤ y3 成立,并且对于包含蛇的任何点,使得 y4 < 0, |y2| ≤ |y4|成立,则坐标 x = i 处的危险值为 y1 + |y2|。如果不存在这样的y1和y2,则危险值为0。

哈利想要计算霍格沃茨入口各个部分的危险值。入口段 [l, r) 的危险值可以通过对段中存在的每个整数 x 坐标的危险值求和来计算。

正式来说,您必须实现两种类型的查询:

- 1 l r k:在 y 坐标 y 坐标 y = k(包括 l,不包括 r)处,从 x = l 到 x = r 处平行于入口添加一条蛇。
- 2 l r:您必须计算段l到r的危险值(包括l,不包括r)。

输入

输入的第一行包含一个整数 q (1 ≤ q ≤ 5·104),表示查询数量。

接下来的 q 行每行描述一个查询。每个查询描述首先包含查询类型 typei (1 ≤ typei ≤ 2)。接下来是查询的进一步描述。如果类型为 1,则后面跟着整数 li、ri 和 ki ($$1 \leq l_i < r_i \leq 10^5$$, - 109 ≤ ki ≤ 109,k ≠ 0)。否则,它只包含两个整数 li 和 ri (1 ≤ li < ri ≤ 105)。

输出

在单独的行中输出类型 2 的每个查询的答案。

示例

输入 #1

3
1 1 10 10
1 2 4 -7
2 1 10

输出 #1

34

输入 #2

7
1 2 3 5
1 1 10 10
1 4 5 -5
2 4 8
1 1 10 -10
2 4 8
2 1 10

输出 #2

15
75
170

注意

在第一个示例案例中,x 坐标 1 的危险值为 0,因为没有 y2 满足 x = 1 的上述条件。

x 坐标 2 和 3 的危险值为 10 + | - 7| = 17。

x 坐标 4 到 9 的危险值再次为 0,因为这些坐标没有满足上述条件的 y2。

因此,总危险值为 17 + 17 = 34。