P8592 『JROI-8』颅脑损伤 2.0（加强版）（线性 dp + 单调队列优化）

P8592 『JROI-8』颅脑损伤 2.0（加强版）

线性 dp + 单调队列优化

最优化问题，考虑 dp。先离散化，按左端点排序，设 \(f_i\) 表示考虑完前 \(i\) 条线段符合条件的染色，最小长度和。转移枚举上一条红色线段 \(j\)，\(f_i=f_j+len_i\)。当然 \(j\) 需要满足题目的条件，即 \((j,i)\) 中的黑色线段要么与 \(i\) 有交，要么与 \(j\) 有交。

条件可以写成，对于 \(r_k<l_i\) 的线段，一定有 \(r_k\le r_j\)，也就是 \(\max(r_k)\le l_j\)。

设 \(b_{r_j}=l_j\)，那么 \(\max(r_k)\) 就是 \(b\) 序列上一段前缀 \(\max\)，可以预处理 \(g_i=\max\limits_{j\le i}b_j\)。

重写一下状态转移方程：

复杂度 \(O(n^2)\)。

发现 \(l_i\) 单调递增，\(g_{l_i}\) 只与 \(l_i\)，所以前缀 \(\max\) 也单调递增，那么转移位置就是一段不断向右的区间，单调队列优化到 \(O(n)\)。

注意单调队列的写法，每次查询都要先把 \(<l_i\) 的位置插入一遍。为了方便，也修改了状态下标的意义，具体看代码。

复杂度 \(O(n\log n)\)，瓶颈是离散化，但可以用基数排序做到 \(\Theta(n)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;
int n;
struct node {
	i64 l, r, len;
	friend bool operator < (node a, node b) {
		return a.l < b.l;
	}
} a[N];
i64 b[N << 1], g[N << 1], f[N << 1], q[N << 1], pos[N << 1];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	std::cin >> n;

	for (int i = 1; i <= n; i++) {
		std::cin >> a[i].l >> a[i].r;
		b[i] = a[i].l, b[i + n] = a[i].r;
		a[i].len = a[i].r - a[i].l;
	}
	i64 m = (n << 1);
	std::sort(b + 1, b + m + 1);
	m = std::unique(b + 1, b + m + 1) - b - 1;

	for (int i = 1; i <= n; i++) {
		a[i].l = std::lower_bound(b + 1, b + m + 1, a[i].l) - b;
		a[i].r = std::lower_bound(b + 1, b + m + 1, a[i].r) - b;
	}
	std::sort(a + 1, a + n + 1);

	for (int i = 1; i <= n; i++) pos[a[i].r] = std::max(pos[a[i].r], a[i].l);
	for (int i = 1; i <= m; i++) g[i] = std::max(g[i - 1], pos[i]);

	i64 h = 1, t = 1, nw = 1;
	memset(f, 0x3f, sizeof(f));
	f[0] = 0;
	i64 ans = linf;
	for (int i = 1; i <= n; i++) {
		while(nw < a[i].l) {
			while(h <= t && f[q[t]] >= f[nw]) t--;
			q[++t] = nw++; 
		}
		while(h <= t && q[h] < g[a[i].l - 1]) h++;
		if(h <= t) f[a[i].r] = std::min(f[a[i].r], f[q[h]] + a[i].len);
		if(a[i].r >= a[n].l) ans = std::min(ans, f[a[i].r]);
	}

	std::cout << ans << "\n";

 	return 0;
}