题解 「JOI 2021 Final」ダンジョン 3 / Dungeon 3

· · 题解

首先有显然的贪心：对于一个位置 i 找到他后面第一个价格小于它的位置 j，二者距离为 L，如果 L\le U，那就将能量填到 L，否则填满。

考虑 Subtask3 (T=N+1) 每次找后面小于它的位置可以联想到离线询问然后倒着扫用单调栈维护价格，每次退栈（当前的价格优于之前的价格）就考虑是否能在当前位置买能量，替代后面的，当前要购买的能量是已知的，考虑要删去多少：

设当前位置到栈顶的距离为 L，到栈顶下一个元素的距离为 L^\prime，如果 L^\prime\le U 删去全部 L^\prime-L，否则 L^\prime-U 是必须的，只能删去 L^\prime-L-(L^\prime-U)=U-L 于是即为 \min(L^\prime,U)-L。

最后栈顶还要加上 \min(L,U)。

考虑用数据结构维护所有 U 的值，我们发现我们要加的都是一条折线（一条斜线段在加上一条平行与 x 轴的线段），我们发现这是可以用树状数组简单维护的，具体来说，设 l 到 r 是斜线段，斜率为 k，截距为 b，平行段的 y 为 c，我们用一个树状数组维护斜率，另一个树状数组维护截距，用差分的思想给 l 斜率加上 k，r+1 斜率减去 k，l 截距加上 b，r+1 截距加上 (r+1-l)\times k。

然后考虑满分做法：设 f(S,T) 为 S 到 T 的答案，我们找到距离 T 小于等于 U 的最小价格处 m 发现只要经过 m 就一定会在 m 处买能量的，于是 f(S,T)=f(S,N+1)-f(m,N+1)+dis(m,T)\times b_m 不用担心在 m 之前买的能量没有用完的问题，这笔钱在 f(m,N+1) 被减去又在后面被加上，但 f(S,N+1) 中在 m 前买的能量是一直有贡献的，用 ST 表找一下 m 即可。

时间复杂度 \operatorname{O}(n\log n)。

const int N = 200005;

namespace BIT {
ll BIT1[N], BIT2[N];
void update(ll l, ll r, ll x);
ll query(int x);
}  // namespace BIT

int getid(ll x);
pii queryA(int l, int r);
pii queryB(int l, int r);

std::vector<std::tuple<int, int, int>> Q[N];
int all[N], tot;
int lg2[N];
pii stA[20][N], stB[20][N];
ll ans[N];
ll X[N];
int sta[N], top;
int A[N], B[N];
int n, m;

int main() {
  read(n), read(m);
  for (int i = 1; i <= n; ++i) {
    read(A[i]);
    X[i + 1] = X[i] + A[i];
  }
  for (int i = 1; i <= n; ++i) read(B[i]);
  lg2[1] = 0;
  for (int i = 2; i <= n; ++i) lg2[i] = lg2[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) {
    stA[0][i] = pii(A[i], i);
    stB[0][i] = pii(B[i], i);
  }
  for (int k = 1; k <= lg2[n]; ++k) {
    for (int i = 1; i <= n - (1 << k) + 1; ++i) {
      stA[k][i] = std::max(stA[k - 1][i], stA[k - 1][i + (1 << (k - 1))]);
      stB[k][i] = std::min(stB[k - 1][i], stB[k - 1][i + (1 << (k - 1))]);
    }
  }
  for (int i = 1; i <= m; ++i) {
    int s, t, u;
    read(s), read(t), read(u);
    if (queryA(s, t - 1).first > u) {
      ans[i] = -1;
      continue;
    }
    all[++tot] = u;
    int mid =
        queryB(std::max(s, static_cast<int>(std::lower_bound(X + 1, X + n + 2, X[t] - u) - X)),
               t - 1)
            .second;
    ans[i] = (X[t] - X[mid]) * B[mid];
    Q[s].emplace_back(i, 1, u);
    Q[mid].emplace_back(i, -1, u);
  }
  std::sort(all + 1, all + tot + 1);
  tot = std::unique(all + 1, all + tot + 1) - all - 1;
  sta[top = 1] = n + 1;
  for (int i = n; i >= 1; --i) {
    while (B[i] < B[sta[top]]) {
      BIT::update(X[sta[top]] - X[i] + 1, X[sta[top - 1]] - X[i], -B[sta[top]]);
      --top;
    }
    BIT::update(1, X[sta[top]] - X[i], B[i]);
    sta[++top] = i;
    for (const auto &[id, k, u] : Q[i]) ans[id] += k * BIT::query(u);
  }
  for (int i = 1; i <= m; ++i) {
    write(ans[i]), EL;
  }
  return 0;
}

pii queryA(int l, int r) {
  int k = lg2[r - l + 1];
  return std::max(stA[k][l], stA[k][r - (1 << k) + 1]);
}
pii queryB(int l, int r) {
  int k = lg2[r - l + 1];
  return std::min(stB[k][l], stB[k][r - (1 << k) + 1]);
}
int getid(ll x) { return std::lower_bound(all + 1, all + tot + 1, x) - all; }

namespace BIT {
void update(ll *A, int x, ll num) {
  while (x <= n) {
    A[x] += num;
    x += x & -x;
  }
}
ll query(ll *A, int x) {
  ll ans = 0;
  while (x) {
    ans += A[x];
    x -= x & -x;
  }
  return ans;
}
void update(ll l, ll r, ll x) {
  int idl = getid(l), idr = getid(r);
  update(BIT1, idl, x);
  update(BIT1, idr, -x);
  update(BIT2, idl, -(l - 1) * x);
  update(BIT2, idr, r * x);
}
ll query(int x) {
  int id = getid(x);
  return query(BIT1, id) * x + query(BIT2, id);
}
}  // namespace BIT