UOJ #712. 【北大集训2021】简单数据结构

Description

你有一个长度为 $n$ 的序列 $a$，下面你要进行 $q$ 次修改或询问。

1. 给定 $v$，将所有 $a_i$ 变为 $\min(a_i, v)$。
2. 将所有 $a_i$ 变为 $a_i + i$。
3. 给定 $l, r$，询问 $\sum_{i=l}^r a_i$。

$1\leq n,q\leq 2\times 10^5,0\leq a_i,v_i\leq 10^{12}$。

Solution

首先如果没有 chkmin 操作是好做的。同时如果 $a_i$ 初始值为 $0$ 那么从始至终序列 $a$ 都是单调不降的，对于 chkmin 操作只要二分+区间赋值，也很好做。

考虑 $a_i$ 初值不为 $0$ 的情况。

注意到如果某个时刻 $x<y$ 且 $a_x\leq a_y$，那么之后的所有时刻都满足 $a_x\leq a_y$，这是显然的。

然后就可以发现对于所有 chkmin 过的位置，它们的 $a$ 值一定单调不降。于是只要维护当前 chkmin 过的位置，对于这些二分+区间赋值。没有 chkmin 的位置直接线段树维护即可。

考虑怎么求出每个 $a_i$ 第一次被 chkmin 的时间。设 $v_i$ 表示第 $i$ 次操作 chkmin 的值，$c_i$ 表示前 $i$ 次操作做了多少次二操作。

容易发现对于每个 $i$，可以二分答案 $p$，那么对于 $[1,p]$ 里的所有操作，如果存在 $a_i+i\cdot c_j\geq v_j$ 就说明 $p$ 可行。移项一下可以得到 $a_i\geq v_j-i\cdot c_j$，右边是个关于 $i$ 的一次函数，所以可以对于前 $p$ 个操作按照 $(c_j,v_j)$ 维护下凸壳，然后用 $k=i$ 的直线去截这个凸壳即可快速得到答案。

但是这么做是 $O\left(nq\log^2 n\right)$ 的，可以用整体二分优化到 $O\left(q\log^2 n\right)$。

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

Code

#include <bits/stdc++.h>

#define int int64_t

using pii = std::pair<int, int>;

const int kMaxN = 2e5 + 5;

int n, q;
int a[kMaxN], op[kMaxN], l[kMaxN], r[kMaxN], v[kMaxN];
std::vector<int> vv[kMaxN];
std::vector<std::tuple<int, int, int>> chkm;

pii add(pii a, pii b) { return {a.first + b.first, a.second + b.second}; }
pii sub(pii a, pii b) { return {a.first - b.first, a.second - b.second}; }
int64_t mul(pii a, pii b) {
  return 1ll * a.first * b.second - 1ll * a.second * b.first;
}

int64_t func(int k, pii a) { return -1ll * k * a.first + a.second; }

void solve(std::vector<std::tuple<int, int, int>> vec, std::vector<int> id) {
  if (!vec.size()) return;
  if (vec.size() == 1) {
    auto [j, c, v] = vec[0];
    for (auto i : id) {
      if (a[i] >= v - i * c) {
        vv[j].emplace_back(i);
      }
    }
    return;
  }
  std::vector<pii> pt, stk;
  std::vector<int> Lv, Rv;
  std::vector<std::tuple<int, int, int>> lvec, rvec;
  for (int i = 0; i < vec.size() / 2; ++i) {
    lvec.emplace_back(vec[i]);
    pt.emplace_back(std::get<1>(vec[i]), std::get<2>(vec[i]));
  }
  for (int i = vec.size() / 2; i < vec.size(); ++i) rvec.emplace_back(vec[i]);
  std::sort(pt.begin(), pt.end());
  for (auto p : pt) {
    for (; stk.size() >= 2 &&
           mul(sub(p, stk.back()), sub(stk.back(), stk[stk.size() - 2])) >= 0;
         stk.pop_back()) {
    }
    stk.emplace_back(p);
  }
  for (auto i : id) {
    int L = 0, R = stk.size(), res = 0;
    while (L + 1 < R) {
      int mid = (L + R) >> 1;
      if (func(i, stk[mid]) <= func(i, stk[mid - 1]))
        L = res = mid;
      else
        R = mid;
    }
    if (func(i, stk[res]) <= a[i])
      Lv.emplace_back(i);
    else
      Rv.emplace_back(i);
  }
  solve(lvec, Lv), solve(rvec, Rv);
}

void prework() {
  std::vector<int> id(n);
  std::iota(id.begin(), id.end(), 1);
  solve(chkm, id);
}

