有没有哪位巨佬帮我修改一下题解的格式啊啊啊,我提交了好多次都过不了,他说我原因是：$【中文标点符号】与【英文、数字、公式或汉字】或【汉字】与【汉字】之间不应添加多余空格；【中文】与【英文、数字或公式】之间应以半角空格隔开；非数学公式（一般英文单词、题目名、算法名、人名等）不应使用 LaTeX；$

先给成品

题解

题意：

给你 $\operatorname{n}$ 个线段，请你在字典序最小的情况下取不相交的 $\operatorname{k}$ 个， 且输出方案。

题目分析：

先考虑合适存在有解：

我们贪心地取线段， 尽力取右端点小的，只要最多可能取得的线段超过 $\operatorname{k}$ 个， 那么显然有解。

接下来考虑字典序最小：

我们依然采用贪心的思路， 我们考虑字典序的定义会造成如下性质：

如果一个元素字典序小且加入后符合条件， 我们就应将其加入至最小字典序中。 因此， 我们从前向后遍历每一个元素， 考虑能否加入。

期望复杂度：

$\color{green}\ O( n^{2} log_{n}) .$ 显然，从各方面， 都是可以优化的。

考虑 $\ n≤10^{5}$ 且$\ L_{i}<R_{i}≤10^{9}$, 显然可以考虑进行离散化。 我们显然可以预处理一段区间内能取到的最大值。 我们考虑加入的时候显然可以根据先前的结果维护。

考虑优化2 ：

我们发现，我们考虑区间线段数是可以考虑以点为切入点。我们可以沿着线段从左端点尽力往右跳。因此考虑倍增 $\operatorname{ST表}$ ， 此时， 我们成功的将查询降到了 $\color{orange}\ O ( \ log_{n})$ 级别。

考虑优化3 ：

我们不仅可以存一个一定要存储的输出答案（一边解决问题一边输出也可），还可以存储一个答案后的状态。

我们设最大的状态为刚开始读入时的块， 即 $\color{green} \operatorname{[1,len]}$（此处 $\operatorname{len}$ 表示离散化后的长度），后可以用珂朵莉树（又名老司机树,ODT）中分裂的思想， 显然可以用 $\operatorname{set}$ 轻松地解决该优化。

具体地，对每一个当前考虑加入的块， 考虑能否加入， 若能加入，进行分裂、加入操作。

由于 $\operatorname{set}$ 的底层定义，需要注意大小比较即代码先后顺序的问题。

附上卑微代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k, p[N << 1], g;
int l[N], r[N], f[N << 1][22];
struct __line {
	int l, r;
	bool operator < (const __line & x) const {
		return r < x.l;
	}
};
vector<int> ans;
set<__line> s;
int main() {
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
		cin >> l[i] >> r[i];
	for(int i = 1; i <= n; i++)
		p[++g] =  l[i], a
		p[++g]  = r[i];
	sort(p + 1, p + g + 1);
	int len = unique(p + 1, p + g + 1) - p - 1;
	auto query = [&](int x) { return lower_bound(p + 1, p + len + 1, x) - p; };c
	for(int i = 1; i <= n; i++)
		l[i] = query(l[i]), r[i] = query(r[i]);f
	for(int i = 1; i <= len + 5; i++)w
		for(int j = 0; j <= 19; j++)e
			f[i][j] = (int)2e5 + 1;	
	for(int i = 1; i <= n; i++)
		f[l[i]][0] = min(f[l[i]][0], r[i]);qwq
	for(int i = len; i >= 1; i--)
		f[i][0] = min(f[i][0], f[i + 1][0]);
	for(int j = 1; j <= 19; j++)
		for(int i = 1; i <= len; i++)
			if(f[i][j - 1] <= len)
				f[i][j] = f[f[i][j - 1]][j - 1];
	auto find = [&](int l, int r) {
		int nowl = l, ret = 0;
		for(int i = 19; i >= 0; i--)
			if(f[nowl][i] <= r)
				nowl = f[nowl][i], ret += (1 << i);
		return ret;
	} ;
	s.insert((__line) {1, len});
	int maxn = find(1, len); 
	if(maxn < k) { printf("-1"); return 0; }
	for(int i = 1; i <= n && ans.size() < k; i++) {
		set<__line>::iterator it = s.find((__line) {l[i], r[i]});
		if(it -> l <= l[i] and r[i] <= it -> r) {
			if(maxn - find(it -> l, it -> r) + find(it -> l, l[i]) + find(r[i], it -> r) >= k - ans.size() - 1) {
				maxn = maxn - find(it -> l, it -> r) + find(it -> l, l[i]) + find(r[i], it -> r);
				ans.push_back(i);
				int p1 = it -> l, p2 = it -> r; 
				s.erase(it);
				s.insert((__line) {p1, l[i]});
				s.insert((__line) {r[i], p2});
			}
		} 
	}
	for(int x : ans) cout << x << "\n";
	return 0;
}

