UVA - 1394:并且有一种算法

Question

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

---

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

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只是所有剩余宝石的数量.在下面的描述中,它对应于树[1].

   注意:数据结构中使用的符号k与表示跳转距离的问题输入中的符号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问题,并且有其他解决方案,所以你可能有兴趣查找它.