題目#
題解#
首先，看到數據範圍這麼大，答案還與值域有關，考慮離散化
按照長度（離散前）排序以後肯定一段一段取
所以，考慮雙指針，維護兩個指針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;
}