Official

V - 連結性 2/Connectivity 2 Editorial by maspy

This editorial uses \(0\)-based indexing.

[1] A connectivity decision problem

First, consider the following decision problem:

Decision problem

Answer \(Q\) queries. Each query gives \(L,R\); determine whether \([L,R]\) is good.

For a subgraph of a tree, the following holds:

  • If \(C\) is the number of connected components, \(V\) the number of vertices, and \(E\) the number of edges, then \(C=V-E\).

Write \(C[L,R]\) for the number of connected components in \([L,R]\).

Consider computing \(C[L,R]\) for various intervals \([L,R]\). When the queries are offline, we can use the following approach:

  • Move the right endpoint \(R\) in the order \(R=0,1,2,\ldots\) and process queries in that order.
  • At each point, maintain information corresponding to the sequence \(C_R = (C[0,R],C[1,R],\ldots,C[R,R])\) in a data structure to answer the queries.

Let us examine what we need to apply this approach. To obtain \(C_R\) from \(C_{R-1}\):

  • Add \(1\), the change in the number of vertices, to the whole sequence.
  • For each edge \(vR\) (\(v < R\)), subtract \(1\), the change in the number of edges, from entries \(0\) through \(v\) of \(C_R\).
  • Append the last entry \(C[R,R]=1\) to the sequence.

Appending an entry can be treated as an update to \(1\) element by using a sequence of length \(N\) initialized with suitable values marking unused entries. Thus, the decision problem can be expressed using \(O(N)\) range additions.

An alternative derivation Above, we computed the number of connected components from the numbers of vertices and edges. Another approach is to treat the tree as rooted and count the LCAs of the connected components. In other words, interpreting the number of connected components as “the number of vertices $v$ for which $v$ is included while $\mathrm{parent}[v]$ is not included” gives a similar solution.

[2] Reducing the original problem to range queries

Keeping the decision problem in [1] in mind, let us consider the original problem. Define a sequence \(D\) as follows:

  • \(D[i]\): The number of times \(C[i,R]=1\) has held up to the current processing point. In other words, the number of \(j\) such that \(i\leq j\leq R\) and \(C[i,j]=1\).

Then the answer to query \((L,R)\) is the range sum \(D[L] + \cdots + D[R]\).

Thus, we can decompose this problem into the following range queries:

  • 1 L R x: Add \(x\) to \(C[L],\ldots,C[R]\).
  • 2: Add \(1\) to \(D[i]\) for every \(i\) such that \(C[i]=1\). All entries of \(C\) are at least \(1\) when this query is processed.
  • 3 L R: Find \(D[L]+\cdots+D[R]\).

The solution below implements these range queries with a lazy segment tree. If you would like to practice segment trees, you may want to try working out the rest yourself using the explanation so far.

[3] A solution using a lazy segment tree

Designing the operator monoid

We have the following types of range actions on \((C,D)=(C[i],D[i])\):

  • F_x: Add \(x\) to \(C\).
  • G: If \(C=1\), add \(1\) to \(D\). It is guaranteed that \(C\geq 1\) when this action is performed.

Consider whether compositions of these \(2\) types of actions can be represented with \(O(1)\) information. For example, consider the following sequence of actions:

  • Example: \(F_2, G, F_{-3}, G, F_3, F_{-2}, G, F_{-1}, G, F_1, F_2, G\)

First, consecutive actions \(F_x\) and \(F_y\) can be combined into \(F_{x+y}\). Also, we can ignore \(G\) except when \(C\) could be at its minimum value over this series of actions. In the example above, writing \(C_0\) for the initial value of \(C\), \(G\) is called when the value is \(C_0+2,C_0-1,C_0,C_0-1,C_0+2\).

Ignoring all calls to \(G\) except those at the minimum, and combining consecutive actions \(F_x, F_y\), compresses the example into:

  • Compressed example: \(F_{-1}, G, G, F_3\)

Continuing this reasoning shows that every composition of actions can be written in the following form \((a,b,c)\), where \(a,b,c\) are nonnegative integers:

  • Subtract \(a\) from \(C\). Then, if \(C=1\), add \(b\) to \(D\). Finally, add \(c\) to \(C\).

Verifying that the composition of actions of this form can also be written in this form, and implementing it, are left as exercises.

Interval information in the segment tree

The information we ultimately want is the sum of \(D[i]\) over an interval. However, this alone is insufficient to apply the actions of the operator monoid defined above.

Instead, maintain the following \(3\) values:

  • \(\mathrm{sum}\): The sum of \(D[i]\) over the interval.
  • \(\mathrm{min}\): The minimum of \(C[i]\) over the interval.
  • \(\mathrm{mincnt}\): The number of indices \(i\) in the interval at which \(C[i]\) attains its minimum.

Merging interval information and applying operators to it follow naturally from these definitions, so we omit the details.

[4] Sample solution

posted:
last update: