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 »

可以看出，这道题就是求以每个点位中心，边长为2*r+1的矩阵的和。最简单的方法就是对于N*N个点，每个点都以R*R的时间复杂度求出矩阵的和，总时间复杂度为O(N^2*R^2)。其实许多次的计算都是冗余的，我们可以类比求最大子矩阵的方法，充分利用已有的值，快速求出矩阵的和。

首先把二维的矩阵压缩为一个一维的序列，即把每k列以第i行为中心[i-r,i+r]的和算出，保存在S[k]中。然后求以第j个位中心，S[k-r]..S[k+r]的和Sum，Sum的值就是对应的W[i,j]的值。当求W[i,j+1]的值时，就不必再重新全部计算，只需考虑它与W[i,j]的增量，即W[i,j+1]=W[i,j]+S[j+r+1]-S[j-r-1]。当换行的时候，只需计算W[i,1]的值即可。这样，由每一行的第一个值推出这一行的所有值，可以大大缩短时间。时间复杂度为O(N^2)，于是完美地解决了这个问题。
Read the rest of this entry »