一道从开始就被我想歪的题目，以至于写了一天最后发现根本就是错误的算法，只好照题解写去了。

$[1, n]$ 的区间内有 $k$ 个标记在整数上，给出 $m$ 段区间内有/没有标记，输出一定有标记的数字。

看完题我就直接给出了一堆“显然”的结论：

1. 去掉没有的，若有的区间长度为 $1$, 那这个就肯定是的了。
2. 把肯定是的去掉，当且仅当剩下还有的标记数和现在有覆盖标记的数字数一样的时候有一定有标记的数字，且一定是全都是。

看上去是不是挺有道理？于是我就设计了一个用 std::set 的算法，用 (twt){st, len} 表示从 st 开始长度 len 的有覆盖，维护一个可能有的区间，和一个一定没有到区间，然后用一定没有的在有的区间内除去，然后判一下前面两条就行了。合并区间的时候注意有标记的区间刚刚好相接是不能接上的，因为要注意一号判断。

似乎好有道理，然后我就写、调了俩小时，最后获得了 $10$ 分的优异成绩。

其实反例很显然：

3 1 3
1 1 1
1 2 1
1 3 1

这样我认为是无法确定的，其实第一个明显是可以确定的。解决这个问题可不是仅仅把开始时长度就为 $1$ 的判掉那么简单。

比如这组反例：

5 1 3
2 3 1
1 5 1
3 3 0

把前两段并起来后就损失了它们单独的信息了！

所以前面的断言根本就是错的。浪费了我许多的时间。在开始写代码前一定要想清楚，充分考虑算法的正确性是否成立。

那么现在来讲正确的做法吧。

正确做法同样维护了可能由标记的区间并从中去掉了一定没有标记的区间，那它是如何处理在合并中的信息损失呢？

其实，正确做法根本不需要这个信息，因为它不依赖于我的断言。

想法很简单，用 $f_i$ 记录前面到 $i$ 段所需的最少标记数量，用 $g_j$ 记录从后面开始的。然后枚举每一个点就强制它不选，选它左边一个，再看下前后所需的会不会超过 $k$ 就好了。

当然细节还是要处理的。

题解里处理合并的方式比我的 set 好多了，既快（没有 $\log$） 又好写 （不用处理迭代器删除的问题），用差分把现在不是肯定没有的点抓出来重新编号，用新编号表示线段的端点。

处理合并可以将一个端点排序后使用单调栈处理合并。至于找左右的线段端点？既然有序，直接二分就好了。

代码实现感觉也一些的难度。

	scanf("%d%d%d", &n, &k, &m);
	for(int i = 1; i <= m; i++) {
		scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].f);
		if(a[i].f == 0) ++b[a[i].l], --b[a[i].r+1];
	}
	int now = 0, cnt = 0;
	for(int i = 1; i <= n; i++) {
		now += b[i];
		if(now == 0) L[i] = R[i] = ++cnt, be[cnt] = i;
	}
	if(cnt == k) {
		for(int i = 1; i <= cnt; i++) printf("%d\n", be[i]);
		return 0;
	}

先是重新编号的过程，如果发现这些点恰好就是需要的，那么直接输出就可以了。

同时标记出了一个新的点左右最靠近的一个端点。

	L[n+1] = n+1;
	for(int i = 1; i <= n; i++) 
		if(R[i] == 0) R[i] = R[i-1];
	for(int i = n; i >= 1; i--) 
		if(L[i] == 0) L[i] = L[i+1];
	cnt = 0;
	for(int i = 1; i <= m; i++) {
		if(a[i].f == 0) continue;
		if(L[a[i].l] <= R[a[i].r]) a[++cnt].l = L[a[i].l], a[cnt].r = R[a[i].r];
	}
	std::sort(a+1, a+cnt+1);

然后更新 a 的编号并进行排序。

以下重新使用了 L 和 R 作为栈，注意这里的合并不是我假做法里的合并，而是把完全覆盖的给并掉了。还求出了 f 和 g。

	int top = 0;
	for(int i = 1; i <= cnt; i++) {
		while(top != 0 && a[i].l >= L[top] && a[i].r <= R[top]) top--;
		L[++top] = a[i].l, R[top] = a[i].r;
	}
	int l = n+1, r = 0;
	for(int i = 1; i <= top; i++) {	
		if (L[i] > r) f[i] = f[i-1] + 1, r = R[i];
		else f[i] = f[i-1];
	}
	for(int i = top; i >= 1; i--) {
		if (R[i] < l) g[i] = g[i+1] + 1, l = L[i];
		else g[i] = g[i+1];
	}

最后是关键的判断环节。

这里还需要说明一下，最后栈中的编号是剩下线段的编号，我们每次只判断了最右边一个是否是一定要有的，是因为这样子显然是最优的，因为放在这个位置右边也可能会利用到，而因为每一段覆盖只需要一个就可以了，其它地方判断出来是不能确定的，因为可以放到线段最右边的位置可能更优。

	bool flag = 0;
	for(int i = 1; i <= top; i++) {
		if(f[i] == f[i-1]) continue;
		if (L[i] == R[i]) {
			printf("%d\n", be[R[i]]);
			flag = 1; 
			continue;
		}
		int l = 1, r = i - 1, x = 0, y = top + 1;
		while (l <= r) {				 
			int mid = l + ((r - l) >> 1);
			if (R[mid] < R[i] - 1) x = mid, l = mid + 1;
			else r = mid - 1;
		}
		l = i + 1, r = top;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			if (L[mid] > R[i] - 1) y = mid, r = mid - 1;
			else l = mid + 1;
		}
		if (f[x] + g[y] + 1 > k) {
			printf("%d\n", be[R[i]]);
			flag = 1;
		}
	}
	if(flag == 0) puts("-1");
}