Submission #1207540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207540		abczz	Fish 2 (JOI22_fish2)	C++20	25 / 100	4103 ms	302088 KiB

fish2

#include <iostream>
#include <map>
#include <array>
#include <algorithm>
#include <cmath>
#define ll long long

using namespace std;

ll n, q, ty, x, y, A[100000], X[100000], ps[100000];
map <ll, ll> mp[30];
struct BIT{
  ll bt[100001];
  void add(ll id, ll w) {
    ++id;
    while (id <= n) {
      bt[id] += w;
      id += id & -id;
    }
  }
  ll ask(ll id) {
    ll res = 0;
    while (id) {
      res += bt[id];
      id -= id & -id;
    }
    return res;
  }
  ll query(ll l, ll r) {
    if (l > r) return (ll)1e18;
    return ask(r+1) - ask(l);
  }
}bit;
array<ll, 2> operator+(array<ll, 2> a, array<ll, 2> b) {
  return {a[0] + b[0], a[1] + b[1]};
}
struct SegTree{
  array<ll, 2> st[400000];
  void update(ll id, ll l, ll r, ll q, array<ll, 2> w) {
    if (l == r) {
      st[id] = w;
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q, w);
    else update(id*2+1, mid+1, r, q, w);
    st[id] = st[id*2] + st[id*2+1];
  }
  array<ll, 2> query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return {0, 0};
    else if (ql <= l && r <= qr) return st[id];
    ll mid = (l+r)/2;
    return query(id*2, l, mid, ql, qr) + query(id*2+1, mid+1, r, ql, qr);
  }
}ST[30];

ll check(ll j, ll u, ll xl, ll xr) {
  ll ql = u, qr = u, v = 1e18;
  auto it = mp[j].find(u);
  if (it != mp[j].begin()) {
    auto pv = prev(it);
    ql = pv->first+1;
    if (pv->first >= xl) v = min(v, A[pv->first]);
  }
  else ql = 0;
  auto nx = next(it);
  if (nx != mp[j].end()) {
    qr = nx->first-1;
    if (nx->first <= xr) v = min(v, A[nx->first]);
  }
  else qr = n-1;
  ql = max(ql, xl);
  qr = min(qr, xr);
  if (bit.query(ql, qr) < v && v != 1e18) return 1;
  else return 0;
}
void reconstruct(ll j, ll l, ll r) {
  ll ql = l, qr = r-1, v = A[r], tot = 0;
  if (j == X[l]-1) tot = check(j, l, (ll)-1e18, (ll)1e18);
  array <ll, 2> u = {0, 0};
  if (j) u = ST[j-1].query(1, 0, n-1, l, r-1);
  if (bit.query(l+1, r-1) < min(A[l], A[r])) {
    ST[j].update(1, 0, n-1, l, {r-l-1-u[1]+tot, r-l-1+tot});
  }
  else {
    ST[j].update(1, 0, n-1, l, {tot, u[1]+tot});
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n;
  for (int i=0; i<n; ++i) {
    cin >> A[i];
    bit.add(i, A[i]);
    ps[i] = A[i] + (i == 0 ? 0 : ps[i-1]);
    X[i] = (ll)(log2(A[i]));
    for (int j=0; j<X[i]; ++j) ++mp[j][i];
  }
  for (int j=0; j<30; ++j) {
    auto it = mp[j].begin();
    while (it != mp[j].end()) {
      auto nx = next(it);
      if (nx == mp[j].end()) break;
      reconstruct(j, it->first, nx->first);
      it = nx;
    }
  }
  cin >> q;
  while (q--) {
    cin >> ty >> x >> y;
    if (ty == 1) {
      --x;
      ll z1 = X[x], z2 = (ll)log2(y);
      bit.add(x, y-A[x]);
      A[x] = y, X[x] = z2;
      for (int j=0; j<30; ++j) {
        ST[j].update(1, 0, n-1, x, {0, 0});
        if (j >= z1 && j < z2) ++mp[j][x];
        if (j >= z2 && j < z1) mp[j].erase(x);
        auto it = mp[j].lower_bound(x);
        if (it != mp[j].end()) {
          if (it != mp[j].begin()) {
            auto pv = prev(it);
            reconstruct(j, pv->first, it->first);
          }
          if (it->first == x) {
            auto nx = next(it);
            if (nx != mp[j].end()) {
              reconstruct(j, it->first, nx->first);
              if (X[nx->first]-1 == j) {
                auto nx2 = next(nx);
                if (nx2 != mp[j].end()) reconstruct(j, nx->first, nx2->first);
              }
            }
          }
          else if (X[it->first]-1 == j) {
            auto nx2 = next(it);
            if (nx2 != mp[j].end()) reconstruct(j, it->first, nx2->first);
          }
        }
        else if (it != mp[j].begin()) {
          auto pv = prev(it);
          ST[j].update(1, 0, n-1, pv->first, {0, 0});
        }
      }
    }
    else {
      --x, --y;
      ll f = y-x+1, nx = x, ny = y;
      for (int j=0; j<30; ++j) {
        auto it = mp[j].lower_bound(x);
        if (it == mp[j].end() || it->first > y) continue;
        auto it2 = mp[j].lower_bound(y+1);
        if (it2 == mp[j].begin()) continue;
        it2 = prev(it2);
        //cout << j << " " << it->first << " " << it2->first << endl;
        if (bit.query(x, it->first-1) < A[it->first]) nx = it->first;
        if (bit.query(it2->first+1, y) < A[it2->first]) ny = it2->first;
      }
      f -= nx-x+y-ny;
      //cout << f << " " << nx << " " << ny << endl;
      for (int j=0; j<30; ++j) {
        auto it = mp[j].lower_bound(nx);
        if (it == mp[j].end() || it->first > ny) continue;
        auto it2 = mp[j].lower_bound(ny+1);
        if (it2 == mp[j].begin()) continue;
        it2 = prev(it2);
        //cout << j << " " << it->first << " " << it2->first << endl;
        if (it->first != it2->first) {
          auto u = ST[j].query(1, 0, n-1, it->first, it2->first-1);
          if (X[it->first]-1 == j) u[0] += check(j, it->first, x, y) - check(j, it->first, (ll)-1e18, (ll)1e18);
          f -= u[0];
        }
        if (X[it2->first]-1 == j) {
          f -= check(j, it2->first, x, y);
        }
      }
      cout << f << '\n';
    }
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17