A11250. Nagini
编程题
普及/提高-
知识点
题目描述
Nagini, being a horcrux You-know-who created with the murder of Bertha Jorkins, has accumulated its army of snakes and is launching an attack on Hogwarts school.
Hogwarts' entrance can be imagined as a straight line (x-axis) from $1$ to $10^{5}$ . Nagini is launching various snakes at the Hogwarts entrance. Each snake lands parallel to the entrance, covering a segment at a distance $k$ from $x=l$ to $x=r$ . Formally, each snake can be imagined as being a line segment between points $(l,k)$ and $(r,k)$ . Note that $k$ can be both positive and negative, but not $0$ .
Let, at some $x$ -coordinate $x=i$ , there be snakes at point $(i,y_{1})$ and point $(i,y_{2})$ , such that $y_{1}>0$ and $y_{2}<0$ . Then, if for any point $(i,y_{3})$ containing a snake such that $y_{3}>0$ , $y_{1}<=y_{3}$ holds and for any point $(i,y_{4})$ containing a snake such that $y_{4}<0$ , $|y_{2}|<=|y_{4}|$ holds, then the danger value at coordinate $x=i$ is $y_{1}+|y_{2}|$ . If no such $y_{1}$ and $y_{2}$ exist, danger value is $0$ .
Harry wants to calculate the danger value of various segments of the Hogwarts entrance. Danger value for a segment $[l,r)$ of the entrance can be calculated by taking the sum of danger values for each integer $x$ -coordinate present in the segment.
Formally, you have to implement two types of queries:
- 1 l r k: a snake is added parallel to entrance from $x=l$ to $x=r$ at y-coordinate $y=k$ ( $l$ inclusive, $r$ exclusive).
- 2 l r: you have to calculate the danger value of segment $l$ to $r$ ( $l$ inclusive, $r$ exclusive).
Hogwarts' entrance can be imagined as a straight line (x-axis) from $1$ to $10^{5}$ . Nagini is launching various snakes at the Hogwarts entrance. Each snake lands parallel to the entrance, covering a segment at a distance $k$ from $x=l$ to $x=r$ . Formally, each snake can be imagined as being a line segment between points $(l,k)$ and $(r,k)$ . Note that $k$ can be both positive and negative, but not $0$ .
Let, at some $x$ -coordinate $x=i$ , there be snakes at point $(i,y_{1})$ and point $(i,y_{2})$ , such that $y_{1}>0$ and $y_{2}<0$ . Then, if for any point $(i,y_{3})$ containing a snake such that $y_{3}>0$ , $y_{1}<=y_{3}$ holds and for any point $(i,y_{4})$ containing a snake such that $y_{4}<0$ , $|y_{2}|<=|y_{4}|$ holds, then the danger value at coordinate $x=i$ is $y_{1}+|y_{2}|$ . If no such $y_{1}$ and $y_{2}$ exist, danger value is $0$ .
Harry wants to calculate the danger value of various segments of the Hogwarts entrance. Danger value for a segment $[l,r)$ of the entrance can be calculated by taking the sum of danger values for each integer $x$ -coordinate present in the segment.
Formally, you have to implement two types of queries:
- 1 l r k: a snake is added parallel to entrance from $x=l$ to $x=r$ at y-coordinate $y=k$ ( $l$ inclusive, $r$ exclusive).
- 2 l r: you have to calculate the danger value of segment $l$ to $r$ ( $l$ inclusive, $r$ exclusive).
输入格式
First line of input contains a single integer $q$ ( $1<=q<=5·10^{4}$ ) denoting the number of queries.
Next $q$ lines each describe a query. Each query description first contains the query type $type_{i}$ ( $1<=type_{i}<=2$ ). This is followed by further description of the query. In case of the type being $1$ , it is followed by integers $l_{i},r_{i}$ and $k_{i}$ (, $-10^{9}<=k_{i}<=10^{9}$ , $k≠0$ ). Otherwise, it just contains two integers, $l_{i}$ and $r_{i}$ ( $1<=l_{i}<r_{i}<=10^{5}$ ).
Next $q$ lines each describe a query. Each query description first contains the query type $type_{i}$ ( $1<=type_{i}<=2$ ). This is followed by further description of the query. In case of the type being $1$ , it is followed by integers $l_{i},r_{i}$ and $k_{i}$ (, $-10^{9}<=k_{i}<=10^{9}$ , $k≠0$ ). Otherwise, it just contains two integers, $l_{i}$ and $r_{i}$ ( $1<=l_{i}<r_{i}<=10^{5}$ ).
输出格式
Output the answer for each query of type 2 in a separate line.
输入输出样例
输入 #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
说明/提示
In the first sample case, the danger value for $x$ -coordinates $1$ is $0$ as there is no $y_{2}$ satisfying the above condition for $x=1$ .
Danger values for $x$ -coordinates $2$ and $3$ is $10+|-7|=17$ .
Danger values for $x$ -coordinates $4$ to $9$ is again $0$ as there is no $y_{2}$ satisfying the above condition for these coordinates.
Thus, total danger value is $17+17=34$ .
Danger values for $x$ -coordinates $2$ and $3$ is $10+|-7|=17$ .
Danger values for $x$ -coordinates $4$ to $9$ is again $0$ as there is no $y_{2}$ satisfying the above condition for these coordinates.
Thus, total danger value is $17+17=34$ .