小小粉丝度度熊

HDU 传送门
开始肯定是先将区间按照 l 然后 r 升序排序。
我的做法：再合并一下区间（能合并的就合并）。
我一开始想了一种可能会超时的做法，我枚举x区间，计算从第x个区间后面的间隙开始补签，一直更新最大值，貌似真的会超时。然后我又想了用前缀和来优化一下，应该会过的。

然后我获悉了一种使用队列的方法，可以做到O(n)。
我们在后面插入下一个区间时：
如果补签数m>=空隙，那么就可以入队，更新最大值和m及nowr。
否则删掉队首的区间，m加上空隙长，更新一下nowl。

一开始写出来不对，一直以为合并区间没问题，是后面的问题，结果最后发现，真的是合并区间的问题！！
南辕北辙啊。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm> 
#include<queue>
#define LL long long
using namespace std;
int n,m,cnt;
LL ans;
struct H{
    int l,r;
}a[100009];
H b[100009];
bool cmp(H x,H y)
{
    if(x.l==y.l) return x.r<y.r;
    return x.l<y.l; 
} 
void work()
{
    queue <H> q;cnt=0;ans=0;
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
    sort(a+1,a+n+1,cmp);

    b[++cnt]=a[1];
    for(int i=2;i<=n;i++)//合并区间 
    {
        if(a[i].l==a[i+1].l) continue;
        if(a[i].l<=b[cnt].r+1) b[cnt].r=max(b[cnt].r,a[i].r);
        else b[++cnt]=a[i]; 
    } 

    LL nowl,nowr;
    q.push(b[1]);nowl=b[1].l,nowr=b[1].r;ans=max(nowr-nowl+1+m,ans);    
    for(int i=2;i<=cnt;i++)
    {
        while(m<b[i].l-b[i-1].r-1&&q.size()>1)
        {
            H k=q.front();q.pop();
            H p=q.front();
            m+=p.l-k.r-1;
            nowl=p.l;
        }
        if(m>=b[i].l-b[i-1].r-1)
        {
            m-=b[i].l-b[i-1].r-1;
            nowr=b[i].r;
            q.push(b[i]);
        } 
        else 
        {
            q.pop();
            nowl=b[i].l,nowr=b[i].r;
            q.push(b[i]);
        }   
        ans=max(ans,nowr-nowl+1+m);
    }
    printf("%lld
",ans);
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF) work();
    return 0;
}