Problem
传送门 https://www.luogu.org/problemnew/show/P2048
给一个长度为 \(n\) 的序列 \(A\), 定义子区间价值 \(W_{[l,r]}=\sum_{i = l}^{i \leq r}A_i\)
要求选出 \(k\) 个互不相同的子区间, 使选出的区间价值和最大.
Solution
首先, 为了快速求出一段区间的和, 我们预处理前缀和
然后就是一个很巧妙的技巧:
定义 \(Max_{(o,l,r)}\) 为以 \(o\) 为左端点, 长度在区间 \([l,r]\) 以内的权值和最大的连续区间.
很显然 \(Max_{(o,l,r)}=max(sum(t)-sum(o - 1), t∈[l,r])\)
其中 \(sum(x) = \sum_{i = 1}^{i \leq x}A[i]\)
因为固定了 o 点,\(sum(o - 1)\) 一定是确定的, 所以我们相当于要求 \(sum(t)\) 在区间 \([l,r]\) 中的最大值.
不难想到用线段树维护, 但是因为没有修改操作, 可以直接用 \(RMQ\)
然后就是贪心了, 维护一个大根堆, 每次询问堆顶元素的权值, 在将它从堆中删除......
然后就愉快的 \(WA\) 成 \(SB\) 了......
分析错误原因, 是我们没有考虑以 \(o\) 为左端点的区间有可能有不止一个区间可以为答案做出贡献......
所以我们在删除对顶元素时, 还需要将剩余部分插入堆
假设当前堆顶的元素为 \(Max_{(o,l,r)}\) 且区间长度为 \(t\) 时, 取到最大值
在删除后我们将 \(Max_{(o,l,t - 1)}\) 与 \(Max_{(o,t + 1, r)}\) 扔回堆中即可
- Code
- #include <bits/stdc++.h>
- using namespace std;
- #define DEBUG(...) fprintf(stderr, __VA_ARGS__)
- #define mp make_pair
- #define fst first
- #define snd second
- template<typename T> inline bool chkmin(T &a, const T &b) { return a> b ? a = b, 1 : 0; }
- template<typename T> inline bool chkmax(T &a, const T &b) { return a <b ? a = b, 1 : 0; }
- inline int read(){
- int res = 0, fl = 1;
- char r = getchar();
- for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
- for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
- return res * fl;
- }
- typedef long long LL;
- typedef pair<int, int> pii;
- const int Maxn = 2e6 + 10;
- int n, L, R, k, a[Maxn], ok;
- namespace RMQ{
- pii RMQ[Maxn][21];
- int Log[Maxn], Pow[30];
- inline pii Query(int l, int r){
- return max(RMQ[l][Log[r - l + 1]], RMQ[r - Pow[Log[r - l + 1]] + 1][Log[r - l + 1]]);
- }
- void init(){
- int num = 1;
- Log[0] = -1;
- for (int i = 1; i <= n; ++i){
- if(i == num) Log[i] = 1, num = num <<1;
- Log[i] += Log[i - 1];
- RMQ[i][0] = mp(a[i], i);
- }
- Pow[0] = 1;
- for (int i = 1; i <= 20; ++i) Pow[i] = Pow[i - 1] << 1;
- for (int j = 1; j <= Log[n]; ++j)
- for (int i = 1; i <= n; ++i)
- RMQ[i][j] = max(RMQ[i][j - 1], RMQ[i + Pow[j - 1]][j - 1]);
- }
- }
- struct node{
- int o, l, r, val;
- bool operator < (const node & T) const{ return val < T.val;}
- inline int Query(){ return RMQ::Query(o + l - 1, o + r - 1).fst - a[o - 1];}
- inline int Where(){ return RMQ::Query(o + l - 1, o + r - 1).snd - o + 1;}
- };
- priority_queue<node> Q;
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("a.in", "r", stdin);
- freopen("a.out", "w", stdout);
- #endif
- n = read(), k = read(), L = read(), R = read();
- for (int i = 1; i <= n; ++i) a[i] = read() + a[i - 1];
- RMQ::init();
- for (int i = 1; i <= n - L + 1; ++i){
- node now = (node){i, L, min(R, n - i + 1), 0};
- now.val = now.Query();
- Q.push(now);
- }
- LL ans = 0;
- node nxt;
- while(k--){
- node now = Q.top();
- ans += now.val;
- Q.pop();
- if(now.Where()> now.l)
- nxt = (node){now.o, now.l, now.Where() - 1, 0}, nxt.val = nxt.Query(), Q.push(nxt);
- if(now.Where() < now.r)
- nxt = (node){now.o, now.Where() + 1, now.r, 0}, nxt.val = nxt.Query(), Q.push(nxt);
- }
- printf("%lld\n", ans);
- return 0;
- }
[NOI2010] 超级钢琴
来源: http://www.bubuko.com/infodetail-3002242.html