#line 2 "/Users/tiramister/CompetitiveProgramming/Cpp/CppLibrary/DataStructure/lazy_segment_tree.hpp" #include #include template struct LazySegmentTree { using DMerger = std::function; using OMerger = std::function; using Applier = std::function; int length; T d_unit; E o_unit; std::vector dat; std::vector ope; DMerger dmerge; OMerger omerge; Applier app; explicit LazySegmentTree(int n, T d_unit, E o_unit, DMerger dmerge, OMerger omerge, Applier app) : length(1), d_unit(d_unit), o_unit(o_unit), dmerge(dmerge), omerge(omerge), app(app) { while (length < n) length <<= 1; dat.assign(length * 2, d_unit); ope.assign(length * 2, o_unit); } template explicit LazySegmentTree(const Container& elems, T d_unit, E o_unit, DMerger dmerge, OMerger omerge, Applier app) : length(1), d_unit(d_unit), o_unit(o_unit), dmerge(dmerge), omerge(omerge), app(app) { int n = elems.size(); while (length < n) length <<= 1; dat.assign(length * 2, d_unit); ope.assign(length * 2, o_unit); std::copy(elems.begin(), elems.end(), dat.begin() + length); for (int nidx = length - 1; nidx >= 1; --nidx) { T vl = dat[nidx * 2 + 0]; T vr = dat[nidx * 2 + 1]; dat[nidx] = dmerge(vl, vr); } } void propagate(int nidx, int len) { if (ope[nidx] == o_unit) return; // propagate if (len > 1) { ope[nidx * 2 + 0] = omerge(ope[nidx * 2 + 0], ope[nidx]); ope[nidx * 2 + 1] = omerge(ope[nidx * 2 + 1], ope[nidx]); } // update data dat[nidx] = app(dat[nidx], ope[nidx], len); ope[nidx] = o_unit; } void update(int ql, int qr, E e, int nidx, int nl, int nr) { propagate(nidx, nr - nl); if (nr <= ql || qr <= nl) return; if (ql <= nl && nr <= qr) { ope[nidx] = omerge(ope[nidx], e); propagate(nidx, nr - nl); return; } int nm = (nl + nr) / 2; update(ql, qr, e, nidx * 2 + 0, nl, nm); update(ql, qr, e, nidx * 2 + 1, nm, nr); // update data dat[nidx] = dmerge(dat[nidx * 2 + 0], dat[nidx * 2 + 1]); } void update(int ql, int qr, E e) { return update(ql, qr, e, 1, 0, length); } T fold(int ql, int qr, int nidx, int nl, int nr) { propagate(nidx, nr - nl); if (nr <= ql || qr <= nl) return d_unit; if (ql <= nl && nr <= qr) return dat[nidx]; int nm = (nl + nr) / 2; T vl = fold(ql, qr, nidx * 2 + 0, nl, nm); T vr = fold(ql, qr, nidx * 2 + 1, nm, nr); return dmerge(vl, vr); } T fold(int ql, int qr) { return fold(ql, qr, 1, 0, length); } T get(int idx) { return fold(idx, idx + 1); } T fold_all() { return fold(0, length); } }; #line 2 "main.cpp" #include #line 4 "main.cpp" using namespace std; using lint = long long; constexpr int X = 20000; struct Rects { LazySegmentTree seg; Rects() : seg( X + 1, 0, -1, [](auto a, auto b) { return a + b; }, [](auto e, auto f) { return f == -1 ? e : f; }, [](auto a, auto e, int k) { return e == -1 ? a : e * k; }) {} lint insert(int x, int y) { int ok = X + 1, ng = -1; while (ok - ng > 1) { int mid = (ok + ng) / 2; if (seg.get(mid) < y) { ok = mid; } else { ng = mid; } } if (ok < x) seg.update(ok, x, y); return seg.fold_all(); } }; void solve() { int n; cin >> n; vector rs(4); lint ps = 0; while (n--) { int xl, yl, xr, yr; cin >> xl >> yl >> xr >> yr; xl = -xl, yl = -yl; lint s = 0; for (int i = 0; i < 4; ++i) { s += rs[i].insert(xl, yl); swap(xl, xr); if (i % 2 == 0) swap(yl, yr); } cout << s - ps << "\n"; ps = s; } } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; }