E - Sliding Edge on Torus Editorial by evima
After a coordinate transformation \((i,\ j) \rightarrow (i-j,\ j)\), each query spans edges between \((u_i,\ k)\) and \((v_i,\ k+p_i)\) for integers \(u_i,\ v_i,\ p_i\). We can then apply another coordinate transformation \((i,\ j) \rightarrow (i,\ j+h_i)\) for an integer sequence \(h=(h_1,\ h_2,\ \dots,\ h_N)\) without affecting the contents of queries (in other words, we may shift each row horizontally).
Let us take \(h\) so that the following is satisfied.
- \(p_i=0\) if \((u_i,\ j)\) and \((v_i,\ j')\) are disconnected for every \(0 \le j,\ j' < N\) just before the \(i\)-th query \((u_i,\ v_i,\ p_i)\) adds edges.
This condition can be written as \(h_{u_i}-h_{v_i}=p'_i\) for \((u_i,\ v_i)\) in those queries. The graph with \(N\) vertices and those edges \((u_i,\ v_i)\) will be a forest, so such \(h\) always exists.
For a query \((u_i,\ v_i,\ p_i)\) that is not among the above ones, \((u_i,\ k)\) and \((v_i,\ k)\) will be already connected when adding edges, so we may assume that it adds edges between \((u_i,\ k)\) and \((u_i,\ k+p_i)\) instead.
As a result, after taking an appropriate \(h\), we have two kinds of queries:
- those that add edges between \((u_i,\ k)\) and \((v_i,\ k)\),
- those that add edges between \((u_i,\ k)\) and \((u_i,\ k+p_i)\).
After processing just the queries of the first kind, each column will have the graph \(G_{row}\): the part of \(G\) in the first column. If we then process queries of the second kind, the \(N\) columns for each connected component in \(G_{row}\) will merge into \(g\) connected components, where \(g\) is the greatest common divisor of \(N\) and the \(p_i\)’s in relevant queries.
Thus, after determining \(h\), we can process the queries by maintaining the following:
- the graph \(G_{row}\), the part of \(G\) in the first column,
- a sequence \(g\), containing the number of connected components corresponding to each connected component in \(G_{row}\),
in \(O((N+Q)\log N)\) time, using tools such as dsu.
posted:
last update: