Holy Diver
Contest: Codeforces Global Round 3
Difficulty rating: 3500
Tags: data structures

You are given an array which is initially empty. You need to perform $$$n$$$ operations of the given format:

- "$$$a$$$ $$$l$$$ $$$r$$$ $$$k$$$": append $$$a$$$ to the end of the array. After that count the number of integer pairs $$$x, y$$$ such that $$$l \leq x \leq y \leq r$$$ and $$$\operatorname{mex}(a_{x}, a_{x+1}, \ldots, a_{y}) = k$$$.

The elements of the array are numerated from $$$1$$$ in the order they are added to the array.

To make this problem more tricky we don't say your real parameters of the queries. Instead your are given $$$a'$$$, $$$l'$$$, $$$r'$$$, $$$k'$$$. To get $$$a$$$, $$$l$$$, $$$r$$$, $$$k$$$ on the $$$i$$$-th operation you need to perform the following:

- $$$a := (a' + lans) \bmod(n + 1)$$$,
- $$$l := (l' + lans) \bmod{i} + 1$$$,
- $$$r := (r' + lans) \bmod{i} + 1$$$,
- if $$$l > r$$$ swap $$$l$$$ and $$$r$$$,
- $$$k := (k' + lans) \bmod(n + 1)$$$,

The $$$\operatorname{mex}(S)$$$, where $$$S$$$ is a multiset of non-negative integers, is the smallest non-negative integer which does not appear in the set. For example, $$$\operatorname{mex}(\{2, 2, 3\}) = 0$$$ and $$$\operatorname{mex} (\{0, 1, 4, 1, 6\}) = 2$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array.

The next $$$n$$$ lines contain the description of queries.

Each of them $$$n$$$ lines contains four non-negative integers $$$a'$$$, $$$l'$$$, $$$r'$$$, $$$k'$$$ ($$$0, \leq a', l', r', k' \leq 10^9$$$), describing one operation.

Output format:
For each query print a single integer — the answer to this query.

Constraints:
Time limit: 3.0 s
Memory limit: 1024.0 MB

Note:
For the first example the decoded values of $$$a$$$, $$$l$$$, $$$r$$$, $$$k$$$ are the following:

$$$a_1=0,l_1=1,r_1=1,k_1=1$$$

$$$a_2=1,l_2=1,r_2=2,k_2=0$$$

$$$a_3=0,l_3=1,r_3=3,k_3=1$$$

$$$a_4=1,l_4=1,r_4=4,k_4=2$$$

$$$a_5=2,l_5=1,r_5=5,k_5=3$$$

For the second example the decoded values of $$$a$$$, $$$l$$$, $$$r$$$, $$$k$$$ are the following:

$$$a_1=2,l_1=1,r_1=1,k_1=2$$$

$$$a_2=2,l_2=1,r_2=2,k_2=1$$$

$$$a_3=0,l_3=1,r_3=3,k_3=0$$$

$$$a_4=0,l_4=2,r_4=2,k_4=3$$$

$$$a_5=0,l_5=3,r_5=4,k_5=0$$$

Example input:
5
0 0 0 1
0 1 0 5
5 2 1 0
5 2 1 0
2 4 3 3

Example output:
1
1
2
6
3

Example input:
5
2 0 0 2
2 0 1 1
0 0 2 0
3 2 2 0
0 2 3 0

Example output:
0
0
3
0
0

Editorial:
First, let's try to solve it if we know the whole array initially.
Let's move from the last element to the first. When we are in the element $$$i$$$ let's store all segments of right borders ($$$[r', r"]$$$) in the set, so that segment $$$[i, r]$$$ have the same mex value for all $$$r' \le r \le r"$$$. You can see that mex values in those segments are increasing from left to right, so you can recalculate those segments efficiently when you add another element from the left.
How to do so? Suppose we added element $$$k$$$ on the left. Then we must remove the segment with mex $$$k$$$ and replace it (with possibly many) segments of greater mex, the last of those segments might get merge with the segment following the removed one. It's easy to see that we add/remove only $$$O(n)$$$ segments in total since each time we remove exactly once segment, but add quite a lot. Informally, we simply can't add too much segments each time, since all mex's are distinct at every moment.
After that for each segment of the right borders we can compute when it was added to the set and when it was deleted. Then we can see it as a rectangle, where $$$x$$$ coordinates correspond to the left borders and $$$y$$$ coordinates correspond to the right borders. After that the problem is reduced to add value in the rectangle and compute the sum of values in the rectangle of a query.
So after that you need to notice, that those rectangles lay like in different stripes of surface. So they don't have points with the same x coordinates from different rectangles. That's why you can say, that to count total area laying on a query rectangle, you just can keep a segment tree with operations: add number to the segment, count the sum of number on the segment.
That's because there is only one rectangle intersecting your query, but not laying completely inside. So when you meet a rectangle during you scan line, you just add its width to the proper segment. Notice that there are actually $$$O(n)$$$ scan lines, because you need to keep them for every mex value. And for the query you need to get the state of your structure after some prefix of rectangles proceeded. They lay completely inside your query, so you need just to take the sum on the segment in your structure. Also there is one rectangle which can intersect you query, and you need to proceed it by hands. Another case is that in your set, when you proceed queries one by one, there are some current segment of mex, who was not deleted yet, so you need to take care about it too, because it can contain one segment with proper mex value for you query.