谈一下尺取法的经典题。
第K大区间
定义一个区间的值为其众数出现的次数。
现给出n个数，求将所有区间的值排序后，第K大的值为多少。
众数：区间里出现次数最多的数字，例如：1 1 2 2 2，区间[1 1]的众数为1，区间[3 5]的众数为2
题解
二分这个值，转化成判断问题。
将求第k大变成求第n*(n-1)/2-k+1小，那么我们就可以用尺取法计算值小于等于二分值的区间的个数。
区间
在数轴上有 n 个闭区间 [l1,r1], [l2,r2], . . . , [ln,rn]。现在要从中选出 m 个区间，使得这 m 个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区[li,ri]，都有 li ≤ x ≤ ri。
对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri − li，即等于它的右端点的值减去左端点的值。
求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。
n ≤ 500000，m ≤ 200000.
题解
将坐标离散化之后，用线段树维护点的覆盖次数。
那么用尺取法即可求出最小花费。
CO int N=500000+10,M=2097152+10;
struct section {int l,r,len;}sec[N];
vector<int> pos;
int tree[M],tag[M];
#define lc (x<<1)
#define rc (x<<1|1)
IN void push_up(int x){
tree[x]=max(tree[lc],tree[rc]);
}
IN void push_down(int x){
if(tag[x]){
tree[lc]+=tag[x],tag[lc]+=tag[x];
tree[rc]+=tag[x],tag[rc]+=tag[x];
tag[x]=0;
}
}
void change(int x,int l,int r,int ql,int qr,int v){
if(ql<=l and r<=qr){
tree[x]+=v,tag[x]+=v;
return;
}
push_down(x);
int mid=(l+r)>>1;
if(ql<=mid) change(lc,l,mid,ql,qr,v);
if(qr>mid) change(rc,mid+1,r,ql,qr,v);
push_up(x);
}
int main(){
int n=read<int>(),m=read<int>();
for(int i=1;i<=n;++i){
read(sec[i].l),read(sec[i].r),sec[i].len=sec[i].r-sec[i].l;
pos.push_back(sec[i].l),pos.push_back(sec[i].r);
}
sort(sec+1,sec+n+1,[](CO section&a,CO section&b)->bool{
return a.len<b.len;
});
sort(pos.begin(),pos.end()),pos.erase(unique(pos.begin(),pos.end()),pos.end());
for(int i=1;i<=n;++i){
sec[i].l=lower_bound(pos.begin(),pos.end(),sec[i].l)-pos.begin()+1;
sec[i].r=lower_bound(pos.begin(),pos.end(),sec[i].r)-pos.begin()+1;
}
int ans=1e9;
for(int l=1,r=0;l<=n;++l){
while(r<n and tree[1]<m)
++r,change(1,1,pos.size(),sec[r].l,sec[r].r,1);
if(tree[1]==m) ans=min(ans,sec[r].len-sec[l].len);
change(1,1,pos.size(),sec[l].l,sec[l].r,-1);
}
if(ans==1e9) puts("-1");
else printf("%d
",ans);
return 0;
}