题意：给你个n行1e9列的01矩阵。i行和i+1行是相邻的当且仅当存在一列，这两行这一列的数都是1。问最少删掉多少行，才能使对于每个1<=i<m，i行和i+1行都相邻。m是删掉之后的总行数。输出方案。
解：首先发现，两个行能够相邻，一定是通过某个两者都是1的位置联系起来。
怎么做呢，想了一想想到了连边图论，然后马上发现边数是n²的，那没事了。再进一步，想到了DO。就设f[i]表示选了第i行，前面的全都相邻，要删掉的最少行数。那么转移就是对于这一行每个是1的地方，如果前面某一行这里也是1，那么可以从那一行转移来，转移方程是f[i]=min(f[j]+(i-j-1))，发现这个转移方程可以化成f[i]-i=min(f[j]-j)-1，于是我们考虑维护一个数据结构来转移，存f[i]-i的最小值。如果第i行这里是1，就把数据结构的这里改成f[i]-i，查询的时候查询这一行是1的地方的最小值，再-1就可以了。最终答案就是f[n+1]+n+1
记录方案就是DO经典套路，转移的同时记。可以把来源和最值一起扔到线段树里来存。然后我写的时候修改不是区间取min而是区间覆盖，因为我赛时想的是靠后的转移一定更优。赛后证了一下，是对于k<j这两个可行的转移，一定可以把j到k的中间这些行全都删了，也就是f[j]<=f[k]+(j-k-1)，也就是f[j]-j<=f[k]-k-1<f[k]-k，所以越靠后的转移越优。
值域是1e9来着所以要离散化一下。我之前动态开点结果MLE on 1
1 /**
2 * There is no end though there is a start in space. ---Infinity.
3 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
4 * Only the person who was wisdom can read the most foolish one from the history.
5 * The fish that lives in the sea doesn't know the world in the land.
6 * It also ruins and goes if they have wisdom.
7 * It is funnier that man exceeds the speed of light than fish start living in the land.
8 * It can be said that this is an final ultimatum from the god to the people who can fight.
9 *
10 * Steins;Gate
11 **/
12
13 #include <bits/stdc++.h>
14 typedef long long LL;
15 inline char gc() {
16 return getchar();
17 static char buf[100000], *p1 = buf, *p2 = buf;
18 if(p1 == p2) {
19 p2 = (p1 = buf) + fread(buf, 1, 100000, stdin);
20 }
21 return (p1 == p2) ? EOF : *p1++;
22 }
23
24 template <typename T>
25 inline void read(T& x) {
26 x = 0;
27 char c(gc());
28 int f(1);
29 while(c < '0' || c > '9') {
30 if(c == '-') {
31 f = -1;
32 }
33 c = gc();
34 }
35 while(c >= '0' && c <= '9') {
36 x = x * 10 + c - '0';
37 c = gc();
38 }
39 x *= f;
40 }
41
42 inline LL read() {
43 LL x;
44 read(x);
45 return x;
46 }
47
48 const int N = 300010;
49
50 struct Node {
51 int l, r;
52 };
53 struct Data {
54 int val, id;
55 Data(int V = 0, int I = 0)
56 : val(V), id(I) {}
57 };
58 std::vector<Node> v[N];
59 int n, m, tot = 1, X[N * 2], top;
60 Data f[N];
61 Data Min[N * 8], tag[N * 8];
62 Data exmin(Data a, Data b) {
63 if(!a.id)
64 return b;
65 if(!b.id)
66 return a;
67 if(a.val < b.val) {
68 return a;
69 }
70 return b;
71 }
72 inline void pushdown(int o) {
73 if(tag[o].id) {
74 int ls = o << 1, rs = o << 1 | 1;
75 tag[ls] = Min[ls] = tag[o];
76
77 tag[rs] = Min[rs] = tag[o];
78
79 tag[o] = Data(0, 0);
80 }
81 }
82 inline void pushup(int o) {
83 Min[o] = exmin(Min[o << 1], Min[o << 1 | 1]);
84 }
85 void change(int L, int R, int v, int id, int l, int r, int o) {
86 if(L <= l && r <= R) {
87 tag[o] = Min[o] = Data(v, id);
88 return;
89 }
90 pushdown(o);
91 int mid = (l + r) >> 1;
92 if(L <= mid) {
93 change(L, R, v, id, l, mid, o << 1);
94 }
95 if(mid < R) {
96 change(L, R, v, id, mid + 1, r, o << 1 | 1);
97 }
98 pushup(o);
99 }
100
101 Data getMin(int L, int R, int l, int r, int o) {
102 if(L <= l && r <= R) {
103 return Min[o];
104 }
105 pushdown(o);
106 int mid = (l + r) >> 1;
107 Data ans(-1, 0);
108 if(L <= mid) {
109 ans = getMin(L, R, l, mid, o << 1);
110 }
111 if(mid < R) {
112 ans = exmin(ans, getMin(L, R, mid + 1, r, o << 1 | 1));
113 }
114 return ans;
115 }
116
117 int main() {
118 // printf("%d\n", (sizeof(ls) + sizeof(rs) + sizeof(tag) + sizeof(Min) + sizeof(v)) / 1048576);
119
120 read(n);
121 read(m);
122 for(int i = 1, x, l, r; i <= m; i++) {
123 read(x);
124 read(l);
125 read(r);
126 v[x].push_back(Node{l, r});
127 X[++top] = l;
128 X[++top] = r;
129 }
130 std::sort(X + 1, X + top + 1);
131 top = std::unique(X + 1, X + top + 1) - X - 1;
132 for(int i = 1; i <= n; i++) {
133 for(int j = 0; j < v[i].size(); j++) {
134 v[i][j].l = std::lower_bound(X + 1, X + top + 1, v[i][j].l) - X;
135 v[i][j].r = std::lower_bound(X + 1, X + top + 1, v[i][j].r) - X;
136 }
137 }
138 for(int i = 1; i <= n; i++) {
139 for(Node node : v[i]) {
140 int L = node.l, R = node.r;
141 f[i] = exmin(f[i], getMin(L, R, 1, top, 1));
142 }
143 f[i].val--;
144 for(Node node : v[i]) {
145 int L = node.l, R = node.r;
146 change(L, R, f[i].val, i, 1, top, 1);
147 }
148 // printf("f %d = %d from %d \n", i, f[i].val + i, f[i].id);
149 }
150 f[n + 1] = Min[1];
151 f[n + 1].val--;
152 printf("%d\n", f[n + 1].val + n + 1);
153 int p = n + 1;
154 while(p) {
155 int nexP = f[p].id;
156 for(int i = nexP + 1; i < p; i++) {
157 printf("%d ", i);
158 }
159 p = nexP;
160 }
161
162 return 0;
163 }
AC代码