#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using lint = long long; using pint = pair; using plint = pair; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template void ndarray(vector& vec, const V& val, int len) { vec.assign(len, val); } template void ndarray(vector& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); } template bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; } template bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; } int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); } template pair operator+(const pair &l, const pair &r) { return make_pair(l.first + r.first, l.second + r.second); } template pair operator-(const pair &l, const pair &r) { return make_pair(l.first - r.first, l.second - r.second); } template vector sort_unique(vector vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; } template int arglb(const std::vector &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); } template int argub(const std::vector &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); } template istream &operator>>(istream &is, vector &vec) { for (auto &v : vec) is >> v; return is; } template ostream &operator<<(ostream &os, const vector &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; } template ostream &operator<<(ostream &os, const array &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; } #if __cplusplus >= 201703L template istream &operator>>(istream &is, tuple &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; } template ostream &operator<<(ostream &os, const tuple &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; } #endif template ostream &operator<<(ostream &os, const deque &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; } template ostream &operator<<(ostream &os, const set &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template ostream &operator<<(ostream &os, const unordered_set &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template ostream &operator<<(ostream &os, const multiset &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template ostream &operator<<(ostream &os, const unordered_multiset &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template ostream &operator<<(ostream &os, const pair &pa) { os << '(' << pa.first << ',' << pa.second << ')'; return os; } template ostream &operator<<(ostream &os, const map &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } template ostream &operator<<(ostream &os, const unordered_map &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } #ifdef HITONANODE_LOCAL const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m"; #define dbg(x) cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << endl #define dbgif(cond, x) ((cond) ? cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << endl : cerr) #else #define dbg(x) 0 #define dbgif(cond, x) 0 #endif #ifndef ATCODER_INTERNAL_BITOP_HPP #define ATCODER_INTERNAL_BITOP_HPP 1 #ifdef _MSC_VER #include #endif namespace atcoder { namespace internal { // @param n `0 <= n` // @return minimum non-negative `x` s.t. `n <= 2**x` int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal } // namespace atcoder #endif // ATCODER_INTERNAL_BITOP_HPP #ifndef ATCODER_LAZYSEGTREE_HPP #define ATCODER_LAZYSEGTREE_HPP 1 #include #include #include #include // #include "atcoder/internal_bit" namespace atcoder { template struct lazy_segtree { public: lazy_segtree() : lazy_segtree(0) {} explicit lazy_segtree(int n) : lazy_segtree(std::vector(n, e())) {} explicit lazy_segtree(const std::vector &v) : _n(int(v.size())) { log = internal::ceil_pow2(_n); size = 1 << log; d = std::vector(2 * size, e()); lz = std::vector(size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) const { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S prod(int l, int r) const { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() const { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template int max_right(int l) const { return max_right(l, [](S x) { return g(x); }); } template int max_right(int l, G g) const { assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) const { return min_left(r, [](S x) { return g(x); }); } template int min_left(int r, G g) const { assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } protected: int _n, size, log; mutable std::vector d; mutable std::vector lz; void update(int k) const { d[k] = op(d[2 * k], d[2 * k + 1]); } virtual void all_apply(int k, F f) const { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) const { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; } // namespace atcoder #endif // ATCODER_LAZYSEGTREE_HPP // Reference: https://atcoder.github.io/ac-library/document_ja/lazysegtree.html // https://betrue12.hateblo.jp/entry/2020/09/22/194541 // https://betrue12.hateblo.jp/entry/2020/09/23/005940 /* struct S {}; S op(S l, S r) { return {}; } S e() { return {}; }; using F = bool; S mp(F f, S x) { return x; } F composition(F fnew, F gold) { return fnew ^ gold; } F id() { return false; } vector A; atcoder::lazy_segtree seg(A); */ template class segtree_beats : public atcoder::lazy_segtree { using Base = atcoder::lazy_segtree; using Base::lazy_segtree; void all_apply(int k, F f) const override { Base::d[k] = mapping(f, Base::d[k]); if (k < Base::size) { Base::lz[k] = composition(f, Base::lz[k]); if (Base::d[k].fail) Base::push(k), Base::update(k); } } }; namespace RangeChMinMaxAddSum { #include template inline Num second_lowest(Num a, Num a2, Num c, Num c2) noexcept { // a < a2, c < c2 return a == c ? std::min(a2, c2) : a2 <= c ? a2 : c2 <= a ? c2 : std::max(a, c); } template inline Num second_highest(Num a, Num a2, Num b, Num b2) noexcept { // a > a2, b > b2 return a == b ? std::max(a2, b2) : a2 >= b ? a2 : b2 >= a ? b2 : std::min(a, b); } using BNum = long long; constexpr BNum BINF = 1LL << 61; struct S { BNum lo, hi, lo2, hi2, sum; unsigned sz, nlo, nhi; bool fail; S() : lo(BINF), hi(-BINF), lo2(BINF), hi2(-BINF), sum(0), sz(0), nlo(0), nhi(0), fail(0) {} S(BNum x, unsigned sz_ = 1) : lo(x), hi(x), lo2(BINF), hi2(-BINF), sum(x * sz_), sz(sz_), nlo(sz_), nhi(sz_), fail(0) {} friend std::ostream &operator<<(std::ostream &os, const S s) { return os << "[(" << s.lo << "x" << s.nlo << ", " << s.lo2 << ", " << s.hi2 << ", " << s.hi << "x" << s.nhi << "), sz=" << s.sz << ", sum=" << s.sum << "]"; } }; S e() { return S(); } S op(S l, S r) { if (l.lo > l.hi) return r; if (r.lo > r.hi) return l; S ret; ret.lo = std::min(l.lo, r.lo), ret.hi = std::max(l.hi, r.hi); ret.lo2 = second_lowest(l.lo, l.lo2, r.lo, r.lo2), ret.hi2 = second_highest(l.hi, l.hi2, r.hi, r.hi2); ret.sum = l.sum + r.sum, ret.sz = l.sz + r.sz; ret.nlo = l.nlo * (l.lo <= r.lo) + r.nlo * (r.lo <= l.lo); ret.nhi = l.nhi * (l.hi >= r.hi) + r.nhi * (r.hi >= l.hi); return ret; } struct F { BNum lb, ub, bias; F() : lb(-BINF), ub(BINF), bias(0) {} F(BNum chmax_, BNum chmin_, BNum add) : lb(chmax_), ub(chmin_), bias(add) {} static F chmin(BNum x) noexcept { return F(-BINF, x, BNum(0)); } static F chmax(BNum x) noexcept { return F(x, BINF, BNum(0)); } static F add(BNum x) noexcept { return F(-BINF, BINF, x); }; }; F composition(F fnew, F fold) { F ret; ret.lb = std::max(std::min(fold.lb + fold.bias, fnew.ub), fnew.lb) - fold.bias; ret.ub = std::min(std::max(fold.ub + fold.bias, fnew.lb), fnew.ub) - fold.bias; ret.bias = fold.bias + fnew.bias; return ret; } F id() { return F(); } S mapping(F f, S x) { if (x.sz == 0) return e(); if (x.lo == x.hi or f.lb == f.ub or f.lb >= x.hi or f.ub < x.lo) return S(std::min(std::max(x.lo, f.lb), f.ub) + f.bias, x.sz); if (x.lo2 == x.hi) { x.lo = x.hi2 = std::max(x.lo, f.lb) + f.bias, x.hi = x.lo2 = std::min(x.hi, f.ub) + f.bias; x.sum = x.lo * x.nlo + x.hi * x.nhi; return x; } if (f.lb < x.lo2 and f.ub > x.hi2) { BNum nxt_lo = std::max(x.lo, f.lb), nxt_hi = std::min(x.hi, f.ub); x.sum += (nxt_lo - x.lo) * x.nlo - (x.hi - nxt_hi) * x.nhi + f.bias * x.sz; x.lo = nxt_lo + f.bias, x.hi = nxt_hi + f.bias, x.lo2 += f.bias, x.hi2 += f.bias; return x; } x.fail = 1; return x; } using segtree = segtree_beats; } // namespace RangeChMinMaxAddSum // UnionFind Tree (0-indexed), based on size of each disjoint set struct UnionFind { std::vector par, cou; UnionFind(int N = 0) : par(N), cou(N, 1) { iota(par.begin(), par.end(), 0); } int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); } bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) return false; if (cou[x] < cou[y]) std::swap(x, y); par[y] = x, cou[x] += cou[y]; return true; } int count(int x) { return cou[find(x)]; } bool same(int x, int y) { return find(x) == find(y); } }; #include #include #include using namespace __gnu_pbds; // find_by_order(), order_of_key() template using pbds_set = tree, rb_tree_tag, tree_order_statistics_node_update>; template using pbds_map = tree, rb_tree_tag, tree_order_statistics_node_update>; int main() { int N, M; cin >> N >> M; using Tpl = tuple; map> bc2a; map p2qr; lint edgelen = 0; int nv = 0; REP(i, N) { int a, b, c; cin >> a >> b >> c; bc2a[b].emplace_back(+1, a, i); bc2a[c + 1].emplace_back(-1, a, i); edgelen += c - b; nv += c - b + 1; } REP(i, M) { int p, q, r; cin >> p >> q >> r; p2qr[p] = make_tuple(q, r, i); edgelen += r - q; nv += r - q + 1; } UnionFind uf(N + M); set y2i; pbds_set y2i2; vector init; REP(i, 200002) init.push_back(RangeChMinMaxAddSum::S(i + 1)); RangeChMinMaxAddSum::segtree tree(init); for (auto [p, qri] : p2qr) { while (bc2a.size() and bc2a.begin()->first <= p) { for (auto [sgn, a, i] : bc2a.begin()->second) { if (sgn > 0) { y2i.insert(make_pair(a, i)); y2i2.insert(make_pair(a, i)); tree.apply(0, a, RangeChMinMaxAddSum::F::chmin(a)); tree.set(a, RangeChMinMaxAddSum::S(a + 1)); } else { y2i.erase(make_pair(a, i)); y2i2.erase(make_pair(a, i)); } } bc2a.erase(bc2a.begin()); } const auto [q, r, im] = qri; int cur = q; while (cur <= r) { dbg(cur); auto itr = y2i.lower_bound(make_pair(cur, 0)); if (itr != y2i.end() and itr->first <= r) { uf.unite(im + N, itr->second); cur = tree.get(itr->first).lo; } else { break; } } tree.apply(q, r, RangeChMinMaxAddSum::F::chmax(r)); nv -= y2i2.order_of_key(make_pair(r + 1, 0)) - y2i2.order_of_key(make_pair(q, 0)); } vector roots; REP(i, N + M) roots.push_back(uf.find(i)); roots = sort_unique(roots); cout << edgelen - nv + 1 + roots.size() - 1 << '\n'; }