HDU 5700 区间交（线段树）

题目链接 区间交

给定n和k，求k个区间，使得这K个区间的交集的数的和最大。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)    for (int i(a); i <= (b); ++i)
#define dec(i, a, b)    for (int i(a); i >= (b); --i)

#define lson i << 1, L, mid
#define rson i << 1 | 1, mid + 1, R

typedef long long LL;

const int N = 200010;

struct node{
        int l, r;
        friend bool operator < (const node &a, const node &b){
            return a.l < b.l;
        }
} a[N];

int tree[N << 2];
int n, k, m;
LL sum[N], ans, x;

void pushup(int i){ tree[i] = tree[i << 1] + tree[i << 1 | 1];  }


void update(int i, int L, int R, int x){
        if (L == R){ ++tree[i]; return;}
        int mid = (L + R) >> 1;
        if (x <= mid) update(lson, x); else update(rson, x);
        pushup(i);
}

int query(int i, int L, int R, int x){
        if (L == R) return L;
        int mid = (L + R) >> 1;
        if (tree[i << 1 | 1] >= x) return query(rson, x);
        else return query(lson, x - tree[i << 1 | 1]);
}

int main(){

        while (~scanf("%d%d%d", &n, &k, &m)){
            sum[0] = 0; ans = 0;
            memset(tree, 0, sizeof tree);
            rep(i, 1, n){
                    scanf("%lld", &x);
                    sum[i] = sum[i - 1] + x;
            }

            rep(i, 1, m) scanf("%d%d", &a[i].l, &a[i].r);
            sort(a + 1, a + m + 1);
            dec(i, k, 1) update(1, 1, n, a[i].r);
            a[m + 1].r = 1;
            rep(i, k, m){
                    int pos = query(1, 1, n, k);
                    if (pos >= a[i].l) ans = max(ans, sum[pos] - sum[a[i].l - 1]);
                    update(1, 1, n, a[i + 1].r);
            }    

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