Submission #1207646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207646		abczz	Fish 2 (JOI22_fish2)	C++20	100 / 100	3913 ms	199144 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];
ll listnx[100000][30], listpv[100000][30];
vector <ll> V[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];
struct MapSegTree{
  ll st[400000];
  void build(ll id, ll l, ll r) {
    if (l == r) {
      st[id] = A[l];
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[id] = max(st[id*2], st[id*2+1]);
  }
  void update(ll id, ll l, ll r, ll q, ll 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] = max(st[id*2], st[id*2+1]);
  }
  ll queryL(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql || st[id] < w) return -1;
    else if (ql <= l && r <= qr) {
      if (l == r) return l;
      ll mid = (l+r)/2;
      if (st[id*2] >= w) return queryL(id*2, l, mid, ql, qr, w);
      else return queryL(id*2+1, mid+1, r, ql, qr, w);
    }
    ll mid = (l+r)/2, res = queryL(id*2, l, mid, ql, qr, w);
    return (res == -1 ? queryL(id*2+1, mid+1, r, ql, qr, w) : res);
  }
  ll queryR(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql || st[id] < w) return -1;
    else if (ql <= l && r <= qr) {
      if (l == r) return l;
      ll mid = (l+r)/2;
      if (st[id*2+1] >= w) return queryR(id*2+1, mid+1, r, ql, qr, w);
      else return queryR(id*2, l, mid, ql, qr, w);
    }
    ll mid = (l+r)/2, res = queryR(id*2+1, mid+1, r, ql, qr, w);
    return (res == -1 ? queryR(id*2, l, mid, ql, qr, w) : res);
  }
}ST2;

ll check(ll j, ll u, ll xl, ll xr) {
  ll ql = u, qr = u, v = 1e18;
  if (listpv[u][j] != -1) {
    ll pv = listpv[u][j];
    ql = pv+1;
    if (pv >= xl) v = min(v, A[pv]);
  }
  else ql = 0;
  ll nx = listnx[u][j];
  if (nx != -1) {
    qr = nx-1;
    if (nx <= xr) v = min(v, A[nx]);
  }
  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) V[j].push_back(i);
    for (int j=0; j<30; ++j) listnx[i][j] = listpv[i][j] = -1;
  }
  for (int j=0; j<30; ++j) {
    for (int i=0; i+1<V[j].size(); ++i) {
      listnx[V[j][i]][j] = V[j][i+1];
      listpv[V[j][i+1]][j] = V[j][i];
      reconstruct(j, V[j][i], V[j][i+1]);
    }
  }
  ST2.build(1, 0, n-1);
  cin >> q;
  while (q--) {
    cin >> ty >> x >> y;
    if (ty == 1) {
      --x;
      ll z1 = X[x], z2 = (ll)log2(y);
      ST2.update(1, 0, n-1, x, 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});
        ll it = ST2.queryL(1, 0, n-1, x, n-1, (1<<(j+1)));
        listnx[x][j] = listpv[x][j] = -1;
        if (it != -1) {
          ll pv = ST2.queryR(1, 0, n-1, 0, it-1, (1<<(j+1)));
          if (pv != -1) {
            listnx[pv][j] = it;
            listpv[it][j] = pv;
            reconstruct(j, pv, it);
          }
          else listpv[it][j] = -1;
          if (it == x) {
            ll nx = ST2.queryL(1, 0, n-1, it+1, n-1, (1<<(j+1)));
            if (nx != -1) {
              listnx[it][j] = nx;
              listpv[nx][j] = it;
              reconstruct(j, it, nx);
              if (X[nx]-1 == j) {
                ll nx2 = ST2.queryL(1, 0, n-1, nx+1, n-1, (1<<(j+1)));
                if (nx2 != -1) reconstruct(j, nx, nx2);
              }
            }
            else listnx[it][j] = -1;
          }
          else if (X[it]-1 == j) {
            ll nx2 = ST2.queryL(1, 0, n-1, it+1, n-1, (1<<(j+1)));
            if (nx2 != -1) reconstruct(j, it, nx2);
          }
        }
        else {
          ll pv = ST2.queryR(1, 0, n-1, 0, x-1, (1<<(j+1)));
          if (pv != -1) {
            listnx[pv][j] = -1;
            ST[j].update(1, 0, n-1, pv, {0, 0});
          }
        }
      }
    }
    else {
      --x, --y;
      ll f = y-x+1, nx = x, ny = y;
      for (int j=0; j<30; ++j) {
        ll it = ST2.queryL(1, 0, n-1, x, n-1, (1LL<<(j+1)));
        if (it == -1 || it > y) continue;
        ll it2 = ST2.queryR(1, 0, n-1, 0, y, (1LL<<(j+1)));
        if (bit.query(x, it-1) < A[it]) nx = it;
        if (bit.query(it2+1, y) < A[it2]) ny = it2;
      }
      f -= nx-x+y-ny;
      for (int j=0; j<30; ++j) {
        ll it = ST2.queryL(1, 0, n-1, nx, n-1, (1<<(j+1)));
        if (it == -1 || it > ny) continue;
        ll it2 = ST2.queryR(1, 0, n-1, 0, ny, (1<<(j+1)));
        if (it != it2) {
          auto u = ST[j].query(1, 0, n-1, it, it2-1);
          if (X[it]-1 == j) u[0] += check(j, it, x, y) - check(j, it, (ll)-1e18, (ll)1e18);
          f -= u[0];
        }
        if (X[it2]-1 == j) {
          f -= check(j, it2, x, y);
        }
      }
      cout << f << '\n';
    }
  }
}

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