P8476 「GLR-R3」惊蛰

· · 题解

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 的最小代价，则需要支持以下操作：

维护区间最大值和赋值，加法，加 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
*/