#include #include using namespace std; using namespace atcoder; using ll=long long; using ull=unsigned long long; using ld=long double; using i128=__int128; using P=pair; template using vc=vector; template using vv=vc>; using vl=vc; using vvl=vc>; using vul=vc; using vs=vc; using vb=vc; #define rep(i,s,n) for(ll i=s;i<(n);i++) #define Rep(i,s,n) for(ll i=n;i>=s;i--) #define nall(x) x.begin(),x.end() #define rall(a) a.rbegin(),a.rend() #define pb push_back #define eb emplace_back #define pob pop_back #define nexp(v) next_permutation(v) #define prep(v) prev_permutation(v) #define YES cout<<"Yes"<b)a=b;} void chmax(ll &a,ll b){if(a struct RangeSet{ set> st; T TINF; RangeSet(){ TINF=numeric_limits::max()/2; st.emplace(TINF,TINF); st.emplace(-TINF,-TINF); } bool covered(T l,T r)const{ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); return ite->first<=l && r<=ite->second; } bool covered(T x)const{ return covered(x,x); } pair covered_by(T l,T r)const{ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l && r<=ite->second)return *ite; return make_pair(-TINF,-TINF); } pair covered_by(T x)const{ return covered_by(x,x); } T insert(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l && r<=ite->second)return T(0); T sum_erased=T(0); if(ite->first<=l && l<=ite->second+1){ l=ite->first; sum_erased+=ite->second-ite->first+1; ite=st.erase(ite); }else ite=next(ite); while(r>ite->second){ sum_erased+=ite->second-ite->first+1; ite=st.erase(ite); } if(ite->first-1<=r && r<=ite->second){ sum_erased+=ite->second-ite->first+1; r=ite->second; st.erase(ite); } st.emplace(l,r); return r-l+1-sum_erased; } T insert(T x){ return insert(x,x); } T erase(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l && r<=ite->second){ if(ite->firstfirst,l-1); if(rsecond)st.emplace(r+1,ite->second); st.erase(ite); return r-l+1; } T ret=T(0); if(ite->first<=l && l<=ite->second){ ret+=ite->second-l+1; if(ite->firstfirst,l-1); ite=st.erase(ite); }else ite=next(ite); while(ite->second<=r){ ret+=ite->second-ite->first+1; ite=st.erase(ite); } if(ite->first<=r && r<=ite->second){ ret+=r-ite->first+1; if(rsecond)st.emplace(r+1,ite->second); st.erase(ite); } return ret; } T erase(T x){ return erase(x,x); } int size()const{ return (int)st.size()-2; } T mex(T x=0)const{ auto ite=prev(st.lower_bound({x+1,x+1})); if(ite->first<=x && x<=ite->second)return ite->second+1; return x; } void output()const{ cout<<"RangeSet : "; for(auto &p:st){ if(p.first==-TINF || p.second==TINF)continue; cout<<"["< struct RangeSet2D{ map> mp; T TINF; RangeSet2D(){ TINF=numeric_limits::max()/2; mp.emplace(-TINF,RangeSet()); mp.emplace(TINF,RangeSet()); } typename map>::iterator split(T x){ auto ite=mp.lower_bound(x); if(ite!=mp.end() && ite->first==x)return ite; assert(ite!=mp.begin()); return mp.emplace_hint(ite,x,prev(ite)->second); } void merge(T l,T r){ auto ite=mp.lower_bound(l); if(ite!=mp.begin())ite=prev(ite); while(ite!=mp.end()){ auto nxt=next(ite); if(nxt==mp.end() || nxt->first>r)break; if(nxt->first!=TINF && ite->second.st==nxt->second.st)mp.erase(nxt); else ite=nxt; } } bool covered(T xl,T xr,T yl,T yr)const{ assert(xl<=xr && yl<=yr); assert(-TINFsecond.covered(yl,yr))return false; auto nxt=next(ite); if(nxt==mp.end() || nxt->first>xr)break; ite=nxt; } return true; } bool covered(T x,T y)const{ return covered(x,x,y,y); } T insert(T xl,T xr,T yl,T yr){ assert(xl<=xr && yl<=yr); assert(-TINFfirst-ite->first)*ite->second.insert(yl,yr); } merge(xl,xr+1); return ret; } T insert(T x,T y){ return insert(x,x,y,y); } T erase(T xl,T xr,T yl,T yr){ assert(xl<=xr && yl<=yr); assert(-TINFfirst-ite->first)*ite->second.erase(yl,yr); } merge(xl,xr+1); return ret; } T erase(T x,T y){ return erase(x,x,y,y); } T mex_y(T x,T y=0)const{ assert(-TINFsecond.mex(y); } T mex_x(T y,T x=0)const{ assert(-TINFsecond.covered(y)){ auto nxt=next(ite); x=nxt->first; ite=nxt; } return x; } ll size()const{ ll ret=0; for(auto ite=mp.begin();next(ite)!=mp.end();++ite){ ret+=ite->second.size(); } return ret; } vc> rectangles()const{ vc xs,ys; for(auto ite=mp.begin();next(ite)!=mp.end();++ite){ auto nxt=next(ite); if(ite->first==-TINF || nxt->first==TINF)continue; bool ok=false; for(auto &p:ite->second.st){ if(p.first==-ite->second.TINF || p.second==ite->second.TINF)continue; ok=true; ys.pb(p.first); ys.pb(p.second+1); } if(!ok)continue; xs.pb(ite->first); xs.pb(nxt->first); } if(xs.empty())return {}; sort(nall(xs)); xs.erase(unique(nall(xs)),xs.end()); sort(nall(ys)); ys.erase(unique(nall(ys)),ys.end()); int nx=(int)xs.size()-1; int ny=(int)ys.size()-1; vc> a(nx,vc(ny)); rep(i,0,nx){ auto ite=prev(mp.upper_bound(xs[i])); rep(j,0,ny){ a[i][j]=ite->second.covered(ys[j]); } } struct R{ int x,y,miss; }; vc rv; vc> id(nx+1,vc(ny+1,-1)); auto cell=[&](int x,int y)->int{ if(x<0 || nx<=x || y<0 || ny<=y)return 0; return a[x][y]; }; rep(i,0,nx+1)rep(j,0,ny+1){ array q={ cell(i-1,j-1), cell(i,j-1), cell(i-1,j), cell(i,j) }; int cnt=q[0]+q[1]+q[2]+q[3]; if(cnt!=3)continue; int miss=0; while(q[miss])miss++; id[i][j]=(int)rv.size(); rv.pb({(int)i,(int)j,miss}); } set> hs,vs; for(auto [x,y,miss]:rv){ if(miss==0 || miss==2){ int k=x; while(k> h(nall(hs)); vc> v(nall(vs)); int H=(int)h.size(); int V=(int)v.size(); vc> g(H); rep(i,0,H)rep(j,0,V){ if(h[i][0]<=v[j][0] && v[j][0]<=h[i][2] && v[j][1]<=h[i][1] && h[i][1]<=v[j][3]){ g[i].pb(j); } } vc mt(V,-1); vc ml(H,-1); function&)> dfs=[&](int x,vc &seen)->bool{ for(auto y:g[x]){ if(seen[y])continue; seen[y]=1; if(mt[y]==-1 || dfs(mt[y],seen)){ mt[y]=x; ml[x]=y; return true; } } return false; }; rep(i,0,H){ vc seen(V); dfs(i,seen); } vc zh(H); vc zv(V); queue> q; rep(i,0,H){ if(ml[i]!=-1)continue; zh[i]=1; q.emplace(0,i); } while(!q.empty()){ auto [side,u]=q.front(); q.pop(); if(side==0){ for(auto y:g[u]){ if(ml[u]==y || zv[y])continue; zv[y]=1; q.emplace(1,y); } }else{ if(mt[u]!=-1 && !zh[mt[u]]){ zh[mt[u]]=1; q.emplace(0,mt[u]); } } } vc> hb(nx,vc(ny+1)); vc> vb(nx+1,vc(ny)); vc> used(nx+1,vc(ny+1)); rep(i,0,H){ if(!zh[i])continue; auto [x1,y1,x2,y2]=h[i]; rep(x,x1,x2)hb[x][y1]=1; used[x1][y1]=1; used[x2][y2]=1; } rep(i,0,V){ if(zv[i])continue; auto [x1,y1,x2,y2]=v[i]; rep(y,y1,y2)vb[x1][y]=1; used[x1][y1]=1; used[x2][y2]=1; } auto has_v=[&](int x,int y)->bool{ return (y> seen(nx,vc(ny)); vc> ret; rep(si,0,nx)rep(sj,0,ny){ if(!a[si][sj] || seen[si][sj])continue; queue> que; que.emplace(si,sj); seen[si][sj]=1; int lx=si; int rx=si; int ly=sj; int ry=sj; ll cnt=0; while(!que.empty()){ auto [x,y]=que.front(); que.pop(); cnt++; lx=min(lx,x); rx=max(rx,x); ly=min(ly,y); ry=max(ry,y); if(0second.st){ if(p.first==-ite->second.TINF || p.second==ite->second.TINF)continue; if(ite->first==-TINF || nxt->first==TINF)continue; cout<<"["<first<<", "<first-1<<"]x["<> h >> w >> n; RangeSet2D st; rep(i,0,n){ ll r1,c1,r2,c2; cin >> r1 >> c1 >> r2 >> c2; st.insert(r1,r2,c1,c2); } auto rect=st.rectangles(); //st.output(); ll sum=0; for(auto [r1,c1,r2,c2]:rect)sum+=(r2-r1+1)*(c2-c1+1); cout << h*w-sum << endl; }