[HDU 6119]小小粉丝度度熊

原题链接

因为肯定是要补连续的
利用队列的思想
区间作为成员

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<climits>
#include<string>
#include<cstdlib>
#include<ctime>
#define LL long long
#define MOD 1000000007
using namespace std;

struct nico
{
    LL l,r,len;
}p[200005],ak[200005];

LL i,n,m,poi,h,t,ans,ans_now,lenth[200005],cnt,ll,rr;

bool comp(nico a,nico b)
{
    if(a.l==b.l) return a.r<b.r;
    return a.l<b.l;
}

int main()
{
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        cnt=0;
        ans=0;
        ans_now=0;

        for(i=1;i<=n;i++)
            scanf("%lld%lld",&p[i].l,&p[i].r);

        sort(p+1,p+n+1,comp);

        cnt++;
        ak[cnt].l=p[1].l;
        ak[cnt].r=p[1].r;       

        for(i=2;i<=n;i++)
        {
            if(ak[cnt].r+1<p[i].l)
            {
                cnt++;
                ak[cnt].l=p[i].l;
                ak[cnt].r=p[i].r;
            }

            else ak[cnt].r=max(ak[cnt].r,p[i].r);
        }

        for(i=1;i<cnt;i++)
            lenth[i]=ak[i+1].l-ak[i].r-1;

        ll=1;

        for(i=1;i<cnt;i++)
        {
            ans_now+=lenth[i];

            while(m<ans_now)
                ans_now-=lenth[ll++];

            ans=max(ans,ak[i+1].r-ak[ll].l+1+m-ans_now);
        }

        ans=max(ans,ak[1].r-ak[1].l+1+m);       
        printf("%lld\n",ans);       
    }

    return 0;
}