今天学了个高级东西——尺取法。(这句话在很多大佬看来是个笑话)。

以下摘自《挑战程序设计竞赛(第二版)》

尺取法通常指对数组保存一对下标(起点和终点)，然后根据实际情况交替推进两个端点直到得到答案的方法。这种操作很像是尺蠖（日文中称为尺取虫）爬行的方式故得名。

举几个栗子：

题意是给你一个正整数数列，一个整数 \(S\)，问和不小于 \(S\) 的连续子序列的最小长度，无解输出 \(0\)。

尺取法入门题。

题目保证 \(a_i > 0\)，所以右端点具有单调性，故可以用尺取法。

按照尺取法，设定前后指针 \(s=0\)，\(t=0\)，然后将 \(t\) 向前移动，判断 \(s\) ~ \(t\) 之间的区间是否满足要求，如果小于 \(S\)，\(t\) 继续移动，直到和大于等于 \(S\) 为止。此时将 \(t\) 向前移动。反复进行该过程，期间记录长度，并更新长度的最小值。复杂度为 \(O(n)\)。

#include 
    
     using namespace std;#define db double#define ll long long#define RG registerinline int gi(){    RG int ret; RG bool flag; RG char ch;    ret=0, flag=true, ch=getchar();    while (ch < '0' || ch > '9')        ch == '-' ? flag=false : 0, ch=getchar();    while (ch >= '0' && ch <= '9')        ret=(ret<<3)+(ret<<1)+ch-'0', ch=getchar();    return flag ? ret : -ret;}const db pi = acos(-1.0);const int N = 1e5+5, inf = 1<<30;int a[N];inline void work(){    int l,r,i,n,lim,s,ans;    n=gi(), lim=gi();    for (i=1; i<=n; ++i)        a[i]=gi();    l=r=1, s=a[l], ans=inf;    while (r <= n)        {            while (s < lim && r <= n)                s+=a[++r];            if (s < lim)                break;            ans=min(ans,r-l+1), s-=a[l++];        }    ans < inf ? printf("%d\n",ans) :puts("0");}int main(){    // freopen("sub.in","r",stdin);    // freopen("sub.out","w",stdout);    int t;    t=gi();    while (t--)        work();    return 0;}
    

题目不解释了。

首先，喻队长教育我：

“他坐标范围这么大，肯定要离散化，所以交点一定可以在端点上。”

傻逼的我想了30秒，发现好有道理：

判断是否有交是左端点取 \(max\)，右端点取 \(min\)。

于是只需要每次判断是否有一个区间的一个端点被覆盖 \(m\) 次即可。

剩下的部分就是贪心了。

把区间按长度排序即可。然后用尺取法，每次用线段树维护一下所有点被覆盖次数的 \(max\) 即可。

至于为什么可以一直加，是因为这个区间就算不在 \(h\) 的要选的 \(m\) 个区间内，它选了也不会对答案造成影响，因为后面肯定还有必须要选的区间 \(t\)，即当前点要选的第 \(m\) 个区间。(这个有点像最大子序列和的思想)

#include 
    
     using namespace std;#define db double#define ll long long#define RG registerinline int gi(){    RG int ret; RG bool flag; RG char ch;    ret=0, flag=true, ch=getchar();    while (ch < '0' || ch > '9')        ch == '-' ? flag=false : 0, ch=getchar();    while (ch >= '0' && ch <= '9')        ret=(ret<<3)+(ret<<1)+ch-'0', ch=getchar();    return flag ? ret : -ret;}const db pi = acos(-1.0);const int N = 1e6+5, inf = (1ll<<31)-10;struct ran{    int l,r,len;    inline bool operator <(const ran &R) const { return len < R.len; }}r[N];int b[N<<1],tr[N<<2],lz[N<<2];inline void down(RG int o){    if (!lz[o])        return;    RG int ls,rs;    ls=o<<1, rs=ls|1;    lz[ls]+=lz[o], lz[rs]+=lz[o];    tr[ls]+=lz[o], tr[rs]+=lz[o];    lz[o]=0;}inline void update(RG int o,RG int l,RG int r,RG int s,RG int t,RG int w){    if (l >= s && r <= t)        {            tr[o]+=w, lz[o]+=w;            return;        }    down(o);    RG int mid,ls,rs;    mid=(l+r)>>1, ls=o<<1, rs=ls|1;    if (s <= mid)        update(ls,l,mid,s,t,w);    if (t > mid)        update(rs,mid+1,r,s,t,w);    tr[o]=max(tr[ls],tr[rs]);}int main(){    // freopen("ran.in","r",stdin);    // freopen("ran.out","w",stdout);    int n,m;    RG int h,t,cnt,i,ans;    n=gi(), m=gi();    cnt=0;    for (i=1; i<=n; ++i)        {            r[i].l=gi(), r[i].r=gi(), r[i].len=r[i].r-r[i].l;            b[++cnt]=r[i].l, b[++cnt]=r[i].r;        }    sort(r+1,r+n+1);    sort(b+1,b+cnt+1);    cnt=unique(b+1,b+cnt+1)-b-1;    for (i=1; i<=n; ++i)        {            r[i].l=lower_bound(b+1,b+cnt+1,r[i].l)-b;            r[i].r=lower_bound(b+1,b+cnt+1,r[i].r)-b;        }    h=t=1, ans=inf;    while (true)        {            while (tr[1] < m && t <= n)                update(1,1,cnt,r[t].l,r[t].r,1), t++;            if (tr[1] < m)                break;            ans=min(ans,r[t-1].len-r[h].len);            update(1,1,cnt,r[h].l,r[h].r,-1), h++;        }    ans < inf ? printf("%d\n",ans) : puts("-1");    return 0;}