Kingdom of Criticism
Contest: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2500
Tags: data structures, dsu

Pak Chanek is visiting a kingdom that earned a nickname "Kingdom of Criticism" because of how often its residents criticise each aspect of the kingdom. One aspect that is often criticised is the heights of the buildings. The kingdom has $$$N$$$ buildings. Initially, building $$$i$$$ has a height of $$$A_i$$$ units.

At any point in time, the residents can give a new criticism, namely they currently do not like buildings with heights between $$$l$$$ and $$$r$$$ units inclusive for some two integers $$$l$$$ and $$$r$$$. It is known that $$$r-l$$$ is always odd.

In $$$1$$$ minute, the kingdom's construction team can increase or decrease the height of any building by $$$1$$$ unit as long as the height still becomes a positive number. Each time they receive the current criticism from the residents, the kingdom's construction team makes it so that there are no buildings with heights between $$$l$$$ and $$$r$$$ units inclusive in the minimum time possible. It can be obtained that there is only one way to do this.

Note that the construction team only cares about the current criticism from the residents. All previous criticisms are forgotten.

There will be $$$Q$$$ queries that you must solve. Each query is one of the three following possibilities:

- 1 k w: The kingdom's construction team changes the height of building $$$k$$$ to be $$$w$$$ units ($$$1 \leq k \leq N$$$, $$$1 \leq w \leq 10^9$$$).
- 2 k: The kingdom's construction team wants you to find the height of building $$$k$$$ ($$$1 \leq k \leq N$$$).
- 3 l r: The residents currently do not like buildings with heights between $$$l$$$ and $$$r$$$ units inclusive ($$$2 \leq l \leq r \leq 10^9-1$$$, $$$r-l$$$ is odd).

Note that each change in height still persists to the next queries.

Input format:
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 4 \cdot 10^5$$$) — the number buildings in the kingdom.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \leq A_i \leq 10^9$$$) — the initial heights of the buildings.

The next line contains a single integer $$$Q$$$ ($$$1 \leq Q \leq 4 \cdot 10^5$$$) — the number of queries.

The $$$j$$$-th of the next $$$Q$$$ lines contains the $$$j$$$-th query as described. There is at least one query of type $$$2$$$.

Output format:
For each query of type $$$2$$$, output a line containing an integer representing the height of the building asked.

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

Note:
After the $$$1$$$-st query, the height of each building is $$$2, 6, 5, 6, 10$$$.

After the $$$3$$$-rd query, the height of each building is $$$3, 6, 5, 6, 10$$$.

After the $$$4$$$-th query, the height of each building is $$$2, 7, 7, 7, 10$$$.

After the $$$5$$$-th query, the height of each building is $$$2, 7, 7, 7, 10$$$.

After the $$$6$$$-th query, the height of each building is $$$2, 9, 7, 7, 10$$$.

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

Example output:
10
7
9
7

Editorial:
We can see that the changes in height for a single query of type $$$3$$$ are as follows:
• Each building with height $$$x$$$ such that $$$l \leq x \leq \frac{l+r}{2}$$$ is changed to have a height of $$$l-1$$$.
• Each building with height $$$x$$$ such that $$$\frac{l+r}{2} \leq x \leq r$$$ is changed to have a height of $$$r+1$$$.
• Note: since $$$r-l$$$ is odd, $$$\frac{l+r}{2}$$$ is not an integer. So there is no uncertainty here.
We can group the buildings into their heights, so buildings with the same height belong in the same group. We can maintain all the different groups in a set such that the groups are sorted by their heights. We can see that using this set, we can perform a type $$$3$$$ query by merging several groups into a single group with a certain height. Note that each time we merge $$$k$$$ groups, the number of groups decreases by $$$k-1$$$.
For each building, to maintain its height while doing all the merging of several groups and the changing of height of an entire group, we can use a simple disjoint-set data structure to make it such that we can request the height of any building quickly.
More specifically, each group is represented as a single connected component. The merging of several groups is equivalent to the merging of several connected components. The changing of height of an entire group can be done by changing the height of the representative building in a connected component.
However, a query of type $$$1$$$ can break our structure. Changing the height of a single building can make it leave its current group and join another group or make a new group. In order to not break our disjoint-set data structure, each time there is a type $$$1$$$ query, we can just leave the old building with the old height alone and make a new building with the new height. After this, each request for this building's height is referred to the new representation we just created. Each query of type $$$1$$$ creates one new building representation and can create at most one new group.
Using this solution, we can see that:
• A type $$$1$$$ query is done in $$$O(\log(N+Q))$$$ time because we have to make changes to the set. This query creates one new building representation and can create at most one new group.
• A type $$$2$$$ query is done in $$$O(1)$$$ time.
• A type $$$3$$$ query is done in $$$O(k\log(N+Q))$$$ time with $$$k$$$ being the number of groups we merge. This query decreases the number of groups by $$$k-1$$$.
Time complexity: $$$O((N+Q)\log(N+Q))$$$
Note: there is also an unintended solution using small-to-large with time complexity of $$$O((N+Q)\log^2(N+Q))$$$, but it needs optimisations in order to pass the time limit.