algorithm - 长波紫外线 - 1394 : And There Was One Algorithm

Question

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

---

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

Answer 1

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 只是所有剩余石头的数量。在下面的描述中，它对应于tree[1]。

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

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-th 个生命元素，我们可以递归地思考:我们目前在节点 n，并且正在寻找其子树的 k-th 事件元素(节点的子树是以该节点为根的树)。如果n的左 child 2n有k个或更多的活元素，设n = 2n 。否则，我们显然会找到正确的 child ，即集合 n = 2n+1。在这种情况下，我们不再寻找子树的第 k 个存活元素。因为我们跳过了左 child 的所有活元素，所以我们从 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 问题，并且有替代解决方案，因此您可能有兴趣查找它。