P9530 [JOISC2022] 鱼 2

· · 题解

*P9530 [JOISC2022] 鱼 2

考虑如何判定一条鱼能够活到最后。从它的位置开始，向左向右找到第一条大于它当前重量的鱼。将这两条鱼之间的所有鱼吃掉，不断重复该过程直到它两侧的鱼的重量都大于它。寻找前驱和后继的过程可以通过线段树上二分维护，而每次寻找大于当前重量的鱼的前驱后继时，由于最终一定会吃掉一个前驱或后继（否则无法继续扩展），于是鱼的重量翻倍。因此整个过程的复杂度是 \mathcal{O}(\log n \log A)。

容易想到用下标区间 [l, r] 记录一条鱼，表示它能吃掉下标区间内的所有鱼，并且被 l - 1 和 r + 1 挡住了。那么，根据上述分析，对于序列的每个位置 i，包含 i 的本质不同的区间数量只有 \mathcal{O}(\log A) 次：较大区间的重量一定大于较小区间重量的两倍。

考虑对一段区间求出区间内每条鱼在当前区间范围内的下标区间 [L, R]，如果某条鱼的下标区间无法到达区间 [l, r] 的左端点和右端点（l < L \leq R < r），那么它无论如何也无法吃掉更大的区间：影响它扩张的前驱 L - 1 和后继 R + 1 在该区间内已经出现了，于是在更大的区间也会影响它扩张。

结合 “包含某点的不同区间数量很少” 以及 “只有包含左端点或右端点的区间有用”，可知只需用 \mathcal{O}(\log A) 个区间 [L, R]（还需维护有多少个下标 C 可以恰好扩张到该区间）就可以描述一段区间的信息。结合带修的要求，用线段树维护。于是只需考虑两个相邻结点 [l, M] 和 [M + 1, r] 的信息的合并。

将区间根据是否可达左右端点分为三类（两者都不可达的区间无用）。左侧可达左端点但不可达右端点的区间依然可达左端点且不可达右端点，右侧同理。

考虑左侧可达右端点 M（不用不可达左端点 l）的区间 [L_i, M] 的贡献，将它们按照包含关系从小到大排序。

为了避免 ”求出最小的满足 …… 的区间“ 的二分，可以用双指针 pl, pr 维护，表示从左侧对应区间 [L_{pl}, M] 开始，可以将右边界扩展到右侧对应区间 R_{pr}，同时记录有多少个下标可以扩张到当前区间。从左侧最小的区间开始：

可以在双指针的过程中求出可达整体右端点 r 的贡献，在双指针结束后求出对可达整体左端点 l 但不可达右端点 r 的贡献。

对右侧可达左端点 M + 1（不用不可达右端点 r）的区间的贡献，同理。

每个 [L, R] 需要维护区间和，对应下标数，以及两侧限制它扩张的鱼的重量（实际上只要一侧：可达左端点的维护右侧；可达右端点的维护左侧；可达左右端点的不用维护，只需在结点处额外维护左右端点的重量）。

时间复杂度 \mathcal{O}((n + q\log n)\log A)。

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 1e5 + 5;
constexpr int inf = 1e9 + 7;

int n, q, a[N];
struct info {int sum, cnt, out;};
struct dat {
  int l, r, sum, cnt;
  vector<info> L, R;
  dat operator + (const dat &z) const {
    dat x = {l, z.r, min(inf, sum + z.sum), 0, L, z.R};

    vector<info> fl = R, fr = z.L;
    fl.push_back({sum, cnt, 0});
    fr.push_back({z.sum, z.cnt, 0});

    vector<info> apl, apr;
    int sum, bound;

    // left
    int pl = 0, pr = -1, tot = fl[0].cnt;
    while(1) {
      sum = min(inf, fl[pl].sum + (pr == -1 ? 0 : fr[pr].sum));
      bound = (pr == -1 ? z.l : fr[pr].out);
      if(sum >= bound && pr + 1 < fr.size()) pr++;
      else if(pl == fl.size() - 1) break;
      else {
        if(sum < fl[pl].out) {
          if(pr == fr.size() - 1) apr.push_back({sum, tot, fl[pl].out});
          tot = 0;
        }
        tot += fl[++pl].cnt;
      }
    }
    if(pr == fr.size() - 1) x.cnt += tot;
    else x.L.push_back({sum, tot, bound});

    swap(fl, fr);

    // right
    pl = 0, pr = -1, tot = fl[0].cnt;
    while(1) {
      sum = min(inf, fl[pl].sum + (pr == -1 ? 0 : fr[pr].sum));
      bound = (pr == -1 ? r : fr[pr].out);
      if(sum >= bound && pr + 1 < fr.size()) pr++;
      else if(pl == fl.size() - 1) break;
      else {
        if(sum < fl[pl].out) {
          if(pr == fr.size() - 1) apl.push_back({sum, tot, fl[pl].out});
          tot = 0;
        }
        tot += fl[++pl].cnt;
      }
    }
    if(pr == fr.size() - 1) x.cnt += tot;
    else x.R.push_back({sum, tot, bound});

    for(info it : apl) x.L.push_back(it);
    for(info it : apr) x.R.push_back(it);

    return x;
  }
} val[N << 2];
void build(int l, int r, int x) {
  if(l == r) return val[x] = {a[l], a[l], a[l], 1}, void();
  int m = l + r >> 1;
  build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
  val[x] = val[x << 1] + val[x << 1 | 1];
}
void modify(int l, int r, int x, int p) {
  if(l == r) return val[x] = {a[l], a[l], a[l], 1}, void();
  int m = l + r >> 1;
  if(p <= m) modify(l, m, x << 1, p);
  else modify(m + 1, r, x << 1 | 1, p);
  val[x] = val[x << 1] + val[x << 1 | 1];
}
dat query(int l, int r, int ql, int qr, int x) {
  if(ql <= l && r <= qr) return val[x];
  int m = l + r >> 1;
  if(qr <= m) return query(l, m, ql, qr, x << 1);
  if(m < ql) return query(m + 1, r, ql, qr, x << 1 | 1); 
  return query(l, m, ql, qr, x << 1) + query(m + 1, r, ql, qr, x << 1 | 1);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  build(1, n, 1);
  cin >> q;
  for(int i = 1; i <= q; i++) {
    int op;
    cin >> op;
    if(op == 1) {
      int x, y;
      cin >> x >> y, a[x] = y;
      modify(1, n, 1, x);
    }
    else {
      int l, r;
      cin >> l >> r;
      dat res = query(1, n, l, r, 1);
      cout << res.cnt << "\n";
    }
  }
  return 0;
}