一 12
问题简述
有一棵Treap，每个节点有一个互不相同的数据值和权值，以及一个访问频度。一个节点的访问代价为它的访问频度乘以它在树中的深度，整棵树的访问代价定义为所有节点的访问代价之和。节点的权值可以修改为任意实数，每修改一个节点的权值的代价为K。任务是修改一些节点的权值，使得整棵树的访问代价与修改代价之和最小。 Read the rest of this entry »
三 21
NOI2001的题目是[反正切函数的应用][聪明的打字员][陨石的秘密][食物链][炮兵阵地][方程的解数]。
其中[反正切函数的应用][聪明的打字员]较为简单，[陨石的秘密][食物链][炮兵阵地][方程的解数]稍有难度。
[反正切函数的应用]是一个求函数最值的问题，要配合数学知识解决。[聪明的打字员]是广度优先搜索问题。[陨石的秘密]是一个树形动态规划的问题，需要仔细思考。[食物链]用到了并差集。[ 炮兵阵地]是个不易看出的动态规划问题。[方程的解数]是搜索问题，需要用哈希表来优化。
二 09
解决这个和问题，需要用到“树套树”。建立一棵线段树，维护N的节点的所有区间，每个线段树节点上有一个平衡树，用来维护当前区间内所有数的动态排名。很显然，每个线段树节点上的平衡树，都是这个线段树节点的两个子节点的平衡树的合并。由于我们无法实现高效的平衡树合并，只好用这种以空间换时间的方法。
对于每个修改操作，只需先在线段树找出单位区间[i,i]上平衡树中的唯一节点，就是A[i]的原值，然后把线段树从根到该节点路径上所有节点的平衡树中都删除掉A[i]的原值，然后插入新值j。
查询操作为比较特殊，因为给定的区间[i,j]可能对应线段树中若干个区间的并，所以首先找出这对应的q区间的平衡树T[1],T[2],T[3],…,T[q]，找出其中的最大值Max和最小值Min，然后在[Min,Max]之间二分答案。对于给定的答案r，判断是符合要求，否则按照单调性缩小二分区间。
如何求给定的r值的总排名，由于r可能不在某些甚至所有的q个平衡树中，所以有时求r的排名是没有意义的，换而我们可以求r在所有平衡树中后继的最小值MinSucc的排名。对于第i个平衡树，要求r在T[i]中的后继(不大于r的最小值)的排名S[i]，MinSucc的排名就是k1=Σ{S[i]-1} + 1。但是相同的MinSucc的值可能会有多个，所以MinSucc的排名实际上是属于一个区间的，应在所有的平衡树中找出MinSucc一共的个数Count，MinSucc的最大排名就是k2=k1+Count-1。如果k属于[k1,k2]，那么结果就是MinSucc。如果k2<k，则应向增大的方向二分答案，否则向减小的方向二分答案。
代码很长，最后一句话，细节决定成败！
感谢slxg，正如你所说的，我写错了。现在错误已经修正。看来zju的数据还是不够强大，原来有点错的也能AC。
二 07
发现坐标的范围很大，而点并不是很多，首先想到了离散化的方法。然后横向扫描每个带状的区间，对于每个带状区间，再纵向扫描其中点的个数。这种方法是最容易想到的，但是时间复杂度却高达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。
于是得到的算法如下：
- 建立离散化坐标系;
- 左右扫描，确定带状区间，维护平衡树中节点;
- 统计对于确定带状区间，平衡树中元素最大的前缀和;
算法总的时间复杂度为O(NlogN)，可以解决问题了。编程中细节要注意，尤其是在于平衡树维护平衡性时要对节点m值重新计算。我用了 Treap，在插入一个点要旋转时，注意要先重新计算旋转到子树的点的m值，再计算子树根节点的m值。而删除仅仅懒惰删除即可，重要的是维护m值。
Read the rest of this entry »
Recent Comments