CLFLARR  COLORFUL ARRAY
You have been given an array of n unpainted elements. By unpainted, we mean that each element initially has a value of 0. You have to process q queries of the form l r c, in which you paint all the elements of the array from index l to index r with color c. Assume that, each new color currently being applied to an element overrides its previous color. Output the color of each element after all the queries have been processed.
Note: The problem is guaranteed to be solved using C or C++ programming language.
Input
The first line of input consists of two integers n and q. Next q lines consists of 3 integers l, r and c denoting the starting index, ending index and the color respectively.
 1 <= n <= 200000
 1 <= q <= 200000
 1 <= l <= r <= n
 1 <= c <= 1 000 000 000
Output
Output the final color of each element starting from index 1 on a new line.
Example
Input 4 3 1 3 2 2 4 6 2 3 7 Output: 2 7 7 6
Input 10 5 3 9 13 1 4 9 2 10 14 2 7 10 6 9 44 Output 9 10 10 10 10 44 44 44 44 14
hide comments
koustubh38:
20230711 13:37:57
Here' a solution using heap and the set approach is also discussed


fuadul_hasan:
20220428 16:23:35
nice one.. it took me 3h to solve but give me so much fun.


ayush_shaz:
20220421 08:04:48
It can also be done in n+q using heap. 

mahbubkuet08:
20220201 10:19:24
This is an offline query problem. Using segment trees will be overkill. Solved using DSU. 

anil_1:
20210922 18:21:52
Can someone tell me how to do it using DSU. 

kumar_sunny:
20210402 08:59:01
No need to use DSU..just an optimistation on array...basically implementation based problem. 

dpw4112001:
20210212 11:59:52
its passing N^2 . TC are not strong 

nikhil_kmtnk:
20210116 10:09:55
This problem can also be solved using sets of C++ STL. Using lower_bound() and upper_bound() function this problem can be easily solved. 

aman_bedi:
20200828 12:53:30
Segment tree with lazy propogation can take time but dsu make it superfast


gnomegeek:
20200805 01:43:29
AC in one go. SegTree with Lazy. 
Added by:  No_idea 
Date:  20190321 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Competitive Programming Community 