#include #include #include using namespace std; using i64 = long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) struct DSU{ vector A; DSU(int n){ A.assign(n, -1); } int leader(int a){ if(A[a] < 0) return a; return A[a] = leader(A[a]); } int merge(int u, int v){ u = leader(u); v = leader(v); if(u == v) return u; if(A[u] == A[v]) A[u]--; else if(A[u] > A[v]) swap(u,v); A[v] = u; return u; } int add(){ int res = A.size(); A.push_back(-1); return res; } int num_groups(){ int ans = 0; rep(i,A.size()) if(A[i] < 0) ans++; return ans; } }; void coordcompress(vector A, vector B){ int n = A.size(); vector I(n); rep(i,n) I[i] = i; sort(I.begin(),I.end(),[&](int l,int r){return *A[l]<*A[r];}); vector S(n); rep(i,n) S[i] = *A[i]; sort(S.begin(), S.end()); rep(i,n) *A[I[i]] = i; for(auto b : B) *b = lower_bound(S.begin(), S.end(), *b) - S.begin(); } struct BIT{ vector A; BIT(int n){ A.assign(n+1, 0); } void add(int i, int x){ i++; while(i < (int)A.size()){ A[i] += x; i += i & -i; } } int sum(int r){ int res = 0; while(r){ res += A[r]; r -= r & -r; } return res; } int sum(int l, int r){ return sum(r) - sum(l); } }; #include struct RMQ{ int N = 0; vector A; void aggregate(int i){ A[i] = max(A[i*2], A[i*2+1]); } RMQ(int n = 0){ N = 1; while(N < n) N *= 2; A.assign(N*2, -1); } int prod(int l, int r){ assert(0 <= l); assert(r <= N); l += N; r += N; int res = -1; while(l < r){ if(l & 1) res = max(res, A[l++]); if(r & 1) res = max(res, A[--r]); l /= 2; r /= 2; } return res; } void set(int p, int x){ assert(p < N); p += N; A[p] = x; while(p != 1){ p /= 2; aggregate(p); } } void dump(){ cout << "[ "; rep(i,N) cout << A[N+i] << " "; cout << "]" << endl; } }; struct VLine{ int x, l, r; }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); // int W, H, N; cin >> W >> H >> N; int W = 1'000'000'000; int H = 1'000'000'000; int N; cin >> N; int M; cin >> M; vector VL; vector HL; /* rep(i,N){ int xl,xr,yl,yr; cin >> xl >> yl >> xr >> yr; if(xl == xr) VL.push_back({ xl,yl,yr+1 }); if(yl == yr) HL.push_back({ yl,xl,xr+1 }); } */ rep(i,N){ int a,b,c; cin >> a >> b >> c; VL.push_back({a,b,c+1}); } rep(i,M){ int a,b,c; cin >> a >> b >> c; HL.push_back({a,b,c+1}); } VL.push_back({ 0,0,H+1 }); VL.push_back({ W,0,H+1 }); HL.push_back({ 0,0,W+1 }); HL.push_back({ H,0,W+1 }); if(VL.size() < HL.size()) swap(VL, HL); { vector XA, XB, YA, YB; for(auto& vl : VL){ XA.push_back(&vl.x); YB.push_back(&vl.l); YB.push_back(&vl.r); } for(auto& hl : HL){ YA.push_back(&hl.x); XB.push_back(&hl.l); XB.push_back(&hl.r); } coordcompress(move(XA), move(XB)); coordcompress(move(YA), move(YB)); } W = VL.size(); H = HL.size(); i64 ans = 0; vector cid(W+1, -1); RMQ spmin = RMQ(W+1); spmin.set(W, W - W); cid[W] = 0; DSU dsu = DSU(1); BIT spcnt = BIT(W+1); RMQ knownmin = RMQ(W+1); vector> inqueries(H); vector midqueries(H); vector> outqueries(H); for(auto vl : VL){ if(vl.l == vl.r) continue; inqueries[vl.l].push_back(vl.x); outqueries[vl.r-1].push_back(vl.x); } rep(i,H) midqueries.at(HL[i].x) = i; rep(y,H){ for(auto x : inqueries[y]){ int nx = W - spmin.prod(x+1, W+1); if(cid[nx] < 0){ cid[nx] = dsu.add(); knownmin.set(nx, W - nx); } cid[x] = cid[nx]; spcnt.add(x, 1); spmin.set(x, W - x); knownmin.set(x, W - x); } rep(dummy_counter,1){ int hli = midqueries[y]; int l = HL[hli].l, r = HL[hli].r; int spl = spmin.prod(l, r); if(spl < 0) break; spl = W - spl; ans += spcnt.sum(spl+1, r); while(true){ int nx = knownmin.prod(spl+1, r); if(nx < 0) break; nx = W - nx; ans--; knownmin.set(nx, -1); cid[nx] = -1; } } for(auto x : outqueries[y]){ int col = cid[x]; int nx = spmin.prod(x+1, W+1); nx = W - nx; if(cid[x] >= 0 && cid[nx] >= 0) dsu.merge(cid[x], cid[nx]); if(cid[nx] >= 0) col = cid[nx]; if(cid[x] >= 0){ cid[x] = -1; knownmin.set(x, -1); } cid[nx] = col; if(cid[nx] >= 0) knownmin.set(nx, W - nx); spcnt.add(x, -1); spmin.set(x, -1); } } ans += dsu.num_groups(); ans --; ans --; cout << ans << '\n'; return 0; }