Hello Codeforces,↵
↵
Recently I was solving some more problems and came across [IPSC 2015 G, Generating Synergy](https://ipsc.ksp.sk/2015/real/problems/g.html). I think the problem and my alternative solution are pretty cool.↵
↵
TLDR: Store decreasing `maxdepth` monostack in each segtree node, for query, binary search $log N$ monostacks and get maximum update.↵
↵
Abridged problem version:↵
You are given a tree of $N$ nodes, rooted at node $1$. Initially, the value of all nodes is $1$. Handle $Q$ operations of 2 possible types:↵
↵
- Update all nodes in subtree of node $a$ and depth $\le dep_a + l$ with value c. $dep_a$ (depth of node a) is defined to be number of nodes on the path from node $a$ to root node. So the root has depth $1$, the root's direct children have depth $2$...etc... ↵
- Find the value of node $a$.↵
↵
We first apply [Euler Tour Technique](https://usaco.guide/gold/tree-euler). Then the original update operation is represented by updating all positions in $[tin_a, tout_a]$ with depth $\le dep_a + l$ (in other words, a `maxdepth` of $dep_a + l$), the query operation is to find value of position $tin_a$. ↵
↵
Then, let's try to incorporate segment tree (after all, this problem is basically Range Update Point Query). From now, we refer to nodes in the original tree as "positions" to avoid confusion with nodes in the segment tree. Each segment tree node will represent a range of positions, to do this we store in each node a resizable array (like `std::vector`). ↵
↵
For updates we "push" the update information to $O(log N)$ nodes. ↵
↵
For queries, we are tasked with finding the **LRU** (latest relevant update) of some position $a$. In other words, the latest update which changes the value of position $a$, i.e. has a `maxdepth` $>= dep_a$ and has been pushed to a segment tree node which contains $a$ (any update that has a chance of changing value of $a$ must have been pushed to a segtree node which contains position $a$.). There are ~$log N$ such nodes.↵
↵
For each query you can independently find the **LRU** of each of the $log N$ nodes and then get the latest one. For each node, iterate through all updates pushed to that node and check their `maxdepth`. Then maximum time of the updates that satisfy the `maxdepth` constraint is the **LRU** for that node. But this approach is too slow :(↵
↵
**However!**↵
↵
When pushing an update to some segtree node, we know that all preexisting updates (in that node) with a $\le$ `maxdepth` will never be the **LRU** (it is trivial to prove this by contradiction). In other words, the only way a previous update can be the **LRU** is if it has a strictly greater `maxdepth` than our current update. So we can delete all updates that don't have a strictly greater `maxdepth`. Provided we push updates to the back of the node's `std::vector`, it is also trivial to prove by induction that the updates we can delete will form a suffix of this `vector` (the invariant is that $maxdepth_{v_1} > maxdepth_{v_2} > maxdepth_{v_3}...$). Another invariant is $time_{v_1} < time_{v_2} < time_{v_3}...$, because later updates are pushed to the back, after earlier updates. ↵
↵
Basically, in each segment tree node we will maintain a *monotonic stack* sorted by decreasing order of `maxdepth` and increasing order of time. We push $O(QlogN)$ updates to nodes. $O(logN)$ times for each update. Since each pushed update is deleted at most once, we delete $O(QlogN)$ updates. In total, time complexity of updates is $O(QlogN)$. ↵
↵
*The final observation:*↵
↵
With respect to a query position $a$ and a segtree node $x$ (which represents a range that contains $a$), the LRU of $x$ is the last update in `std::vector` of $x$ such that the update has a `maxdepth` $\ge dep_{a}$. Any updates after that will not be relevant to $a$ (`maxdepth too small`), and any updates before are relevant, but not the latest.↵
↵
Because the `std::vector` is already sorted by `maxdepth`, you can binary search it to findaforementionedthe node's LRU. You need to find the LRU of $log N$ nodes for each query, so each query is completed in $O(log Q) * O(log N)$ which is $O(log^{2}N)$.↵
↵
Our time complexity is $O(QlogN) + O(Qlog^{2}N)$ which is $O(Nlog^{2}N)$.↵
↵
*P.S: Thank you for reading my 2nd Codeforces blog post. I'm still learning the style of solution blogs around here, so if I overexplained something or didn't explain something well enough, please tell me in the comments. Other feedback is also greatly appreciated. Have a nice day :)*↵
↵
Further reading: [Official editorial, which uses 2D Segment Tree](https://ipsc.ksp.sk/2015/real/solutions/g.html)
↵
Recently I was solving some more problems and came across [IPSC 2015 G, Generating Synergy](https://ipsc.ksp.sk/2015/real/problems/g.html). I think the problem and my alternative solution are pretty cool.↵
↵
TLDR: Store decreasing `maxdepth` monostack in each segtree node, for query, binary search $log N$ monostacks and get maximum update.↵
↵
Abridged problem version:↵
You are given a tree of $N$ nodes, rooted at node $1$. Initially, the value of all nodes is $1$. Handle $Q$ operations of 2 possible types:↵
↵
- Update all nodes in subtree of node $a$ and depth $\le dep_a + l$ with value c. $dep_a$ (depth of node a) is defined to be number of nodes on the path from node $a$ to root node. So the root has depth $1$, the root's direct children have depth $2$...etc... ↵
- Find the value of node $a$.↵
↵
We first apply [Euler Tour Technique](https://usaco.guide/gold/tree-euler). Then the original update operation is represented by updating all positions in $[tin_a, tout_a]$ with depth $\le dep_a + l$ (in other words, a `maxdepth` of $dep_a + l$), the query operation is to find value of position $tin_a$. ↵
↵
Then, let's try to incorporate segment tree (after all, this problem is basically Range Update Point Query). From now, we refer to nodes in the original tree as "positions" to avoid confusion with nodes in the segment tree. Each segment tree node will represent a range of positions, to do this we store in each node a resizable array (like `std::vector`). ↵
↵
For updates we "push" the update information to $O(log N)$ nodes. ↵
↵
For queries, we are tasked with finding the **LRU** (latest relevant update) of some position $a$. In other words, the latest update which changes the value of position $a$, i.e. has a `maxdepth` $>= dep_a$ and has been pushed to a segment tree node which contains $a$ (any update that has a chance of changing value of $a$ must have been pushed to a segtree node which contains position $a$.). There are ~$log N$ such nodes.↵
↵
For each query you can independently find the **LRU** of each of the $log N$ nodes and then get the latest one. For each node, iterate through all updates pushed to that node and check their `maxdepth`. Then maximum time of the updates that satisfy the `maxdepth` constraint is the **LRU** for that node. But this approach is too slow :(↵
↵
**However!**↵
↵
When pushing an update to some segtree node, we know that all preexisting updates (in that node) with a $\le$ `maxdepth` will never be the **LRU** (it is trivial to prove this by contradiction). In other words, the only way a previous update can be the **LRU** is if it has a strictly greater `maxdepth` than our current update. So we can delete all updates that don't have a strictly greater `maxdepth`. Provided we push updates to the back of the node's `std::vector`, it is also trivial to prove by induction that the updates we can delete will form a suffix of this `vector` (the invariant is that $maxdepth_{v_1} > maxdepth_{v_2} > maxdepth_{v_3}...$). Another invariant is $time_{v_1} < time_{v_2} < time_{v_3}...$, because later updates are pushed to the back, after earlier updates. ↵
↵
Basically, in each segment tree node we will maintain a *monotonic stack* sorted by decreasing order of `maxdepth` and increasing order of time. We push $O(QlogN)$ updates to nodes. $O(logN)$ times for each update. Since each pushed update is deleted at most once, we delete $O(QlogN)$ updates. In total, time complexity of updates is $O(QlogN)$. ↵
↵
*The final observation:*↵
↵
With respect to a query position $a$ and a segtree node $x$ (which represents a range that contains $a$), the LRU of $x$ is the last update in `std::vector` of $x$ such that the update has a `maxdepth` $\ge dep_{a}$. Any updates after that will not be relevant to $a$ (`maxdepth too small`), and any updates before are relevant, but not the latest.↵
↵
Because the `std::vector` is already sorted by `maxdepth`, you can binary search it to find
↵
Our time complexity is $O(QlogN) + O(Qlog^{2}N)$ which is $O(Nlog^{2}N)$.↵
↵
*P.S: Thank you for reading my 2nd Codeforces blog post. I'm still learning the style of solution blogs around here, so if I overexplained something or didn't explain something well enough, please tell me in the comments. Other feedback is also greatly appreciated. Have a nice day :)*↵
↵
Further reading: [Official editorial, which uses 2D Segment Tree](https://ipsc.ksp.sk/2015/real/solutions/g.html)
