CF1557

Codeforces Round #737 (Div. 2)

D. Ezzat and Grid

题意

给出一个 $n\cdot 10^9$ 的网格，初始网格上的数字都是0，再给出 $m$ 个横向区间该区间上的数字都是1
每个横向区间用 $i, l, r$ 表示，第 $i$ 行上列号为 $[l,r]$ 上的数字都是1，如 $1, 3, 4$ 表示第1行上 $[3,4]$ 列上都是1

现在可以删去一些行，使得剩下的行中的任意相邻两行至少有一列都是1

求最少的删去行数，并输出删去的行号

思路

最一开始想到了dp但没有往下像，因为感觉空间复杂度炸了，结果是可以优化一维的

令 $f(i, j)$ 表示前 $i$ 行中最大的剩余行数，且剩余的最后一行的第 $j$ 列为1

那么对于当前第 $i$ 行有转移：

$$f(i,j) = \begin{cases} 1+\max\limits_{k\in C_i} f(i-1,k), &grid(i, j) = 1;\\ f(i-1,j), &grid(i, j)=0. \end{cases}\\$$

其中 $C_i$ 为第 $i$ 行中为1的列号

通过上面的转移方程可以发现，dp的第一维是可以去掉的，可以通过线段树优化第二维转移时间复杂度为 $O(logM)$ (需要先离散一下)

然后就是求解最后要删除的行号，因为删除的行号等价于求解最后保留的行号，对于第 $i$ 行，一定可以在线段树上找到最大的 $val$ 对应的顶点，将每个顶点再存储一个行号，代表上次最大值更新是通过该行更新过来的，那么当前的第 $i$ 行的上一行就是最大 $val$ 顶点对应的行号，存储下来，最后最大保留的行号就能形成一条链，通过线段树根顶点的行号，倒序求出链上的结点就是最大可以保留的行号

总时间复杂度 $O(NlogM)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
#define ls (p << 1)
#define rs (p << 1 | 1)
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 6e5 + 10;
struct SEG {
	struct Node {
		int l, r, mx, idx, cg;
	}t[N<<2];
	void build(int p, int l, int r) {
		t[p].l = l, t[p].r = r;
		t[p].mx = 0, t[p].cg = t[p].idx = -1;
		if (l == r) {
			return;
		}
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
	}
	void calc(int p, int x, int id) {
		t[p].mx = t[p].cg = x;
		t[p].idx = id;
	}
	void pushdown(int p) {
		if (t[p].cg != -1) {
			calc(ls, t[p].cg, t[p].idx);
			calc(rs, t[p].cg, t[p].idx);
			t[p].cg = -1;
		}
	}
	void pushup(int p) {
		t[p].mx = max(t[ls].mx, t[rs].mx);
		t[p].idx = (t[ls].mx >= t[rs].mx) ? t[ls].idx : t[rs].idx;
	}
	void update(int p, int l, int r, int x, int id) {
		if (t[p].l > r || t[p].r < l) return;
		if (t[p].l >= l && t[p].r <= r) {
			calc(p, x, id);
			return;
		}
		pushdown(p);
		update(ls, l, r, x, id);
		update(rs, l, r, x, id);
		pushup(p);
	}
	pii query(int p, int l, int r) {
		if (t[p].l > r || t[p].r < l) return mkp(0, -1);
		if (t[p].l >= l && t[p].r <= r) {
			return mkp(t[p].mx, t[p].idx);
		}
		pushdown(p);
		pii L = query(ls, l, r), R = query(rs, l, r);
		return (L.first >= R.first) ? L : R;
	}
}seg;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vi hsh, pre(n, -1);
	vip a(n);
	for (int i = 0; i < m; i++) {
		int id, l, r;
		cin >> id >> l >> r;
		a[id-1].pb({l, r});
		hsh.pb(l);
		hsh.pb(r);
	}
	sort(hsh.begin(), hsh.end());
	hsh.resize(unique(hsh.begin(), hsh.end()) - hsh.begin());
	seg.build(1, 0, hsh.size() - 1);
	for (int i = 0; i < n; i++) {
		int mx = 0, prt = -1;
		for (auto &j : a[i]) {
			j.first = lower_bound(hsh.begin(), hsh.end(), j.first) - hsh.begin();
			j.second = lower_bound(hsh.begin(), hsh.end(), j.second) - hsh.begin();
			pii tmp = seg.query(1, j.first, j.second);
			if (tmp.first > mx) {
				mx = tmp.first;
				prt = tmp.second;
			}
		}
		pre[i] = prt;
		for (auto j : a[i]) {
			seg.update(1, j.first, j.second, mx+1, i);
		}
	}
	cout << n - seg.t[1].mx << '\n';
	vi vis(n);
	for (int i = seg.t[1].idx; i >= 0; i = pre[i]) {
		vis[i] = 1;
	}
	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			cout << i+1 << ' ';
		}
	}
	cout << '\n';
	return 0;
}