struct SGT {
  int cnt[kMaxN * 4];
  int64_t mx[kMaxN * 4], mxid[kMaxN * 4], sum[kMaxN * 4], sumid[kMaxN * 4],
      tag[kMaxN * 4], tagcov[kMaxN * 4];

  void pushup(int x) {
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    sumid[x] = sumid[x << 1] + sumid[x << 1 | 1];
    mx[x] = std::max(mx[x << 1], mx[x << 1 | 1]);
    mxid[x] = std::max(mxid[x << 1], mxid[x << 1 | 1]);
    cnt[x] = cnt[x << 1] + cnt[x << 1 | 1];
  }

  void addtag1(int x, int64_t v) {
    if (!cnt[x]) return;
    sum[x] += sumid[x] * v, tag[x] += v;
    mx[x] += mxid[x] * v;
  }

  void addtag2(int x, int64_t v) {
    if (!cnt[x]) return;
    sum[x] = cnt[x] * v, mx[x] = tagcov[x] = v;
    tag[x] = 0;
  }

  void pushdown(int x) {
    if (~tagcov[x]) {
      addtag2(x << 1, tagcov[x]), addtag2(x << 1 | 1, tagcov[x]);
      tagcov[x] = -1;
    }
    if (tag[x]) {
      addtag1(x << 1, tag[x]), addtag1(x << 1 | 1, tag[x]);
      tag[x] = 0;
    }
  }

  void build(int x, int l, int r, bool op = 1) {
    tagcov[x] = -1;
    if (l == r) {
      if (op) {
        cnt[x] = 1, sumid[x] = mxid[x] = l;
        sum[x] = a[l];
      } else {
        mxid[x] = mx[x] = -1;
      }
      return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid, op), build(x << 1 | 1, mid + 1, r, op);
    pushup(x);
  }

  void update1(int x, int l, int r, int ql, int v, bool op = 1) {
    if (l == r) {
      if (op) {
        tag[x] = 0, tagcov[x] = -1, cnt[x] = 1, sumid[x] = mxid[x] = l;
        addtag2(x, v);
      } else {
        cnt[x] = sum[x] = sumid[x] = mxid[x] = tag[x] = 0;
        tagcov[x] = mx[x] = -1;
      }
      return;
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    if (ql <= mid)
      update1(x << 1, l, mid, ql, v, op);
    else
      update1(x << 1 | 1, mid + 1, r, ql, v, op);
    pushup(x);
  }

  void update2(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 addtag2(x, v);
    pushdown(x);
    int mid = (l + r) >> 1;
    update2(x << 1, l, mid, ql, qr, v),
        update2(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }

  int getpos(int x, int l, int r, int v) {
    if (mx[x] < v) return 0;
    if (l == r) return l;
    pushdown(x);
    int mid = (l + r) >> 1;
    if (mx[x << 1] >= v)
      return getpos(x << 1, l, mid, v);
    else
      return getpos(x << 1 | 1, mid + 1, r, v);
  }

  int64_t query(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql)
      return 0;
    else if (l >= ql && r <= qr)
      return sum[x];
    pushdown(x);
    int mid = (l + r) >> 1;
    return query(x << 1, l, mid, ql, qr) +
           query(x << 1 | 1, mid + 1, r, ql, qr);
  }

  void print(int x, int l, int r) {
    if (l == r) return void(std::cerr << sum[x] << ' ');
    pushdown(x);
    int mid = (l + r) >> 1;
    print(x << 1, l, mid), print(x << 1 | 1, mid + 1, r);
  }
  void print() {
    print(1, 1, n);
    std::cerr << '\n';
  }
} sgt[2];

void dickdreamer() {
  std::cin >> n >> q;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  int nowcnt = 0;
  for (int i = 1; i <= q; ++i) {
    std::cin >> op[i];
    if (op[i] == 1) {
      std::cin >> v[i];
      chkm.emplace_back(i, nowcnt, v[i]);
    } else if (op[i] == 2) {
      ++nowcnt;
    } else {
      std::cin >> l[i] >> r[i];
    }
  }
  prework();
  sgt[0].build(1, 1, n, 0), sgt[1].build(1, 1, n, 1);
  for (int i = 1; i <= q; ++i) {
    if (op[i] == 1) {
      for (auto x : vv[i]) {
        sgt[0].update1(1, 1, n, x, v[i]);
        sgt[1].update1(1, 1, n, x, 0, 0);
      }
      int p = sgt[0].getpos(1, 1, n, v[i]);
      if (p) sgt[0].update2(1, 1, n, p, n, v[i]);
    } else if (op[i] == 2) {
      sgt[0].addtag1(1, 1), sgt[1].addtag1(1, 1);
    } else {
      std::cout << sgt[0].query(1, 1, n, l[i], r[i]) +
                       sgt[1].query(1, 1, n, l[i], r[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;
}