The Potion of Great Power
Contest: Central-European Olympiad in Informatics, CEOI 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated)
Difficulty rating: 2400
Tags: *special, 2-sat, binary search, data structures, graphs, interactive, sortings, two pointers

Once upon a time, in the Land of the Shamans, everyone lived on the Sky-High Beanstalk. Each shaman had a unique identifying number $$$i$$$ between $$$0$$$ and $$$N-1$$$, and an altitude value $$$H_i$$$, representing how high he lived above ground level. The distance between two altitudes is the absolute value of their difference.

All shamans lived together in peace, until one of them stole the formula of the world-famous Potion of Great Power. To cover his/her tracks, the Thief has put a Curse on the land: most inhabitants could no longer trust each other...

Despite the very difficult circumstances, the Order of Good Investigators have gained the following information about the Curse:

- When the Curse first takes effect, everyone stops trusting each other.
- The Curse is unstable: at the end of each day (exactly at midnight), one pair of shamans will start or stop trusting each other.
- Unfortunately, each shaman will only ever trust at most $$$D$$$ others at any given time.

They believe the Thief has whispered the formula to an Evil Shaman. To avoid detection, both of them visited the home of one of their (respective) trusted friends. During the visit, the Thief whispered the formula to the Evil Shaman through the window. (Note: this trusted friend did not have to be home at the time. In fact, it's even possible that they visited each other's houses – shamans are weird.)

Fortunately, whispers only travel short distances, so the Order knows the two trusted friends visited (by the Thief and the Evil Shaman) must live very close to each other.

They ask you to help with their investigation. They would like to test their suspicions: what if the Thief was $$$x$$$, the Evil Shaman was $$$y$$$, and the formula was whispered on day $$$v$$$? What is the smallest distance the whispered formula had to travel? That is, what is the minimum distance between the apartments of some shamans $$$x'$$$ and $$$y'$$$ (i.e. $$$\min\left(\left|H_{x'} - H_{y'}\right|\right)$$$), such that $$$x'$$$ was a trusted friend of $$$x$$$ and $$$y'$$$ was a trusted friend of $$$y$$$ on day $$$v$$$?

They will share all their information with you, then ask you a number of questions. You need to answer each question immediately, before receiving the next one.

Interaction format:
The interaction will begin with a line containing $$$N$$$, $$$D$$$, $$$U$$$ and $$$Q$$$ $$$(2 \leq N \leq 100000$$$, $$$1 \leq D \leq 500$$$, $$$0 \leq U \leq 200000$$$, $$$1 \leq Q \leq 50000)$$$ – the number of shamans, the maximum number of trusted friends a shaman can have at any given point, the number of days, and the number of questions.

On the next line $$$N$$$ space separated integers will follow, the $$$i$$$th $$$(1\leq i \leq N)$$$ of which being $$$H_{i-1}$$$ $$$(0\leq H_{i-1} \leq 10^9)$$$, the altitude of shaman $$$i-1$$$.

On the next $$$U$$$ lines there will be two integers each, on the $$$i$$$th ($$$1 \leq i \leq U$$$) $$$A_i$$$ and $$$B_i$$$ $$$(0 \leq A_i, B_i < N$$$ and $$$A_i \neq B_i)$$$, which represents a pair of shamans who started or stopped trusting each other at the end of day $$$i-1$$$. That is, if $$$A_i$$$ and $$$B_i$$$ trusted each other on day $$$i-1$$$, they did not trust each other on day $$$i$$$, or vice versa. Read all of these integers.

The interactor now will ask you $$$Q$$$ question, so the following interaction should happen $$$Q$$$ times:

1. Read $$$3$$$ integers describing the current query: $$$x,y$$$ and $$$v$$$ ($$$x \neq y$$$, $$$0 \leq x,y < N$$$ and $$$0 \leq v \leq U$$$), where $$$x$$$ is the suspected Thief, $$$y$$$ is the suspected Evil Shaman, and $$$v$$$ is the suspected day..
2. Then print the answer to this query on a single line, i.e. you should print the minimum distance the whispered formula had to travel from some trusted friend $$$x'$$$ of $$$x$$$ to a trusted friend $$$y'$$$ of $$$y$$$.   In case someone trusted both $$$x$$$ and $$$y$$$ (i.e. $$$x'=y'$$$), you should print $$$0$$$.  If $$$x$$$ or $$$y$$$ had no trusted friends, print $$$10^9$$$.

After printing each line do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

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

