問題#
解法#
まず、データ範囲がこれほど大きく、答えが値域に関係していることを考慮して離散化を検討します。
長さ（離散化前）でソートした後、必ず一段一段取ります。
したがって、二重ポインタを考え、2 つのポインタl,rを維持します。意味はlからrまでちょうどm個の区間が 1 つの点を包みます。
毎回r++し、同じ点を含む数がmを超えた場合はl++し、mを超えないまで続けます。
もちろん、最初に区間をサイズでソートする必要があります。
（なぜソートが必要なのか、誰か説明してくれませんか）
我々は最大区間の長さから最小の区間の長さを引くことが要求されていることを見ています。したがって、自然に彼らを区間の長さでソートすることを考えます。
鍋#
線分木の和を求めることは多くやりましたが、最大を求めることはできませんでした（
経験教訓#
今後、このような区間の極差問題を見た場合、ソートして単調性を持たせ、二重ポインタを考慮することができます。
例：この問題
それでは、長さを小から大にソートし、最短区間を列挙し、その最小区間の前提の下で小から大に長い区間を列挙し、現在のこれらの区間が合法な解であるかどうかを判断します。
コード#
#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;
// 複雑すぎる!!!
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;
}