CF1555 E

E. Boring Segments

题意

有一个大区间 $[1,m]$，给定 $n$ 个小区间
每个小区间范围是 $[l_i, r_i] (1\leqslant l_i<r_i\leqslant m)$，每个小区间还有一个权值 $w_i$

定义两个区间中的点可以相互到达，当且仅当，两个区间存在交集，如 $[1,3],[3,4]$ 连通，而 $[1,3],[4,5]$ 不连通

定义一个子集的花费为：该子集中的最大的权值-最小的权值

现在求一个子集使得在区间 $[1,m]$ 中的任意两个点都可以相互到达，且花费最少

思路

最一开始想了半天二分答案，发现check函数不好写

看了题解后，发现可以直接通过双指针的方法，对区间的权值进行查询

双指针的方法，一般用于求一个连续的区间，并且右端点关于左端点单调递增

这道题如果将区间按权值，从小到大排序，我们发现它其实是满足使用双指针条件的

当左端点是 $l$ 时，我们令：$f(l)$ 为最小的满足条件的右端点位置

我们用反证法证明：$f(x)$ 是单增的，若 $\exists x < x+1, f(x) > f(x+1)$
由于集合区间 $[x+1,f(x+1)]$ 是满足题目要求的
那么集合区间 $x \cap [x+1, f(x+1)]=[x, f(x+1)]$ 一定也是满足题目要求的
那么一定有 $f(x) \leqslant f(x+1)$ 与 $f(x) > f(x+1)$ 矛盾，则 $f(x)$ 一定单增

判断一个区间 $[1,m]$ 中的任意两点是否能互相到达，我是直接把数域扩大2倍后，用线段树判断是否能完全覆盖 $[2,2m]$ 的，不过感觉标程好像更简单

如 $[1,3],[3,4]\iff [2,6]\cap[6,8]=\{6\}\ yes,\quad [1,2],[3,4]\iff [2,4]\cap[6,8]=\varnothing\ no$

总复杂度 $O(MlogM+NlogM)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define ls (p<<1)
#define rs (p<<1|1)
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 3e5 + 10;
const int M = 2e6 + 10;
struct SEG {
	struct Node {
		int l, r;
		int sum, mn;
	}t[M<<2];
	void pushup(int p) {
		t[p].mn = min(t[ls].mn, t[rs].mn);
	}
	void modify(int p, int x) {
		t[p].sum += x;
		t[p].mn += x;
	}
	void pushdown(int p) {
		if (t[p].sum) {
			modify(ls, t[p].sum);
			modify(rs, t[p].sum);
			t[p].sum = 0;
		}
	}
	void build(int p, int l, int r) {
		t[p].l = l, t[p].r = r;
		t[p].mn = t[p].sum = 0;
		if (l == r) {
			return;
		}
		int mid = (l+r) >> 1;
		build(ls, l, mid);
		build(rs, mid+1, r);
	}
	void update(int p, int l, int r, int x) {
		if (t[p].l > r || t[p].r < l) return;
		if (t[p].l >= l && t[p].r <= r) {
			modify(p, x);
			return;
		}
		pushdown(p);
		update(ls, l, r, x);
		update(rs, l, r, x);
		pushup(p);
	}
}seg;
struct Node {
	int l, r, w;
	friend bool operator < (const Node &x, const Node &y) {
		return x.w < y.w;
	}
}a[N];
int n, m;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	m <<= 1;
	seg.build(1, 2, m);
	for (int i = 0; i < n; i++) {
		cin >> a[i].l >> a[i].r >> a[i].w;
		a[i].l <<= 1, a[i].r <<= 1;
	}
	sort(a, a + n);
	int ans = 9e18;
	int l = 0, r = 0;
	for (int l = 0; l < n; l++) {
		while (seg.t[1].mn == 0 && r < n) {
			seg.update(1, a[r].l, a[r].r, 1);
			r++;
		}
		if (seg.t[1].mn == 0) break;
		ans = min(ans, a[r-1].w - a[l].w);
		seg.update(1, a[l].l, a[l].r, -1);
	}
	cout << ans << '\n';
	return 0;
}