Moamen was drawing a grid of ??n rows and 109109 columns containing only digits 00 and 11. 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 11 in these two rows.
Ezzat will give you the number of rows ??n, and ??m segments of the grid that contain digits 11. 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 ??=3n=3, ??=6m=6, and the segments are (1,1,1)(1,1,1), (1,7,8)(1,7,8), (2,7,7)(2,7,7), (2,15,15)(2,15,15), (3,1,1)(3,1,1), (3,15,15)(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≤??,??≤3?1051≤n,m≤3?105).
Each of the next ??m lines contains three integers ??i, ??l, and ??r (1≤??≤??1≤i≤n, 1≤??≤??≤1091≤l≤r≤109). Each of these ??m lines means that row number ??i contains digits 11 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 ??1,??2,…,????r1,r2,…,rk, representing the rows that should be removed (1≤????≤??1≤ri≤n), in any order.
If there are multiple answers, print any.
Examples
input
Copy
3 6
1 1 1
1 7 8
2 7 7
2 15 15
3 1 1
3 15 15
output
Copy
0
input
Copy
5 4
1 2 3
2 4 6
3 3 5
5 1 1
output
Copy
3
2 4 5
线段树优化DP。很显然首先要对数据进行离散化（当然也可以直接动态开点）。然后按行考虑，会发现这是一个类似求最长上升子序列的过程，最终答案就是用n减去求出来的这个长度。能够发生转移当且仅当前一行和当前行的某个位置都有1。考虑对离散化后的列的范围建线段树，线段树上维护区间最值以及对应的行号以及支持区间覆盖的操作。对于每一行的所有线段，先依次取出来，查询其对应的范围里包含的最大的dp值（即查询区间最值）以及对应的行号（因为相邻行同一个位置有1才可以，否则就要进行删除），所有查询出来的值取max再+1得到当前行的dp值并更新答案（行号是用来最后输出方案的）。然后再遍历这一行的所有线段，用当前行的dp值更新线段树的区间（即进行区间覆盖）即可。
注意：
if(t[p].l >= L && t[p].r <= R) {
t[p].dp = v;
t[p].id = id;
t[p].tag1 = v;
t[p].tag2 = id;
return;
}
此处不论v是否大于t[p].dp 都要进行更新。
#include <bits/stdc++.h>
#define fi first
#define se second
#define N 800005
using namespace std;
int n, m;
struct line {
int l, r;
};
vector<line> b[N];
struct SegmentTree {
int p, l, r;
int dp;//区间最大值
int id;//这个最大值对应的行号 便于输出
int tag1, tag2;
} t[N * 4];
int root, tot;
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
t[p].tag1 = t[p].tag2 = -1;
if(l == r) {
t[p].dp = t[p].id = 0;
return;
}
int mid = (l + r) >> 1;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
t[p].dp = t[p].id = 0;
return;
}
void spread(int p) {
if(t[p].tag1 != -1) {
t[2 * p].dp = t[p].tag1;
t[2 * p].tag1 = t[p].tag1;
t[2 * p].id = t[p].tag2;
t[2 * p].tag2 = t[p].tag2;
t[2 * p + 1].dp = t[p].tag1;
t[2 * p + 1].tag1 = t[p].tag1;
t[2 * p + 1].id = t[p].tag2;
t[2 * p + 1].tag2 = t[p].tag2;
t[p].tag1 = t[p].tag2 = -1;
}
}
pair<int, int> query(int p, int L, int R) {
if(t[p].l >= L && t[p].r <= R) {
return make_pair(t[p].dp, t[p].id);
}
spread(p);
int mid = (t[p].l + t[p].r) >> 1;
int mx = 0, id = 0;
pair<int, int> ret = {0, 0};
if(L <= mid) ret = query(2 * p, L, R);
if(R > mid) {
pair<int, int> tmp = query(2 * p + 1, L, R);
if(tmp.fi > ret.fi) {
ret.fi = tmp.fi;
ret.se = tmp.se;
}
}
return ret;
}
void modify(int p, int L, int R, int v, int id) {
if(t[p].l >= L && t[p].r <= R) {//注意 不论v是否大于t[p].dp 都要进行更新
t[p].dp = v;
t[p].id = id;
t[p].tag1 = v;
t[p].tag2 = id;
return;
}
spread(p);
int mid = (t[p].l + t[p].r) >> 1;
if(L <= mid) modify(2 * p, L, R, v, id);
if(R > mid) modify(2 * p + 1, L, R, v, id);
t[p].dp = max(t[2 * p].dp, t[2 * p + 1].dp);
if(t[2 * p + 1].dp > t[2 * p].dp) {
t[p].dp = t[2 * p + 1].dp;
t[p].id = t[2 * p + 1].id;
} else {
t[p].dp = t[2 * p].dp;
t[p].id = t[2 * p].id;
}
}
int pre[N];
bool vis[N];
int ans = 0, last = 0;
int main() {
cin >> n >> m;
vector<int> v;
for(int i = 1; i <= m; i++) {
int row, l, r;
scanf("%d%d%d", &row, &l, &r);
v.push_back(l);
v.push_back(r);
b[row].push_back({l, r});
}
sort(v.begin(), v.end());
vector<int>::iterator it = unique(v.begin(), v.end());
v.erase(it, v.end());
for(int i = 1; i <= n; i++) {
for(int j = 0; j < b[i].size(); j++) {
b[i][j].l = lower_bound(v.begin(), v.end(), b[i][j].l) - v.begin() + 1;
b[i][j].r = lower_bound(v.begin(), v.end(), b[i][j].r) - v.begin() + 1;
}
}
build(1, 1, v.size());
for(int i = 1; i <= n; i++) {
int mx_result = 0, pre_row = 0;
for(int j = 0; j < b[i].size(); j++) {
pair<int, int> tmp = query(1, b[i][j].l, b[i][j].r);
if(tmp.fi > mx_result) {
mx_result = tmp.fi;
pre_row = tmp.se;
}
}
int dp = mx_result + 1;
pre[i] = pre_row;
if(dp > ans) {
ans = dp;
last = i;
}
for(int j = 0; j < b[i].size(); j++) {
modify(1, b[i][j].l, b[i][j].r, dp, i);
}
}
cout << n - ans << ‘\n‘;
int now = last;
vis[now] = 1;
while(pre[now]) {
now = pre[now];
vis[now] = 1;
}
vector<int> aa;
int fk = 0;
for(int i = 1; i <= n; i++) {
if(!vis[i]) cout << i << " ";
}
return 0;
}