自动搬运

查看原文

来自洛谷，原作者为

	lalaouye 星河滚烫，你是人间理想。

搬运于2025-08-24 21:57:47，当前版本为作者最后更新于2025-08-19 11:48:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这题看着就很费用流。

我们不妨建出模型，首先对每个 $i$ 建边 $(S,i,D_i,0)$，$(i,T,U_i,P_i)$。

然后注意到保留产品就是后面的销售用前面的产品，也就是连边 $(i,i-1,\infty,M_{i-1})$，而延迟销售显然就是连边 $(i,i+1,\infty,C_i)$。

这个数据范围下费用流显然是跑不动的，但是这个费用流模型很简单，考虑模拟费用流。这里有个小细节，就是我们连源点的边不是表示产生的产品而是需要的产品，这其实是为了让每个出边都一定流满，这个性质可以让我们以任意顺序去增广每个出边的增广路。

并且对于任意费用流都满足性质：与 $S,T$ 直接相连的边不会退流。

知道这些我们考虑怎么去模拟，首先我们不妨从前往后增广出边，那么增广路分为向左增广和向右增广，我们发现向右增广时不会受到反向边影响，而向左会，我们考虑反向边会带来怎样的影响。

首先我们观察过程，发现反向边之后出现一次消失一次，因为在它之前的出边都会使它的容量增加，而在它之后的边都会使它的容量减少。那么我们如果向右增广，相当于直接给区间反向边容量加一，此时我们可以在线段树上均摊激活，每条反向边激活时顶多花 $\mathcal{O}(\log n)$ 的时间激活，那么总复杂度是 $\mathcal{O}(n\log n)$。

考虑向左影响的影响，其实差不太多，就是给区间内被激活的反向边的容量减去一个数，取消激活也可以均摊。

对于维护距离我们并不必像区间最大子段和那样维护几个东西，我们 $i\rightarrow i+1$ 时，会使当前位置到 $[1,i]$ 的距离增加 $M_{i}$，$[i+1,n]$ 的距离减去 $C_i$，直接区间加求区间最大值维护即可。

