#include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 998244353; // constexpr int MOD = 1000000007; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; template struct FenwickTree { explicit FenwickTree(const int n, const Abelian ID = 0) : n(n), ID(ID), data(n, ID) {} void add(int idx, const Abelian val) { for (; idx < n; idx |= idx + 1) { data[idx] += val; } } Abelian sum(int idx) const { Abelian res = ID; for (--idx; idx >= 0; idx = (idx & (idx + 1)) - 1) { res += data[idx]; } return res; } Abelian sum(const int left, const int right) const { return left < right ? sum(right) - sum(left) : ID; } Abelian operator[](const int idx) const { return sum(idx, idx + 1); } int lower_bound(Abelian val) const { if (val <= ID) return 0; int res = 0, exponent = 1; while (exponent <= n) exponent <<= 1; for (int mask = exponent >> 1; mask > 0; mask >>= 1) { const int idx = res + mask - 1; if (idx < n && data[idx] < val) { val -= data[idx]; res += mask; } } return res; } private: const int n; const Abelian ID; std::vector data; }; struct UnionFind { explicit UnionFind(const int n) : data(n, -1) {} int root(const int ver) { return data[ver] < 0 ? ver : data[ver] = root(data[ver]); } bool unite(int u, int v) { u = root(u); v = root(v); if (u == v) return false; if (data[u] > data[v]) std::swap(u, v); data[u] += data[v]; data[v] = u; return true; } bool is_same(const int u, const int v) { return root(u) == root(v); } int size(const int ver) { return -data[root(ver)]; } private: std::vector data; }; // https://atcoder.jp/contests/joi2014ho/tasks/joi2014ho5 int main() { constexpr int L = 200000; int n_, m_; cin >> n_ >> m_; const int n = n_ + m_; vector a(n + 4), b(n + 4), c(n + 4), d(n + 4); REP(i, n_) { cin >> b[i] >> a[i] >> c[i]; d[i] = b[i]; } FOR(i, n_, n) { cin >> a[i] >> b[i] >> d[i]; c[i] = a[i]; } a[n] = b[n] = d[n] = 0; c[n] = L + 1; a[n + 1] = b[n + 1] = c[n + 1] = 0; d[n + 1] = L + 1; a[n + 2] = c[n + 2] = L + 1; b[n + 2] = 0; d[n + 2] = L + 1; a[n + 3] = 0; b[n + 3] = d[n + 3] = L + 1; c[n + 3] = L + 1; vector xs{0, L + 1}; xs.reserve((n + 4) * 6 + 2); copy(ALL(a), back_inserter(xs)); REP(i, n + 4) { if (a[i] > 0) xs.emplace_back(a[i] - 1); if (a[i] + 1 <= L + 1) xs.emplace_back(a[i] + 1); } copy(ALL(c), back_inserter(xs)); REP(i, n + 4) { if (c[i] > 0) xs.emplace_back(c[i] - 1); if (c[i] + 1 <= L + 1) xs.emplace_back(c[i] + 1); } sort(ALL(xs)); xs.erase(unique(xs.begin(), xs.end()), xs.end()); const int x_size = xs.size(); vector ys{0, L + 1}; ys.reserve((n + 4) * 6 + 2); copy(ALL(b), back_inserter(ys)); REP(i, n + 4) { if (b[i] > 0) ys.emplace_back(b[i] - 1); if (b[i] + 1 <= L + 1) ys.emplace_back(b[i] + 1); } copy(ALL(d), back_inserter(ys)); REP(i, n + 4) { if (d[i] > 0) ys.emplace_back(d[i] - 1); if (d[i] + 1 <= L + 1) ys.emplace_back(d[i] + 1); } sort(ALL(ys)); ys.erase(unique(ys.begin(), ys.end()), ys.end()); const int y_size = ys.size(); REP(i, n + 4) a[i] = distance(xs.begin(), lower_bound(ALL(xs), a[i])); REP(i, n + 4) b[i] = distance(ys.begin(), lower_bound(ALL(ys), b[i])); REP(i, n + 4) c[i] = distance(xs.begin(), lower_bound(ALL(xs), c[i])); REP(i, n + 4) d[i] = distance(ys.begin(), lower_bound(ALL(ys), d[i])); vector>> par_y(x_size), ins_x(x_size), era_x(x_size); REP(i, n + 4) { if (a[i] == c[i]) { par_y[a[i]].emplace_back(b[i], d[i]); } else { ins_x[a[i]].emplace_back(b[i], i); era_x[c[i]].emplace_back(b[i], i); } } ll ans = -(n + 4); FenwickTree bit(y_size); REP(x, x_size) { for (const auto& [y, _] : ins_x[x]) bit.add(y, 1); for (const auto& [y1, y2] : par_y[x]) { const int cross = bit.sum(y1, y2 + 1); ans += cross; if (cross == 0) ++ans; } for (const auto& [y, _] : era_x[x]) bit.add(y, -1); } UnionFind union_find(n + 4); vector id_y(y_size, -1); set t; map intervals; const auto find = [&](const int y) { const auto it = intervals.lower_bound(y); if (it != intervals.end() && it->first == y) return it; if (it != intervals.begin() && prev(it)->first <= y && y <= prev(it)->second) return prev(it); return intervals.end(); }; REP(x, x_size) { for (const auto [y, id] : ins_x[x]) { if (const auto it = find(y); it != intervals.end()) { const auto [l, r] = *it; intervals.erase(it); const auto it_r = t.lower_bound(y); if (it_r != t.end() && *it_r <= r) { assert(intervals.emplace(*it_r, r).second); } if (it_r != t.begin() && *prev(it_r) >= l) { assert(intervals.emplace(l, *prev(it_r)).second); } assert(intervals.emplace(y, y).second); } else { assert(intervals.emplace(y, y).second); } id_y[y] = id; assert(t.emplace(y).second); } for (const auto& [y1, y2] : par_y[x]) { auto it = find(y1); if (it == intervals.end()) { it = intervals.lower_bound(y1); if (it != intervals.end() && it->first > y2) it = intervals.end(); } if (it != intervals.end()) { vector> segs; for (; it != intervals.end() && it->first <= y2; it = intervals.erase(it)) { segs.emplace_back(*it); } FOR(i, 1, segs.size()) { union_find.unite(id_y[segs[i - 1].first], id_y[segs[i].first]); } assert(intervals.emplace(segs.front().first, segs.back().second).second); } } for (const auto& [y, _] : era_x[x]) { id_y[y] = -1; assert(t.erase(y) > 0); const auto it = find(y); assert(it != intervals.end()); const auto [l, r] = *it; intervals.erase(it); const auto it_r = t.lower_bound(y); if (it_r != t.end() && *it_r <= r) { assert(intervals.emplace(*it_r, r).second); } if (it_r != t.begin() && *prev(it_r) >= l) { assert(intervals.emplace(l, *prev(it_r)).second); } } } REP(i, n + 4) { if (b[i] == d[i] && union_find.root(i) == i) ++ans; } cout << ans - 1 << '\n'; return 0; }