Editorial for Dream and the Multiverse

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: TechnobladeNeverDies

This problem effectively asks us to support queries of an arbitrary subrectangle of the transitive closure of the given DAG.

Consider how we would solve the problem if there were only one query of the form $[1,n]$ ~[1,n]~. We will use an array of $n$ ~n~ bitsets:

The $j$ ~j~-th element of the $i$ ~i~-th bitset is $1$ ~1~ if, and only if, there exists a path from $i$ ~i~ to $j$ ~j~.
The $i$ ~i~-th element of the $i$ ~i~-th bitset is always $1$ ~1~.
The $i$ ~i~-th bitset is formed by taking the bitwise OR of all its adjacent nodes, in topological order.

The time complexity of this is $\mathcal O((n+m)\frac nw)$ ~\mathcal O((n+m)\frac nw)~, with a space complexity of $\mathcal O(n^2/w)$ ~\mathcal O(n^2/w)~. We can reduce the space complexity to linear by processing the nodes in chunks of length $w$ ~w~, that is, only storing the nodes in $[64k,64k+63]$ ~[64k,64k+63]~ that any node can reach, and iterating through $k$ ~k~.

Consider how to extend this to interval queries. If we query $[l,r]$ ~[l,r]~, then we want the number of 1's in the subrectangle formed with opposite corners $(l,l)$ ~(l,l)~ and $(r,r)$ ~(r,r)~. Keeping in mind the chunk borders, we can separate the subrectangle into seven regions:

    |    |    |
 aaa|dddd|dddd|eee
 aaa|dddd|dddd|eee
 aaa|dddd|dddd|eee
====+====+====+====
 bbb|dddd|dddd|fff
 bbb|dddd|dddd|fff
 bbb|dddd|dddd|fff
 bbb|dddd|dddd|fff
====+====+====+====
 bbb|dddd|dddd|fff
 bbb|dddd|dddd|fff
 bbb|dddd|dddd|fff
 bbb|dddd|dddd|fff
====+====+====+====
 ccc|dddd|dddd|ggg
 ccc|dddd|dddd|ggg
 ccc|dddd|dddd|ggg
    |    |    |

The number of $1$ ~1~'s in the regions $a,c,e,g$ ~a,c,e,g~ can be calculated with one popcount loop each, contributing $\mathcal O(w)$ ~\mathcal O(w)~ to the time complexity.

Consider what happens when we shrink each chunk into one element, whose number of $1$ ~1~'s is easily calculated by a popcount per element:

 | | |
 |d|d|
 |d|d|
 |d|d|
-+-+-+-
 |d|d|
 |d|d|
 |d|d|
 |d|d|
-+-+-+-
 |d|d|
 |d|d|
 |d|d|
 |d|d|
-+-+-+-
 |d|d|
 |d|d|
 |d|d|
 | | |

To calculate the number of $1$ ~1~'s in the $d$ ~d~ region, we do a two-dimensional prefix sum on the popcount of each row of each chunk, contributing $\mathcal O(1)$ ~\mathcal O(1)~ to the time complexity.

Lastly, we need to deal with $b$ ~b~ and $f$ ~f~. We can't calculate them directly, but we can transpose the graph - and along with it the transitive closure matrix - and then deal with them in the same way we deal with $d$ ~d~'s.

The total time complexity is $\mathcal O((n+m)n/w+qw)$ ~\mathcal O((n+m)n/w+qw)~ with linear memory usage.

Comments

There are no comments at the moment.