P8518 [IOI2021] 分糖果 题解

Description

Khong 阿姨正在给附近一所学校的学生准备 \(n\) 盒糖果。盒子的编号分别为 \(0\) 到 \(n - 1\)，开始时盒子都为空。第 \(i\) 个盒子 \((0 \leq i \leq n - 1)\) 至多可以容纳 \(c[i]\) 块糖果（容量为 \(c[i]\)）。

Khong 阿姨花了 \(q\) 天时间准备糖果盒。在第 \(j\) 天 \((0 \leq j \leq q - 1)\)，她根据三个整数 \(l[j]\)、 \(r[j]\) 和 \(v[j]\) 执行操作，其中 \(0 \leq l[j] \leq r[j] \leq n - 1\) 且 \(v[j] \neq 0\)。对于每个编号满足 \(l[j] \leq k \leq r[j]\) 的盒子 \(k\)：

• 如果 \(v[j] > 0\)，Khong 阿姨将糖果一块接一块地放入第 \(k\) 个盒子，直到她正好放了 \(v[j]\) 块糖果或者该盒子已满。也就是说，如果该盒子在这次操作之前已有 \(p\) 块糖果，那么在这次操作之后盒子将有 \(\min(c[k], p + v[j])\) 块糖果。

• 如果 \(v[j] < 0\)，Khong 阿姨将糖果一块接一块地从第 \(k\) 个盒子取出，直到她正好从盒子中取出 \(-v[j]\) 块糖果或者该盒子已空。也就是说，如果该盒子在这次操作之前已有 \(p\) 块糖果，那么在这次操作之后盒子将有 \(\max(0, p + v[j])\) 块糖果。

你的任务是求出 \(q\) 天之后每个盒子中糖果的数量。

约束条件

• \(1 \le n \le 200 000\)

• \(1 \le q \le 200 000\)

• \(1 \le c[i] \le 10 ^ 9\) （对所有 \(0 \le i \le n - 1\)）

• \(0 \le l[j] \le r[j] \le n - 1\)（对所有 \(0 \le j \le q - 1\)）

• \(−10 ^ 9 \le v[j] \le 10 ^ 9\) , \(v[j] ≠ 0\)（对所有 \(0 \le j \le q - 1\)）

Solution

不妨设 \(a_i\) 表示当前 \(i\) 的糖果数量，那么每次操作就是让 \(a_i\leftarrow\max\left(\min\left(a_i+v,c_i\right),0\right)\)，容易发现可以扫描线然后维护一个关于时间轴的线段树。

如果取 min 和 max 中只有一种是很好做的，就是这题，但是两个放在一起就不好做了。

容易发现只要找到最小的后缀 \([p,q]\) 使得这个后缀同时存在 min 和 max，那么 \([p+1,q]\) 就只有一种 min 或者 max 了，所以确定 \(p\) 时刻的值就可以通过 \([p+1,q]\) 的操作得出答案。

考虑如何找到 \(p\)。

观察可知如果 \([p,q]\) 前缀和的极差 \(\geq c_i\) 就一定同时存在 max 和 min，并且如果极差 \(<c_i\) 就一定不会同时存在 max 和 min，所以只要在线段树上二分即可。

时间复杂度：\(O\left((n+q)\log n\right)\)。

Code

#include "candies.h"

#include <bits/stdc++.h>

const int kMaxN = 2e5 + 5;

int n, q;
int c[kMaxN], l[kMaxN], r[kMaxN], v[kMaxN];
std::vector<std::pair<int, int>> vec[kMaxN];

struct SGT {
  int64_t mx[kMaxN * 4], mi[kMaxN * 4], posmx[kMaxN * 4], posmi[kMaxN * 4], tag[kMaxN * 4];

  void pushup(int x) {
    if (mx[x << 1] > mx[x << 1 | 1]) {
      mx[x] = mx[x << 1], posmx[x] = posmx[x << 1];
    } else {
      mx[x] = mx[x << 1 | 1], posmx[x] = posmx[x << 1];
    }
    if (mi[x << 1] < mi[x << 1 | 1]) {
      mi[x] = mi[x << 1], posmi[x] = posmi[x << 1];
    } else {
      mi[x] = mi[x << 1 | 1], posmi[x] = posmi[x << 1 | 1];
    }
  }

