我试图在SPOJ上解决这个问题:http: //www.spoj.com/problems/DQUERY/
但经过几个小时的尝试解决后,我搜索了一个可能的提示.我找到了一种方法:http : //apps.topcoder.com/forums/;jsessionid=5A69961AF7DF7FBB00FDFE13B80B5D2E?module=Thread&threadID=627423&start=0&mc=13
但我无法正确理解它.任何人都可以帮助我理解这种方法.
查询[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(Binary Indexed Tree aka Fenwick Tree).
但首先我们必须把事件整理好.什么事？事件是某个位置上的数字(所以一对(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_position 2并且它是空的,所以我们将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).所以我们更新树[13] + = 1(第一个树[]全是0).我们向上移动到包含5..5的间隔,并且它是4..5,索引楼层(13/2)= 6(从链接的图片上查看).我们也必须更新它,所以我们做树[6] =树[2*6 = 12] +树[2*6 + 1 = 13].然后:树[6/2 = 3] = 1,树[3/2 = 1] = 1然后我们有1/2 = 0所以我们停止(正如我所说 - 我们从1开始计算索引,所以当我们有0时我们走出了循环).添加数字的时间是logaritmic(每次除以2的数字).我们可以用同样的方法从树中减去一个数字.只需减去1而不是添加它.
查询:我们可以在logaritmic时间内检查区间a..b中有多少个数字.我们对数字> = a感兴趣所以结果是查询(max)-query(a-1).在我们的情况下,Max等于n,因为我们在树中保持位置,它们来自范围1..n.所以我们对查询(n,a-1)感兴趣.如何计算查询？首先添加n和a-1数字2 ^ 3(范围1..x)以获得间隔n..n和a-1..a-1.然后我们将树[a](其中a = a-1)或树[b](其中b = n)添加到结果中,而a = = b.如果%2 = 0则a是正确的孩子,我们添加它.另外b%2 = 1然后b是左孩子.我们对b的左边孩子感兴趣,否则他们会比b大,所以他们会超出范围.同样的.a的左孩子超出范围.
您可以在链接中查看查询和插入的代码.
如果您有任何疑问 - 请问.