ACLを使ってセグ木を学び始めた

セグ木、構造とか何をやるものとかは知ってたけど、コードを書けていたわけではなかったので、コンテストではほとんど使ってませんでした。で、ここ数日で、AtCoder Library(ACL) を使って、セグ木と格闘してました。

AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA

この記事が素晴らしいので、ほとんどこれで理解を進めていってる感じ。

いろいろ過去問とかをセグ木や遅延セグ木を使って解きなおしたりしてるんだけど、少しずつわかってきた。ただ、変なのはまだよくわかってないけど。

例えば、PAST第1回の H - まとめ売りをやってみた。受験したときは次のようなコードを書いてた。

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll N; cin >> N;
  ll c1 = N; c1++; c1 /= 2ll;
  vector<ll> C(N, 0);
  ll m0 = 1e10, m1 = 1e10;

  for (int i = 0; i < N; i++) {
    cin >> C[i];
    m0 = min(m0, C[i]);
    if (i % 2 == 0) m1 = min(m1, C[i]);
  }

  int Q; cin >> Q;
  ll ans = 0, t0 = 0, t1 = 0;
  for (int i = 0; i < Q; i++) {
    int q; cin >> q;
    if (q == 1) {
      ll x; cin >> x; x--;
      ll a; cin >> a;
      if (x % 2 == 0 && C[x] - t0 - t1 >= a) {
        C[x] -= a;
        ans += a;
        m1 = min(m1, C[x] - t0 - t1);
        m0 = min(m0, m1);
      } else if (x % 2 == 1 && C[x] - t0 >= a) {
        C[x] -= a;
        ans += a;
        m0 = min(m0, C[x] - t0);
      }
    } else if (q == 2) {
      ll a; cin >> a;
      if (m1 >= a) {
        ans += a * c1;
        m1 -= a;
        m0 = min(m0, m1);
        t1 += a;
      }
    } else if (q == 3) {
      ll a; cin >> a;
      if (m0 >= a) {
        ans += a * N;
        m1 -= a;
        m0 -= a;
        t0 += a;
      }
    }
  }

  cout << ans << '\\n';
  return 0;
}

全体の最小、奇数番目の最小を保持しておいて、値を更新するたびにこれらも更新したり、1個の値を更新するときにためていた引き算を計算したりしている。ヘビー過ぎる。時間内に通せたけど、これはバグらせる自信がある。

で、遅延セグ木を使って書いて見たのがこれ。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;

ll INF = 1e9 + 1;
struct S { ll x; };
struct F { ll x; };

S op(S l, S r) { return S{min(l.x, r.x)}; }
S e() { return S{INF}; }
S mapping(F l, S r) { return S{l.x + r.x}; }
F composition(F l, F r) { return F{l.x + r.x}; }
F id() { return F{0}; }


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll N; cin >> N;
  ll H = (N + 1) / 2;

  vector<ll> C(N); for (ll i = 0; i < N; i++) cin >> C[i];

  vector<S> v(N);
  for (ll i = 0; i < N; i++) {
    ll j;
    if (i % 2 == 0) j = i / 2;
    else j = H + i / 2;

    v[j] = S{C[i]};
  }
  lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);

  ll ans = 0;
  ll Q; cin >> Q;
  for (ll i = 0; i < Q; i++) {
    ll choice; cin >> choice;
    if (choice == 1) {
      ll x; cin >> x;
      x--;
      if (x % 2 == 0) x = x / 2;
      else x = H + x / 2;
      S t = seg.prod(x, x + 1);

      ll a; cin >> a;
      if (t.x >= a) {
        seg.apply(x, F{-a});
        ans += a;
      }
    } else if (choice == 2) {
      ll a; cin >> a;
      S t = seg.prod(0, H);
      if (t.x >= a) {
        seg.apply(0, H, F{-a});
        ans += a * H;
      }
    } else {
      ll a; cin >> a;
      S t = seg.prod(0, N);
      if (t.x >= a) {
        seg.apply(0, N, F{-a});
        ans += a * N;
      }
    }
  }
  cout << ans << '\\n';
  return 0;
}

奇数番目を更新するのは難しいので、もともと奇数番目だったものを前の方に、偶数番目だったものを後の方に並び替えている。あとは、区間加算、区間最小値取得をやればいい。だいぶ精神的に楽。