arrays - find lowest value for each element given some intervals and its values -

i thinking this:

a market has n products , m sellers. each seller k, have triplet (i,j,p): means seller selling products numbered i, i+1, .., j each @ price p.

goal:
find lowest price each product (1..n) in market. can assume price of product infinity no seller exist.

example:
n=4, m=3 , 3 triplets (1,3,4), (2,3,2), (3,4,1). lowest values products (1..4) are: (4, 2, 1, 1).

the o(nm) solution trivial. can use binary indexed tree range updates , point query in o(n+ mlogn).

can suggest easier method (may sorting) in o(nlogn)?

you can preprocess in o(m*(logn+logm)) , answer each query in o(logn) using segment tree, described here algorithm gym :: data structures - codeforces.

for problem:

• for each interval, update corresponding nodes in segment tree. (note here need use lazy propagation, described in above link)
• after update done, can use segment tree answer queries.