# 非遅延塗りつぶしツリー

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;
}
}
}
}