CODEWITHSUNDEEP
algorithmdynamic-programming
Shubham Sharma
Shubham Sharma

Reputation: 839

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

This is from a contest! I have suppose M intervals of type [L,R] ,(1<= L , R <= N ) each having a cost Ci. Now These intervals aren't to be taken as whole(We can split them!) After splitting them, I have to report the minimum value possible , i.e. if i (1<=i <=N) belongs to K intervals , I want the minimum value of all the costs of Intervals that contain i!

What am I doing ? I tried to create a Segment Tree (Modified a bit) ! I am using lazy propagation.! Note every segment is a waste to me except Segments of Length one ! Why? Just because I need the minimum value of each point rather than a segment! So I Update each interval and then build my solution from it

It isn't working properly I guess (It is giving wrong answer!)

I just want to know whether am I totally wrong (So I can quit it ! ) Or not ! My Update function:

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 Function:

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

Note the actual problem requires much more than this.! It is just facilitating the problem not actually solving the problem!

Upvotes: 3

Views: 672

Answers (1)

Shubham Sharma
Shubham Sharma

Reputation: 839

Actually My code really works and it gives me correct output. Lately I figured out that I was making a mistake somewhere else. The explanation of my segment tree is as follows: 1) Build a tree with all values +INFINITY

2) Now whenever a range comes go till that range and mark it's child as lazy but here we do not necessarily change the value we take the min of Lazy value just because it is not an update rather than one more value.!

3) When relaxing the Lazy node, You do not necessarily change the value you take the min of Lazy parameter and value !

4) Now whenever you query(for point),the Lazy values will traverse down and give you correct output.

But I realised I can do it via simple brute force too! By maintaining one array in complexity O(N+M).

Upvotes: 1

Related Questions