B.Be Geeks
前言:妙中妙。非常喜歡這一題.
題目大意:
給你一個長度為N的序列忙干。問你所有連續(xù)子序列的最大值 * 區(qū)間GCD 的和.形式化表示為:
題目思路:
兩個子問題我都會求，拼在一起明顯難度就大了很多浪藻。捐迫。
子問題一:求解
%20)
思路:
不難想到，我們可以分治的求解爱葵。在區(qū)間[L,R]中找到最大的值mx的位置POS.那么有(POS-L+1) * (R - POS+1) 個區(qū)間的最大值為mx. 計算完之后施戴，對區(qū)間[L,POS-1]與[POS+1,R]進(jìn)行分治.
利用ST表預(yù)處理∶日桑總時間復(fù)雜度為:
子問題二:求解
)
思路:
經(jīng)典結(jié)論:左端點固定的情況下赞哗，右端點向右移動的過程中，區(qū)間GCD的值的不同的個數(shù)最多為logn個.
所以可以枚舉左端點辆雾，二分右端點按段計算肪笋。st表預(yù)處理區(qū)間GCD《扔兀總時間復(fù)雜度:
大問題:
思路：
考慮先找最大值:對于最大值藤乙，向左二分找logn段區(qū)間GCD值相同的段。向右也這么找,得到如下形式:
左右部分兩兩組合英岭，logn*logn的復(fù)雜度湾盒，注意區(qū)間的組合計數(shù)方式。中間有一個求GCD的操作诅妹。那么復(fù)雜度為:logn * logn * logn.
對剩下兩部分分別分治,
時間復(fù)雜度為：
1.7s飄過
AC代碼:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45137038
G.K==S?
已補:http://www.reibang.com/p/7793c63ecc1b
