#include using namespace std; typedef long long ll; #define MAX_N (ll)110000 #define MAX_POS (ll)660000 #define INFTY (ll)1000000000000000000 #define MOD (ll)998244353 #define ZERO (ll)0 #define iscan(x) scanf("%d", &x) #define llscan(x) scanf("%lld", &x) #define isarray(ar, ln) for(ll scani=0; scani using is_signed_int128 = typename std::conditional::value || std::is_same::value, std::true_type, std::false_type>::type; template using is_unsigned_int128 = typename std::conditional::value || std::is_same::value, std::true_type, std::false_type>::type; template using make_unsigned_int128 = typename std::conditional::value, __uint128_t, unsigned __int128>; template using is_integral = typename std::conditional::value || is_signed_int128::value || is_unsigned_int128::value, std::true_type, std::false_type>::type; template using is_signed_int = typename std::conditional<(is_integral::value && std::is_signed::value) || is_signed_int128::value, std::true_type, std::false_type>::type; template using is_unsigned_int = typename std::conditional<(is_integral::value && std::is_unsigned::value) || is_unsigned_int128::value, std::true_type, std::false_type>::type; template using to_unsigned = typename std::conditional< is_signed_int128::value, make_unsigned_int128, typename std::conditional::value, std::make_unsigned, std::common_type>::type>::type; #else template using is_integral = typename std::is_integral; template using is_signed_int = typename std::conditional::value && std::is_signed::value, std::true_type, std::false_type>::type; template using is_unsigned_int = typename std::conditional::value && std::is_unsigned::value, std::true_type, std::false_type>::type; template using to_unsigned = typename std::conditional::value, std::make_unsigned, std::common_type>::type; #endif template using is_signed_int_t = std::enable_if_t::value>; template using is_unsigned_int_t = std::enable_if_t::value>; template using to_unsigned_t = typename to_unsigned::type; } template struct fenwick_tree { using U = internal::to_unsigned_t; public: fenwick_tree() : _n(0) {} fenwick_tree(int n) : _n(n), data(n) {} void add(int p, T x) { assert(0 <= p && p < _n); p++; while (p <= _n) { data[p - 1] += U(x); p += p & -p; } } T sum(int l, int r) { assert(0 <= l && l <= r && r <= _n); return sum(r) - sum(l); } private: int _n; std::vector data; U sum(int r) { U s = 0; while (r > 0) { s += data[r - 1]; r -= r & -r; } return s; } }; struct dsu { public: dsu() : _n(0) {} dsu(int n) : _n(n), parent_or_size(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } std::vector> groups() { std::vector leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector& v) { return v.empty(); }), result.end()); return result; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector parent_or_size; }; int main() { int n,m; iscan(n); iscan(m); static int xbegin[MAX_N], xend[MAX_N], ybegin[MAX_N], yend[MAX_N]; int a, b, c, fi, se, v, w, pmin, pmax; static pair query[MAX_POS]; for range(i, n) { iscan(a); iscan(b); iscan(c); xbegin[i] = a; xend[i] = a; query[i*2] = {b*3-1, i}; query[i*2+1] = {c*3+1, i}; } for range(i, m) { iscan(a); iscan(b); iscan(c); ybegin[i] = b; yend[i] = c; query[2*n+i] = {a*3, i}; } sort(query, query+(2*n+m)); int line_cnt = n+m; long long intersects=0, connected_cnt=0; static dsu uf(MAX_POS); set set_t; set> set_s; fenwick_tree bit(MAX_POS); for range(q, 2*n+m) { fi = query[q].first; se = query[q].second; switch (fi % 3) { case 2: bit.add(xbegin[se], 1); break; case 0: intersects += bit.sum(ybegin[se], yend[se]+1); break; case 1: bit.add(xend[se], -1); } } set>::iterator sec; set::iterator lb; pair p1, p2; for range(q, 2*n+m) { fi = query[q].first; se = query[q].second; switch (fi % 3) { case 2: v = xbegin[se]; set_t.insert(v); sec = set_s.lower_bound({v, v}); if (sec != set_s.begin()) { sec--; if ((*sec).second > v) { lb = set_t.lower_bound(v); p1 = {*++lb, (*sec).second}; lb--; lb--; p2 = {(*sec).first, *lb}; set_s.erase(sec); set_s.insert(p1); // printf("case 2: add back %d %d in query %lld\n", p1.first, p1.second, q); set_s.insert(p2); // printf("case 2: add front %d %d in query %lld\n", p2.first, p2.second, q); } } set_s.insert(make_pair(v, v)); // printf("case 2: add itself %d %d in query %lld\n", v, v, q); break; case 0: v = ybegin[se]; w = yend[se]; lb = set_t.lower_bound(v); if (lb == set_t.end() || *lb > w) { connected_cnt++; // printf("case 0: dont merge in query %lld\n", q); break; } for (sec = set_s.begin(); sec != set_s.end(); sec++) { // printf("case 0: segment list %d %d in query %lld\n", (*sec).first, (*sec).second, q); } sec = set_s.lower_bound({v, 0}); if (sec != set_s.begin() && (*--sec).second < v) sec++; pmin = (*sec).first; while (sec != set_s.end() && (*sec).first <= w) { pmax = (*sec).second; uf.merge(pmin, (*sec).first); // printf("case 0: merge %d %d in query %lld\n", pmin, (*sec).first, q); // printf("case 0: erase %d %d in query %lld\n", (*sec).first, (*sec).second, q); set_s.erase(sec++); } set_s.insert({pmin, pmax}); // printf("case 0: merge segment into %d %d in query %lld\n", pmin, pmax, q); break; case 1: v = xend[se]; set_t.erase(v); sec = set_s.lower_bound({v, 10000000}); sec--; if (v == (*sec).first) { if (v == (*sec).second) { set_s.erase(sec); // printf("case 1: erase segment %d %d in query %lld\n", (*sec).first, (*sec).second, q); break; } lb = set_t.lower_bound(v); p1 = {*lb, (*sec).second}; set_s.erase(sec); // printf("case 1: erase segment %d %d in query %lld\n", (*sec).first, (*sec).second, q); set_s.insert(p1); // printf("case 1: add back %d %d in query %lld\n", p1.first, p1.second, q); } else if (v == (*sec).second) { lb = set_t.lower_bound(v); p2 = {(*sec).first, *--lb}; set_s.erase(sec); // printf("case 1: erase segment %d %d in query %lld\n", (*sec).first, (*sec).second, q); set_s.insert(p2); // printf("case 1: add front %d %d in query %lld\n", p2.first, p2.second, q); } else { lb = set_t.lower_bound(v); p1 = {*lb, (*sec).second}; p2 = {(*sec).first, *--lb}; set_s.erase(sec); // printf("case 1: erase segment %d %d in query %lld\n", (*sec).first, (*sec).second, q); set_s.insert(p1); // printf("case 1: add back %d %d in query %lld\n", p1.first, p1.second, q); set_s.insert(p2); // printf("case 1: add front %d %d in query %lld\n", p2.first, p2.second, q); } } } set used; for range(i, n) { int l = uf.leader(xbegin[i]); if (used.find(l) == used.end()) { connected_cnt++; used.insert(l); // iprint(l); } } // iprint(line_cnt); // iprint(intersects); // iprint(connected_cnt); llprint(connected_cnt + intersects - line_cnt); }