小编Bad*_*adf的帖子

这个问题可以在每个查询的O(n + m)中轻松解决,但是这可以通过比O(n²)更好的预处理来更好地回答这些查询吗？

在树中,可以通过预订和按顺序轻松完成.我在DAG尝试了类似的东西,但它没有任何意义.

我也尝试在DAG问题中将此问题更改为LCA,但在DAG中找到LCA无法快速解决.

准确地说,约束让我们说:

n - 顶点数,最多10 ^ 5

m - 边数,最多10 ^ 5

q - 查询数量,最多10 ^ 5

我正试图解决这个问题.

我找到了这个问题的教程但是我没有得到如何构建分段树,它将在O(log n)中找到小于x的数字(x可以改变).在教程中它已被省略.

任何人都可以解释我该怎么做？