Doremy's Paint 2
Contest: Codeforces Global Round 24
Difficulty rating: 3400
Tags: data structures

Doremy has $$$n$$$ buckets of paint which is represented by an array $$$a$$$ of length $$$n$$$. Bucket $$$i$$$ contains paint with color $$$a_i$$$. Initially, $$$a_i=i$$$.

Doremy has $$$m$$$ segments $$$[l_i,r_i]$$$ ($$$1 \le l_i \le r_i \le n$$$). Each segment describes an operation. Operation $$$i$$$ is performed as follows:

- For each $$$j$$$ such that $$$l_i < j \leq r_i$$$, set $$$a_j := a_{l_i}$$$.

Doremy also selects an integer $$$k$$$. She wants to know for each integer $$$x$$$ from $$$0$$$ to $$$m-1$$$, the number of distinct colors in the array after performing operations $$$x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$$$. Can you help her calculate these values? Note that for each $$$x$$$ individually we start from the initial array and perform only the given $$$k$$$ operations in the given order.

Input format:
The first line of input contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1\le n,m\le 2\cdot 10^5$$$, $$$1 \le k \le m$$$) — the length of the array $$$a$$$, the total number of operations, and the integer that Doremy selects.

The $$$i$$$-th line of the following $$$m$$$ lines contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — the bounds of the $$$i$$$-th segment.

Output format:
Output $$$m$$$ integers. The $$$(x+1)$$$-th integer should be the number of distinct colors in the array if we start from the initial array and perform operations $$$x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$$$.

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

Note:
In the first test case, the picture below shows the resulting array for the values of $$$x=0,1,2$$$ respectively.

Example input:
7 5 5
3 5
2 3
4 6
5 7
1 2

Example output:
3 3 3 3 2

Example input:
10 9 4
1 1
2 3
3 4
7 9
6 8
5 7
2 4
9 10
1 3

Example output:
6 6 7 6 5 5 7 7 7

Editorial:
The main idea of the solution is that we can try to the answers for position $$$x,x+1,\ldots,x+k$$$ all at once. We do this by representing the interval $$$[x+i,x+k+i)$$$ as $$$[x+i,x+k) \cup [x+k,x+k+i)$$$ and perform sweep line on both halves of interval.
Firstly, after applying some operations on the array $$$a$$$, we will have $$$a_i \leq a_{i+1}$$$. That is, we can instead count the number of indices such that $$$a_i \neq a_{i+1}$$$ for one less than the number of distinct elements. From here on, we will be counting the number of elements that $$$a_i \neq a_{i+1}$$$ instead.
Let us consider that the state of the array is $$$a$$$ after applying operations $$$[s+1,e]$$$. Consider the effect of applying operations $$$[s,e]$$$ instead. The change this operation will make is that we replace all $$$i$$$ such that $$$a_i \in [l_{s},r_{s}]$$$ with $$$a_i=l_{s}$$$. We can think about it as only counting $$$a_i \not\cong a_{i+1}$$$ where we can view the above operation of replacing $$$a_i \in [l_{s},r_{s}]$$$ with $$$l_{s}$$$ as instead merging $$$[l_{s},r_{s}]$$$ values as a single equivalence class which we label $$$l_s$$$.
So for interval $$$[x+i,x+k+i) = [x+i,x+k) \cup [x+k,x+k+i)$$$ we will get the equivalence class for values when considering ranges $$$[l_j,r_j$$$] with $$$j \in [x+i,x+k-1]$$$. This is a natural line sweep when considering going from $$$[s,x+k-1]$$$ to $$$[s-1,x+k-1]$$$ that uses $$$O(n \log n)$$$ by amortized analysis.
We can find the state of the array when applying operations $$$[x+k,x+k],[x+k,x+k+1],\ldots,[x+k,x+2k-1]$$$ in $$$O(n \log n)$$$ time by amoritzed analysis by only storing contiguous values as a set. By storing the changes we made when we go from $$$[x+k,e]$$$ to $$$[x+k,e+1]$$$, we are able to "undo" the changes to go from $$$[x+k,e+1]$$$ to $$$[x+k,e]$$$.
Now, we want to go from applying operations in $$$[x+i+1,x+k+i+1) = [x+i+1,x+k) \cup [x+k,x+k+i+1)$$$ to $$$[x+i,x+k+i) = [x+i,x+k) \cup [x+k,x+k+i)$$$, first we go from $$$[x+k,x+k+i+1)$$$ to $$$[x+k,x+k+i)$$$ by undoing the operation (and checking how many adjacent values are $$$\not\cong$$$), then we update our equivalence classes to go from $$$[x+i+1,x+k)$$$ to $$$[x+i,x+k)$$$.
However, The problem is that this algorithm runs in $$$O(\frac{m}{k} n \log n)$$$ time. However, we note that we can discretize the range $$$[1,n]$$$ using the ranges $$$[l_j,r_j]$$$ with $$$j \in [x,x+2k)$$$, so that our amortization works in $$$O(k \log k)$$$, to obtain a complexity of $$$O(\frac{m}{k} k \log k) = O(m \log k)$$$ (with a super huge constant). Note that since the element of the array $$$a$$$ are integers but are instead ranges now, there are some implementation details that are left as an exercise to the reader.