在给定值的区间时找到每个点的最小值（见正文）

Question

这是一场比赛！我假设 M 个 [L,R] 类型的区间，(1<= L , R <= N ) 每个区间的成本为 Ci。现在这些间隔不能作为一个整体（我们可以拆分它们！）拆分后，我必须报告可能的最小值，即如果 i (1<=i <=N) 属于 K 个区间，我想要包含 i 的区间的所有成本的最小值！

我在做什么？我试图创建一个线段树（修改了一下）！我正在使用惰性传播。！请注意，除了长度为 1 的段外，每个段对我来说都是浪费！为什么？只是因为我需要每个点的最小值而不是一个段！所以我更新每个间隔，然后从中构建我的解决方案

我猜它没有正常工作（它给出了错误的答案！）

我只是想知道我是否完全错了（所以我可以放弃它！）还是不是！ 我的更新函数：

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 ;
}

获取函数:

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));
}

请注意，实际问题远不止于此！这只是解决问题而不是解决问题！[=12=]

Answer 1

实际上我的代码确实有效，它给了我正确的输出。最近我发现我在其他地方犯了一个错误。我的线段树的解释如下： 1) 构建一棵所有值为 +INFINITY

的树

2) 现在，无论何时出现一个范围，直到该范围并将其标记为 child 为惰性，但在这里我们不一定要更改值，我们取惰性值的最小值只是因为它不是更新而是不止一个价值。！

3) 放宽Lazy节点时，不一定要改取Lazy参数的最小值和取值!

4) 现在无论何时你查询（for point），惰性值都会向下遍历并给你正确的输出。

但我意识到我也可以通过简单的蛮力来做到这一点！通过维护一个复杂度为 O(N+M) 的数组。

在给定值的区间时找到每个点的最小值（见正文）

Finding Minimum Value of each point when interval with values are given(See Body)

algorithm

dynamic-programming