Problem#
Solution#
First, seeing that the data range is so large and the answer is related to the value range, consider discretization.
After sorting by length (before discretization), it is certain that we will take segments one by one.
So, consider using two pointers, maintaining two pointers l, r, meaning that from l to r there are exactly m intervals covering one point.
Every time r++, if the number of intervals containing the same point exceeds m, then l++, until it is no longer greater than m.
Of course, we need to sort the intervals by size at the beginning.
(Why sort? Can someone explain?)
We see that what is required is the maximum interval length minus the minimum interval length. Thus, we naturally think of sorting them by interval length first.
Pitfall#
I have written a lot of segment trees for sum, but I can't do max (
Lessons Learned#
In the future, when encountering such interval range problems, consider sorting to create monotonicity, then use two pointers.
eg: In this problem
We will sort the lengths from smallest to largest, enumerate the shortest intervals, and then under the premise of this minimum interval, enumerate the longer intervals from smallest to largest, checking whether these intervals are valid solutions.
Code#
#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;
}