Beyond the Void

发现坐标的范围很大，而点并不是很多，首先想到了离散化的方法。然后横向扫描每个带状的区间，对于每个带状区间，再纵向扫描其中点的个数。这种方法是最容易想到的，但是时间复杂度却高达O(N^2logN)。关键在于优化每次确定带状区间的纵向扫描。

显然对于确定的带状区间，我们扫描时只需考虑它们的纵坐标。如果我们把一个纵坐标为y的点描述成两个事件(y,1)和 (y+h+1,-1)，然后把所有事件按照第一关键字排序，定义S[i]为前i项事件的第二关键字之和，那么Max{S[i]}就是确定的带状区间内高度 为w的矩形最多覆盖到的点数。为什么是这样，我们可以想象有两个挡板，分别是y=A-h-1(下板)和y=A(上板)，从下向上移动挡板，从而确定一个矩 形。某个点的第一个事件为(y,1)，当上板A=y时，该点被覆盖，若A继续增大，使得A-h-1=y，该点就恰好离开了覆盖区域，反过来我们可以以为是 A=y+h+1，所以定义第二个事件为(y+h+1,-1)。这样，前i个事件的第二关键字和S[i]，就代表了矩形在某个位置时覆盖的点数。S[i]的 最大值就是确定的带状区间内最大的覆盖点数。

带状区间的左右扫描，也可以考虑成两个挡板之间的问题，首先确定挡板的初始位置在最左端，依次向右移动左右两个挡板。确定一个区间后，统 计点事件的最大前缀和成了最关键的问题。由于左右挡板是移动的，我们需要动态统计一个排序结构。于是我们想到了用平衡树，维护每个点事件的第一关键字(y 坐标)升序，并记录权。移动右挡板时，把右挡边新位置所在线上的所有点对应的两个点事件加入平衡树；移动左挡板时，把左挡板时，把左挡边所在线上的所有点 事件从平衡树中删除。

为了快速统计出最大的前缀和，在此基础上，我们还需要对于平衡树中每个节点维护其子树所有节点权值和，以及子树中最大的前缀和。定义p的权值为p.w，以节点p为根的子树的权值和为p.s，以节点p为根的子树的最大的前缀和为p.m，我们可以递推算出p.m的值。

p.m=Max{
	p.left.m; //最大前缀和的尾元素在左子树
	p.left.s+p.w; //最大前缀和的尾元素就是p
	p.left.s+p.w+p.right.m; //最大前缀和的尾元素在右子树
}

于是全部序列的最大前缀和就是根节点root.m。

于是得到的算法如下：

1. 建立离散化坐标系;
2. 左右扫描，确定带状区间，维护平衡树中节点;
3. 统计对于确定带状区间，平衡树中元素最大的前缀和;

算法总的时间复杂度为O(NlogN)，可以解决问题了。编程中细节要注意，尤其是在于平衡树维护平衡性时要对节点m值重新计算。我用了 Treap，在插入一个点要旋转时，注意要先重新计算旋转到子树的点的m值，再计算子树根节点的m值。而删除仅仅懒惰删除即可，重要的是维护m值。
Read the rest of this entry »

对于区间问题，常常使用标记开头结尾后排序，然后扫描的方法解决问题。这道题也不例外，首先把每个区间分开看作两个点，区间[a,b]记做a s(a为s点),b e(b为e点)，所有区间都这样，然后按照在数轴上的位置排序，如果坐标相同，s点放前面。从第一个点开始扫描，最初的Level为0，遇到s点就把 Level值加1，遇到e点就把Level值减1。当处理了某个s点，如果Level变成了1，则这个点就是结果中的一个区间的左界。当处理了某个e点， 如果Level变成了0，则这个点就是右界。

例如样例给出的区间[5,6],[1,4],[10,10],[6,9],[8,10]，标记后排序，成为 1.s 4.e 5.s 6.s 6.e 8.s 9.e 10.s 10.e 10.e 扫描到每个点的Level依次是1 0 1 2 1 2 1 2 1 0 于是结果就是[1,4],[5,10]。

扫描的时间复杂度为O(N)，而快速排序的时间复杂度为O(N*logN)，于是算法的总时间复杂度为O(N*logN)。
Read the rest of this entry »

Read the rest of this entry »

Read the rest of this entry »