找到給定值間隔的每個點的最小值（請參閱正文）

這是參加比賽的最佳選擇！我有類型的假設M個間隔[L，R]，（1 < = L，R < = N）每一個都具有成本次。現在這些時間間隔不應被視爲整體（我們可以將它們分割！）分裂他們之後，我已經報到的最小值可能，也就是說，如果我（1 < =我< = N）屬於到K的間隔，我想要包含我的間隔的所有成本的最小值！找到給定值間隔的每個點的最小值（請參閱正文）

我在做什麼？我試圖創建一個段樹（修改了一下）！我正在使用惰性傳播。請注意，每個細分受衆羣對我來說都是一種浪費，除了細分受衆羣！爲什麼？僅僅因爲我需要每個點的最小值而不是一個段！所以我每次更新間隔，然後建立我的解決方案，從它

它不能正常工作，我想（這是給錯誤的答案！）

我只是想知道是否我完全錯了（這樣我就可以退出它！）或不！ 我的更新功能：

void Update(int L,int R,int qe ,int qr,int e,int idx) 
{ 
    if(Tree[idx].lazy!=INT_MAX) 
    { 
     Tree[idx].value=min(Tree[idx].value,Tree[idx].lazy); 
     if(L!=R) 
     { 
      Tree[rc(idx)].lazy=min(Tree[rc(idx)].lazy,Tree[idx].lazy); 
      Tree[lc(idx)].lazy=min(Tree[lc(idx)].lazy,Tree[idx].lazy); 
     } 
     Tree[idx].lazy=INT_MAX; 
    } 
    if(L>qr || qe>R) 
     return ; 
    if(L>=qe && qr>=R) 
    { 
      Tree[idx].value=min(Tree[idx].value,e); 
      if(L!=R) 
       { 
        Tree[rc(idx)].lazy=min(Tree[rc(idx)].lazy,e); 
        Tree[lc(idx)].lazy=min(Tree[lc(idx)].lazy,e); 
       } 
      return ; 
    } 
    Update(L,mid(L,R),qe,qr,e,lc(idx)); 
    Update(mid(L,R)+1,R,qe,qr,e,rc(idx)); 
    Tree[idx]=Merge(Tree[lc(idx)],Tree[rc(idx)]); 
    return ; 
}

GET功能：

int Get(int L,int R,int qe,int idx) 
{ 
    if(Tree[idx].lazy!=INT_MAX) 
    { 
     Tree[idx].value=min(Tree[idx].value,Tree[idx].lazy); 
     if(L!=R) 
     { 
      Tree[rc(idx)].lazy=min(Tree[rc(idx)].lazy,Tree[idx].lazy); 
      Tree[lc(idx)].lazy=min(Tree[lc(idx)].lazy,Tree[idx].lazy); 
     } 
     Tree[idx].lazy=INT_MAX; 
    } 
    if(L==qe && qe==R) 
     return Tree[idx].value; 
    if(qe<=mid(L,R)) 
     return Get(L,mid(L,R),qe,lc(idx)); 
    else 
     return Get(mid(L,R)+1,R,qe,rc(idx)); 
}

注意的實際問題，需要的遠不止這些！這只是爲了解決問題而不是解決問題！

來源

2015-07-03 Shubham Sharma

你能舉一個例子輸入和輸出嗎？ –

其實我的代碼確實有效，它給了我正確的輸出。最近我發現我在其他地方犯了一個錯誤。我段樹的解釋如下： 1）建立了一棵樹的所有值+ INFINITY

2）現在只要一個範圍自帶去到那範圍，標誌着它的孩子懶惰，但在這裏我們並不一定變化我們認爲Lazy值的最小值僅僅是因爲它不是一個更新而不是一個更多的值。

3）當放鬆懶惰節點，你不必改變你採取懶惰的參數和值的最小的值！

4）現在，只要你查詢（點），懶惰值將穿越下來，給你正確的輸出。

但我意識到，我可以通過簡單的蠻力做得到！通過維護一個複雜度爲O（N + M）的數組。

來源

2015-07-05 04:10:39

找到給定值間隔的每個點的最小值（請參閱正文）

回答

相關問題