P9530 [JOISC2022] 鱼 2 题解

Description

JOI 君有 $N$ 条鱼，编号为 $1,2,\dots,N$。第 $i$ $(1 \le i \le N)$ 条鱼的大小为 $A_i$。

当我们养鱼的时候，需要注意如下的一个事实：如果有两条鱼离得很近，那么随着时间的流逝，可能会有其中一条吃掉另一条。其中，两条鱼离得很近，当且仅当它们中间没有鱼。
更具体地，如果鱼 $x$ 的大小不小于鱼 $y$ 的大小，且鱼 $x,y$ 离得很近，那么 $x$ 可以吃掉 $y$，且 $x$ 的大小变为原来 $x,y$ 的大小之和。如果 $x,y$ 一样大，那么 $x$ 吃掉 $y$ 或 $y$ 吃掉 $x$ 都可能发生。

JOI 君会养 $Q$ 天鱼。为了消磨时光，他会进行如下的思想实验。在第 $j$ 天 $(1 \le j \le Q)$，JOI 君会进行如下行动中的一个：

• 第一类：JOI 君给鱼 $X_j$ 吃了某些秘制的食物。这会将鱼 $X_j$ 的大小变为 $Y_j$。

• 第二类：JOI 君将编号在区间 $[L_j,R_j]$ 内的鱼单独拿出来，并进行以下实验：
  JOI 君将鱼 $L_j,L_j+1,\dots,R_j$ 从左到右依次放在一个鱼缸中。由于鱼们具有如上所述的特点，最后只有一条鱼会存活。存活的这条鱼的编号取决于在哪些时刻哪些鱼吃掉了哪些鱼。JOI 君想知道可能成为最后存活者的鱼的条数。在实验中，鱼的编号不会改变，也不能有两条鱼同时吃掉同一条鱼。

请写一个程序，对于给定的 JOI 君的鱼和实验的信息，计算每个第二类行动的答案来让 JOI 君能够证明或证伪自己的观点。注意这只是思想实验，并没有任何鱼真的被吃掉。

【数据范围】

对于所有数据，满足：

• $1 \le N,Q \le 100\,000$。
• $1 \le A_i \le 10^9$ $(1\le i\le N)$。
• $T_j \in \{1,2\}$。
• $1 \le X_j \le N$ $(1\le j\le Q)$。
• $1 \le Y_j \le 10^9$。
• $1 \le L_j \le R_j \le N$ $(1 \le j \le Q)$。

Solution

先假设询问区间为 $[1,n]$。

首先直接判断一条鱼 $x$ 是否有解是不好做的，考虑判断是否无解。

容易发现如果存在一个区间 $[l,r]$，满足 $l<x<r$ 并且 $sum_{l+1,r-1}<\min\{a_l,a_r\}$ 就说明 $x$ 一定无法突破 $[l,r]$ 的限制，也就是无解。并且如果 $x$ 不被任何一个这样的 $[l,r]$ 包含就一定有解。

直接枚举每个 $[l,r]$ 显然无法接受，但有个结论是总共最多 $O(n\log V)$ 个这样的区间。证明就考虑假设存在两个区间 $[l,r_1]$ 和 $[l,r_2]$ 满足性质，那么 $sum_{l+1,r_2}>2\cdot sum_{l+1,r_2-1}>2\cdot sum_{l+1,r_1}$，所以对于每个 $l$ 只存在 $O(\log V)$ 个符合条件的 $r$，总个数也就是 $O(n\log V)$。同样可以证明包含任意一点的线段数也是 $O(\log V)$ 的，这里就不证了。

快速找到这些线段可以使用线段树二分。询问时相当于问有多少个点没有被线段覆盖，同样用线段树维护即可。

对于修改 $(x,y)$ 就暴力删去与 $x$ 有关的线段，修改后再加入。

---

然后考虑询问为任意区间的情况。

不妨设询问为 $[L,R]$，那么对于全局的一个线段 $[l,r]$ 满足 $L\leq l\leq r\leq R$ 或者 $l\leq L\leq r\leq R$ 或 $L\leq l\leq R\leq r$ 的话这个线段一定能造成贡献，而如果 $[l,r]$ 完全包含 $[L,R]$ 就说明 $[l,r]$ 不能造成贡献，找到这些线段再去掉即可。

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

Code

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 1e5 + 5;

int n, q;
int a[kMaxN];
std::set<std::pair<int, int>> st;
std::vector<int> vl[kMaxN], vr[kMaxN];

