PROBLEM LINK:Author: Hanlin Ren Tester: Jingbo Shang Editorialist: Hanlin Ren DIFFICULTY:Hard PREREQUISITES:shortest path tree, divide and conquer, heavylight decomposition PROBLEM:You are given an $M\times N$ undirected grid graph. Every edge has a weight that's fixed and used to calculate shortest paths. Every vertex has a weight that's initially $0$. The problem asks you to support two types of operations:
It's guaranteed that for any operation of the first type, the shortest path is unique. QUICK EXPLANATION:We find $K=O(M\log N)$ spanning trees: first we find all shortestpath trees rooted at $(i,\frac{N}{2})$, and recursively find $K'=KM$ trees $TL_1,\dots,TL_{K'}$ for the left grid, and $K'$ trees $TR_1,\dots,TR_{K'}$ for the right grid. Then we combine the $K'$ left trees and $K'$ right trees into $K'$ spanning trees of the whole grid. These trees have a property that every shortest path is described(see below) by some of them. The rest is very easy: for each modification find which tree describes its shortest path, and use heavylight decomposition to maintain these trees. EXPLANATION:subtask 1For any query of the first type, we can use Dijkstra's Algorithm to compute the shortest path, and iterate all vertices on it to update vertex weights. If we use heap to optimize the algorithm, its complexity becomes $O(E\log V)$. The time complexity is $O(MNQ\log MN)$. subtask 2In this subtask $M=1$, so the graph becomes a path. This problem becomes the classical datastructure exercise: add $c$ on one interval or output the value of one vertex. Segment Trees or Fenwick Trees can do the job on $O(N+Q\log N)$. subtask 35The crucial idea for this problem is that, there exists $K=O(M\log N)$ spanning trees $T_1,T_2,\dots,T_K$ of the graph such that, for any two vertices $u,v$, their shortest path is the path between them in $T_i$ for some $i\le K$. In other words, we can use $K$ spanning trees to describe all shortest paths. Note that in this editorial, we say tree $T$ describes the shortest path from $(i_1,j_1)$ to $(i_2,j_2)$, if that shortest path coincides with the simple path from $(i_1,j_1)$ to $(i_2,j_2)$ in $T$. Finding the spanning treesWe use $solve(l,r)$ to denote the procedure that, only consider vertices whose column number is in $[l,r]$, and finds $M\lceil\log_2(rl+1)\rceil$ spanning trees that satisfies the above condition. Let's consider an easier case: for every modification, $j_1\le mid$ and $j_2\ge mid$, where $mid=\lfloor\frac{l+r}{2}\rfloor$. The shortest path between such $(i_1,j_1)$ and $(i_2,j_2)$ must pass some vertex at $(u,mid)$ where $1\le u\le M$. We let $T_i$ be the shortestpath tree rooted at $(i,mid)$. Suppose the shortest path between $(i_1,j_1)$ and $(i_2,j_2)$ passes vertex $(u,mid)$, then this shortest path is described by $T_u$. How about the case that both $j_1,j_2$ are less(greater) than $mid$? Note that in this case, it's still possible that the shortest path passes through some vertex at $(i_0,mid)$. See example below. In this example, blue edges have weight $1$ and all other edges have weight $10^{10}$. However, if the shortest path passes through $(u,mid)$, then we can still use $T_u$ to describe this path. So we can assume that this path doesn't pass through $(*,mid)$. Then we can do things recursively! Let's call $solve(l,mid1)$ and $solve(mid+1,r)$. Suppose $solve(l,mid1)$ returns $K'=M\lceil\log_2(midl)\rceil$ trees $TL_1,TL_2,\dots,TL_{K'}$; $solve(mid+1,r)$ returns $K'$ trees $TR_1,TR_2,\dots,TR_{K'}$. For any pair of vertices $(i_1,j_1)$ and $(i_2,j_2)$, if both $j_1,j_2$ are less than $mid$, then some tree $TL_i$ will contain their shortest path; if both $j_1,j_2$ are greater than $mid$, then some tree $TR_i$ will contain their shortest path. We can combine these trees together: for $TL_i$ and $TR_i$, we find some path in the original grid graph to connect them together, such that they become one tree. We number this tree $T_{i+M}$(note that we already had $M$ trees above), then $T_{i+M}$ can describe all shortest paths that $TL_i$ or $TR_i$ can describe. Since all $TL_i$'s and all $TR_i$'s together can describe all shortest paths that doesn't pass through $(*,mid)$, all $T_i(i>M)$'s also can. And the paths that pass through $(*,mid)$ are described by $T_i(i\le M)$. Our method $solve(l,r)$ just returns all $T_i$'s. The number of trees is the recursion depth multiply $M$, i.e., $O(M\log N)$. To find a shortestpath tree, we can use Dijkstra's Algorithm(use a heap to optimize) and it works on $O(M(rl)\log(M(rl)))$. The complexity for $solve(1,N)$ is $$T(N)=O(M^2N\log(MN))+2T(\frac{N}{2})\implies T(N)=O(M^2N\log^2 N).$$ Performing all queriesOnce we find the trees $T_1,T_2,\dots,T_K(K=O(M\log N))$, the queries become very easy. We can use heavylight decomposition to maintain these trees. We need to perform pathadd operation(add $c$ to all weights of vertices on some path of some tree) and vertexquery operation(output the weight of some vertex on some tree). Also we need HLD to help us querying distances on these trees. For a modification $1\ i_1\ j_1\ i_2\ j_2\ c$, we iterate all trees $T_1,\dots,T_K$ to find which tree describes the shortest path, and perform a path add operation on that tree. For a query $2\ i\ j$, we output the sum of the weights of $(i,j)$ over all trees. The complexity for this part is $O(QM\log^2 N)$. ALTERNATIVE SOLUTION:If your solution is different with ours, feel free to leave a comment. Also, solutions for subtask 3($M=2$) and subtask 4(random data) are welcome! AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:
A bonus problemOriginally this problem was: you're given a grid graph, and support two operations:
However I couldn't get a satisfactory solution. My solution requires $O(\sqrt{N}\log^2 N)$ time per operation, and I'm not sure if it's faster than an optimized brute force, so I made a simpler version. This problem is left as a bouns.
This question is marked "community wiki".
asked 22 Aug '17, 19:09

I have an $(N + Q)\log(N)M^3$ online solution which worked pretty fast (About 1.4 seconds) answered 11 Sep '17, 21:54

Nice approach! I was wondering why my code is so slow before seeing this editorial. It seems that I even did not realize that one should find only O(m log n) spanning trees. I built about $4mn$ trees, more precisely, I built a segment tree with each node associated with $2m$ trees, where each tree is rooted at some boundary vertex (totally $2m$ such vertices for every interval), and only contains all vertices in the interval. Totally about $O(m^2 n \log^2 n)$ operations. For each query, I maintain a $2m \times 2m$ 2darray $d[][]$, where $d[i][j]$ means the minimal distance between some boundary vertex $i$ to some boundary vertex $j$. When updating two interval's information, I choose two intermediate vertex $x$ and $y$, and try such path $i \to x \to y \to j$. Thus we can get information of an interval in $O(m^4 \log n)$ per query. When we get the $d[i][j]$ of an interval, we'll use $d[i][j]$ to backtrace the shortest path, which goes through at most $O(\log n)$ my trees. In each tree, we should play an operation that adds $c$ from some vertex to the root. So we can use tree's DFS order to simplify the problem, and then use a BIT to maintain it. As a result, this step needs $O(m^2 \log^2 n)$ per query. To sum it up, my solution is totally $O(m^2 n \log^2 n + q(m^4 \log n + m^2 \log^2 n))$. Here is my code. However, I think it is the most stupid AC solution to this problem. QAQ... answered 11 Sep '17, 21:45

We don't actually need heavy light decomposition to maintain the trees. The queries we have are: 1) Add x to all nodes on a path from root to a node 2) Find the value of a node. We can convert it to point updates and range queries. We keep a binary indexed tree, and we increase the value at node by x in a query of type 1. Then, in a query of type 2, we find sum in subtree. answered 12 Sep '17, 05:10

It seems that I'm only one who got 'm = 2' and 'random m = 3', but didn't get full problem. My solution for 'm = 2' was based on decomposition of field on blocks of size $M(N /K)$. For each block I had 2M side vertices, for each pair I calculate distances in block with Dijkstra. This part was done in $O(NM^2log(MN/K))$. Let's call minimal path between two side vertices in block 'atomic' if it doesn't contain another side vertex from this block. So we can divide any minimal path between two vertices as set of 'atomic' paths plus paths from start and end to some side vertex in their block. For each pair of side vertices in the same block I stored if path between them is atomic. And for each 'not side' vertex in block I stored which atomic paths contain it. After that I built graph with 2MK vertices, where edges were between
and calculated full distance matrix d[i][j] with Dijkstra runs for each vertex in $O(M^3Klog(M^2K))$. Now update on the path needs next actions:
Query of value for vertex can be done in $O(M^2)$  just need to sum up values, associated with all atomic paths that contain vertex. Total complexity is about $O(NM^2log(MN/K)+M^3Klog(M^2K)+Q_1(MN/Klog(MN/K)+M^2K) + Q_2(M^2)$. I tried several values of K, good balance was found with K = 250 (I coded on Java if it is important). There is link to my 'block' solution (I removed huge template): Code on pastebin answered 12 Sep '17, 11:16

And for any 'm = 3' test my block solution was TL, so for 'random m = 3' I created next solution. Let's call path from (1, 1) to (m, n) as 'main path'. My idea was that with random weights all paths between 'far' vertices will be divided in
So we could run dijkstras from start and end to the 'nearest' vertices and
Query of value in vertex can be done in $O(logMN)$ as query to index in tree (same as for M = 1 too). One more querstion  when is vertex 'nearest'? My dijkstra processed only vertices that were not far than K edges from initial. I got AC with K = 40 (30 was not enough). So total complexity of solution is $O(NMlog(NM)+Q_1(MKlog(MK)+(MK)^2 + log(MN)) + Q_2log(MN))$ There is link to my 'main path' solution (I removed huge template): Code on pastebin answered 12 Sep '17, 11:40

Can anyone tell me why do we are doing the recursion in this case ?? I am unable to find out.. Why we need to recur while we will get the required result from the first tree only....???? why do we need to divided and conquer ?? answered 24 Sep '17, 10:30
