HDU 5700 区间交

枚举起点 二分终点 树状数组check

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<map>
#include<queue>
#include<vector>
using namespace std;

const int maxn=200000+10;
int n,k,m;
long long a[maxn];
long long sum[maxn];
int c[maxn];

struct X
{
    int L,R;
} s[maxn];

bool cmp(const X&a,const X&b)
{
    return a.L<b.L;
}

int lowbit(int x)
{
    return x&(-x);
}

void update(int pos,int val)
{
    while(pos<=n)
    {
        c[pos]=c[pos]+val;
        pos=pos+lowbit(pos);
    }
}

int getsum(int pos)
{
    int res=0;
    while(pos>0)
    {
        res=res+c[pos];
        pos=pos-lowbit(pos);
    }
    return res;
}

int main()
{
    while(~scanf("%d%d%d",&n,&k,&m))
    {
        memset(c,0,sizeof c);
        sum[0]=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        for(int i=1; i<=m; i++) scanf("%d%d",&s[i].L,&s[i].R);
        sort(s+1,s+1+m,cmp);

        long long ans=0;
        int now=1;
        for(int i=1; i<=n; i++)
        {
            while(now<=m&&s[now].L==i)
            {
                update(s[now].R,1);now++;

                int p=-1;
                int l=i,r=n;

                while(l<=r)
                {
                    int mid=(l+r)/2;
                    int q=getsum(n)-getsum(mid-1);
                    if(q>k) l=mid+1;
                    else if(q<k) r=mid-1;
                    else p=mid,l=mid+1;
                }

                if(p==-1) continue;
                ans=max(ans,sum[p]-sum[i-1]);

            }
        }
        printf("%lld
",ans);
    }
    return 0;
}