5

我试图在 SPOJ 上解决这个问题： http ://www.spoj.com/problems/DQUERY/

但在尝试解决它几个小时后，我用谷歌搜索了一个可能的提示。我发现这里描述的一种方法：http ://apps.topcoder.com/forums/;jsessionid=5A69961AF7DF7FBB00FDFE13B80B5D2E?module=Thread&threadID=627423&start=0&mc=13

但我无法正确理解它。任何人都可以帮助我理解这种方法。

4

1 回答 1

7

查询 [a, b] 的结果是在 [1, b] 中最后一次出现 >= a 的整数数。

假设我们对示例中的序列有查询 (2;4)：[1, 1, 2, 1, 3]。要从多重集 [1, 2, 1] 中创建一个集合，我们可以计算从 1 到 b 的数字的最后位置，并仅选择 >= a 的那些。所以这个例子中的这些出现是：4（对于 1）和 3（对于 2）。它们都是 >= 2 = a 所以结果是 2。

如何有效地存储所有最后出现的事件并能够快速找到所有 >= a 的事件？在树中（区间树或分段树）。我会使用这里描述的 BIT（二进制索引树又名 Fenwick 树） 。

但首先我们必须按顺序排列事件。什么活动？事件要么是某个位置上的数字（因此是一对 (x;y)，其中 x 是一个数字，y 是一个位置） - NumberEvent - 或者是一个间隔（一对 (a;b)） - QueryEvent。我们必须对查询进行排序。首先，我们应该考虑数字，因为不将它们添加到树查询中是没有意义的。所以我们想从第一个位置开始（所以我们按位置 - y 对 NumberEvents 进行排序）。在第一个位置有 1。我们记得 last_position 1 = 1，我们将位置 1 添加到树中。接下来我们在位置 2 上有 1。我们检查 last_position 1并且它不是空的，所以我们从树中删除位置 1，将位置 2 添加到树中并更新 last_position 1 = 2。接下来我们在位置 3 上有 2。我们检查 last_position2并且它是空的，所以我们有 last_position 2 = 3 并且我们将 3 添加到树中。接下来我们在位置 4 上有 1。我们从树中删除位置 2，添加 4 并更新 last_position 1 = 4。现在有些不同了。我们看到我们有一个 b=4 的查询，我们考虑了位置 [1;b] 的所有数字。唯一剩下的就是我们计算树中 >= a=2 的位置。其中有 2 个：3、4。我们记得对于 (2;4)，结果是 2（我们必须以良好的顺序打印它，所以我将查询而不是 (2;4) 记住为 (2 ;4;2) 因为它是第二个查询，最后我会打印从 1 到 q) 的所有查询。就是这样。因此，排序后的查询是：

1 1 NumberEvent [number;position]
1 2 NumberEvent
2 3 NumberEvent
1 4 NumberEvent
2 4 QueryEvent [a;b] or [i;j] from the task - sorted by b
3 5 NumberEvent
1 5 QueryEvent
3 5 QuertEvent

排序和连接所有 q+n 个查询需要 (q+n)log(q+n) 时间。然后，对于每个 q+n 查询，我们使用 log(n) 时间（因为树中最多有 n 个数字）。整体复杂度为 O((q+n)log(q+n))。

至于对树的操作。

我将根据这个波兰网站进行描述。有很好的图像和代码。

索引：如果我们想要为范围为 0..x 的数字创建区间树，我们必须首先将 x 取整到 2 的幂减去 1。因此对于 x=5，我们将 x 更改为 2^3-1=7。间隔就像链接中的图像一样。例如，对于范围 0..7 和区间 4..5，它的索引是 6（我们从 1 开始计数，而不是 0）。

加/减值​​：假设我们要添加到范围为 0..7 数字 5 的树。区间的 5..5 索引为 5+2^3=13（因为我们有范围为 0..2^3 的值-1)。所以我们更新 tree[13]+=1 （第一个 tree[] 都是 0）。我们向上移动到包含 5..5 的区间，它是 4..5，索引层 (13/2)=6（在链接中的图片上查看）。我们也必须更新它，所以我们执行 tree[6]=tree[2*6=12]+tree[2*6+1=13]。然后： tree[6/2=3]=1, tree[3/2=1]=1 然后我们有 1/2=0 所以我们停止（正如我所说 - 我们从 1 开始计算索引，所以当我们有 0我们摆脱了循环）。添加一个数字的时间是对数的（我们每次将数字除以 2）。我们可以用同样的方法从树中减去一个数。只需减去 1 而不是添加它。

查询：我们可以在对数时间内检查区间 a..b 中有多少个数字。我们对数字 >=a 感兴趣，所以结果是 query(max)-query(a-1)。在我们的例子中，Max 等于 n，因为我们在树中保留位置，它们的范围是 1..n。所以我们对查询（n，a-1）感兴趣。如何计算查询？首先添加到 n 和 a-1 数字 2^3（对于范围 1..x）以获得间隔 n..n 和 a-1..a-1。然后我们将 tree[a]（其中 a=a-1）或 tree[b]（其中 b=n）添加到结果中，而 a!=b。如果 a%2=0 则 a 是正确的孩子，我们添加它。同样 b%2=1 然后 b 是左孩子。我们对 b 的左孩子感兴趣，因为否则它们会大于 b，因此它们会超出范围。与a相同。a 的左孩子超出范围。

您可以在链接中查看查询代码和插入代码。

如果您有任何疑问 - 问。

于 2013-09-01T01:09:44.063 回答