P10455 Genius Acm
题目大意
给定 n 个数 ai,定义一段区间的 SPD 为将这段区间内的数两两配对成 m 对(区间内数字不够就尽量选),将这 m 对数的差的绝对值的平方相加,最大值即为这段区间的 SPD。
现在需要你求出,给定 K,最少将原序列划分成几段才能满足每段 SPD 最大值 ≤K。
数据范围:1≤n,m≤5×105,0≤k≤1018,0≤ai≤220。
题解
把 SPD 的求法翻译一下,由于要求这个式子最大值,显然是不能枚举的,那么考虑贪心。
具体的,将这个区间 [l,r] 中的所有数排序,记为 bi,要让 SPD 最大,就要让 b1 和 blen 配对,b2 和 blen−1 配对,以此类推。
有了这个,我们可以在 O(LlogL) 的复杂度内求出一个区间的 SPD。
由于原本的式子过于复杂,很难上什么数据结构维护,考虑贪心地划分原序列。
贪心策略
从当前区间左端点 s 找到一个最大的满足要求的右端点 d,然后贪心 d+1 到 n。
证明
令 f(x) 表示从 ax 到 an 的最小划分段数,容易发现 f(x) 单调不增。
对于当前区间 [s,n],假设最优解选择 r 作为分割点,贪心策略选择 t 作为分割点。
由于 [s,t] 合法,容易发现任意一个合法区间的子区间一定合法,于是有:r≤t⟹f(r)≥f(t)。
也就是说,贪心策略不会更劣,证毕。
有了贪心策略,一种朴素的实现是二分右端点然后判断,这么做最坏 O(n) 次二分,最坏复杂度 O(n2log2n) 一定是过不了的。
分析发现,上一种算法是因为答案区间过短时会浪费复杂度,我们需要一种只与右端点距离有关的算法。
考虑倍增+二分,也就是维护 p 表示扩展长度,判断 [s,p] 是否合法,合法时 p←2p,否则 p←2p,每次只需要对新的 [s,p′] 进行排序,然后将其和有序的 [s,p] 归并即可。
这么做的复杂度是 O(nlogn)。
