自动搬运

查看原文

来自洛谷，原作者为

	jr_linys 人要学会认识自己

搬运于2025-08-24 22:40:29，当前版本为作者最后更新于2023-08-08 21:19:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

2023/8/9 把这篇烂题解翻了出来，优化了分析，没那么烂了

2023/8/12 对最新数据进行更新。

题目传送门:普通版 加强版

前言

赛时第 $3$ 题推了个柿子调不出来，直接开摆，没看第4题。赛后一看好像还挺简单，小WA一下，开个 long long 就 AC 了。

$O(n^2)$ 和 $O(n\log n)$ 本题解都有。

---

题目大意直接 copy

给定 $n$ 条线段，第 $i$ 条是 $[l_i,r_i]$。将每一条线段染成红色或黑色，要求：

1. 任意两条红色线段不相交。
2. 任意一条黑色线段至少和一条红色线段相交。

请最小化红色线段的长度和，并输出这个长度和。

一条线段 $[l_i,r_i]$ 的长度定义为 $r_i-l_i$，两条线段 $[l_i,r_i],[l_j,r_j]$ 交当且仅当 $l_i\le r_j$ 且 $l_j\le r_i$。

数据范围

$n\le3000,-10^9\le l_i<r_i\le10^9$

困难版 $n\le5\times 10^5$

---

$O(n^2)$

普通版扫一眼数据范围，按出题套路肯定是 $O(n^2)$ DP。

排序 一般来说，需要给线段排个序，最基础的两种就是按前端排序和按后端排序。 考虑按后端排序，后端相等按前端排序，那么定义 $f_i$ 为按排序后第 $i$ 条线段染成红色,保证前 $i$ 条线段合法，红色线段的总长度。

状态转移 设左端点为 $x$，右端点为 $y$，上一条红线为第$j$ 条（$0\le j<i$）（$j=0$ 时第 $i$ 条线段为第 $1$ 条红线，不妨使 $x_0=y_0=-\infty$）。

1. 因为两条红线不可重叠，所以要保证 $y_j<x_i$。

2. 又要保证中间剩下的黑线（$j<k<i$）至少接触一条红线，对于 $x_i \le y_k$ 的黑线可以接触到第 $i$ 条线段，所以只要保证 $x_i>y_k$ 的线段要接触第 $j$ 条线段。

设 $p_i$ 为满足 $y_k<x_i$ 的最后后一条线段。 则要保证 $\max^{p_i}\limits_{k=j+1} x_k \le y_j$。由于 $l \in[0,j],x_l\le y_l\le y_j$，等价于 $\max^{p_i}\limits_{k=0} x_k \le y_j$。

3. 那么加上第 $i$ 条线段长度 $y_i-x_i$，总得（"[ ]"内的表示条件）

$$f_i= \min^{p_i}\limits_{j=0} [\max^{p_i}\limits_{k=0} x_k \le y_j] f_j+y_i-x_i $$

统计 红色线段要把所有黑色线断覆盖,对于每一个 $i$，若 $\max^{n} \limits_{j=0} x_j \le y_i$，则在保证前面合法的情况下，后面的线段也能被这条线段覆盖，所以可以作为最后一条红线。

---

$O(n^2)$ 代码

可结合注释李姐

