Colorful Operations
Contest: Codeforces Round 771 (Div. 2)
Difficulty rating: 2400
Tags: brute force, data structures, implementation

You have an array $$$a_1,a_2, \dots, a_n$$$. Each element initially has value $$$0$$$ and color $$$1$$$. You are also given $$$q$$$ queries to perform:

- Color $$$l$$$ $$$r$$$ $$$c$$$: Change the color of elements $$$a_l,a_{l+1},\cdots,a_r$$$ to $$$c$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le c \le n$$$).
- Add $$$c$$$ $$$x$$$: Add $$$x$$$ to values of all elements $$$a_i$$$ ($$$1 \le i \le n$$$) of color $$$c$$$ ($$$1 \le c \le n$$$, $$$-10^9 \le x \le 10^9$$$).
- Query $$$i$$$: Print $$$a_i$$$ ($$$1 \le i \le n$$$).

Input format:
The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 10^6$$$) — the length of array $$$a$$$ and the number of queries you have to perform.

Each of the next $$$q$$$ lines contains the query given in the form described in the problem statement.

Output format:
Print the answers to the queries of the third type on separate lines.

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

Note:
The first sample test is explained below. Blue, red and green represent colors $$$1$$$, $$$2$$$ and $$$3$$$ respectively.

Example input:
5 8
Color 2 4 2
Add 2 2
Query 3
Color 4 5 3
Color 2 2 3
Add 3 3
Query 2
Query 5

Example output:
2
5
3

Example input:
2 7
Add 1 7
Query 1
Add 2 4
Query 2
Color 1 1 1
Add 1 1
Query 2

Example output:
7
7
8

Editorial:
In the first part, let's consider that for all update operations $$$l=r$$$. The idea is not to update each element in an Add operation and instead, keeping an array $$$lazy[color]$$$ which stores for each color the total sum we must add to it (because we didn't do it when we had to).
Lets's discuss each operation:
• Update $$$l$$$ $$$r$$$ $$$c$$$:We will use the notation $$$l=r=i$$$. In this operation we change the color of element $$$i$$$ from $$$c'$$$ to $$$c$$$. First, remember that we have the sum $$$lazy[c']$$$ that we haven't added to any of the elements of color $$$c'$$$ (including $$$i$$$), so we better do it now because the color changes: $$$a[i] := a[i] + lazy[c']$$$. Now we can change the color to $$$c$$$.But wait, what about $$$lazy[c]$$$? It says that we will need to add some value to element $$$i$$$, but this is obviously false, since now it is up to date. We can compensate by subtracting now $$$lazy[c]$$$ from element $$$i$$$, repairing the mistake we will do later: $$$a[i] := a[i] - lazy[c]$$$. Finally, don't forget to set $$$color[i] := c$$$.
• Add $$$c$$$ $$$x$$$:This is as simple as it gets: $$$lazy[c] := lazy[c] + x$$$.
• Query $$$i$$$:The query operation is also not very complicated. We print the value $$$a[i]$$$ and don't forget about $$$lazy[color[i]]$$$: $$$print(a[i] + lazy[color[i]])$$$.
The time complexity is $$$O(1)$$$ per query.
Now we get back to the initial problem and remove the restriction $$$l=r$$$. Let's keep an array of maximal intervals of elements with the same color. We will name them color intervals. By doing so, we can keep the $$$lazy$$$ value for the a whole color interval. When we change the color of all elements in $$$[l,r]$$$, there are two kinds of color intervals that interest us in our array:
• $$$[l',r'] \subseteq [l,r]$$$:In this case the whole interval changes its color. First, we add the $$$lazy$$$ values to each interval. Then, after changing the color of all these intervals into the same one, we can merge them all. Now we update the resulting interval similar to how we would update a single element.
• $$$l \in [l',r']$$$ or $$$r \in [l',r']$$$ (or both):These are the two (or one) intervals that contain the endpoints $$$l$$$ and $$$r$$$. Here we will first split the color interval into two (or three) smaller ones: outside and inside $$$[l,r]$$$. Then, we just update the one inside $$$[l,r]$$$ as before.
Notice that in contrast to the solution for $$$l=r$$$, here we have to add some value on a range. We can do this using a data structure such as Fenwick tree or segment tree in $$$O(log_2{(n)})$$$. Also, for storing the color intervals we can use a set. This allows insertions and deletions, as well as quickly finding the range of intervals modified in a coloring.
The time complexity is a bit tricky to determine because at first it might seem like it is $$$O(q \cdot n)$$$, but if we analyze the effect each update has on the long term, it turns out to be much better.
We will further refer to the number of intervals in our array as the potential of the current state. Let's consider that in our update we found $$$k$$$ color intervals contained in the update interval, the potential decreases by $$$k-1$$$ and then it grows by at most $$$2$$$ (because of the two splits). The number of steps our program performs is proportional to the total changes in potential.
In one operation, the potential can decrease by a lot, but luckily, it can only grow by $$$2$$$. Because the potential is always positive, it decreases in total at most as much as it increases. Thus, the total change in potential is $$$O(q)$$$.
Although not described here, there exists another solution to this problem using only a segment tree with lazy propagation. In this solution, our data structure stops only on monochrome segments. The time complexity is the same.
Time complexity: $$$O(n+q \cdot log_2{(n)})$$$.