0

我想用段树来解决 Joseph Flavius 问题。我几乎可以肯定，简单的模拟（即行列表）是O(n^2). 我想要实现的是在特定距离的数组上跳跃，取自段树。换句话说，段树将保留有关已删除元素数量的信息，并从树中获取一些信息将允许在 O(1) 中找到下一个要删除的元素。问题是我不知道如何在段树中存储信息以使其适用于 Joseph Flavius 问题。

每个节点中保留了某种额外的值？但是如何查询下一个元素呢？

4

1 回答 1

0

我的第一个想法是二分搜索+总和的sement树给O（log ^ 2（n））

从 L 跳转到 R 具有以下性质：

R - L + 1 - sum(L, R) == skip_value

您可以使用 bin-search 轻松找到具有此属性的 R。当你绕一个完整的圈子时，它会变得有点复杂，但我相信你明白了。

如果有任何不清楚的地方，请随时询问。

（我也会考虑 log(n) 解决方案）

于 2020-11-05T22:15:17.480 回答