P1712 [NOI2016] 区间

题目

link

题解

首先，看到数据范围这么大，答案还与值域有关，考虑离散化

按照长度（离散前）排序以后肯定一段一段取

所以，考虑双指针，维护两个指针l,r,意义是从l到r恰好是有m个区间包裹一个点

每次r++，如果包含同一个点的数量大于m了，就l++，知道不大于m

当然，一开始要给区间按大小排个序。

（为啥要排序，有没有大佬解释一下）

我们看到要求的是最大区间长度减去最小的区间长度。从而我们自然地想到要先给他们按照区间长度排一个序。

锅

线段树求和写多了，求max不会了（

经验教训

以后看到这种区间极差问题，可以考虑排序让它有单调性，然后双指针

eg:此题
那么我们就将长度排序 从小到大枚举最短区间 然后在这个最小区间的前提下从小到大枚举长区间，判断当前的这些区间是不是合法方案。

代码

#include<bits/stdc++.h>
const int N = 5e5 + 10;
using namespace std;
#define ll long long
int n, m;
struct U
{
	ll l, r;
	ll length;
	bool operator < (U o) const
	{
		return length < o.length;
	}
} segment[N];
ll b[N << 1], btop;
ll c[N << 1], ctop; 

struct Seg
{
	#define ls (u << 1)
	#define rs ((u << 1) | 1)
	int tree[N << 4];
	int tag[N << 4];
	void pushup(int u)
	{
		tree[u] = max(tree[ls], tree[rs]);
	}
	
	void pushdown(int u, int l, int r)
	{
		int mid = (l + r) >> 1;
		tree[ls] +=  tag[u];
		tree[rs] +=  tag[u];
		tag[ls] += tag[u], tag[rs] += tag[u];
		tag[u] = 0;
	}
	
	void change(int u, int l, int r, int L, int R, int val)
	{
		if(L <= l && r <= R)
		{
			tree[u] += val;
			tag[u] += val;
			return;
		}
		pushdown(u, l, r);
		int mid = (l + r) >> 1;
		if(L <= mid) change(ls, l, mid, L, R, val);
		if(R > mid) change(rs, mid + 1, r, L, R, val);
		pushup(u);
	}
	
	int query()
	{
//		if(L <= l && r <= R)
//		{
//			return tree[u];
//		}
//		pushdown(u, l, r);
//		int mid = (l + r) >> 1;
//		ans = 0;
//		if(L <= mid) ans = max(ans, query(ls, l, mid, L, R));
//		if(R > mid) ans = max(ans, query(rs, mid + 1, r, L, R));
//		return ans;
// complex!!!
		return tree[1];
	}
	
}sgtree;

int main()
{
//	cout << "qwq" << sgtree.tree[10];
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		cin >> segment[i].l >> segment[i].r;
		segment[i].length = segment[i].r - segment[i].l;
		b[++btop] = segment[i].l, b[++btop] = segment[i].r; 
	}
	b[0] = -1;
	sort(b + 1, b + 1 + btop);
	for(int i = 1;i <= btop;i++)
	{
		if(b[i] != b[i - 1])
			c[++ctop] = b[i];
	}
	
	for(int i = 1;i <= n;i++)
	{
		segment[i].l = lower_bound(c + 1, c + 1 + ctop, segment[i].l) - c;
		segment[i].r = lower_bound(c + 1, c + 1 + ctop, segment[i].r) - c;
	}
	
	sort(segment + 1, segment + 1 + n);
	
	int l = 1, r = 1;
	ll ans = 1145141919810;
	for(int r = 1;r <= n;r++)
	{
//		cout << r << "qwq"<<endl;
		sgtree.change(1, 1, ctop, segment[r].l, segment[r].r, 1);
//		cout << r <<" -- " << sgtree.tree[1] << endl;
		while(sgtree.query() >= m)
		{
			ans = min(ans, segment[r].length - segment[l].length);
			sgtree.change(1, 1, ctop, segment[l].l, segment[l].r, -1);
			l++;
		}
	}
	if(ans == 1145141919810)
	{
		printf("-1");
		return 0;
	}
	else
	{
		cout << ans << endl;
	}
	return 0;
}