算法合集之《一类算法复合的方法》.ppt

一类算法复合的方法
江苏省扬州中学张煜承
问题描述
维护集合S,初始时为空。有N个操作需要依次处理
B X 在S中插入一个整数X
A Y 询问S中被Y除余数最小的数,如果有多个则任取一个
1≤N≤40000,1≤X,Y≤R=500000
允许离线算法
初步分析
算法1:对询问中每个不同的Y,维护它对应的询问当前的答案
时间复杂度为O(N2),不能解决问题
但当询问中出现的不同Y的个数比较少时会很快,时间复杂度可以写成O(不同Y的个数×N)
进一步分析
当遇到一个询问"A Y"时,要在S中寻找使得x mod Y最小的数x
把这里的x写成kY+r,其中0≤r<Y,k和r是整数
也就是说,我们要在集合S中,寻找使得r最小的数kY+r
算法2:枚举k,找[kY,(k+1)Y)中的最小值。最后在这些最小值中取最优的
一个例子
S={2,3,6,8} Y=5
最小值为2
最小值为6
2 mod 5 = 26 mod 5 = 1
因此取6
现在的问题:询问S中给定区间[a,b]内的最小数
可以看成是询问≥a的最小数q(a)
a
q(a)
对很多连续的a,q(a)是相等的
形成了若干个区间
假设X所在的区间为[s,t],现在在S中插入X
[s,t]被拆分成了区间[s,X]和[X+1,t]
a
q(a)
只有插入操作,所以一直在拆分区间,而不合并区间
让时间倒流,把所有操作按照从后往前的顺序处理,那么区间就一直都在被合并了
并查集
把这里每个区间看作是一个集合,并维护它们对应的q
每次操作近似地认为是均摊O(1)
算法2
对一个询问“A Y”,需要询问O(R/Y)个区间,最多O(R)个区间
一次询问的时间复杂度高达O(R)
总时间复杂度 O(NR),也不能解决问题
尝试着优化
算法2的瓶颈在于一次询问需要处理的区间可能非常多,但只会发生在很少当Y非常小的时候
一个例子:当Y>,算法2已经可以接受了
我们可以对这部分很少的Y的询问使用另一种算法
算法1当询问中的不同的Y很少时会很快,所以这里的另一种算法可以选择算法1