0x00.前言

近一个月以来，不管是在模拟赛中，还是在日常做题中，甚至是在CSP考试中，都遇到了各种各样的区间问题，其题目形式、背景多种多样，但其根本都可以归纳为一种区间线段模型，遂加以整理。

0x01. 维护单一线段+选取部分区间

首先来看这一种较为基础的版本。

题目链接：luogu P1803

题目大意：给定 $n$ 个区间，要求维护一条线段（时间线），使得落在该条线段上的区间尽可能的多。注意：任取这条线段上一点，都要满足不被两个及以上的区间覆盖。求最多能放多少个线段。

题目解析：这道题目要求线段上任意一个点都不被两个及以上的区间覆盖，也就是说凡是合法解必然是由不相交的区间构成的。考虑用贪心的策略：**对于所有区间，按左端点排序，然后依次考虑每个区间，能放就放。**这个策略的正确性显然，因为越靠前的区间放置后，对于后面的区间影响越小。如何维护这个线段呢？区间有哪几种关系呢？停下来思考。

显然，区间有且只有 相交、相离、包含 三种关系。

更为具体的，在这个题目背景下，我们不难发现，只需要维护线段的右端点$pos$，依次考虑每个区间，如果区间与线段相交，则跳过这个线段，如果区间被线段包含，则需要用当前区间右端点替换线段右端点，因为这样对最终的答案不会更差，如果区间与线段相离，更新$pos$为当前区间右端点，$ans$++

#include <bits/stdc++.h>
#define MAXN (1000007)

using namespace std;

int n, ans = 1;

struct edge {
	int l, r;
}e[MAXN];

bool inline cmp(const edge x, const edge y) {
	if(x.l == y.l) return x.r < y.r;
	return x.l < y.l;
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &e[i].l, &e[i].r);
	}
	sort(e + 1, e + 1 + n, cmp);
	int pos = e[1].r;
	for(int i = 2; i <= n; ++i) {
		if(e[i].l >= pos) {
			++ans;
			pos = e[i].r;
		} else {
			if(e[i].r <= pos) {
				pos = e[i].r;
			}
		}
	}
	printf("%d\n", ans);
	return 0; 
}

值得提出的是，如果在对所有区间进行排序时按照右端点升序排序，则不需要考虑区间被包含的情况，读者可以自行证明并编写对应代码，这里不再赘叙。

这是较为基础的一种模型，他的本质是选取不相交区间问题，也就是维护单一线段，选取总区间的子集。

0x02.维护多个线段+选取部分区间

这个模型是$0x01$中所提及的模型的升级版。

题目链接：luogu P7391

题目大意：给定$n$个区间，要求维护$m$条线段，使得落在所有线段上的区间总数尽可能的多。注意：这些线段上的区间不能相交。问这个最多的区间总数是多少。

题目分析：很显然，这道题目是上一个模型的升级版；上一个模型是这道题目的一个特例，即$m=1$时。对于所有区间，依然是按照区间左端点排序。贪心策略依然不变，即能放就放，与上一道题目类似的，依然需要对区间与线段的关系进行分类讨论。停下来思考。

与上道题目类似的，讨论相离、相交、包含三种关系。

不同的是，对于相交来说，$pos$应当是所有线段中最小的右端点，因为这个线段越靠前（短），越容易拼接上一个新区间；对于包含来说，$pos$应当是所有线段中最大的右端点，因为这个线段越靠后（长），越容易包含一个子区间。同时我们还需要修改$pos$，因此我们可以通过普通的模拟来实现：建立一个数组s，记录每个线段的右端点，每次需要查询这个数组的最小值、删除这个数组的最小值、查询这个数组的最大值、删除这个数组的最大值，这个东西的维护是$O(N^2)$的，可以通过数据结构优化。

也就是我们需要维护一个数据结构，支持： - 查询全局最小值 - 删除全局最小值 - 查询全局最大值 - 删除全局最大值 - 插入元素

于是可以联想到堆， 这里推荐使用std::multiset方便的实现上述操作。

与上道题目一样的，这道题目也可以按照右端点排序，感兴趣的读者可以自行实现。

#include <bits/stdc++.h>
#define MAXN (200000 + 7)

using namespace std;

multiset <int> s;
multiset <int>::iterator it;

int n, m, ans;

struct po{
	int l, r;
}e[MAXN];

bool inline cmp (const po x, const po y) {
	if(x.l == y.l) return x.r < y.r;
		else return x.l < y.l; 
}

int main() {
	scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &e[i].l, &e[i].r);
	}
	
	sort(e + 1, e + 1 + n, cmp);
	
	for(int i = 1; i <= n; ++i) {
		if(m) {
			s.insert(e[i].r);
			--m;
		} else if((*(s.begin())) <= e[i].l) {
				s.erase(s.begin());
				s.insert(e[i].r);
		} else {
			++ans;
			it = s.end();
			--it;
			if((*it) > e[i].r) {
				s.erase(it);
				s.insert(e[i].r);
			}
		}
	}
	
	printf("%d\n", ans);
	return 0;
}

0x03. 维护多条线段+选取所有区间

这个模型与前两个模型的主要区别在于要求选取所有区间。

题目链接：acwing 113

题目大意：给定$n$个区间，求使所有区间在不相交情况下最少需要多少线段，以及每个区间的安排方式。注意：合法的一条线段中不能有相交的区间。

题目解析：这道题目与前两道题目都有不同，与$0x02$相比，它要求选取所有区间，并且要求输出每个区间的安排方式。对于问题一，按照前两题的思维方式，对于所有线段按照左端点升序排列，并分类讨论区间与线段间的关系。与第二道题类似的，如果区间与线段相离，可以直接把区间拼接在线段后面；如果区间与线段相交，则新建一个线段；不同的是，如果区间被线段包含，**请问可以将线段的右端点更新成区间的右端点吗？**停下来思考。

答案是：不可以。

为什么呢？因为将线段右端点更新成区间右端点的操作相当于舍弃了原线段上的一个区间，但题目明确要求选取所有区间。这样做是不合题意的。

因此对与线段与区间的相交与包含关系，可以统一为新建一个线段。

更为具体的，由于这道题目需要查询所有线段的最大值、删除所有线段的最大值的操作，可以使用大根堆（std::priority_queue）来实现以上操作。

#include <bits/stdc++.h>
#define MAXN (50007)

using namespace std;

int n, ans, pos[MAXN];

struct edge {
	int l, r, pos;
}e[MAXN];

priority_queue <edge> q;

inline bool operator < (edge x, edge y) {
	if(x.r == y.r) return x.l > y.l;
		else return x.r > y.r;	
}

bool inline cmp(edge x, edge y) {
	if(x.l == y.l) return x.r < y.r;
		else return x.l < y.l;
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &e[i].l, &e[i].r);
		e[i].pos = i;
	}
	
	sort(e + 1, e + 1 + n, cmp);
	
	for(int i = 1; i <= n; ++i) {
		if(!q.empty() && q.top().r < e[i].l) { 
			pos[e[i].pos] = pos[q.top().pos]; // 用于解决问题二
			q.pop();
			q.push(e[i]);
		} else { 
			++ans;
			pos[e[i].pos] = ans;
			q.push(e[i]);
		}
	}
	
	printf("%d\n", ans);
	for(int i = 1; i <= n; ++i) {
		printf("%d\n", pos[i]);
	}
	return 0;
}

0x04.练习题目

  1. 模型一：维护单一线段+选取部分区间 ：acwing 112

  2. 模型二：维护多条线段+选取全部区间 ：luogu P7913