題目花了不少時間自己理解
防雷
防雷
dp倍增 (反白)
這題就算理解完，要寫也是蠻麻煩的
不過現在刻完，砸一砸感覺還是挺愉快的
題目說明:
給一個數組 a，有 q 筆詢問
每次給你個 left 跟 right
問你要把 a[left]~a[right] 切成最少幾個區間
才能讓各個區間的 lcm = 乘積
以下不專業講解...
我們在切區間時，只要從頭
每次把一個區間切得盡可能大
這樣 greedy 做，能保證區間數最少
lcm = 乘積，基本上就是任兩個數彼此都互質
但如果我們兩個兩個的做 gcd
這樣光一個 query 就是 O(n²logC) 會燒雞
因此我們得想其他方式
不難想到就是用質數 或是 質因數分解
因為一個數字的質因數數量 頂多就 log(n) 個
這邊做法也蠻多種的
以下是我的寫法，應該很好理解
我們可以先用篩法找出 1e5 以內的所有質數
然後使用這些質數建出質因數分解表
可以用成 set 的方式，我們只需要質數有哪幾種
不需要質數的冪次
我們維護一個 set，判斷新加入的數的質因數
如果跟現有的有交集，則代表我們要切新區間了
到這邊為止，對於每個 query，我們來算一下求解的複雜度
區間大小 * 因式分解質因數數量 * 求 set 交集
大約是 O(nlog²n)，總之硬吃 O(n) 就是不行
那我們可不可以一次求很多個區間呢
可以，我們有方法求出對於每個起點
它最大可以拓展到哪裡
方法很簡單 可以使用 two pointers
只需要在新區間產生時，把頭的質因數拔掉即可
於是現在在求答案
你可以透過不斷的查詢左界的最大右界
再把這個右界設為左界，不斷求解就能得到答案了
但是如果每次左右界都很近
這個複雜度還是可能到 O(n)
以下就要進入 dp倍增 的環節
如果我們在不斷更新左界時
如果能一次跳好幾個，這樣就能加速求解了
於是有這麼一個 dp 方法
前置條件是 我們要先求出:
每個起點它最大可以拓展到哪裡?
前面已經提過了，這點我們可以做到
再來 我們用 dp[i][j]
代表以 j 為左界，重複執行 2^i 次所得到的右界
則有以下 dp 式
dp[i][j] = dp[i-1][dp[i-1][j]]
其他人在講解時可能用 2^(i-1) + 2^(i-1) = 2^i 來解釋
但其實概念不難，右式裡面的 dp[i-1][j]
其實就代表上個動作的右界
把上一個動作的右界拿來當左界算
得到的當然就是現在要求的右界了
再來就是求出 dp 值的複雜度
首先，dp的row大小會是 O(log(n))
因為每次做操作，原本的左界至少會增加 1
而做 2^(log(n)) 次，就肯定會跳到底
詳細地說，dp 的 row 我們要開到 n.bit_legth()+1
在 dp[0][j] 已經在之前被我們求出來的情況下
我們只要 i從1到n-1，j從0到n-1，這樣迴圈去算
總共就是 O(nlogn) 個值要去填
那有了這個 dp 表，我們要怎麼求解呢
很簡單，就一樣用剛剛那個不斷求解的方式
只是套到成 dp[i][left]
我們枚舉從0(或1)枚舉這個 i
若 dp[i][left] 這個右界不會超出 right，那就繼續
否則，我們就把 left 更新到上個動作的右界
直到我們我們有個左界，它做一次擴展就超過右界
那我們就做完了
實際上其實就是我們對答案進行二分搜
只是每次的判斷結果，都會產生一些額外的變化
而我們所操作的 i，對應到的就是實際操作了 2^i 次
因此，我們也是依此利用指數來更新答案
如果你看得懂 python 的話，
dp 的 row 那邊應該是說:
2**(18-1) > 1e5，才是正確的
創作內容
cf #717(Div. 2) pD Cut
未分類 (17)