#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 Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } int uf[200'010]; int root(int u) { return (uf[u] < 0) ? u : (uf[u] = root(uf[u])); } bool connect(int u, int v) { u = root(u); v = root(v); if (u == v) return false; if (uf[u] > uf[v]) swap(u, v); uf[u] += uf[v]; uf[v] = u; return true; } template void bAdd(vector &bit, int pos, const T &val) { const int bitN = bit.size(); for (int x = pos; x < bitN; x |= x + 1) bit[x] += val; } template T bSum(const vector &bit, int pos) { T ret = 0; for (int x = pos - 1; x >= 0; x = (x & (x + 1)) - 1) ret += bit[x]; return ret; } template T bSum(const vector &bit, int pos0, int pos1) { return bSum(bit, pos1) - bSum(bit, pos0); } int M, N; vector A, B, C; vector P, Q, R; int main() { for (; ~scanf("%d%d", &M, &N); ) { A.resize(M); B.resize(M); C.resize(M); for (int i = 0; i < M; ++i) scanf("%d%d%d", &A[i], &B[i], &C[i]); P.resize(N); Q.resize(N); R.resize(N); for (int j = 0; j < N; ++j) scanf("%d%d%d", &P[j], &Q[j], &R[j]); int lim = 0; for (int i = 0; i < M; ++i) { chmax(lim, A[i]); chmax(lim, B[i]); chmax(lim, C[i]); } for (int j = 0; j < N; ++j) { chmax(lim, P[j]); chmax(lim, Q[j]); chmax(lim, R[j]); } lim += 5; Int numComps = 0; { int segN; for (segN = 1; segN < lim; segN <<= 1) {} vector> iss(segN << 1), jss(segN << 1); for (int i = 0; i < M; ++i) { // x \in [B[i], C[i]] int a = B[i], b = C[i] + 1; for (a += segN, b += segN; a < b; a >>= 1, b >>= 1) { if (a & 1) iss[a++].push_back(i); if (b & 1) iss[--b].push_back(i); } } for (int j = 0; j < N; ++j) { int a = P[j]; for (a += segN; a; a >>= 1) { jss[a].push_back(j); } } fill(uf, uf + (M + N), -1); for (int a = 1; a < segN << 1; ++a) if (!iss[a].empty() && !jss[a].empty()) { // cerr<<"is = ";pv(iss[a].begin(),iss[a].end()); // cerr<<"js = ";pv(jss[a].begin(),jss[a].end()); vector, int>> events; for (const int i : iss[a]) { events.emplace_back(make_pair(A[i], 1), i); } for (const int j : jss[a]) { events.emplace_back(make_pair(Q[j], 0), j); } sort(events.begin(), events.end()); using Entry = pair; priority_queue, greater> que; for (const auto &e : events) { if (e.first.second) { const int i = e.second; for (; !que.empty() && que.top().first < A[i]; que.pop()) {} if (!que.empty()) { for (; ; ) { const auto p = que.top(); que.pop(); connect(i, M + p.second); if (que.empty()) { que.push(p); break; } } } } else { const int j = e.second; que.emplace(R[j], j); } } } for (int u = 0; u < M + N; ++u) if (uf[u] < 0) { ++numComps; } } // cerr<<"uf = ";pv(uf,uf+(M+N)); cerr<<"numComps = "<> adds(lim), rems(lim), jss(lim); for (int i = 0; i < M; ++i) { adds[B[i]].push_back(i); rems[C[i]].push_back(i); } for (int j = 0; j < N; ++j) { jss[P[j]].push_back(j); } vector bit(lim, 0); for (int x = 0; x < lim; ++x) { for (const int i : adds[x]) { bAdd(bit, A[i], +1); } for (const int j : jss[x]) { Int num = 0; num += bSum(bit, R[j] + 1); num -= bSum(bit, Q[j]); numPoints += num; } for (const int i : rems[x]) { bAdd(bit, A[i], -1); } } } cerr<<"numPoints = "<