Codeforces Round #737 (Div. 2) D. Ezzat and Grid

题目链接
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

The first line contains two integers $n$ and $m$ ($1\le n,m\le 3\cdot 10^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

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,\dots ,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.

Examples

input

3 6
1 1 1
1 7 8
2 7 7
2 15 15
3 1 1
3 15 15
1
2
3
4
5
6
7

output

0
1

B题两次读错题加上D题一开始以为是图论，导致想到正解却没写完
对于每一行，该行的区间与其覆盖到的之前的区间之间进行dp转移，可以用线段树维护。

#include <bits/stdc++.h>

using namespace std;
const int N = 3e5 + 10;

struct Seg_Tree {
    struct {
        int l, r;
        pair<int, int> cur, add;
    } t[N << 3];

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
    }

    inline void spread(int p) {
        if (!t[p].add.first) return;
        t[p << 1].cur = max(t[p << 1].cur, t[p].add);
        t[p << 1 | 1].cur = max(t[p << 1 | 1].cur, t[p].add);
        t[p << 1].add = max(t[p << 1].add, t[p].add);
        t[p << 1 | 1].add = max(t[p << 1 | 1].add, t[p].add);
    }

    void change(int p, int l, int r, pair<int, int> v) {
        if (l <= t[p].l && t[p].r <= r) {
            t[p].add = max(t[p].add, v);
            t[p].cur = max(t[p].cur, v);
            return;
        }
        spread(p);
        int mid = (t[p].l + t[p].r) >> 1;
        if (l <= mid) change(p << 1, l, r, v);
        if (r > mid) change(p << 1 | 1, l, r, v);
        t[p].cur = max(t[p << 1].cur, t[p << 1 | 1].cur);
    }

    pair<int, int> ask(int p, int l, int r) {
        if (l <= t[p].l && r >= t[p].r) return t[p].cur;
        spread(p);
        int mid = (t[p].l + t[p].r) >> 1;
        pair<int, int> res = {0, 0};
        if (l <= mid) res = ask(p << 1, l, r);
        if (r > mid) res = max(res, ask(p << 1 | 1, l, r));
        return res;
    }
} S;

int n, m, pre[N];
vector<pair<int, int>> seg[N];
vector<int> seq;
bool v[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, id, l, r; i <= m; i++) {
        scanf("%d%d%d", &id, &l, &r);
        seg[id].emplace_back(l, r);
        seq.push_back(l), seq.push_back(r);
    }
    sort(seq.begin(), seq.end());
    seq.erase(unique(seq.begin(), seq.end()), seq.end());
    for (int i = 1; i <= n; i++)
        for (auto &it : seg[i]) {
            it.first = lower_bound(seq.begin(), seq.end(), it.first) - seq.begin() + 1;
            it.second = lower_bound(seq.begin(), seq.end(), it.second) - seq.begin() + 1;
        }
    S.build(1, 1, (int) seq.size());
    for (int i = 1; i <= n; i++) {
        pair<int, int> cur = {0, 0};
        for (auto it : seg[i]) cur = max(cur, S.ask(1, it.first, it.second));
        pre[i] = cur.second, cur.second = i, cur.first++;
        for (auto it : seg[i]) S.change(1, it.first, it.second, cur);
    }
    for (int i = S.t[1].cur.second; i; i = pre[i]) v[i] = true;
    int num = n - S.t[1].cur.first;
    printf("%d\n", num);
    for (int i = 1, j = 0; i <= n; i++)
        if (!v[i]) printf("%d%c", i, ++j == num ? '\n' : ' ');
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84