hdu 3333 turing tree 解题报告
需积分: 9 41 浏览量
2010-03-10
18:22:30
上传
评论 2
收藏 92KB DOC 举报
0
0 0
0 0 0 0
0 0 0 0 0 0 0 0
Hdu 3333 解题报告
题意描述：
给你 n 个数现在要你求在 k 个区间上[ai, bi]的不相同的数之和各是多少.
N<=30,000; k<=100,000;
显然，这题不能用暴力来做。
这题我们选择用线段数来做。 可是， 我们经常遇到的情况是求一个区间上的数之和，而本
题是要求一个区间上不同的数之和，怎么办呢？一开始我也没想出什么好办法， 后来在网
上看了牛人的代码后才发现原来题目很简单，先用一个例子来说明这个算法吧。
比如说， 给出的 n 个数是 2，4，5，4，5，7， 8，2. 我们用一个数组 num[9]来记录这 8 个
数,num[i]来表示第 i 个数(从 1 开始计数，现在建立如上图所示的线段树，树的各节点包括 5
个值，他们分别是 int a, b, value; node *le#, right;其中 a，b 代表节点线段的左右边界，value
来表示在区间[a, b]上各个不同数之和。le# 和 right 来表示左右子节点的指针。
假设现在要求的区间有 k 个[a1, b1], [a2, b2], ….[ak, bk].将这 k 个区间按 bi 的值大小来排序。
定义两个变量 la, lb. lb = 0; 将第 lb+1 到 b1 的数插入到线段数中遇到前面出现的数，就将前
面出现的数从线段数中取出，然后将其插入。如插入 2，4， 5， 后各节点的值变为
2+4+5，2+4+5， 0， 2+4， 5， 0， 0， 2， 4， 5，0，0，0，0，0.当再插入 4 时现将前面
那个 4 取出。节点的值变为 2+5, 2+5, 0, 2, 5, 0, 0, 2, 0, 5, 0, 0, 0, 0, 0.再插入 4 节点的值为
2+4+5， 2+4+5， 2，4+5，0，0，2，0，4，5，0，0，0，0，0。如此进行下去知道第 b1
个数。然后就来求[a1,b1]的 ans. 在求第二个区间是从 b1+1 开始插入直到 b2,然后求该区间
的 ans，在求第 i+1 个区间时，从 bi + 1 个数开始插入，直到第 b(i+1) 个数。这样就求出 k 个
区间的数值由于每个数插入一次和最多取出一次，所以算法复杂度是 n*logn;
[1， 8]
[1， 4]
[5， 8]
[1
，
2]
[3， 4]
[5， 6] [7， 8]
[1,1]
[2,2]
[3,3]
[4,4]
[5,5]
[6,6] [7,7]
[8,8]
资源评论
michael200892458
- 粉丝: 9
- 资源: 3
