Ezzat and Grid
Contest: Codeforces Round 737 (Div. 2)
Difficulty rating: 2200
Tags: data structures, dp, greedy

Moamen was drawing a grid of $$$n$$$ rows and $$$10^9$$$ columns containing only digits $$$0$$$ and $$$1$$$. Ezzat noticed what Moamen was drawing and became interested in the minimum number of rows one needs to remove to make the grid beautiful.

A grid is beautiful if and only if for every two consecutive rows there is at least one column containing $$$1$$$ in these two rows.

Ezzat will give you the number of rows $$$n$$$, and $$$m$$$ segments of the grid that contain digits $$$1$$$. Every segment is represented with three integers $$$i$$$, $$$l$$$, and $$$r$$$, where $$$i$$$ represents the row number, and $$$l$$$ and $$$r$$$ represent the first and the last column of the segment in that row.

For example, if $$$n = 3$$$, $$$m = 6$$$, and the segments are $$$(1,1,1)$$$, $$$(1,7,8)$$$, $$$(2,7,7)$$$, $$$(2,15,15)$$$, $$$(3,1,1)$$$, $$$(3,15,15)$$$, then the grid is:

Your task is to tell Ezzat the minimum number of rows that should be removed to make the grid beautiful.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 3\cdot10^5$$$).

Each of the next $$$m$$$ lines contains three integers $$$i$$$, $$$l$$$, and $$$r$$$ ($$$1 \le i \le n$$$, $$$1 \le l \le r \le 10^9$$$). Each of these $$$m$$$ lines means that row number $$$i$$$ contains digits $$$1$$$ in columns from $$$l$$$ to $$$r$$$, inclusive.

Note that the segments may overlap.

Output format:
In the first line, print a single integer $$$k$$$ — the minimum number of rows that should be removed.

In the second line print $$$k$$$ distinct integers $$$r_1, r_2, \ldots, r_k$$$, representing the rows that should be removed ($$$1 \le r_i \le n$$$), in any order.

If there are multiple answers, print any.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
In the first test case, the grid is the one explained in the problem statement. The grid has the following properties:

1. The $$$1$$$-st row and the $$$2$$$-nd row have a common $$$1$$$ in the column $$$7$$$.
2. The $$$2$$$-nd row and the $$$3$$$-rd row have a common $$$1$$$ in the column $$$15$$$.

In the second test case, the given grid is as follows:

Example input:
3 6
1 1 1
1 7 8
2 7 7
2 15 15
3 1 1
3 15 15

Example output:
0

Example input:
5 4
1 2 3
2 4 6
3 3 5
5 1 1

Example output:
3
2 4 5

Editorial:
We can use dynamic programming to get the maximum number of rows that make a beautiful grid.
Define the 2d array $$$dp$$$, where $$$dp_{i,j}$$$ $$$=$$$ maximum number of rows from row $$$1$$$ to row $$$i$$$ that make a beautiful grid, and the last row I keep have $$$1$$$ in the column $$$j$$$.
Form the definition:
- $$$dp_{0,j}$$$ $$$=$$$ $$$0$$$.
- $$$dp_{i,j}$$$ = $$$1$$$ $$$+$$$ $$$\max_{k \in C_i}$$$ $$$dp_{i-1,k}$$$ ,if $$$grid_{i,j}$$$ $$$=$$$ $$$1$$$.
- otherwise $$$dp_{i,j}$$$ = $$$\max_{k \in C_i}$$$ $$$dp_{i-1,k}$$$.
where $$$C_i$$$ is that set of columns that contains $$$1$$$ in row $$$i$$$.
As you know the set $$$C_i$$$ is intervals, so I just search in some intervals for the maximum or update some intervals in the previous layer in $$$dp$$$. We can do It faster with [Segment tree](https://cp-algorithms.com/data_structures/segment_tree.html).
**So the algorithm will be as follow:**
- Define an array $$$prev$$$, where $$$prev_i$$$ $$$=$$$ the previous row of $$$i$$$ in maximum beautiful grid end with $$$i$$$ row, you will use it to know the rows you will not remove.
- Build a segment tree of pairs (value, index) initially with {$$$0$$$ $$$,$$$ $$$-1$$$}.
- then for $$$i$$$ from 1 to $$$n$$$:  - get max value in all ranges $$$[l_j,r_j]$$$ that contains $$$1$$$ of the $$$i$$$ row, let call it $$$mx$$$.
- store $$$prev_{i}$$$ $$$=$$$ $$$mx.index$$$.
- update all ranges $$$[l_j,r_j]$$$ of this row with $$$seg_j$$$ = $$$max($$$ $$$seg_j$$$ $$$,$$$ { $$$mx.value$$$ $$$+$$$ $$$1$$$ $$$,$$$ $$$i$$$ }$$$)$$$.
- and finally, you can get the rows you can keep to get the maximum using the $$$prev$$$ array, and remove others.
the total complixty will be $$$\mathcal{O}(n + m\log{}10^9)$$$ Or $$$\mathcal{O}(n + m\log{}m)$$$ If you do a coordinate compression to values.