Nagini
Contest: Manthan, Codefest 17
Difficulty rating: 3100
Tags: binary search, data structures

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 105. 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, y1) and point (i, y2), such that y1 > 0 and y2 < 0. Then, if for any point (i, y3) containing a snake such that y3 > 0, y1 ≤ y3 holds and for any point (i, y4) containing a snake such that y4 < 0, |y2| ≤ |y4| holds, then the danger value at coordinate x = i is y1 + |y2|. If no such y1 and y2 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).

Input format:
First line of input contains a single integer q (1 ≤ q ≤ 5·104) denoting the number of queries.

Next q lines each describe a query. Each query description first contains the query type typei (1 ≤ typei ≤ 2). This is followed by further description of the query. In case of the type being 1, it is followed by integers li, ri and ki ($$1 \leq l_i < r_i \leq 10^5$$,  - 109 ≤ ki ≤ 109, k ≠ 0). Otherwise, it just contains two integers, li and ri (1 ≤ li < ri ≤ 105).

Output format:
Output the answer for each query of type 2 in a separate line.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first sample case, the danger value for x-coordinates 1 is 0 as there is no y2 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 y2 satisfying the above condition for these coordinates.

Thus, total danger value is 17 + 17 = 34.

Example input:
3
1 1 10 10
1 2 4 -7
2 1 10

Example output:
34

Example input:
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

Example output:
15
75
170

Editorial:
This problem can be solved by using the concept of square root decomposition. Let us divide the total range of x-axis, that is, from 1 to 105 in $$\sqrt{10^5}$$. Then, blockSize = $$\sqrt{10^5}$$, and number of blocks, nb = 105 / blockSize. Now, we maintain the following structures:
• An array ans that stores the answer for each block.
• Two values upper and lower for each block. upper stores the closest line segment with y > 0 that covers the complete block. Similarly lower stores the closest line with y < 0 that covers the complete block.
• Maps low and up for each block. up maps for each height y > 0, the number of x-coordinates with its minimum height as y. Similarly low maps for each height y < 0, the number of x-coordinates with its maximum height as y. Also, note that this map stores the information only for those x-coordinates which have atleast one line segment on both sides of axis.
• Maps vnotup and vnotdown for each block. These are similar to maps low and up except that these stores value for those coordinates that do not have line on one of the sides. That is, vnotup maps the height y to its count for y < 0 such that at those coordinates, there do not exists any line for y > 0.
• Value notboth for each block, this stores the number of x-coordinates that do not have line segments on any of the two sides of axis.
• Arrays minup and mindown for each value from 1 to 105. minup stores the minimum value for y such that y > 0 and there is a snake at that point and that snake does not cover the complete block. Similar value for y < 0 is stored by mindown
Now we have to maintain these structure throughout the update operation. To do so, we divide the update operations into two halves, the update for initial and final blocks which are only partially covered by a line, and the update for complete block. For now, let us assume that the update is for some y > 0. For y < 0, a similar approach can be done:
• Updating the initial and final blocks: Iterate through every x-coordinate in the range. There can be four cases:   If all the values, minup, mindown for that coordinate and value lower and upper for that block are inf, this means that this is the first time a line is coming at this coordinate. Reduce notboth of the block by 1 and update the map vnotdown.  Else if minup and upper are inf, this means that for this x-coordinate there is a line below axis, but not above. Update vnotup, up, low and ans accordingly.  Else if mindown and lower are inf, this means that there is no line with y < 0 at this x-coordinate. Just update vnotdown.  Else if both side lines are there, just update ans and up.  Also, update the value of minup for each coordinate.
• If all the values, minup, mindown for that coordinate and value lower and upper for that block are inf, this means that this is the first time a line is coming at this coordinate. Reduce notboth of the block by 1 and update the map vnotdown.
• Else if minup and upper are inf, this means that for this x-coordinate there is a line below axis, but not above. Update vnotup, up, low and ans accordingly.
• Else if mindown and lower are inf, this means that there is no line with y < 0 at this x-coordinate. Just update vnotdown.
• Else if both side lines are there, just update ans and up.
• Updating the complete block Remove all the elements from vnotup and update the up, low maps and ans for that block accordingly. Put notboth as 0 and update the map vnotdown acccordingly. Remove elements from vnotdown which are greater than this value of y and update it again. Finally update the up array and value of ans for that block. Also update the value of upper.
For answering the queries, you will need to answer the half-block(initial and final block) queries by iterating through each x-coordinate. For answering full-block queries, just return the ans for that block.
If we take n = 105, the expected complexity of the solution is $${ \mathcal { O } } ( q \cdot { \sqrt { n } } \cdot \log n )$$