博客中为数不多的NOI的题目的题解……
先将区间都离散化，再按区间长度排序
用双指针，并线段树维护出现最多的数出现了多少次
如果(> m)次，就移动左指针，删除最左边的区间，直到(= m)次，在这个过程中记录答案
如果(< m)次，就移动右指针，加入右边的区间
可以保证这样一定能找出最优解
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define ls p << 1
#define rs p << 1 | 1
#define mid ((l+r) >> 1)
using namespace std;
LL read() {
LL k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
k = k * 10 + c - 48, c = getchar();
return k * f;
}
struct zzz {
int l, r, len;
}q[500010];
bool cmp(zzz x, zzz y) {
return x.len < y.len;
}
int a[1000010], maxn = 0;
int tree[1000010 << 2], tag[1000010 << 2];
inline void up(int p) {
tree[p] = max(tree[ls], tree[rs]);
}
inline void down(int p) {
tree[ls] += tag[p]; tree[rs] += tag[p];
tag[ls] += tag[p], tag[rs] += tag[p];
tag[p] = 0;
}
void update(int nl, int nr, int k, int l = 1, int r = maxn, int p = 1) {
if(nl <= l && nr >= r) {
tree[p] += k; tag[p] += k; return ;
}
down(p);
if(nl <= mid) update(nl, nr, k, l, mid, ls);
if(nr > mid) update(nl, nr, k, mid+1, r, rs);
up(p);
}
int main() {
//freopen("2.in", "r", stdin);
int n = read(), m = read();
for(int i = 1; i <= n; ++i) {
q[i].l = read(), q[i].r = read(), q[i].len = q[i].r - q[i].l;
a[i << 1] = q[i].l, a[(i<<1) - 1] = q[i].r;
}
sort(a+1, a+n*2+1); int pos = unique(a+1, a+n*2+1) - a - 1;
sort(q+1, q+n+1, cmp);
for(int i = 1; i <= n; ++i)
q[i].l = lower_bound(a+1, a+pos+1, q[i].l) - a,
q[i].r = lower_bound(a+1, a+pos+1, q[i].r) - a,
maxn = max(q[i].r, maxn);
int l = 1, r = 0, ans = 2147483647;
for(r = 1; r <= n; ++r) {
update(q[r].l, q[r].r, 1);
while(tree[1] >= m) {
update(q[l].l, q[l].r, -1);
ans = min(ans, q[r].len - q[l].len);
++l;
}
}
if(ans != 2147483647) cout << ans;
else cout << -1;
return 0;
}