-1
$\begingroup$

This question already has an answer here:

Assume that initially in array each element has infinity as value.

Now M queries are input of the type l r x.

Here l to r is range where value need to be updated if a[i]>x where l<=i<=r. and l<=r<=n

After M queries you need to output the minimum value at each index.

One way to this is to use Brute Force

memset(a,inf,sizeof(a));
while(j<m)
 {
     scanf("%d %d %d",&l,&r,&c);
     for(i=l-1;i<r;i++)
     {
            if(a[i]>c )
                a[i]=c;

     }

     j++;
 }

Now this takes O(mn) time where n=size of each query which can be n in worst case.

What are more efficient ways to solve this in lesser time complexity?

$\endgroup$

marked as duplicate by D.W., David Richerby, Kyle Jones, Juho, lPlant Jul 21 '15 at 0:31

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ I can't understand the problem you're trying to decribe. You say that a value needs to be updated under certain conditions but you don't say what it's updated to. $\endgroup$ – David Richerby Jul 12 '15 at 15:38
  • 1
    $\begingroup$ Very similar question; duplicate? $\endgroup$ – Raphael Jul 12 '15 at 17:29
0
$\begingroup$

It can be done by using Segment Tree data structure:

  1. Originally described query is just "lowering values at some segment", so let's call it update query. To perform this query you need to update at most $O(log N)$ segments and it also can be done with $O(log N)$ time-complexity. So for run all update queries we need $O(N log N)$ time.
  2. We have another type of query "what is the value at $a[i]$. In general we can answer to such query with $O(log N)$ time, by going through all segments that contains $a[i]$ and take minimum from such values and due to nature of segment tree there will be at most $\lceil log N \rceil$ such segments. At this point we have online solution (e.g. queries of 1st and 2nd types can be mixed). Also gathering resulting array after all queries of 1st type (e.g. offline solution that asked in original post) can be performed even with $linear$ complexity(relatively to array length); please, note that it's time complexity only for constructing result array by segment tree, for performig $N$ queries we still need $O(N log N)$ time.

For example:

  1. To perform update query on segment $[1, 4]$ you need to update pink nodes.
  2. To know what is value at $a[4]$ you need to go through all segments rounded by yellow and takes minimum from values at this segments.

example

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.