algorithm - IOI 预选赛 INOI 任务 2

Question

我不知道如何有效地解决以下链接中的问题 2: http://www.iarcs.org.in/inoi/2012/inoi2012/inoi2012-qpaper.pdf

Answer 1

您可以在 On log n) 时间内完成此操作。 (或者线性，如果你真的很在意的话。)首先，使用一些非常大的负数将输入数组填充到 2 的下一个幂。现在，构建一个区间树状的数据结构；通过将数组分成两半来递归地对数组进行分区。树中的每个节点代表一个子数组，其长度是 2 的幂并且开始于其长度的倍数的位置，并且每个非叶节点都有一个“左半”子节点和一个“右半”子节点。

计算，对于树中的每个节点，当您将 0,1,2,3,... 添加到该子数组并获取最大元素时会发生什么。请注意，这对于表示长度为 1 的子数组的叶子来说是微不足道的。对于内部节点，这只是长度为/2 + 右 child 的左 child 的最大值。所以你可以在线性时间内构建这棵树。

现在我们要在这棵树上运行一系列 n 查询并打印出答案。查询的形式是“如果我将 k,k+1,k+2,...n,1,...,k-1 添加到数组并报告最大值会发生什么？”

请注意，当我们将该序列添加到整个数组时，n 和 1 之间的中断要么出现在开头/结尾，要么出现在中间，要么出现在左半部分的某个位置，要么出现在右半部分的某个位置。因此，将数组划分为 k,k+1,k+2,...,n 部分和 1,2,...,k-1部分。如果您识别树中的所有节点，这些节点表示完全位于两个序列之一内但其父节点不存在或跨越断点的子数组，则您将拥有 O(log n) 个节点。您需要查看它们的值，添加各种常数，然后取最大值。所以每次查询都需要 O(log n) 时间。