#pragma GCC optimize("Ofast") #include using namespace std; typedef long long int ll; typedef unsigned long long int ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull) rng() % B; } // 1-indexed template struct BIT{ int n; vector bit; BIT(int n_=0):n(n_),bit(n+1){} T sum(int i){ T res=0; for(;i>0;i-=(i&-i))res+=bit[i]; return res; } void add(int i,T a){ if(i==0)return; for(;i<=n;i+=(i&-i)){bit[i]+=a;} } int lower_bound(T k){ // k<=sum(res) if(k<=0)return 0; int res=0,i=1; while((i<<1)<=n)i<<=1; for(;i;i>>=1){ if(res+i<=n&&bit[res+i] par,num; UnionFind(int n):par(n),num(n,1){ iota(par.begin(),par.end(),0); //include } int find(int v){ return (par[v]==v)?v:(par[v]=find(par[v])); } void unite(int u,int v){ u=find(u),v=find(v); if(u==v)return; if(num[u]> n >> m; ll res = -(n+m); // 共有点の数と連結成分数を足したのが答え vector> yoko(N,{-1,-1}); vector>> in(N),out(N); for (int i = 0; i < n; ++i) { int a,b,c; cin >> a >> b >> c; yoko[a] = {b,c}; } for (int i = 0; i < m; ++i) { int a,b,c; cin >> a >> b >> c; in[b].push_back({a,i}); out[c].push_back({a,i}); } // 共有点の数を求める { BIT bit(N); for (int i = 0; i < N; ++i) { for (auto j:in[i]) { bit.add(j.first, 1); } if(yoko[i].first != -1) { res += bit.sum(yoko[i].second); res -= bit.sum(yoko[i].first-1); } for (auto j:out[i]) { bit.add(j.first, -1); } } } // 連結成分の数を求める { UnionFind uf(n+m); int id = m; set> S,T; for (int i = 0; i < N; ++i) { for (auto j:in[i]) { S.insert(j); T.insert(j); } if(yoko[i].first != -1) { auto [l,r] = yoko[i]; auto it = T.lower_bound({l,-1}); if(it != T.end() and it->first <= r) { int d = it->second; uf.unite(id, d); it++; if (it != T.end() and it->first <= r) { uf.unite(id, it->second); } it = S.lower_bound({l,-1}); while (it != S.end() and it->first <= r) { uf.unite(id, it->second); it = S.erase(it); } } id++; } for (auto j:out[i]) { if(S.find(j) != S.end()) S.erase(j); T.erase(j); } } for (int i = 0; i < n+m; ++i) { if(uf.find(i) == i) res++; } } cout << res << endl; }