  void addtag(int x, int64_t v) { tag[x] += v, mx[x] += v, mi[x] += v; }

  void pushdown(int x) {
    if (tag[x]) {
      addtag(x << 1, tag[x]), addtag(x << 1 | 1, tag[x]);
      tag[x] = 0;
    }
  }

  void build(int x, int l, int r) {
    mx[x] = mi[x] = tag[x] = 0, posmx[x] = posmi[x] = r;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  }

  void update(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql) return;
    else if (l >= ql && r <= qr) return addtag(x, v);
    pushdown(x);
    int mid = (l + r) >> 1;
    update(x << 1, l, mid, ql, qr, v), update(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }

  int getpos(int x, int l, int r, int64_t nowmx, int64_t nowmi, int64_t v) {
    if (std::max(nowmx, mx[x]) - std::min(nowmi, mi[x]) < v || l == r) return l;
    pushdown(x);
    int mid = (l + r) >> 1;
    if (std::max(nowmx, mx[x << 1 | 1]) - std::min(nowmi, mi[x << 1 | 1]) >= v)
      return getpos(x << 1 | 1, mid + 1, r, nowmx, nowmi, v);
    else 
      return getpos(x << 1, l, mid, std::max(nowmx, mx[x << 1 | 1]), std::min(nowmi, mi[x << 1 | 1]), v);
  }

  std::pair<int64_t, int> querymin(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return {1e18, -1};
    else if (l >= ql && r <= qr) return {mi[x], posmi[x]};
    pushdown(x);
    int mid = (l + r) >> 1;
    return std::min(querymin(x << 1, l, mid, ql, qr), querymin(x << 1 | 1, mid + 1, r, ql, qr));
  }

  std::pair<int64_t, int> querymax(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return {-1e18, -1};
    else if (l >= ql && r <= qr) return {mx[x], posmx[x]};
    pushdown(x);
    int mid = (l + r) >> 1;
    return std::max(querymax(x << 1, l, mid, ql, qr), querymax(x << 1 | 1, mid + 1, r, ql, qr));
  }
} sgt;

std::vector<int> solve() {
  std::vector<int> ans;
  for (int i = 1; i <= q; ++i) {
    vec[l[i]].emplace_back(i, v[i]), vec[r[i] + 1].emplace_back(i, -v[i]);
  }
  sgt.build(1, 0, q);
  for (int i = 1; i <= n; ++i) {
    for (auto [x, v] : vec[i]) sgt.update(1, 0, q, x, q, v);
    int p = sgt.getpos(1, 0, q, -1e18, 1e18, c[i]);
    int64_t sump = sgt.querymin(1, 0, q, p, p).first;
    if (p && sump == sgt.querymin(1, 0, q, p, q).first) { // 后面只会顶上界
      auto [mx, id] = sgt.querymax(1, 0, q, p, q);
      if (mx - sump <= c[i]) ans.emplace_back(sgt.querymax(1, 0, q, q, q).first - sump);
      else ans.emplace_back(c[i] - (mx - sgt.querymax(1, 0, q, q, q).first));
    } else if (p) {
      auto [mi, id] = sgt.querymin(1, 0, q, p, q);
      if (sump - mi <= c[i]) ans.emplace_back(c[i] - (sump - sgt.querymin(1, 0, q, q, q).first));
      else ans.emplace_back(sgt.querymin(1, 0, q, q, q).first - mi);
    } else if (sgt.querymin(1, 0, q, 0, q).first >= 0) {
      auto [mx, id] = sgt.querymax(1, 0, q, p, q);
      if (mx <= c[i]) ans.emplace_back(sgt.querymax(1, 0, q, q, q).first);
      else ans.emplace_back(c[i] - (mx - sgt.querymax(1, 0, q, q, q).first));
    } else {
      auto [mi, id] = sgt.querymin(1, 0, q, p, q);
      if (mi >= 0) ans.emplace_back(sgt.querymin(1, 0, q, q, q).first);
      else ans.emplace_back(sgt.querymin(1, 0, q, q, q).first - mi);
    }
  }
  return ans;
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
  n = c.size(), q = l.size();
  for (int i = 0; i < n; ++i) ::c[i + 1] = c[i];
  for (int i = 0; i < q; ++i)
    ::l[i + 1] = l[i] + 1, ::r[i + 1] = r[i] + 1, ::v[i + 1] = v[i];
  return solve();
}