[NOI2010]超级钢琴题解

很妙的一道题，用到了 贪心 + 堆 + ST表

先考虑 $k=1$ 的方法。

$k=1$

先对原序列前缀和。

然后枚举左端点，$ans = \max_{r = l + a - 1}^{l + b - 1} (s_r - s_{l - 1})$, 如果要让 $ans$ 最大，只需让 $s_r$ 最大即可, 区间最大值可以用 $ST表$ 来求。复杂度 $O(n)$

正解

像这种要求前 $k$ 大， 目前会求最大的情况下可以考虑使用堆。

设五元组 $(x, l, r, p, mx)$ 表示 (左端点的位置($x$)，右端点所在区间($l,r$)，最优右端点位置($p$)，最大值($mx$))

以 $mx$ 为权值，维护大根堆。

对于每个点作为左端点都可以得到一个五元组，把它们都放到堆中。

堆顶即为当前最大值。

取出堆顶后，由于已经选了 $(x,p)$ 所以把它分成两个五元组 $(x,l,p-1,p_l,mx_l)$ 和 $(x,p+1,r,p_r,mx_r)$, 并放入堆中, $p_l,mx_l,p_r,mx_r$ 可以用 $ST表$ 求出。

把这个操作重复 $k$ 次，每次结果的和即为所求。

Code:

#include <iostream>
#include <cstdio>
#include <queue>
#define int long long

using namespace std;

const int N = 5e5 + 10;
int st[N][30], d[N][30];

int n, k, l, r;
int a[N], lg[N];

int find(int x, int y)
{
  int k = lg[y - x + 1];
  if (st[x][k] > st[y - (1 << k) + 1][k])
  {
    return d[x][k];
  }
  else return d[y - (1 << k) + 1][k];
}

struct Node
{
  int x, l, r, p;

  bool operator < (const Node b) const
  {
    return a[find(l, r)] - a[x - 1] < a[find(b.l, b.r)] - a[b.x - 1];
  }
};

priority_queue<Node> q;

signed main()
{
  scanf("%lld%lld%lld%lld", &n, &k, &l, &r);
  lg[1] = 0;
  for (int i = 1; i <= n; ++i)
  {
    scanf("%lld", &a[i]);
    a[i] = a[i - 1] + a[i];
    st[i][0] = a[i];
    d[i][0] = i;
  }
  for (int i = 2; i <= n; ++i)
  {
    lg[i] = lg[i / 2] + 1;
  }
  for (int k = 1; k <= lg[n]; ++k)
  {
    for (int i = 1; i + (1ll << k) - 1 <= n; ++i)
    {
      if (st[i][k - 1] > st[i + (1ll << (k - 1))][k - 1])
      {
        st[i][k] = st[i][k - 1];
        d[i][k] = d[i][k - 1];
      }
      else
      {
        st[i][k] = st[i + (1ll << (k - 1))][k - 1];
        d[i][k] = d[i + (1ll << (k - 1))][k - 1];
      }
    }
  }
  for (int i = 1; i <= n - l + 1; ++i)
  {
    q.push((Node){i, min(n, i + l - 1), min(n, i + r - 1), find(min(n, i + l - 1), min(n, i + r - 1))});
  }
  int ans = 0;
  while (k--)
  {
    Node u = q.top();
    q.pop();
    ans += a[u.p] - a[u.x  - 1];
    if (u.l <= u.p - 1) q.push((Node){u.x, u.l, u.p - 1, find(u.l, u.p - 1)});
    if (u.p + 1 <= u.r) q.push((Node){u.x, u.p + 1, u.r, find(u.p + 1, u.r)});
  }
  cout <<ans << endl;
  return 0;
}