Recently, the following problem was presented at the school BSUIR OPEN XIII:
Given an array of integers and point update queries. After each such query, you need to respond online: how many pairs $$$i, j$$$ exist that yield the maximum possible sum and are at a distance of no more than $$$k$$$.
Without online processing — this is almost a classic problem from the Canadian Olympiad for school students (solvable using DCP-offline), but we will learn to do it online. Essentially, I want to learn how to create a data structure that can account for each such pair exactly once. Personally, I can do it in $$$O(\log n)$$$ per query.
Let's complete the segment tree to a power of two (otherwise it won't work). Then we will have some number of levels, and at each level, we will have the same number of nodes. For convenience, let $$$l_v, r_v$$$ denote the segment that the subtree is responsible for, and let $$$lvl_{i, j}$$$ denote the node at level $$$i$$$ with number $$$j$$$ (the nodes at the same level are ordered by the increasing right boundary). We will also calculate $$$nxt_v$$$ — the last node at the level of node $$$v$$$ for which $$$r_{nxt} - r_v \leq k$$$ (in other words, this is the farthest node at the level for which any pair from these subtrees forms a suitable pair).
Then the statement is that it is sufficient to consider all pairs in the following subtrees:
For each node $$$v$$$, we say that the answer for it is the maximum of the answers from the left/right subtree, and also consider the optimum in pairs of subtrees $$$v, nxt_v$$$, as well as $$$v, 'nxt_v$$$, where $$$ 'nxt_v$$$ is the first node to the left at the level of $$$nxt_v$$$. We also take two optimums for the subtree of size $$$\leq k$$$.
Now, how to account for each pair exactly once — we will not merge two nodes if their ancestors also fit (that is, the maximum distance between pairs of nodes will be less than or equal to $$$k$$$). This fact is already obvious.
Proof: it passes stress tests, which means it is correct. Since the sizes of all trees are powers of two, and the condition is the same everywhere, this recount will only occur at one level (when we consider that if the ancestors fit, we do not account for this pair). In this case, at most $$$3$$$ nodes at this level will be involved. (Otherwise, their ancestors would also be relevant). In this case, this algorithm will indeed account for each pair exactly once, as these will be all relevant pairs. The uniqueness is obvious, so I will leave it for the reader to prove.
We have learned to account for each pair exactly once. Now we need to learn how to update with point changes. Let's note that when changing a node, the answer will only change for its ancestors, which is trivial to do, as well as for the nodes for which our node was one of the two right ones. We can easily precompute these nodes. Therefore, we need to recount the answer for them and then recursively update their parents. Given that we also need to update the parents, it results in $$$O(\log^2)$$$ (and it is quite long, as the recounting code itself is quite heavy). (Alternatively, if we carefully look at the proof, not many interesting nodes of the segment tree will change, resulting in $$$O(\log)$$$, but below is an implementation that runs in $$$O(\log^2)$$$).
getting rid of that negative contribution i see :)
wth is DCP offline?
It's "dynamic connectivity problem offline". But in the context of this blog it means the idea of that solution of the dynamic connectivity problem (in short: build a segment tree on the times of the queries where in each vertex [tl, tr] you store the edges that are alive in this segment) not the problem itself. You can also read about the general technique here.
cool, thanks
This is not a dcp, but an online solution to this problem :)