小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。

这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。

一个“超级***”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级***的美妙度为其包含的所有音符的美妙度之和。两个超级***被认为是相同的，当且仅当这两个超级***所包含的音符集合是相同的。

小Z决定创作一首由k个超级***组成的乐曲，为了使得乐曲更加动听，小Z要求该乐曲由k个不同的超级***组成。我们定义一首乐曲的美妙度为其所包含的所有超级***的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。

ST表+优先队列 + 前缀和

优先队列的节点维护的信息

struct Node{
	int i; 以i开头
    int l;当前字符串结尾所在的区间左端点
    int r;当前字符串结尾所在的区间的右端点
    int pos;当前字符串尾端点
    int val;当前字符串的价值
}

对于每一个i，以i开头的长度为L ~ R之间的字符串的价值是可以用ST表和前缀和O(1)的时间求出来的。首先我们找到对于每一个i对于的长度为L~R的价值最大值加入优先队列当中，每次弹出价值最大的值，但是要注意一点，下一个最大值是哪个字符串，有两种可能，第一种是优先队列中的次大值，另外一种可能是刚刚弹出的以i开头的字符串的次大值，那么就要再次求出以i开头的另外一个次大值，那么次大值可能是{i, l, pos - 1, query(l, pos - 1), sum[query(l, pos - 1)] - sum[i - 1]}和{i, pos + 1, r, query(pos + 1, r), sum[query(pos + 1, r) - sum[i - 1]},所以弹出最大值是还要把这两个节点加进去。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

#define int long long
const int N = 2e6 + 10;
int n, k, L, R;
int f[N][22];
int sum[N];

struct Node{
    int id, l, r, pos, val;
    bool operator<(const Node & t) const{
        return val < t.val;
    }
}tr[N];

void ST()
{
    for(int j = 1; j <= 20; j ++ )
        for(int i = 1; i <= n; i ++ )
        {
            int x = f[i][j - 1], y = f[i + (1 << j - 1)][j - 1];
            f[i][j] = sum[x] > sum[y] ? x : y;
        }
}

int query(int l, int r)
{
    int len = r - l + 1;
    int k = log(len) / log(2);
    int x = f[l][k], y = f[r - (1 << k) + 1][k];
    return sum[x] > sum[y] ? x : y;
}

signed main()
{
    priority_queue<Node> q;
    cin >> n >> k >> L >> R;
    for(int i = 1; i <= n; i ++ ) cin >> sum[i], sum[i] += sum[i - 1], f[i][0] = i;
    ST();
    
    for(int i = 1; i <= n; i ++ )
    {
        if(i + L - 1 > n) break;
        if(i + L - 1 == n) q.push({i, n, n, n, sum[n] - sum[i - 1]});
        else
        {
            int x = query(i + L - 1, min(i + R - 1, n));
            q.push({i, i + L - 1, min(i + R - 1, n), x, sum[x] - sum[i - 1]});
        }
    }
    
    int ans = 0;
    while(k -- )
    {
        auto t = q.top();
        q.pop();
        
        int i = t.id, l = t.l, r = t.r, pos = t.pos, val = t.val;
        ans += val;
        
        if(pos > l)
        {
            int a = query(l, pos - 1);
            q.push({i, l, pos - 1, a, sum[a] - sum[i - 1]});
        }
        if(pos < r)
        {
            int b = query(pos + 1, r);
            q.push({i, pos + 1, r, b, sum[b] - sum[i - 1]});
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

题解 | #超级钢琴#

ST表+优先队列 + 前缀和