P7408 [JOI 2021 Final] 地牢 3 题解

Description

有一个 $N+1$ 层的地牢，在地牢里有 $M$ 个玩家。地牢的每层从入口开始，用 $1$ 到 $N+1$ 的整数编号。玩家从 $1$ 到 $M$ 标号。

玩家使用能量从一层移动到下一层。玩家从第 $i\ (1\le i\le N)$ 层移动到第 $i+1$ 层所用的能量为 $A_i$。因为这是一个单向通行的地牢，所以玩家只能从第 $i$ 层移动到第 $i+1$ 层，并且要保证 $1\le i\le N$。

在第 $1$ 到第 $N$ 层的每层（包括第 $1$ 和第 $N$ 层）都有治疗泉。在第 $i$ 层的治疗泉处，玩家可以花 $B_i$ 金币，使自己的能量增加 $1$。只要玩家有足够的金币，他就可以多次使用治疗泉。但是，每个玩家都有最大能量，使用治疗泉的话也不能使自己的能量超过最大值。

现在玩家 $j\ (1\le j\le M)$ 在第 $S_j$ 层。他目前的能量为 $0$。他的最大能量是 $U_j$。他想要到第 $T_j$ 层。在路上他的能量不能小于 $0$。他需要多少金币呢？

给定这个地牢和玩家的信息，写一个程序计算对于每个玩家，是否可以在移动过程中能量不小于 $0$ 的情况下到达目的地。如果可以的话，计算他最少需要多少金币才能达成目标。

对于所有数据，满足：

$1\le N,M\le 2\times 10^5$；
$1\le A_i,B_i\le 2\times 10^5\ (1\le i\le N)$；
$1\le S_j<T_j\le N+1\ (1\le j\le M)$；
$1\le U_j\le 10^8\ (1\le j\le M)$。

Solution

首先考虑对题意进行转化，设 $c_i=\sum_{j<i}{a_j}$，将走地牢转化为在数轴上从 $c_s$ 走到 $c_t$，而使用治疗泉可以看作是在 $[c_i,c_i+U)$ 这个区间里用 $b_i$ 的代价选择一个位置激活，问将 $[c_s,c_t)$ 里所有的位置都激活的最小代价。

容易发现一个位置 $p$ 的代价是 $[p-U+1,p]$ 区间内关键点权值的最小值。

考虑对于每个关键点 $i$ 算出其控制的区间，设 $pre$ 为 $i$ 之前第一个代价小于 $b_i$ 的位置，$nxt$ 为 $i$ 之后第一个代价小于 $b_i$ 的位置。

那么一个位置 $p$ 被 $i$ 控制当且仅当 $p-U\geq c_{pre},p-U<c_i,p<c_{nxt}$，整理一下为：$\max\{c_i,c_{pre}+U\}\leq p<\min\{c_i+U,c_{nxt}\}$。

于是关键点 $i$ 对答案的贡献为 $b_i\times\left(\min\{c_i+U,c_{nxt}\}-\max\{c_i,c_{pre}+U\}\right)$，这是个关于 $U$ 的分段一次函数，可以用动态开点线段树维护每个 $U$ 的答案。

对于终点全是 $n+1$ 的子任务直接将询问离线下来倒着枚举关键点，同时维护一个代价从栈顶到栈底递增的单调栈来求出每个点的 $pre$ 和 $nxt$。

每次加入一个点 $i$ 时，将所有 $pre$ 为 $i$ 的位置 $j$ 之前的贡献去掉，再加上 $(j,pre_j,nxt_j)$ 的贡献，然后加入 $(i,0,nxt_i)$ 的贡献表示当 $s=i$ 时 $i$ 找不到 $pre$ 时 $i$ 对答案的贡献。

如果终点不固定，则找到询问为 $(s,n+1)$ 时控制 $c_t$ 的关键点 $k$，容易发现 $c_t-U<c_k\leq c_t$，那么 $(s,n+1)$ 和 $(k,n+1)$ 两组询问在 $[c_t,c_{n+1})$ 的贡献是相等的，并且 $(k,n+1)$ 在 $[c_k,c_t)$ 的贡献为 $b_k\cdot(c_t-c_k)$，所以 $ans(s,t)=ans(s,n+1)-ans(k,n+1)+b_k\cdot(c_t-c_k)$，就转化为终点固定的情况了。

时间复杂度：$O((n+m)\log V)$。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 2e5 + 5;

int n, m, rt, sgt_cnt;
int a[kMaxN], b[kMaxN], c[kMaxN], ans[kMaxN];
int lg[kMaxN], sta[kMaxN][20], stb[kMaxN][20];
int ls[kMaxN * 60], rs[kMaxN * 60], sum[kMaxN * 60], tag[kMaxN * 60];
std::vector<std::tuple<int, int, int>> qq[kMaxN];

int get(int x, int y) {
  return b[x] < b[y] ? x : y;
}

