【TIOJ 1872】最小公倍數

原題連結：http://tioj.infor.org/problems/1872
這題本來沒什麼想法，看題解想了好久才搞懂QQ

首先我們要先對詢問區間的右界排序(QlgQ)
然後利用差分的概念，維護序列b[i]=query(i,r)/query(i+1,r)
也就是計算詢問往左擴大一個後會需要多乘多少
這裡我是用bit維護，這樣對於一個詢問[l,r]，固定r後求得的答案就是bit_query(r)*inv(bit_query(l-1))
維護良好的話，詢問複雜度會是QlgN

再來是維護的部分
當我們要增加一個r的時候，我們對於每個a[r]的質因數p做分開處理(質因數分解O(NlgN))
假想r-1以前的維護都已經完成，那麼對於一個質數p，我們將會維護出一個從a[1]~a[r-1]的「嚴格遞減單調隊列」
其中內含的是a[i]中最大的p冪次因數

這時候就可以開始用一個stack做單調隊列的維護，先求出a[r]中最大的p冪次因數，冪次為c
則當top的冪次r：
r<=c 該top原位置的b[i]必須被更動(因為表示這個冪次r會完全被c蓋住)，然後就可以把top拔掉了
r>c 該top原位置的b[i]必須稍做更動(增加幅度減少)，並把c推入stack後更新b[r]退出(更後面的元素我們可以相信他們已經被前面的元素更新完了)

更新b[r]、更動b[i]的部分分別一個是用乘的，一個是用除的(乘反元素)
這裡我在線篩的時候有預處理把每個質數的冪次和反元素都蓋好(複雜度NlgN)，所以更新更動都是lgN
對於每個質數，每個元素至多加入一次、拔掉一次，均攤O(1)，單一質數最慘複雜度O(NlgN)

但注意到數字最大只有10^6，所以要卡最緊也只能多約lgC個質數(實際上是更好的一個反函數)，維護總複雜度O(NlgClgN)

總複雜度O(Q(lgQ+lgN)+NlgClgN)

附上code: