自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:39:25，当前版本为作者最后更新于2022-08-21 12:50:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

C. P8476「GLR-R3」惊蛰

考虑 DP，设 $g_{i, j}$ 表示使得 $b_i = j$ 的最小代价，则 $g_{i, j} = \min\limits_{k \geq j} g_{i - 1, k} + f(j, a_i)$。直接做时间复杂度 $\mathcal{O}(nV)$，不可接受。

考虑转移的本质，对 $g_{i - 1}$ 做一遍后缀 $\min$，然后令 $g_{i, j} \gets g_{i - 1, j} + f(j, a_i)$。$f$ 和后缀 $\min$ 的优秀性质使得可以快速维护 $g$。具体地，对 $g_{i - 1}$ 做后缀 $\min$ 之后 $g_{i - 1}$ 具有单调性 $g_{i - 1, j}\leq g_{i - 1, j + 1}$，而 $f(j, a_i)$ 是关于 $j$ 的分段函数，当 $j < a_i$ 时相当于为 $g_{i - 1, j}$ 区间加 $C$，当 $j \geq a_i$ 时相当于为 $g_{i - 1, j}$ 加上 $j - a_i$，两部分分别具有单调性，所以操作结束后 $g_{i, j}$ 以 $a_i$ 为分割线变成两段关于 $j$ 具有单调性的序列。

根据上述分析，对 $g_{i - 1}$ 做后缀 $\min$ 时，只需线段树二分出 $< a_{i - 1}$ 的位置中最后一个使得 $g_{i, j} > g_{i, a_{i - 1}}$ 的位置 $j$，则该操作可视为对 $g_{i - 1, j}\sim g_{i - 1, a_{i - 1} - 1}$ 区间赋值 $g_{i - 1, a_i - 1}$。

将 $a$ 离散化，设 $g_{i, j}$ 表示使得 $b_i = a_j$ 的最小代价，则需要支持以下操作：

• 区间给位置 $i$ 加上 $a_i$。
• 区间加法。
• 区间赋值。
• 线段树二分 $< p$ 的位置最后一个 $> v$ 的位置 $q$，保证 $< p$ 的位置具有单调性。

维护区间最大值和赋值，加法，加 $a_i$ 懒标记即可。时间复杂度 $\mathcal{O}(n\log n)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
bool Mbe;
constexpr int N = 1e6 + 5;
ll val[N << 2], b[N];
struct tag {
  ll ass, add, badd;
  tag operator + (const tag &x) const {
    if(x.ass != -1) return x;
    tag z = *this;
    z.add += x.add, z.badd += x.badd;
    return z;
  }
} laz[N << 2];
void eff(int l, ll x, tag v) {
  if(v.ass != -1) val[x] = v.ass;
  val[x] += v.add + b[l] * v.badd;
  laz[x] = laz[x] + v;
}
void down(int l, int r, int x) {
  int m = l + r >> 1;
  eff(m, x << 1, laz[x]);
  eff(r, x << 1 | 1, laz[x]);
  laz[x] = {-1, 0, 0};
}
void modify(int l, int r, int ql, int qr, int x, tag v) {
  if(ql > qr) return;
  if(ql <= l && r <= qr) return eff(r, x, v);
  int m = l + r >> 1;
  down(l, r, x);
  if(ql <= m) modify(l, m, ql, qr, x << 1, v);
  if(m < qr) modify(m + 1, r, ql, qr, x << 1 | 1, v);
  val[x] = max(val[x << 1], val[x << 1 | 1]);
}
int binary(int l, int r, int p, int x, ll lim) { // find the first position that val[x] >= lim
  if(r <= p && val[x] < lim) return -1;
  if(l == r) return l;
  int m = l + r >> 1;
  down(l, r, x);
  int res = binary(l, m, p, x << 1, lim);
  if(res != -1) return res;
  res = m < p ? binary(m + 1, r, p, x << 1 | 1, lim) : -1;
  return res;
}
ll query(int l, int r, int p, int x) {
  if(l == r) return val[x];
  int m = l + r >> 1;
  down(l, r, x);
  if(p <= m) return query(l, m, p, x << 1);
  return query(m + 1, r, p, x << 1 | 1);
}
int n, C, a[N];
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0);
  cin >> n >> C;
  for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
  sort(b + 1, b + n + 1);
  for(int i = 1; i <= n << 2; i++) laz[i].ass = -1;
  for(int i = 1; i <= n; i++) {
    int p = lower_bound(b + 1, b + n + 1, a[i]) - b;
    modify(1, n, p + 1, n, 1, (tag) {-1, -a[i], 1});
    if(p == 1) continue;
    modify(1, n, 1, p - 1, 1, (tag) {-1, C, 0});
    ll v = query(1, n, p, 1);
    int pos = binary(1, n, p - 1, 1, v);
    if(pos != -1) modify(1, n, pos, p - 1, 1, (tag) {v, 0, 0});
  }
  cout << query(1, n, 1, 1) << "\n";
  cerr << TIME << " ms\n";
  return 0;
}
/*
2022/8/14
Author: Alex_Wei
start coding at 15:55
finish debugging at 16:40
*/