提交记录

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=3*1e3,IINF=1e9+10;
const long long INF=1e18;
long long f[N+5],ans=INF;
struct stu{int x,y;}a[N+3];
bool cmp(stu a,stu b){//按后端排序，后端相等按前端排序
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}
int main(){
	int n,zmax=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
		zmax=max(zmax,a[i].x);//记录最大的左端点
	}
	sort(a+1,a+1+n,cmp);//排序
	a[0].x=-IINF,a[0].y=-IINF;//j=0时第i条线段为第1条红线,不妨使x[0]=y[0]=-无限
	for(int i=1;i<=n;i++){
		int j;
		for(j=i-1;a[j].y>=a[i].x;j--);//跳过y[j]>=x[i]的线段，这些线段能被第i条线段覆盖
		int maxx=-IINF;f[i]=INF;
		for(;j>=0&&a[j].y>=maxx;j--) f[i]=min(f[i],f[j]),maxx=max(maxx,a[j].x);//要满足中间的黑线对第i,j条线，至少触碰一条
		f[i]+=a[i].y-a[i].x;//加上本条线段长度
		if(a[i].y>=zmax) ans=min(ans,f[i]);//判断能否覆盖后面所有的线段，作为最后一条线段 更新
	}
	printf("%lld",ans);
}

$O(n\log n)$

26号，突然看见有困难版，便想用 双指针+线段树 优化，然后一直 WA，打了两个小时之后才发现被证伪了......别问为什么，问就是我太睿智了。普通版提交寄录

回归正题。其实上面 $O(n^2)$ 的代码已经有雏形了。

不难看出，第 $p_i$ 条线段一定可以满足转移的条件。 而以此线段为右端点向左扩展，$y_j$ 满足不上升，$\max^{p_i}\limits_{k=0} x_k \le y_j$ 满足不下降。

换句话说，可转移的上一条红线是一段区间，而且右端点可以二分，从右端点往左拓展也满足单调性。

所以可以二分左右端点，右端点为 $p_i$，左端点为满足 $\max^{p_i}\limits_{k=0} x_k \le y_j$ 的第一条。可用数组 $maxx[i]$ 表示 $\max^{i} \limits_{k=0} x_k$。

然后用线段树区间查询求出 $[l,r]$ 区间最小的 f[j]，然后插入 f[i]。

$O(n\log n)$ 代码

提交记录

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=5e5,IINF=1e9+10;
const long long INF=1e18;
struct stu{int x,y;}a[N+5];
int maxx[N+5];
long long f[N+5],ans=INF,tree[5*N];
void updata(int l,int r,int rt,int x,long long y){//模板而已
	if(l==r){
		tree[rt]=y;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) updata(l,mid,rt<<1,x,y);
	else updata(mid+1,r,rt<<1|1,x,y);
	tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
}
long long ask(int l,int r,int rt,int x,int y){
	if(x<=l&&r<=y) return tree[rt];
	int mid=l+r>>1;long long ans=INF;
	if(x<=mid) ans=min(ans,ask(l,mid,rt<<1,x,y));
	if(y>mid) ans=min(ans,ask(mid+1,r,rt<<1|1,x,y));
	return ans;
}

int main(){
	int n,zmax=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
		zmax=max(zmax,a[i].x);
	}
	sort(a+1,a+1+n,
	[](stu a,stu b){
		if(a.y==b.y) return a.x<b.x;
		return a.y<b.y;
	});//一种奇妙的写法
	
	for(int i=1;i<=4*n+100;i++) tree[i]=INF;
	a[0].x=a[0].y=maxx[0]=-IINF;
	updata(0,n,1,0,0);//注意下
	for(int i=1;i<=n;i++){
		maxx[i]=max(maxx[i-1],a[i].x);//更新最大的x
		int l,r,x,y;
		x=0,y=i;
		while(y-x>1){
			int mid=x+y>>1;
			if(a[mid].y<a[i].x) x=mid;
			else y=mid;
		}r=x;//二分右端点
		x=-1,y=r;
		while(y-x>1){
			int mid=x+y>>1;
			if(a[mid].y>=maxx[r]) y=mid;//右端点r就是最后一个满足a[r].y<a[i].x的线段
			else x=mid;
		}l=y;//二分左端点
		
		f[i]=ask(0,n,1,l,r)+a[i].y-a[i].x;
		updata(0,n,1,i,f[i]);//要不断插入
		if(a[i].y>=zmax) ans=min(ans,f[i]);
	}
	printf("%lld",ans);
}