Question 1785

Divided Over Time

CDQ divide and conquer: what shape of problem, and what bound?

A

Offline problems where you sort on one dimension, recurse, and let the left half's modifications apply to the right half's queries. Three-dimensional dominance counting is the canonical case, at O(nlog⁡n)O(n \log n) with a sorted merge for the third dimension.

B

Offline problems where you sort on one dimension, recurse, and let the left half's modifications apply to the right half's queries. Three-dimensional dominance counting is the canonical case, at O(nlog⁡2n)O(n \log^2 n) with a Fenwick tree for the third dimension.

C

Online problems where you sort on one dimension, recurse, and let the left half's modifications apply to the right half's queries. Three-dimensional dominance counting is the canonical case, at O(nlog⁡2n)O(n \log^2 n) with a Fenwick tree for the third dimension.

D

Offline problems where you sort on one dimension, recurse, and let the right half's modifications apply to the left half's queries. Three-dimensional dominance counting is the canonical case, at O(nlog⁡2n)O(n \log^2 n) with a Fenwick tree for the third dimension.