1

该问题的链接是UVA-1394: And There Was One。
朴素的算法是扫描整个数组并在每次迭代中标记第 k 个元素，并在最后一次停止：这需要 O(n^2) 时间。
我已经搜索了一种替代算法，并遇到了一个中文博客，该博客指出我使用惰性传播作为 O(N lgN) 时间的解决方案来分割树。
研究了段树后，我尝试为 O(N lgN) 时间形成算法，但无济于事。

我的问题是：
1. 可以使用分段树来获得所需的运行时间吗？
2. 如果是，请告诉我如何使用它们。
3. 段树和“zkw”段树是一回事吗？- 他在博客中提到了 zkw 段树。
更新：上述问题是约瑟夫斯问题的一个例子。

4

1 回答 1

5

  1. 是的，它可以。

  2. 您可以在下面看到数据结构的描述，这里我将提示如何在给定的问题中使用它。我们所代表的人口显然是石头圈。我们从所有N块石头都活着开始，然后在每一步都杀死我们树上的相应石头。只需要知道我们当前处于哪个元素（我认为将其称为m是合适的）。高级算法（我把细节留给你）如下（P是我们的数据结构）：

    While P.size > 1:
  P.toggle(m) // remove the m-th stone
  m = P.kth(next stone to be killed)

    上面代码中的 P.size 就是所有剩余石头的数量。在下面的描述中，它对应于树[1]。

    注意：数据结构中使用的符号k与问题输入中表示跳跃距离的符号不同。

  3. 差不多。我以前没见过这个名字，但代码看起来和我见过的人们所说的一样人口树。

    人口树是使用线段树的一种简单方法。您有N个元素，每个元素都有两种可能的状态：1 表示活着，0 表示死亡。树支持两种操作：

    • 切换编号为i的元素的状态。
    • 返回第k 个（按其索引大小）活动元素的索引。

    为了阐明第二个操作，假设生活元素的集合是 {1, 2, 4, 7}。如果N = 8，则对应于状态数组 01101001（元素 0 已死亡，元素 1 处于活动状态，元素 3 处于活动状态，依此类推）。

    那么，如何实现呢？像往常一样，树的叶子对应于数组。也就是说，如果第 i 个元素是活动的，则第 i 个叶子的值为 1，否则为 0。每个内部节点都会记住其子节点的值的总和。

    为了切换元素的状态，我们切换相应叶子的值，然后固定从该叶子到根的路径：

    const int size = 1 << 18; // 2^17 elements, the rest are internal nodes
int tree[size]; // number of living elements in the subtree of a node

void toggle(int i) {
  tree[i + size / 2] ^= 1; // toggle the leaf
  for (i /= 2; i > 0; i /= 2)
    tree[i] = tree[2 * i] + tree[2 * i + 1];
}

    注意：标记节点的常用方法是使根等于 1，递归地，节点n的子节点是2n和2n+1。

    要找到第k 个活元素，我们可以递归思考：我们当前在节点n处，并且正在寻找第k 个活元素它的子树（节点的子树是根在该节点的树）。如果n的左孩子2n有k或更多的生活元素，设置n = 2n。否则，我们显然会找到正确的孩子，即设置n = 2n+1。在这种情况下，我们不再寻找子树的第 k 个活元素。因为我们跳过了左孩子的所有生活元素，所以我们从k中减去该计数. 在这里，为了简单起见，我们正在查看基于 1 的生活元素。

    这里的基本思想可能是递归的，但描述暗示迭代地做它也应该很简单：

    int kth(int k) {
  ++k; // because this method looks at elements 1-based
  int current_node = 1; // start at the root
  while (current_node < size / 2) {
    if (tree[2 * current_node] >= k) 
      current_node = 2 * current_node; // descend into the left child
    else {
      k -= tree[2 * current_node]; // fix k
      current_node = 2 * current_node + 1; // descend into the right child
    }
  }
}

    这两个功能使该分段树成为人口树。

这是一个数据结构问题，因此所描述的想法使用了数据结构。但是，我想提一下这个问题被称为Josephus 问题，并且有替代解决方案，因此您可能有兴趣查找它。

于 2013-01-22T17:42:04.047 回答