一類算法復(fù)合的方法

一類算法復(fù)合的方法編輯ppt問題描述維護(hù)集合S，初始時(shí)為空。有N個(gè)操作需要依次處理BX

在S中插入一個(gè)整數(shù)XAY

詢問S中被Y除余數(shù)最小的數(shù)，如果有多個(gè)則任取一個(gè)1≤N≤40000，1≤X,Y≤R=500000允許離線算法編輯ppt初步分析算法1：對詢問中每個(gè)不同的Y，維護(hù)它對應(yīng)的詢問當(dāng)前的答案時(shí)間復(fù)雜度為O(N2)，不能解決問題但當(dāng)詢問中出現(xiàn)的不同Y的個(gè)數(shù)比較少時(shí)會很快，時(shí)間復(fù)雜度可以寫成O(不同Y的個(gè)數(shù)×N)編輯ppt進(jìn)一步分析當(dāng)遇到一個(gè)詢問"AY"時(shí)，要在S中尋找使得xmodY最小的數(shù)x把這里的x寫成kY+r，其中0≤r<Y，k和r是整數(shù)也就是說，我們要在集合S中，尋找使得r最小的數(shù)kY+r算法2：枚舉k，找[kY,(k+1)Y)中的最小值。最后在這些最小值中取最優(yōu)的編輯ppt一個(gè)例子S={2,3,6,8}Y=5012345678910…最小值為2最小值為62mod5=2

6mod5=1因此取6編輯ppt現(xiàn)在的問題：詢問S中給定區(qū)間[a,b]內(nèi)的最小數(shù)可以看成是詢問≥a的最小數(shù)q(a)012345678910…aq(a)222366688+∞+∞…對很多連續(xù)的a，q(a)是相等的形成了若干個(gè)區(qū)間編輯ppt假設(shè)X所在的區(qū)間為[s,t]，現(xiàn)在在S中插入X[s,t]被拆分成了區(qū)間[s,X]和[X+1,t]ss+1…X-1XX+1…t-1taq(a)tttttttttss+1…X-1XX+1…t-1tXXXXXtttt編輯ppt只有插入操作，所以一直在拆分區(qū)間，而不合并區(qū)間讓時(shí)間倒流，把所有操作按照從后往前的順序處理，那么區(qū)間就一直都在被合并了并查集把這里每個(gè)區(qū)間看作是一個(gè)集合，并維護(hù)它們對應(yīng)的q每次操作近似地認(rèn)為是均攤O(1)編輯ppt算法2對一個(gè)詢問“AY”，需要詢問O(R/Y)個(gè)區(qū)間，最多O(R)個(gè)區(qū)間一次詢問的時(shí)間復(fù)雜度高達(dá)O(R)總時(shí)間復(fù)雜度O(NR)，也不能解決問題編輯ppt嘗試著優(yōu)化算法2的瓶頸在于一次詢問需要處理的區(qū)間可能非常多，但只會發(fā)生在很少當(dāng)Y非常小的時(shí)候一個(gè)例子：當(dāng)Y>R0.5時(shí)，算法2已經(jīng)可以接受了我們可以對這部分很少的Y的詢問使用另一種算法算法1當(dāng)詢問中的不同的Y很少時(shí)會很快，所以這里的另一種算法可以選擇算法1編輯ppt算法3設(shè)一個(gè)邊界值K對Y>K的詢問使用算法2O(NR/K)

對Y≤K的詢問使用算法1O(NK)總時(shí)間復(fù)雜度O(NK+NR/K)將N和R看作常數(shù)，容易得出當(dāng)K=R0.5時(shí)總時(shí)間復(fù)雜度最小，為O(NR0.5)算法3可以完全解決本題編輯ppt我們解決本題的重點(diǎn)是：不使用統(tǒng)一的算法，而是同時(shí)使用這個(gè)問題的兩種算法，分別解決問題中的兩個(gè)互補(bǔ)的部分我的論文里還有另一個(gè)例子

SPOJRECTANGL

這個(gè)問題同樣可以通過同時(shí)使用兩種不同的算法得到較好的解決編輯ppt總結(jié)一個(gè)問題往往可以被看作是由若干個(gè)相對并列的部分組成起來的通常對這些部分使用統(tǒng)一的算法而有時(shí)這個(gè)問題可以使用多種算法解決，并且當(dāng)這些算法應(yīng)用在問題中不同特征的部分時(shí)，會有不同的效果這時(shí)就可以將這些算法復(fù)合，對問題的不同部分，根據(jù)它們的特征分別選擇使用對這個(gè)部分較優(yōu)的算法編輯ppt總結(jié)兩個(gè)算法合并起來后，很神奇地得到了一個(gè)更優(yōu)的算法這是因?yàn)檫@兩種算法具有互補(bǔ)的優(yōu)勢，而我們把問題分成了若干部分，對每一部分根據(jù)其特征使用較優(yōu)的算法，就使