B.Be Geeks
前言:妙中妙。非常喜欢这一题.
题目大意:
给你一个长度为N的序列。问你所有连续子序列的最大值 * 区间GCD 的和.形式化表示为:
题目思路:
两个子问题我都会求，拼在一起明显难度就大了很多。。
子问题一:求解
%20)
思路:
不难想到，我们可以分治的求解。在区间[L,R]中找到最大的值mx的位置POS.那么有(POS-L+1) * (R - POS+1) 个区间的最大值为mx. 计算完之后，对区间[L,POS-1]与[POS+1,R]进行分治.
利用ST表预处理。总时间复杂度为:
子问题二:求解
)
思路:
经典结论:左端点固定的情况下，右端点向右移动的过程中，区间GCD的值的不同的个数最多为logn个.
所以可以枚举左端点，二分右端点按段计算。st表预处理区间GCD。总时间复杂度:
大问题:
思路：
考虑先找最大值:对于最大值，向左二分找logn段区间GCD值相同的段。向右也这么找,得到如下形式:
左右部分两两组合，logn*logn的复杂度，注意区间的组合计数方式。中间有一个求GCD的操作。那么复杂度为:logn * logn * logn.
对剩下两部分分别分治,
时间复杂度为：
1.7s飘过
AC代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45137038
G.K==S
已补://www.greatytc.com/p/7793c63ecc1b
