是否存在表示大量S(64位)整数的数据结构,这些整数从空开始并支持以下两个操作:
insert(s)将数字s插入S;minmod(m)返回数字s中S,使得s mod m最小.一个例子:
insert(11)
insert(15)
minmod(7) -> the answer is 15 (which mod 7 = 1)
insert(14)
minmod(7) -> the answer is 14 (which mod 7 = 0)
minmod(10) -> the answer is 11 (which mod 10 = 1)
我有兴趣尽量减少在一系列n此类操作上花费的最长总时间.显然可以只S为每个minmod操作维护一个元素列表并迭代它们; 然后插入is O(1)和minmod O(|S|),这将花费O(n^2)时间进行n操作(例如,n/2 insert操作后面的n/2 minmod操作将花费大致n^2/4操作). …