void st_prework() {
  lg[0] = -1;
  for (int i = 1; i <= n + 1; ++i) {
    sta[i][0] = a[i];
    stb[i][0] = i;
    lg[i] = lg[i >> 1] + 1;
  }
  for (int i = 1; i <= lg[n + 1]; ++i) {
    for (int j = 1; j <= n + 1 - (1 << i) + 1; ++j) {
      sta[j][i] = std::max(sta[j][i - 1], sta[j + (1 << (i - 1))][i - 1]);
      stb[j][i] = get(stb[j][i - 1], stb[j + (1 << (i - 1))][i - 1]);
    }
  }
}

int querya(int l, int r) {
  int k = lg[r - l + 1];
  return std::max(sta[l][k], sta[r - (1 << k) + 1][k]);
}

int queryb(int l, int r) {
  int k = lg[r - l + 1];
  return get(stb[l][k], stb[r - (1 << k) + 1][k]);
}

void prework() {
  st_prework();
}

void update(int &x, int l, int r, int ql, int qr, int v) {
  if (l > qr || r < ql) return;
  if (!x) x = ++sgt_cnt;
  sum[x] += 1ll * v * (std::min(r, qr) - std::max(l, ql) + 1);
  if (l >= ql && r <= qr) return void(tag[x] += v);
  int mid = (l + r) >> 1;
  update(ls[x], l, mid, ql, qr, v), update(rs[x], mid + 1, r, ql, qr, v);
}

int query(int x, int l, int r, int ql, int qr) {
  if (!x || l > qr || r < ql) return 0;
  else if (l >= ql && r <= qr) return sum[x];
  int mid = (l + r) >> 1;
  return query(ls[x], l, mid, ql, qr) + query(rs[x], mid + 1, r, ql, qr) + 1ll * tag[x] * (std::min(r, qr) - std::max(l, ql) + 1);
}

int res[kMaxN];

void upd(int l, int r, int k, int b, int v) {
  l = std::max<int>(l, 0), r = std::min<int>(r, 1e8);
  if (l > r || !k && !b) return;
  // std::cerr << l << ' ' << r << ' ' << k << ' ' << b << ' ' << v << '\n';
  update(rt, 0, 1e8, l, l, (k * l + b) * v);
  update(rt, 0, 1e8, l + 1, r, k * v);
  update(rt, 0, 1e8, r + 1, r + 1, -(k * r + b) * v);
  // for (int i = l; i <= r; ++i) res[i] += v * (k * i + b);
}

void work(int x, int pre, int nxt, int v) {
  assert(x > pre && x < nxt);
  std::vector<int> vec = {0, c[nxt] - c[x]};
  if (pre) vec.emplace_back(c[nxt] - c[pre]), vec.emplace_back(c[x] - c[pre]);
  else vec.emplace_back(1e8 + 1);
  std::sort(vec.begin(), vec.end());
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
  for (int i = 0; i + 1 < (int)vec.size(); ++i) {
    int l = vec[i], r = vec[i + 1] - 1, k = 0, b = 0;
    if (c[x] + l <= c[nxt] && c[x] + r <= c[nxt]) ++k, b += c[x];
    else b += c[nxt];
    if (c[x] >= c[pre] + l && c[x] >= c[pre] + r) b -= c[x];
    else --k, b -= c[pre];
    upd(l, r, k, b, v * ::b[x]);
  }
  // for (int u = 0; u <= 1e3; ++u) {
  //   if (std::max(c[i], c[pre] + u) < std::min(c[i] + u, c[nxt]))
  //     res[u] += v * b[i] * (std::min(c[i] + u, c[nxt]) - std::max(c[i], c[pre] + u));
  // }
}

void getans() {
  static int top, stk[kMaxN], nxt[kMaxN];
  stk[top = 1] = n + 1;
  c[0] = -1e9;
  for (int i = n; i; --i) {
    for (; top && b[stk[top]] >= b[i]; --top) {
      work(stk[top], 0, nxt[stk[top]], -1);
      work(stk[top], i, nxt[stk[top]], 1);
    }
    nxt[i] = stk[top];
    stk[++top] = i;
    work(i, 0, nxt[i], 1);
    for (auto [id, u, v] : qq[i]) ans[id] += v * query(rt, 0, 1e8, 0, u);
    // for (auto [id, u, v] : qq[i]) ans[id] += v * res[u];
  }
}

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    c[i + 1] = c[i] + a[i];
  }
  for (int i = 1; i <= n; ++i)
    std::cin >> b[i];
  prework();
  for (int i = 1; i <= m; ++i) {
    int s, t, u;
    std::cin >> s >> t >> u;
    if (querya(s, t - 1) > u) {
      ans[i] = -1;
      continue;
    }
    int p = std::max(s, std::upper_bound(c + 1, c + 2 + n, c[t] - u) - c), k = queryb(p, t);
    ans[i] = b[k] * (c[t] - c[k]);
    qq[s].emplace_back(i, u, 1), qq[k].emplace_back(i, u, -1);
  }
  getans();
  for (int i = 1; i <= m; ++i) std::cout << ans[i] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}