均摊时有一些细节，具体可以看代码：

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i (l); i <= (r); ++ i)
#define rrp(i, l, r) for (int i (r); i >= (l); -- i)
#define eb emplace_back
using namespace std;
#define pii pair <int, int>
#define inf 1000000000
#define ls (p << 1)
#define rs (ls | 1)
#define fi first
#define se second
constexpr int N = 1e5 + 5, M = 5e5 + 5;
typedef long long ll;
typedef unsigned long long ull;
inline int rd () {
  int x = 0, f = 1;
  char ch = getchar ();
  while (! isdigit (ch)) {
    if (ch == '-') f = -1;
    ch = getchar ();
  }
  while (isdigit (ch)) {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar ();
  }
  return x * f;
}
int n, D[N], U[N], P[N], A[N], B[N], d[N];
class sgt {
  public:
  int tag[N << 2];
  pii Min[N << 2];
  int mn[N << 2];
  bool vis[N << 2];
  void build (int p, int l, int r, int o) {
    vis[p] = o;
    if (l == r) return Min[p].se = l, void ();
    int mid (l + r >> 1);
    build (ls, l, mid, o), build (rs, mid + 1, r, o);
  }
  void add (int p, int k) {
    mn[p] += k, Min[p].fi += k, tag[p] += k;
    Min[p].fi = min (Min[p].fi, inf);
  }
  void psd (int p) {
    if (tag[p]) {
      add (ls, tag[p]);
      add (rs, tag[p]);
      tag[p] = 0;
    }
  }
  void upd (int p, int l, int r, int L, int R, int k) ;
  void upd2 (int p, int l, int r, int L, int R, int k) ;
  pii qry (int p, int l, int r, int L, int R) {
    if (! vis[p]) return pii (inf, 0);
    if (L <= l && r <= R) return Min[p];
    int mid (l + r >> 1); pii ret = pii (inf, 0); psd (p);
    if (L <= mid) ret = qry (ls, l, mid, L, R);
    if (R > mid) ret = min (ret, qry (rs, mid + 1, r, L, R));
    return ret;
  }
} t1, t2, t3;
void sgt :: upd (int p, int l, int r, int L, int R, int k) {
  if (L <= l && r <= R) return add (p, k);
  int mid (l + r >> 1); psd (p);
  if (L <= mid) upd (ls, l, mid, L, R, k);
  if (R > mid) upd (rs, mid + 1, r, L, R, k);
  Min[p] = min (Min[ls], Min[rs]);
  mn[p] = min (mn[ls], mn[rs]);
  vis[p] = vis[ls] | vis[rs];
}
void sgt :: upd2 (int p, int l, int r, int L, int R, int k) {
  if (k < 0 && ! vis[p]) return ;
  if (l == r || L <= l && r <= R && ((mn[p] > 0 && k > 0) || (k < 0 && Min[p].fi + k > 0))) {
    add (p, k); 
    if (vis[p] && ! mn[p]) vis[p] = 0, t1.upd (1, 1, n, 1, l, A[l] + B[l]);
    if (! vis[p] && mn[p] == k) vis[p] = 1, d[l] += A[l] + B[l], assert (l == r);
    return ;
  } int mid (l + r >> 1); psd (p);
  if (L <= mid) upd2 (ls, l, mid, L, R, k);
  if (R > mid) upd2 (rs, mid + 1, r, L, R, k);
  Min[p] = min (vis[ls] ? Min[ls] : pii (inf, 0), vis[rs] ? Min[rs] : pii (inf, 0));
  mn[p] = min (mn[ls], mn[rs]);
  vis[p] = vis[ls] | vis[rs];
}
int32_t main () {
  // freopen ("1.in", "r", stdin);
  // freopen ("1.out", "w", stdout);
  n = rd ();
  rep (i, 1, n) D[i] = rd ();
  rep (i, 1, n) U[i] = rd ();
  rep (i, 1, n) P[i] = rd ();
  rep (i, 1, n - 1) A[i] = rd ();
  rep (i, 1, n - 1) B[i] = rd ();
  t1.build (1, 1, n, 1), t2.build (1, 1, n, 1), t3.build (1, 1, n, 0);
  rep (i, 1, n) t1.upd (1, 1, n, i, i, P[i]);
  int sum (0);
  rep (i, 1, n) sum += B[i - 1], t2.upd (1, 1, n, i, i, sum + P[i]);
  ll ans (0);
  rep (i, 1, n) {
    t2.upd (1, 1, n, i, n, - B[i - 1]);
    if (i > 1) t1.upd (1, 1, n, 1, i - 1, A[i - 1] - d[i - 1]);
    while (D[i] > 0) {
      pii p = i > 1 ? t1.qry (1, 1, n, 1, i - 1) : pii (inf, 0);
      pii q = t2.qry (1, 1, n, i, n);
      p = min (p, q); int j (p.se);
      if (j < i) {
        pii t = t3.qry (1, 1, n, j, i - 1);
        int f = min (min (D[i], U[j]), t.fi);
        ans += 1ll * p.fi * f;
        D[i] -= f, U[j] -= f;
        if (! U[j]) t1.upd (1, 1, n, j, j, inf), t2.upd (1, 1, n, j, j, inf);
        if (j < i) t3.upd2 (1, 1, n, j, i - 1, - f);
      } else {
        int f = min (D[i], U[j]);
        ans += 1ll * p.fi * f;
        D[i] -= f, U[j] -= f;
        if (! U[j]) t1.upd (1, 1, n, j, j, inf), t2.upd (1, 1, n, j, j, inf);
        if (i < j)
        t3.upd2 (1, 1, n, i, j - 1, f);
      }
    }
  } 
  cout << ans;
}