C/C++教程

codeforces 1557D Ezzat and Grid 线段树 DP

本文主要是介绍codeforces 1557D Ezzat and Grid 线段树 DP,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

首先要把求最少删几个改为最多留几个这一转换,因为求最多留几个可以用类似最长上升子序列的dp,从所有的合法前继转移过来。

如果把所有的1区间看成是点,有相交的区间之间,从行号小的向行号大的连边,那么会形成一张DAG,求出最长路即为最多能保留几个。但边数可以到\(O(m^2)\)级别。考虑最终答案的连边方式,如果答案中有a->b->c,那么a->c这条边若存在也不会用上。因此每个区间只需要从行号比其小且以其为终点的最长路最长的区间连一条边过来就行。 对区间查询max并修改可以使用线段树。

写成dp的形式就是,枚举当前第\(i\)行的区间\([l,r]\),在线段树中查找\([l,r]\)内前\(i\)行dp值最大的行(记为\(j\)),那么\(dp[i]=max(dp[i],dp[j]+1)\)

由于每个区间内的dp值都是单调递增的,更新完答案后直接区间修改即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 7, maxm = maxn << 3;
#define ls p << 1
#define rs p << 1 | 1
typedef pair<int, int> pii;
pii mx[maxm], tag[maxm];
int dp[maxn], a[maxn << 1], n, m, tot, P[maxn], vis[maxn];
vector<pii> vec[maxn];
map<int, int> ID;
int rd() {int s = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') {s = s * 10 + c - '0'; c = getchar(); } return s * f;}
void up(int p) {
	if (mx[ls].first > mx[rs].first) mx[p] = mx[ls];
	else mx[p] = mx[rs];
}
void down(int p, int l, int r) {
	if (tag[p].second) {
		mx[ls] = mx[rs] = tag[ls] = tag[rs] = tag[p];
		tag[p] = make_pair(0, 0);
	}
}
void modify(int p, int l, int r, int x, int y, pii v) {
	if (x <= l && r <= y) {
		mx[p] = tag[p] = v;
		return;
	}
	int mid = l + r >> 1;
	down(p, l, r);
	if (x <= mid) {
		modify(ls, l, mid, x, y, v);
	}
	if (y > mid) {
		modify(rs, mid + 1, r, x, y, v);
	}
	up(p);
}
pii query(int p, int l, int r, int x, int y) {
	if (x <= l && r <= y) {
		return mx[p];
	}
	int mid = l + r >> 1;
	down(p, l, r);
	pii res = make_pair(0, 0), ll = res, rr = res;
	if (x <= mid) {
		ll = query(ls, l, mid, x, y);
		if (ll.first > res.first) res = ll;
	}
	if (y > mid) {
		rr = query(rs, mid + 1, r, x, y);
		if (rr.first > res.first) res = rr;
	}
	return res;
}
int main() {
	n = rd(), m = rd();
	for (int i = 1; i <= m; i++) {
		int ii = rd(), l = rd(), r = rd();
		a[++tot] = l; a[++tot] = r;
		vec[ii].push_back(make_pair(l, r));
	}
	sort(a+1, a+2*m+1);
	tot = 0;
	for (int i = 1; i <= 2*m; i++) {
		if (i == 1 || a[i] != a[i-1]) {
			a[++tot] = a[i];
			ID[a[tot]] = tot;
		}
	}
	int mxi = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < vec[i].size(); j++) {
			int l = ID[vec[i][j].first], r = ID[vec[i][j].second];
			pii pre = query(1, 1, tot, l, r);
			if (dp[pre.second] + 1 > dp[i]) {
				dp[i] = dp[pre.second] + 1;
				P[i] = pre.second;
				if (dp[i] > dp[mxi]) {
					mxi = i;
				}
			}
		}
		for (int j = 0; j < vec[i].size(); j++) {
			int l = ID[vec[i][j].first], r = ID[vec[i][j].second];
			modify(1, 1, tot, l, r, make_pair(dp[i], i));
		}
	}
	printf("%d\n", n-dp[mxi]);
	for (; mxi; mxi = P[mxi]) vis[mxi] = 1;
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) printf("%d ", i);
	}
}
这篇关于codeforces 1557D Ezzat and Grid 线段树 DP的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!