Description
定义一个区间(l,r)的长度为r-l，空区间的长度为0。
给定数轴上n个区间，请选择其中恰好k个区间，使得交集的长度最大。
Input
第一行包含两个正整数n,k(1<=k<=n<=1000000)，表示区间的数量。
接下来n行，每行两个正整数l,r(1<=l<r<=10^9)，依次表示每个区间。
Output
第一行输出一个整数，即最大长度。
第二行输出k个正整数，依次表示选择的是输入文件中的第几个区间。
若有多组最优解，输出任意一组。
按左端点排序，i=1..n，取左端点前i小的区间中，右端点最大的k个，可以用堆维护。
#include<bits/stdc++.h>
typedef long long i64;
const int N=1e6+;
char ib[N*],*ip=ib;
int _(){int x;scanf("%d",&x);return x;}
struct itv{
int l,r,id;
bool operator<(const itv&w)const{return l<w.l;}
}is[N];
int n,k;
std::priority_queue<int,std::vector<int>,std::greater<int> >q1;
int ans=,L=INT_MAX,R=INT_MIN;
void upd(int l,int r){
if(r-l>ans)ans=r-l,R=r,L=l;
}
int main(){
n=_(),k=_();
for(int i=;i<n;++i){
is[i].l=_();
is[i].r=_();
is[i].id=i+;
}
std::sort(is,is+n);
for(int i=;i<k;++i)q1.push(is[i].r);
upd(is[k-].l,q1.top());
for(int i=k;i<n;++i){
int x=is[i].r;
if(x>q1.top()){
q1.push(x);
q1.pop();
}
upd(is[i].l,q1.top());
}
printf("%d\n",ans);
for(int i=;k&&i<n;++i)
if(is[i].l<=L&&is[i].r>=R){
printf("%d ",is[i].id);
--k;
}
return ;
}