51nod - 1672 线段树（插队问题变形）

题意：

给出n个数，再给出m个区间，要求从中选择k个区间，要求k个区间的所重合的部分的和的最大值。

思路：

线段树。 首先先将n个数按照右端点排序，然后从n到1枚举每个位置作为最后并出来区间的右端点，对于每个确定的右端点R，我们就是要找到一个L保证[L,R]这段区间至少能被k个区间所覆盖。当枚举到位置pos的时候，就是要找区间右端点r >= pos，且区间左端点l <= pos区间的l值，如果有若干这样的区间存在，对于固定的R，很显然最后的区间L越小越好，但是又要保证这部分会被至少k个区间覆盖，所以要在这些区间中找左端点l第k小的位置。 这里就可以利用线段树，每次枚举新的位置pos，都可能会有新的区间满足条件R > pos，都要更新线段树，让线段树上这些区间的L位置+1，然后按照插队问题的思路，找到第k个l即可，通过之前保存的前缀和更新答案。 另外还有一个now表示当前符合条件的区间数，如果小于k就不用找第k个了，num[i]则是用来保存当前位置i上有多少个l占着的，用来更新now。 具体细节看代码：

代码：

#include <bits/stdc++.h> using namespace std; #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 const int MAXN = 2e5 + 10; struct SegmentTree { int C[MAXN << 2]; void push_up(int rt) { C[rt] = C[rt << 1] + C[rt << 1 | 1]; } void build(int l, int r, int rt) { C[rt] = 0; if (l == r) return; int m = (l + r) >> 1; build(lson); build(rson); } int query(int pos, int l, int r, int rt) { if (l == r) return l; int m = (l + r) >> 1, res; if (C[rt << 1] >= pos) res = query(pos, lson); else res = query(pos - C[rt << 1], rson); return res; } void update(int pos, int val, int l, int r, int rt) { if (l == r) { C[rt] += val; return; } int m = (l + r) >> 1; if (pos <= m) update(pos, val, lson); else update(pos, val, rson); push_up(rt); } }segtree; struct node { int l, r; bool operator < (const node &rhs) const { return r < rhs.r || (r == rhs.r && l < rhs.l); } } a[MAXN]; int num[MAXN]; long long sum[MAXN]; int main() { //freopen("in.txt", "r", stdin); int n, k, m; scanf("%d%d%d", &n, &k, &m); for (int i = 1; i <= n; i++) { scanf("%I64d", &sum[i]); sum[i] += sum[i - 1]; } for (int i = 1; i <= m; i++) scanf("%d%d", &a[i].l, &a[i].r); sort (a + 1, a + 1 + m); int now = 0; long long ans = 0; segtree.build(1, n, 1); for (int i = n, j = m; i >= 1; i--) { while (j > 0 && a[j].r == i) { ++now; segtree.update(a[j].l, 1, 1, n, 1); num[a[j].l]++; --j; } if (now >= k) { int pos = segtree.query(k, 1, n, 1); ans = max(ans, sum[i] - sum[pos - 1]); } now -= num[i]; } printf("%I64d\n", ans); return 0; }