非遅延塗りつぶしツリー

大分前に塗りつぶし操作は非遅延でも出きるみたいな事を言っておきながら実装してなかったので実装した。塗りつぶしと総和の木。

N=500, Q=500000 でのランダムテストは通ったのでバグは無いと思う(多分)。これを非遅延と呼ぶかは怪しい。

原理は意外とトリッキーだと思うけど説明するほどでも無いので省略する。

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>

using namespace std;

const int N = 1 << 10;

struct SegmentTree {
  vector<int> dt;
  vector<pair<int, int>> lz;

  SegmentTree() : dt(N * 2), lz(N * 2) {}

  void update(int l, int r, pair<int, int> f, pair<int, int> g, int k = 1, int ll = 0, int rr = N) {
    if (rr <= l || r <= ll) return;
    if (l <= ll && rr <= r) {
      lz[k] = f;
      dt[k] = f.second * (rr - ll);
      return;
    }
    lz[k] = max(lz[k], g);
    update(l, r, f, lz[k], k * 2 + 0, ll, ll + rr >> 1);
    update(l, r, f, lz[k], k * 2 + 1, ll + rr >> 1, rr);
    dt[k] = 0;
    dt[k] += lz[k] <= lz[k * 2 + 0] ? dt[k * 2 + 0] : lz[k].second * (rr - ll) / 2;
    dt[k] += lz[k] <= lz[k * 2 + 1] ? dt[k * 2 + 1] : lz[k].second * (rr - ll) / 2;
  }

  int query(int l, int r, pair<int, int> g, int k = 1, int ll = 0, int rr = N) {
    if (rr <= l || r <= ll) return 0;
    if (l <= ll && rr <= r) return lz[k] < g ? (rr - ll) * g.second : dt[k];
    g = max(g, lz[k]);
    int vl = query(l, r, g, k * 2 + 0, ll, ll + rr >> 1);
    int vr = query(l, r, g, k * 2 + 1, ll + rr >> 1, rr);
    return vl + vr;
  }
};

struct Naive {
  vector<int> dat;

  Naive() : dat(N) {}

  void update(int l, int r, int v) {
    for (int i = l; i < r; i++) {
      dat[i] = v;
    }
  }

  int query(int l, int r) {
    int ret = 0;
    for (int i = l; i < r; i++) {
      ret += dat[i];
    }
    return ret;
  }
};

int main() {
  Naive naive;
  SegmentTree st;

  int n = 500;
  mt19937 mt(123456);

  for (int ii = 1; ii <= 500000; ii++) {
    int type = uniform_int_distribution<int>(0, 1)(mt);
    if (type == 0) {
      int l = uniform_int_distribution<int>(0, n - 1)(mt);
      int r = uniform_int_distribution<int>(0, n - 1)(mt);
      if (l > r) swap(l, r);
      int v = uniform_int_distribution<int>(1, 100)(mt);

      naive.update(l, r + 1, v);
      st.update(l, r + 1, make_pair(ii, v), make_pair(0, 0));
    } else {
      int l = uniform_int_distribution<int>(0, n - 1)(mt);
      int r = uniform_int_distribution<int>(0, n - 1)(mt);
      if (l > r) swap(l, r);

      int vl = st.query(l, r + 1, make_pair(0, 0));
      int vr = naive.query(l, r + 1);
      if (vl != vr) {
        cout << "ERROR" << endl;
      }
    }
  }
}