POSTERS  Election Posters
A parliamentary election was being held in Byteland. Its enterprising and orderly citizens decided to limit the entire election campaign to a single dedicated wall, so as not to ruin the panorama with countless posters and billboards. Every politician was allowed to hang exactly one poster on the wall. All posters extend from top to bottom, but are hung at different points of the wall, and may be of different width. The wall is divided horizontally into sections, and a poster completely occupies two or more adjacent sections.
With time, some of the posters were covered (partially or completely) by those of other politicians. Knowing the location of all the posters and the order in which they were hung, determine how many posters have at least one visible section in the end.
Input
The input begins with the integer t, the number of test cases. Then t test cases follow.
Each test case begins with a line containing integer n  the number of posters (1 <= n <= 40000). Then n lines follow, the ith (1 <= i <= n) containing exactly two integers l_{i} r_{i}, denoting the numbers of the leftmost and rightmost sections covered by the ith poster (1 <= l_{i} < r_{i} <= 10^{7}). The input order corresponds to the order of hanging posters.
Output
For each test case output a line containing one integerĀ  the number of posters with visible sections.
Example
Sample input: 1 5 1 4 2 6 8 10 3 4 7 10 Sample output: 4
An illustration of the sample input is given below.
hide comments
kumarpritam863:
20200907 11:07:45
coordinate compression is the easiest way to solve although can be solved using lazy propagation and dsu. 

geek_goku6:
20200726 22:10:16
Can someone tell me how to do this problem with lazy propagation. Email id: ssrivastava990@gmail.com Last edit: 20200727 13:58:12 

thanos_tapras:
20200615 21:36:35
Nice problem!


nafisa_naznin:
20200611 14:25:10
@fahimcp495. You said,


fahimcp495:
20200603 02:33:17
it seems to me that the judge solution is not right according to the problem statement.


masterchef2209:
20200407 09:38:35
nice lazy propogation,segtree+coordinate compression 

aayush_b1999:
20200328 12:52:13
can be solved using coordinate compression and sqrt decomposition 

chinhchamhoc:
20191129 04:22:32
could someone tells me how to solve using DSU pls 

hduoc2003:
20190928 18:08:29
Weak test cases.


prmondal:
20190701 17:39:21
Last edit: 20190705 08:55:25 
Added by:  adrian 
Date:  20040719 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  VI Polish Collegiate Team Programming Contest (AMPPZ), 2001 