struct BIT {
  int c[kMaxN];

  void upd(int x, int v) {
    for (; x <= n; x += x & -x) c[x] += v;
  }

  int qry(int x) {
    int ret = 0;
    for (; x; x -= x & -x) ret += c[x];
    return ret;
  }
} bit;

struct SGT1 {
  int mx1[kMaxN * 4], tag1[kMaxN * 4];
  int mx2[kMaxN * 4], tag2[kMaxN * 4];

  void pushup(int x) {
    mx1[x] = std::max(mx1[x << 1], mx1[x << 1 | 1]);
    mx2[x] = std::max(mx2[x << 1], mx2[x << 1 | 1]);
  }

  void addtag(int x, int v1, int v2) {
    mx1[x] += v1, tag1[x] += v1;
    mx2[x] += v2, tag2[x] += v2;
  }

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

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

  int getpos1(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql || mx1[x] <= v || ql > qr) return 0;
    else if (l >= ql && r <= qr) {
      if (l != r) pushdown(x);
      int mid = (l + r) >> 1;
      if (l == r) return l;
      else return mx1[x << 1 | 1] > v ? getpos1(x << 1 | 1, mid + 1, r, ql, qr, v) : getpos1(x << 1, l, mid, ql, qr, v);
    }
    pushdown(x);
    int mid = (l + r) >> 1, R = getpos1(x << 1 | 1, mid + 1, r, ql, qr, v);
    if (R) return R;
    else return getpos1(x << 1, l, mid, ql, qr, v);
  }

  int getpos2(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql || mx2[x] <= v || ql > qr) return 0;
    else if (l >= ql && r <= qr) {
      if (l != r) pushdown(x);
      int mid = (l + r) >> 1;
      if (l == r) return l;
      else return mx2[x << 1] > v ? getpos2(x << 1, l, mid, ql, qr, v) : getpos2(x << 1 | 1, mid + 1, r, ql, qr, v);
    }
    pushdown(x);
    int mid = (l + r) >> 1, L = getpos2(x << 1, l, mid, ql, qr, v);
    if (L) return L;
    else return getpos2(x << 1 | 1, mid + 1, r, ql, qr, v);
  }
} sgt1;

struct SGT2 {
  int mi[kMaxN * 4], cnt[kMaxN * 4], tag[kMaxN * 4];

  void pushup(int x) {
    mi[x] = std::min(mi[x << 1], mi[x << 1 | 1]);
    cnt[x] = 0;
    if (mi[x << 1] == mi[x]) cnt[x] += cnt[x << 1];
    if (mi[x << 1 | 1] == mi[x]) cnt[x] += cnt[x << 1 | 1];
  }

  void addtag(int x, int v) {
    mi[x] += v, tag[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) {
    cnt[x] = r - l + 1;
    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);
  }

  std::pair<int, int> query(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return {1e9, 0};
    else if (l >= ql && r <= qr) return {mi[x], cnt[x]};
    pushdown(x);
    int mid = (l + r) >> 1;
    auto L = query(x << 1, l, mid, ql, qr), R = query(x << 1 | 1, mid + 1, r, ql, qr);
    if (L.first == R.first) return {L.first, L.second + R.second};
    else return std::min(L, R);
  }
} sgt2;

void ins(int l, int r) {
  if (r - l + 1 != 1 && !st.count({l, r})) {
    sgt2.update(1, 1, n, l + 1, r - 1, 1);
    st.emplace(l, r);
  }
}

void del(int l, int r) {
  if (r - l + 1 == 1 || !st.count({l, r})) return;
  sgt2.update(1, 1, n, l + 1, r - 1, -1);
  st.erase({l, r});
}

std::vector<std::pair<int, int>> getseg(int x) {
  std::vector<std::pair<int, int>> vl, vr, seg;
  int s1 = bit.qry(x), s2 = -bit.qry(x - 1);
  for (int p = sgt1.getpos1(1, 1, n, 1, x - 1, s1); p; p = sgt1.getpos1(1, 1, n, 1, p - 1, s1)) {
    vl.emplace_back(p, s1 - bit.qry(p));
  }
  for (int p = sgt1.getpos2(1, 1, n, x + 1, n, s2); p; p = sgt1.getpos2(1, 1, n, p + 1, n, s2)) {
    vr.emplace_back(p, bit.qry(p - 1) - s1);
  }
  for (auto [p1, s1] : vl) {
    for (auto [p2, s2] : vr) {
      if (a[p1] > s1 + s2 && a[p2] > s1 + s2) {
        seg.emplace_back(p1, p2);
      }
    }
  }
  return seg;
}

