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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
struct Node { // 线段节点
int l, r, mid;
PII mx, tag; // val为线段和的值, tag为标记值
} t[MAXN << 3]; // 线段节点要开4倍数据点的大小
/* 更新一条完整的线段 */
void updateNode(int u, PII d) {
t[u].mx = max(t[u].mx, d);
t[u].tag = max(t[u].tag, d); //打上标记, 不再往下
}
/* 将标记下放 */
void pushDown(int u) {
updateNode(LCH(u), t[u].tag);
updateNode(RCH(u), t[u].tag);
t[u].tag = {0, 0}; //取消标记
}
/* 由左右儿子线段合并更新当前线段 */
void pushUp(int u) {
t[u].mx = max(t[LCH(u)].mx, t[RCH(u)].mx);
}
/* 递归建树 */
void build(int l, int r, int u) {
t[u] = Node{l, r, (l+r)>>1, {0, 0}, {0, 0}};
if (l == r) return; //该线段只有一个点
else { //分成左右两边递归求和
build(l, t[u].mid, LCH(u));
build(t[u].mid+1, t[u].r, RCH(u));
pushUp(u);
}
}
/* 初始化一棵线段树 */
void init(int _n) {
build(1, _n, 1);
}
/* 区间修改 */
void update(int l, int r, PII d, int u = 1) {
if (t[u].l == l && t[u].r == r)
updateNode(u, d); // 找到对应线段更新
else {
pushDown(u); // 访问u的儿子线段, 需要先下放标记更新
if (l > t[u].mid)
update(l, r, d, RCH(u)); //更新的线段全在该区间右边
else if (r <= t[u].mid)
update(l, r, d, LCH(u)); // 全在左边
else { // 跨越了左右两边
update(l, t[u].mid, d, LCH(u));
update(t[u].mid+1, r, d, RCH(u));
}
pushUp(u); // 由儿子线段的更新后的值计算当前线段值
}
}
/* 区间查询 */
PII query(int l, int r, int u = 1) {
if (t[u].l == l && t[u].r == r) return t[u].mx;
pushDown(u);
if (l > t[u].mid) return query(l, r, RCH(u));
if (r <= t[u].mid) return query(l, r, LCH(u));
else return max(query(l, t[u].mid, LCH(u)),
query(t[u].mid+1, r, RCH(u)));
}
int n, m, dp[MAXN], path[MAXN];
vector<PII> ones[MAXN];
VI b;
bool remain[MAXN];
int getID(int x) {
return lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int id, l, r;
scanf("%d%d%d", &id, &l, &r);
b.push_back(l), b.push_back(r);
ones[id].emplace_back(l, r);
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (int i = 1; i <= n; i++)
for (int j = 0; j < ones[i].size(); j++) {
auto[l, r] = ones[i][j];
ones[i][j] = make_pair(getID(l), getID(r));
}
init(b.size());
for (int i = 1; i <= n; i++) {
PII k = {0, 0};
for (auto[l, r] : ones[i])
k = max(k, query(l, r));
auto[mx, id] = k;
dp[i] = mx + 1, path[i] = id;
for (auto[l, r] : ones[i])
update(l, r, make_pair(dp[i], i));
}
auto[ans, last] = query(1, b.size());
ans = n - ans;
while (last) {
remain[last] = 1;
last = path[last];
}
printf("%d\n", ans);
for (int i = 1; i <= n; i++)
if (!remain[i])
printf("%d%c", i, "\n "[--ans>0]);
return 0;
}
|