由于%沒有逆運(yùn)算,直接樹狀數(shù)組或線段樹會出問題 //考試時(shí)搞了半天樹狀數(shù)組,發(fā)現(xiàn)會出現(xiàn)0,只好暴力,居然有60分,正解真心不好想出來
正解思路:
把序列分成長度為k的若干塊,每一塊維護(hù)前綴和后綴乘積(代碼中的f和g分別維護(hù)前綴后綴乘積)每個(gè)長度為k的區(qū)間對應(yīng)了一整塊或者前一塊的后綴和后一塊的前綴,直接乘起來就得到答案時(shí)間復(fù)雜度為O(N)新聞熱點(diǎn)
疑難解答