std::vector<std::pair<int, int>> getsegs(int x) {
  std::vector<std::pair<int, int>> seg;
  for (auto [l, r] : st)
    if (l < x && x < r)
      seg.emplace_back(l, r);
  return seg;
}

std::vector<std::pair<int, int>> getsegl(int x) {
  std::vector<std::pair<int, int>> vec;
  int s = -bit.qry(x);
  for (int p = sgt1.getpos2(1, 1, n, x + 1, n, s); p; p = sgt1.getpos2(1, 1, n, p + 1, n, s)) {
    int sum = bit.qry(p - 1) + s;
    if (sum < a[x] && sum < a[p]) vec.emplace_back(x, p);
  }
  return vec;
}

std::vector<std::pair<int, int>> getsegr(int x) {
  std::vector<std::pair<int, int>> vec;
  int s = bit.qry(x - 1);
  for (int p = sgt1.getpos1(1, 1, n, 1, x - 1, s); p; p = sgt1.getpos1(1, 1, n, 1, p - 1, s)) {
    int sum = s - bit.qry(p);
    if (sum < a[x] && sum < a[p]) vec.emplace_back(p, x);
  }
  return vec;
}

void prework() {
  for (int i = 1; i <= n; ++i) {
    sgt1.update(1, 1, n, i, i, a[i], a[i]);
    sgt1.update(1, 1, n, i, n, a[i], 0);
    sgt1.update(1, 1, n, i + 1, n, 0, -a[i]);
    bit.upd(i, a[i]);
  }
  sgt2.build(1, 1, n);
  for (int i = 2; i < n; ++i) {
    auto vec = getseg(i);
    for (auto [l, r] : vec) ins(l, r);
  }
}

void update(int x, int y) {
  auto segs = getseg(x);
  for (auto [l, r] : segs) del(l, r);
  if (x < n - 1) {
    auto seg = getsegl(x);
    for (auto [l, r] : seg) del(l, r);
  }  
  if (x > 2) {
    auto seg = getsegr(x);
    for (auto [l, r] : seg) del(l, r);
  }

  bit.upd(x, y - a[x]);
  sgt1.update(1, 1, n, x, x, y - a[x], y - a[x]);
  sgt1.update(1, 1, n, x, n, y - a[x], 0);
  sgt1.update(1, 1, n, x + 1, n, 0, -(y - a[x]));
  a[x] = y;

  auto seg1 = getseg(x);
  for (auto [l, r] : seg1) ins(l, r);
  if (x < n - 1) {
    auto seg = getsegl(x);
    for (auto [l, r] : seg) ins(l, r);
  }
  if (x > 2) {
    auto seg = getsegr(x);
    for (auto [l, r] : seg) ins(l, r);
  }
}

int query(int l, int r) {
  std::vector<std::pair<int, int>> vec, tmp;
  auto segs = getseg(l);
  for (auto [ll, rr] : segs)
    if (rr > r)
      vec.emplace_back(ll, rr);
  for (auto [l, r] : vec) sgt2.update(1, 1, n, l + 1, r - 1, -1);

  int s1 = bit.qry(r), s2 = -bit.qry(l - 1);
  
  for (int p = sgt1.getpos1(1, 1, n, l, r - 1, s1); p; p = sgt1.getpos1(1, 1, n, l, p - 1, s1)) {
    tmp.emplace_back(p, r + 1);
    sgt2.update(1, 1, n, p + 1, r, 1);
  }

  for (int p = sgt1.getpos2(1, 1, n, l + 1, r, s2); p; p = sgt1.getpos2(1, 1, n, p + 1, r, s2)) {
    tmp.emplace_back(l - 1, p);
    sgt2.update(1, 1, n, l, p - 1, 1);
  }

  auto p = sgt2.query(1, 1, n, l, r);
  for (auto [l, r] : vec) sgt2.update(1, 1, n, l + 1, r - 1, 1);
  for (auto [l, r] : tmp) sgt2.update(1, 1, n, l + 1, r - 1, -1);
  if (!p.first) return p.second;
  else return 0;
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  prework();
  std::cin >> q;
  for (int i = 1; i <= q; ++i) {
    int op, l, r;
    std::cin >> op >> l >> r;
    if (op == 1) update(l, r);
    else std::cout << query(l, r) << '\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;
}