$\color{green} 萌新求赞QAQ$

$\color{blue}求管理员大大通过QwQ$

然后是原码

# 题解

### 题意：
给你 $\operatorname{n}$ 个线段，请你在字典序最小的情况下取不相交的 $\operatorname{k}$ 个， 且输出方案。

### 题目分析：
先考虑合适存在有解：

我们贪心地取线段， 尽力取右端点小的，只要最多可能取得的线段超过 $\operatorname{k}$ 个， 那么显然有解。

##### 接下来考虑字典序最小：

我们依然采用贪心的思路， 我们考虑字典序的定义会造成如下性质：

如果一个元素字典序小且加入后符合条件， 我们就应将其加入至最小字典序中。
因此， 我们从前向后遍历每一个元素， 考虑能否加入。
##### 期望复杂度：
$\color{green}\ O( n^{2}  log_{n}) . $
显然，从各方面， 都是可以优化的。

考虑 $\  n≤10^{5}$
且$\  L_{i}<R_{i}≤10^{9}$,  显然可以考虑进行离散化。
我们显然可以预处理一段区间内能取到的最大值。
我们考虑加入的时候显然可以根据先前的结果维护。

### 考虑优化2 ：

我们发现，我们考虑区间线段数是可以考虑以点为切入点。我们可以沿着线段从左端点尽力往右跳。因此考虑倍增 $\operatorname{ST表}$ ， 此时， 我们成功的将查询降到了 $ \color{orange}\ O ( \ log_{n}) $ 级别。

### 考虑优化3 ：

我们不仅可以存一个一定要存储的输出答案（一边解决问题一边输出也可），还可以存储一个答案后的状态。

我们设最大的状态为刚开始读入时的块， 即 $ \color{green} \operatorname{[1,len]}$（此处 $\operatorname{len}$ 表示离散化后的长度），后可以用珂朵莉树（又名老司机树,ODT）中分裂的思想， 显然可以用 $ \operatorname{set} $ 轻松地解决该优化。

具体地，对每一个当前考虑加入的块， 考虑能否加入， 若能加入，进行分裂、加入操作。

由于 $\operatorname{set}$  的底层定义，需要注意大小比较即代码先后顺序的问题。

#### 附上卑微代码:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k, p[N << 1], g;
int l[N], r[N], f[N << 1][22];
struct __line {
	int l, r;
	bool operator < (const __line & x) const {
		return r < x.l;
	}
};
vector<int> ans;
set<__line> s;
int main() {
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
		cin >> l[i] >> r[i];
	for(int i = 1; i <= n; i++)
		p[++g] =  l[i], a
		p[++g]  = r[i];
	sort(p + 1, p + g + 1);
	int len = unique(p + 1, p + g + 1) - p - 1;
	auto query = [&](int x) { return lower_bound(p + 1, p + len + 1, x) - p; };c
	for(int i = 1; i <= n; i++)
		l[i] = query(l[i]), r[i] = query(r[i]);f
	for(int i = 1; i <= len + 5; i++)w
		for(int j = 0; j <= 19; j++)e
			f[i][j] = (int)2e5 + 1;	
	for(int i = 1; i <= n; i++)
		f[l[i]][0] = min(f[l[i]][0], r[i]);qwq
	for(int i = len; i >= 1; i--)
		f[i][0] = min(f[i][0], f[i + 1][0]);
	for(int j = 1; j <= 19; j++)
		for(int i = 1; i <= len; i++)
			if(f[i][j - 1] <= len)
				f[i][j] = f[f[i][j - 1]][j - 1];
	auto find = [&](int l, int r) {
		int nowl = l, ret = 0;
		for(int i = 19; i >= 0; i--)
			if(f[nowl][i] <= r)
				nowl = f[nowl][i], ret += (1 << i);
		return ret;
	} ;
	s.insert((__line) {1, len});
	int maxn = find(1, len); 
	if(maxn < k) { printf("-1"); return 0; }
	for(int i = 1; i <= n && ans.size() < k; i++) {
		set<__line>::iterator it = s.find((__line) {l[i], r[i]});
		if(it -> l <= l[i] and r[i] <= it -> r) {
			if(maxn - find(it -> l, it -> r) + find(it -> l, l[i]) + find(r[i], it -> r) >= k - ans.size() - 1) {
				maxn = maxn - find(it -> l, it -> r) + find(it -> l, l[i]) + find(r[i], it -> r);
				ans.push_back(i);
				int p1 = it -> l, p2 = it -> r; 
				s.erase(it);
				s.insert((__line) {p1, l[i]});
				s.insert((__line) {r[i], p2});
			}
		} 
	}
	for(int x : ans) cout << x << "\n";
	return 0;
}

$ \color{green} 萌新求赞QAQ $

$ \color{blue}求管理员大大通过QwQ $