UVA - 1394 :有一个算法

Question

问题的链接是UVA - 1394 :有一个。

朴素算法是扫描整个数组并在每次迭代中标记kth元素，最后停止:这需要O(n^2)时间。

我搜索了另一种算法，并遇到了一个中文博客，它将段树作为O(N lgN)时间的一种解决方案。

在研究了分段树之后，我尝试在O(N lgN)时间内形成一个算法，但没有结果。

我的问题是：

1. 是否可以使用段树来获得所需的运行时间？
2. 如果是的话，教我如何使用它们。
3. 段树和" zkw“段树是一样的吗？-他在博客中提到了zkw段树。

更新：上面的问题是约瑟夫斯问题的一个例子。

​

Answer 1

1. 是的可以。
2. 您可以看到下面对数据结构的描述，这里我将提示如何在给定的问题中使用它。我们所代表的人口显然是石头的圆圈。我们从所有的N石头都还活着开始，在每一步杀死我们树中合适的石头。只需要知道我们目前使用的是哪个元素(我认为将其命名为m是合适的)。高级算法(请您详细说明)如下(P是我们的数据结构)： 而P.size > 1: P.toggle(m) //移除第m个石头m=P.kth(下一个要被杀死的石头) 上面的代码中的P.size只是所有剩馀石块的数量。在下面的描述中，它对应于tree1。 注意：数据结构中使用的符号k不同于表示跳转距离的问题输入中的符号。
3. 差不多吧。我以前还没见过这个名字，但是代码看起来和我见过的人口树一样。 人口树是使用分段树的一种简单方法。您有N元素，每个元素都有两种可能的状态:1表示活动，0表示死亡。树支持两个操作：

- Toggle the state of element numbered **i**.
- Return the index of the **k-th** (in size of its index) living element.  

为了澄清第二个操作，假设活元素的集合是{1，2，4，7}。如果N = 8，则对应于状态数组01101001 (元素0是死的，元素1是活动的，元素3是活动的，等等)。

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

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

结论int =1 << 18；// 2^17元素，其余为树大小内的内节点；//节点空节点( int i) { treei + size /2 ^= 1的子树中的活元素数；//切换(i /= 2；i> 0；i /= 2) treei = tree2 *i+ tree2 *i+ 1；

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

要找到k-th活动元素，我们可以递归地考虑:我们目前在节点n，并且正在寻找k-th活动元素的子树(节点的子树是植根于该节点的树)。如果n的左子2n有k或更多的活元素，则设置n =2nE 248。否则，我们显然将转到正确的子节点，即设置为n = 2n+1。在这种情况下，我们不再寻找子树的k-th活动元素。因为我们跳过了左子的所有活元素，所以我们从k中减去了这些元素。为了简单起见，我们来看看基于1的活元素。

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

int kth(int k) { ++k；//因为该方法在根处查看基于元素1的int current_node = 1；// start在根处，而(current_node < size / 2) { if (tree2 * current_node >= k) current_node =2* current_node；//下降到左侧子程序{k -= tree2 * current_node；// fix k current_node =2* current_node + 1；//下降到正确的子}}

这两个函数使段树成为种群树。

这是一个数据结构问题，所以描述的思想使用了一个数据结构。然而，我想提到的是，这个问题被称为约瑟夫斯问题，并且有其他的解决方案，所以你可能有兴趣去查找它。