Note:
Scoring:
$$$ \begin{array}{|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & 0 & \text{samples}\\ \hline 2 & 17 & Q,U \leq 1000 \\ \hline 3 & 14 & v=U \: \text{for all questions} \\ \hline 4 & 18 & H_i \in \left\{0,1\right\} \: \text{for all shamans} \: i \\ \hline 5 & 21 & U,N \leq 10000\\ \hline 6 & 30 & \text{no additional constraints}\\ \hline \end{array} $$$

Example queries:

Evolution of friendships:

Example input:
6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4
3 0 8
0 5 5
3 0 11

Example output:
26
0
1000000000
14

Editorial:
We denote the maximum number of edges in the graph by $$$M$$$. You can see that $$$U$$$ is an upper bound for it.
Subtask 2
$$$Q, U \leq 1000$$$
We can store each operation, and replay them for each question. We can store all edges in a data structure, or keep neighbours in separate data structures for each node.
When answering a question, find the neighbours of both nodes, and consider the distance of each pair of neighbours, computing the minimum. This yields to a simple solution in $$$O(QUD + QD^2)$$$ time, or $$$O(QU\log(D) + QD^2)$$$ when using an associative container, like std::set.
Ordering Trick
Although not required for this subtask, we can improve the second part by ordering the neighbour lists by $$$H$$$ value, and stepping through them simultaneously, using two pointers. We always step in the list in which the pointer points to the entry with the smaller $$$H$$$ value out of the two, and consider the current pair for the minimum computation:
The correctness of this is easy to prove.
Subtask 3
$$$V=U$$$ for all queries
In this case, each question will refer to the same version (the final one). Hence, we can just apply all updates at the start once (applying updates is done in the same way as in Subtask 2), and then answer questions on this single version (like before). Using an efficient data structure and the ordering trick (we can actually pre-sort, before answering any questions), we can solve this subtask in $$$O(U\log(D) + M\log(D) + Q D \log(D))$$$.
Subtask 4
$$$H[i] \in \{0,1\}$$$ for all nodes $$$i$$$
For a node $$$u$$$ and version $$$V$$$, we need to be able to tell whether $$$u$$$ had a neighbour $$$u'$$$ with $$$H[u'] = f$$$ for both possible values of $$$f$$$ ($$$0$$$ or $$$1$$$). Once we have obtained this information for both $$$X$$$ and $$$Y$$$, we can easily work out the answer.
For each node $$$u$$$ and possible $$$f$$$ value, let us build an ordered list of 'events' of the following types:
• Node $$$u$$$ stopped having any neighbours $$$u'$$$ with $$$H[u'] = f$$$ in version $$$V$$$.
• Node $$$u$$$ started having neighbours with $$$H[u'] = f$$$ in version $$$V$$$.
This yields a solution in $$$O(U\log(M) + Q\log(U))$$$ time and $$$O(U)$$$ space for this special case.
Subtask 5
$$$U,N \leq 10000$$$
$$$\sqrt{U}$$$ checkpoints
We first apply all updates in order, producing $$$\sqrt{U}$$$ checkpoints, evenly spaced, then – for each question – we simulate updates from the closest checkpoint (in the same way as we did for Subtask 1). An efficient implementation of this can achieve $$$O(U\log(M) + \sqrt{U} M + Q \sqrt{U} \log(M) + Q D \log(D))$$$ time and $$$O(\sqrt{U}M)$$$ memory.
Save neighbour list by node, binary search by version
Another solution is to separate updates by node, and save the neighbour list of the updated node for each update (in a vector of neighbour lists for that node). Then, we can binary search for the neighbour list at version $$$V$$$. This can be implemented in $$$O(UD + Q \log(U) + QD)$$$ time and $$$O(UD)$$$ space.
Self-copying data structures
We can use a self-copying (also known as persistent or copy-on-write) data structure. These data structures are constructed as a (directed) tree, where each node holds some information. When updates are applied, we copy every node that was modified, including nodes whose children are modified, thus each version will have its own root node, from which queries can be performed. There are multiple possibilities here from static binary trees (holding neighbour lists, or neighbours directly) to balanced binary search trees (e.g. treap). These will solve this subtask, but will struggle to gain full marks for the problem due to exceeding memory constraints: the static versions have a high complexity ($$$O(ND + U\log(ND))$$$ space, or worse), and the BST version has very high constants (both in space and time).
One segment tree
We need to find when each edge is present in the graph. For each edge, this is the union of contiguous intervals. In total, we have at most $$$U$$$ intervals.
Take a segment tree of length $$$U$$$, with one leaf per version. Each node will contain a vector of edges, ordered by starting node (edge $$$e$$$ is stored in the tree node for $$$[a,b]$$$, if edge is present in each version during the interval $$$[a,b]$$$ – and not entirely present in the parent's interval). This has a combined space requirement of $$$O(U\log(U))$$$. For each question, we look up edges starting from $$$X$$$ and $$$Y$$$ using binary search in the vector of each of the $$$\log U$$$ relevant tree nodes.
This can be implemented in $$$O(U\log^2(U) + Q\log^2(U) + QD\log(D))$$$ time and $$$O(U\log U)$$$ space. With a few tricks and an efficient implementation, this solution could possibly pass subtask 6.
Subtask 6
No additional constraints
Save neighbour list by node, reduce storage space by constant factor
Clearly, saving each version of the neighbour lists of each node will not fit in memory for these limits. However, since memory limits are very generous, we can cut this down by a reasonably small constant $$$C$$$: we only save the neighbour list of node $$$u$$$ after every $$$C$$$'th update that affects $$$u$$$. We also save an ordered list of updates affecting each node. For each question, we only need to replay at most $$$2C$$$ updates ($$$C$$$ for $$$X$$$ and $$$C$$$ for $$$Y$$$). Choosing $$$C\approx 50$$$ will suffice the pass every subtask. The time complexity is $$$O(U\log D + \frac{UD}{C} + Q(D+C\log C))$$$, using $$$O(\frac{UD}{C})$$$ memory.
We think this solution is interesting in the sense that it demonstrates how big-$$$O$$$ complexity can often be misleading for real-world problems: this solution is far simpler than other solutions, some of which do not even gain $$$100$$$ marks, and it passes the limits because the constants involved (normally hidden by big-$$$O$$$ complexity classes) are far smaller.
Multiple segment trees
We can eliminate the binary search from the previous segment tree solution, by keeping a separate segment tree for each node. Na"ively, this will not fit in the memory limits. However, we can save space by only keeping a leaf for each update where the given node was affected. This yields a solution in $$$O(U\log(U) + Q\log(U) + QD\log(D))$$$ time and $$$O(U\log(U))$$$ space.