狠狠撸

从区间第碍大讲起
归并树划分树树套树块状数组
可持久化线段树

约定
? 根据汉语口语的一些性质，以及不要在意细节，
以及第k大和第k小本质相同，下面约定：

? 区间第k大
意为
区间第k小

Problem 1: 在线无修改
复杂度要求：
空间：O(n*logn)
预处理时间：O(n*logn)
单次查询时间：O(log3n)

归并树可以解决

? 二分答案，将问题转化为判定性问题
? 在已知答案ans的情况下，计算ans在所求区间
的Rank，根据Rank与k的关系，缩紧二分区间

? 如何判定ans在所求区间的Rank?

? 按照归并排序建树，sum[deep][i]记录当前
深度下i所在区间中，前i-l个数中有多少个分
到了左子树当中
? 即有多少数比排序完的a[mid]小

? 求Rank的时候分别计算在左右两棵子树当中的
Rank，然后再合并，就是所求Rank

? 怎么求ans在某个区间的rank？
? 二分！

? Find(p, deep, value) //每组调用logn次
? if SegmentTree[p]为叶子节点
? return lower_bound(lef, rig, value)-lef //O(logn)
? res = 0
? res += Find(p*2, deep+1, value)
? res += Find(p*2+1, deep+1, value)
? return res

? Main
? lef = min{a[i]}, rig = max{a[i]}
? while (lef+1 < rig) //计算logn组
? mid = (lef+rig)/2
? if Find(1, 1, mid) >= k
? rig = mid
? else
? lef = mid

? 二分答案 O(logn)
? 在线段树中操作 O(logn)
? 每个线段树叶子节点中确定Rank O(logn)

? 单次查询 O(log3n)

Problem 2: 在线无修改无相同数
复杂度要求：
空间：O(n*logn)
单次查询时间：O(logn)

划分树可以解决

? sum[deep][i]记录对于每个区间[l, r]的
前i-l+1项中，合并时有多少个数归到左边
? 即有多少数比排序完的a[mid]小
? 最多有log(n)层

? 每次查询线段树区间[l, r]第k大时，根据
sum[deep][i]调整，递归解决

? 查询[2, 7]的第3大
? sorted[] [1 2 3 4 5 6 7 8]
? a[0] [4 2 7 1 5 6 8 3]
? a[1] [4 2 1 3][7 5 6 8]
? a[2] [2 1][4 3][5 6][7 8]
? a[3] [1][2][3][4][5][6][7][8]

? Query(deep, st, ed, lef, rig, k)
? 深度：deep
? 线段树区间：[st, ed]
? 查询区间：[lef, rig]
? 查询第k大

? Query(deep, st, ed, lef, rig, k)
? if (lef == rig)
? return a[deep][lef]
? CountLef = sum[deep][lef-1]
? CountRig = sum[deep][rig]
? if (CountRig-CountLef >= k)
? //左边的个数多于k个，答案在左边
? return Query(deep+1, st, mid, CountLef+st, st+CountRig-1, k)
? else
? //否则就在右边查找第k-(CountLef-CountRig)大
? return Query(deep+1, mid+1, ed, mid+1+lef-st-CountLef,
mid+1+rig-st-CountRig, k-(Countlef-CountRig))

? st lef rig ed
[ [ ] ]
|-CountLef-|
|------CountRig-----|

PKU2104 Accepted 14900K 1094MS G++

Problem 1: 在线无修改有相同数 Sol2
复杂度要求：
空间：O(n*logn)

划分树可以解决

? 我发现原来写的划分树有问题，遇到重复的数
就挂掉了
? HDU2665 RE!

? 讨论下

Problem 3: 在线有修改
复杂度要求：
空间：O(n*logn)
单次修改时间：O(log2n)
单次查询时间：O(log3n)

树套树！

? 线段树能够完成对区间的限制
? 平衡树能够完成统计区间上不大于k的数

? 线段树套平衡树！

? 每一个线段树的节点为一棵平衡树
? 显然叶子节点的每一棵平衡树只有一个节点
? 对于线段树非叶子节点，保存所有叶子节点平
衡树的并

? 修改：从线段树根进去，递归处理
? 每一棵子树，都要从它的平衡树中把待修改节
点的旧值删去
? 然后用同样的方法添加新值

? O(2*logn)

? 查询：二分答案，计算在区间内的Rank
? 如何计算Rank?

? 平衡树中每个节点记下当前节点为根的子树有
多少节点
? 平衡树旋转的时候重新统计节点数量

? 查询时根据平衡树的性质向两边递归查找

? Hint:平衡树重复节点的处理方法：可以在每
个节点中添加属性Count，保存有几个相同节
点
? 删除时Count-1，如果Count=0，再合并子树

? Rank(BSTNode, ToRank)
? if BSTNode为空
? return 0
? if (ToRank < BSTNode.Value) //查询的比当前节点小，递归左子树
? return Rank(BSTNode.LeftChild, ToRank)
? else
? return Rank(BSTNode.RightChild, ToRank) //同上处理右子树
+ BSTNode.Count //当前节点的个数
+ BSTNode.LeftChild.Size //左子树中的数一定比它小

? 二分答案 O(logn)
? 线段树中操作 O(logn)
? 递归处理平衡树 O(logn)
? 单次查询 O(log3n)

? 单次插入删除 O(log2n)
? 预处理相当于n次插入 O(nlogn)

? 线段树常数略大，考虑用树状数组实现

Accepted ZJU2112 C++ 3040MS 19320KB

BZOJ1901 Accepted 4172 kb 1244 ms C++

Problem 3: 在线有修改 Sol2

? 初始化：将数据放入块状数组中，排序每个块
? 修改：确定修改的数所在块状数组中的位置，
直接修改，然后暴力重新排序当前块
? 查询：二分答案，查询答案在块状数组中的
Rank

Accepted ZJU2112 C++ 4770ms 572kb

BZOJ1901 Accepted 884 kb 1264 ms C++

说好的可持久化数据结构呢？

Problem 1: 在线无修改 Sol 3
复杂度要求：
空间：O(4n+nlogn)
预处理时间：O(nlogn)

可持久化线段树！

? A[] 1 5 2 6 3 7 4
? 按权值建线段树：

? 线段树版本 1 2 3 4 5 6 7
? 0
? 1 +1
? 2 +1 +1
? 3 +1 +1 +1
? 4 +1 +1 +1 +1
? 5 +1 +1 +1 +1 +1
? 6 +1 +1 +1 +1 +1 +1
? 7 +1 +1 +1 +1 +1 +1 +1

? 查询[2, 5]的第3大
? A[] 1 5 2 6 3 7 4
? 线段树版本 1 2 3 4 5 6 7
? 0
? 1 +1
? 2 +1 +1
? 3 +1 +1 +1
? 4 +1 +1 +1 +1
? 5 +1 +1 +1 +1 +1
? 6 +1 +1 +1 +1 +1 +1
? 7 +1 +1 +1 +1 +1 +1 +1

? 5-(2-1) +1 +1 +1 +1

PKU2104 Accepted 26884K 2047MS G++

Problem 3: 在线有修改 Sol3
复杂度要求：
空间：O(???)
预处理时间：O(???)
单次修改时间：O(???)
单次查询时间：O(???)

可持久化线段树！

Thanks:
? Orz 云南
? Orz 大表
? Orz 小胖

狠狠撸

从区间第碍大讲起

More Related Content

从区间第碍大讲起