51nod 1672 区间交 好题

链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1672

思路： 我们可以按线段的右端点排序，然后对于每个线段，更新他的左端点，然后查询右端点，如果右端点>=K ，那么我们就二分找到树状数组中第K小的位置。肯定这个位置就是我们想要的交的左端点。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 100005;

struct node
{
    int l,r;
}xd[N];

int n,K,m;
int c[N];
ll a[N];
ll sum[N];

bool cmp(node a,node b)
{
    return a.r<b.r;
}

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

void update(int x,int val)
{
    for(;x<n+2;x+=lowbit(x))
    {
        c[x]+=val;
    }
}

int query(int x)
{
    int sum=0;
    for(;x>0;x-=lowbit(x))
    {
        sum+=c[x];
    }
    return sum;
}

int main()
{
    scanf("%d %d %d",&n,&K,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }

    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&xd[i].l, &xd[i].r);
    }

    sort(xd+1,xd+m+1,cmp);

    for(int i=m;i>=m-K+2;i--)
    {
        update(xd[i].l,1);
    }

    ll Ans=0;
    for(int i=m-K+1;i>=1;i--)
    {
        update(xd[i].l,1);
        int tmp=query(xd[i].r);
        if(tmp>=K)
        {
            int l=1,r=xd[i].r;
            int mid,ans=-1;
            while(l<=r)
            {
                mid=(l+r)>>1;
                if(query(mid)>=K)
                {
                    ans=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            if(ans!=-1){
                //printf("*** %d %d\n",ans,xd[i].r);
                Ans=max(Ans,sum[xd[i].r]-sum[ans-1]);
            }
        }
    }

    printf("%lld\n",Ans);

    return 0;
}