HDU－5700－区间交

Problem Description

小A有一个含有n个非负整数的数列与m个区间。每个区间可以表示为li,ri。
它想选择其中k个区间，使得这些区间的交的那些位置所对应的数的和最大。
例如样例中，选择[2,5]与[4,5]两个区间就可以啦。

Input
多组测试数据
第一行三个数n,k,m(1≤n≤100000,1≤k≤m≤100000)。
接下来一行n个数ai，表示lyk的数列(0≤ai≤109)。
接下来m行，每行两个数li,ri，表示每个区间(1≤li≤ri≤n)。

Output
一行表示答案

Sample Input
5 2 3
1 2 3 4 6
4 5
2 5
1 4

Sample Output
10

Source
2016”百度之星” - 初赛（Astar Round2B）

Recommend
wange2014

一道线段树问题，加上枚举，就可以解决，这是第一次做线段数问题，先查阅了一天的相关资料，然后尝试做这道题，因为初次做这种类型题，着实费了不少时间，还出来一个bug，难为死我了，找了好久好久，提交了七八次都没有过，全部是因为一个问题，一个基础的问题，把我卡的死死的。

题解

首先排序右端点从小到大，然后枚举右端点（保证所枚举的那个端点最少有k个区间可以覆盖）作为所求的交区间的右端点，这时候需要求出交区间的左端点，我们可以知道，右端点确定下，如果左端点越靠左，这个区间的范围约大。为了保证所交区间有k个，我们需要找到第k小的左端点，为了保证我枚举的右端点肯定是交区间的右端点，我们必须边枚举，边单点更新左端点。

具体的代码实现还是有很多需要注意的地方（注释写得很清晰），有一些代码段不是十分容易理解，另外，排序也可以对左端点进行排序，也可以从大到小排序，不同的排序，后边的处理手段会有一些区别，但是整体是一样的。

代码(C)：

#include <stdio.h>
#include <stdlib.h>
//#pragma GCC optimize("02")
#define MAXSIZE 100005
#define MID (L + R) >> 1
#define LSON tag * 2, L, MID
#define RSON tag * 2 + 1, (MID) + 1, R
#define MAX(a, b) a > b ? a : b

typedef long long LL;
LL A, ans;
LL sum[MAXSIZE] = {
  0};    //前缀和

typedef struct
{
    int left;
    int right;
}route;
route rou[MAXSIZE];

struct seg
{
    int cover;
}segs[MAXSIZE * 4];

//输入LL
void scanfDiyLL(LL *ret)
{
    char c;
    *ret = 0;
    while((c = getchar()) < '0' || c > '9');
    while(c >= '0' && c <= '9')
        *ret = (*ret) * 10 + (c - '0'), c = getchar();
    return ;
}
//输入int
void scanfDiyInt(int *ret)
{
    char c;
    *ret = 0;
    while((c = getchar()) < '0' || c > '9');
    while(c >= '0' && c <= '9')
        *ret = (*ret) * 10 + (c - '0'), c = getchar();
    return ;
}

int cmp(const void *a, const void *b)
{
    route *aa = (route *)a;
    route *bb = (route *)b;
    if (aa->right != bb->right)
    {
        return aa->right > bb->right ? 1 : -1;
    }
    return 0;
}

void pushUp(int tag)
{
    segs[tag].cover = segs[tag * 2].cover + segs[tag * 2 + 1].cover;
    return ;
}

void buildTree(int tag, int L, int R)
{
    if (L == R)
    {
        segs[tag].cover = 0;    //建树时初始化重叠次数为0
        return ;
    }
    buildTree(LSON);
    buildTree(RSON);
    pushUp(tag);
    return ;
}

//查找并更新
void upDate(int tag, int L, int R, int id)
{
    if (L == R)
    {
        segs[tag].cover++;
        return ;
    }
    if (id <= MID)
    {
        upDate(LSON, id);
    }
    else
    {
        upDate(RSON, id);
    }
    pushUp(tag);
    return ;
}

int query(int tag, int L, int R, int k)
{
    if (L == R)
    {
        return L;
    }
    if (k <= segs[tag * 2].cover)   //左边为最高优先选择
    {
        return query(LSON, k);
    }
    else
    {
        return query(RSON, k - segs[tag * 2].cover);    //左边不足，取左边，剩余不足的取右边
    }
}

int main(int argc, const char * argv[])
{
    int n, k, m;

    while (~scanf("%d %d %d", &n, &k, &m))
    {
        buildTree(1, 1, n);

        for (int i = 1; i <= n; i++)
        {
            scanfDiyLL(&A);
            sum[i] = sum[i - 1] + A;
        }
        for (int i = 1; i <= m; i++)
        {
            scanfDiyInt(&rou[i].left);
            scanfDiyInt(&rou[i].right);
        }

        qsort(rou + 1, m, sizeof(rou[0]), cmp); //右端点由小到大排序

// for (int i = 1; i <= m; i++)
// {
   
// printf("%d %d\n", rou[i].begin, rou[i].end);
// }

        for (int i = m - k + 1; i <= m; i++)    //这一部分右端点可以肯定不会是交区间右端点
        {
            upDate(1, 1, n, rou[i].left);
        }

        ans = 0;
        for (int i = m - k + 1; i >= 1; i--)
        {
            int l = query(1, 1, n, k);
            if (l <= rou[i].right)    //以rou[i].end为右端点
            {
                ans = MAX(ans, sum[rou[i].right] - sum[l - 1]);
            }
            upDate(1, 1, n, rou[i - 1].left);  //继续加区间端点
        }

        printf("%lld\n", ans);
    }

    return 0;
}