找到给定值间隔的每个点的最小值（请参阅正文）

这是参加比赛的最佳选择！我有类型的假设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

找到给定值间隔的每个点的最小值（请参阅正文）

回答

相关问题