IOI预选赛INOI任务2 [英] IOI Qualifier INOI task 2

问题描述

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

I can't figure out how to solve question 2 in the following link in an efficient manner: http://www.iarcs.org.in/inoi/2012/inoi2012/inoi2012-qpaper.pdf

推荐答案

您可以做这在日志n）的时间。 （或直线，如果你真的关心。）首先，键盘输入数组出两个使用一些非常大的负数的下一个动力。现在，建设周期树状数据结构;通过递归划分它在半隔断的阵列。在树重新$ P $每个节点psents一个子阵列，它的长度是二的幂并且开始在一个位置上其长度的倍数，并且每个非叶节点具有左半子和一个右半孩子。

You can do this in On log n) time. (Or linear if you really care to.) First, pad the input array out to the next power of two using some really big negative number. Now, build an interval tree-like data structure; recursively partition your array by dividing it in half. Each node in the tree represents a subarray whose length is a power of two and which begins at a position that is a multiple of its length, and each nonleaf node has a "left half" child and a "right half" child.

计算，为树中的每个节点，什么时候你 0,1,2,3，... 添加到该子阵列，并采取最大元素发生。请注意，这是平凡的叶子，从而重新长度为1的present子阵列内部节点，这简直是左子长度/ 2 +右子的最大值。所以，你可以在线性时间建造这棵树。

Compute, for each node in your tree, what happens when you add 0,1,2,3,... to that subarray and take the maximum element. Notice that this is trivial for the leaves, which represent subarrays of length 1. For internal nodes, this is simply the maximum of the left child with length/2 + right child. So you can build this tree in linear time.

现在，我们想在这棵树运行 N 查询序列，并打印出答案。该查询的形式为如果我添加 K，K + 1，K + 2，...，N，1，...，K-1 来会发生什么该阵列并报告最大？

Now we want to run a sequence of n queries on this tree and print out the answers. The queries are of the form "what happens if I add k,k+1,k+2,...n,1,...,k-1 to the array and report the maximum?"

注意的是，当我们添加序列与整个阵列，n和1之间的断裂或者出现在开始/结束，或嫌在中间，或介于左半边，或在右半某处。因此，划分数组复制到 K，K + 1，K + 2，...，N 部分和 1,2，... ，K-1 部分。如果您发现该重新present子阵躺在完全内的两个序列中的一个，但他们的父母要么不存在，或跨越断点树中的所有节点上，您将有O（log n）的节点。你需要看看他们的价值观，添加各种常量和取最大值。因此，每个查询需要O（log n）的时间。

Notice that, when we add that sequence to the whole array, the break between n and 1 either occurs at the beginning/end, or smack in the middle, or somewhere in the left half, or somewhere in the right half. So, partition the array into the k,k+1,k+2,...,n part and the 1,2,...,k-1 part. If you identify all of the nodes in the tree that represent subarrays lying completely inside one of the two sequences but whose parents either don't exist or straddle the break-point, you will have O(log n) nodes. You need to look at their values, add various constants, and take the maximum. So each query takes O(log n) time.

这篇关于IOI预选赛INOI任务2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！