比较抽象的一个题。
首先先考虑 \(T=1\)，如果我们建一张图，将图上所有横线与竖线的交点看作图上的点，相邻的有线段相连的点看作图上的边的话，那么显然会得到一张平面图，而我们要计算的是平面图上面的个数，根据公式 \(F=E-V+C+1\)，其中 \(C\) 为这张图中连通块的个数。设 \(c\) 为线段与线段在非线段四个角上的交点个数，那么带入 \(V=4n+c,E=4n+2c\) 可得 \(F=c+C-1\)，而 \(c\) 容易由扫描线 + 树状数组维护，\(C\) 的求解实际上是 https://www.luogu.com.cn/problem/P7712 的一个弱化版，但杀鸡不用牛刀，对于这题而言，我们只要计算连通块个数，因此做法其实很简单：对 \(x\) 这一维扫描线，然后支持在一个位置加入一个点，在一个位置删除一个点，将区间中的点合并到一起。这显然可以用支持区间删点的数据结构轻松维护。时间复杂度 \(O(n\log n)\)。这样我们解决了第一问。
考虑如何计算黑白区域的个数，这也是我在思考过程中所卡住的一步。先考虑一种比较特殊的情况：subtask 4 也就是边界线连通的情况。显然一个矩形的存在会使得内部所有位置的颜色状态改变，因此还是考虑对 \(x\) 这一维扫描线。考虑用一种比较感性的方式求解黑色区域个数：
- 称一段极长的不包含矩形左右边界的 \(y\) 坐标区间为“段”，那么我们在碰到矩形上 / 下边界的时候会使得一段 \(y\) 坐标区间中区域的颜色反转，那么我们考虑区间中每一段，如果这段是黑变白那么我们认为它没有产生新的黑色区域（即使产生了，我们也不把贡献放到这里计算），于是我们重点考虑白变黑的情况：
- 如果执行完翻转操作之后两边段的颜色都是白色，那么情况可以看作产生了一个新的黑色区域，答案加一。
- 如果执行完翻转操作之后两边段的颜色是一白一黑，那么情况可以看作原来的黑色区域向一侧延申了一段，答案不变。
- 如果执行完翻转操作之后两边段的颜色都是黑色（这种情况只有一种情况会出现，那就是这个区间中有且只有一段，且这一段本来是白色，这样它两侧的段的颜色都不变，才有可能都是黑色），那么这种情况可以看作两侧的黑色区域进行了合并，答案减一。
这个过程看似复杂，但是体现在代码中却比较容易。具体来说，如果碰到上边界，那么黑色区域会增加 \(\lfloor\dfrac{sumr}{2}\rfloor-\lfloor\dfrac{suml}{2}\rfloor\)；如果碰到下边界，那么黑色区域会增加 \(\lfloor\dfrac{sumr}{2}\rfloor-\lfloor\dfrac{suml+1}{2}\rfloor\)。来其中 \(sumr,suml\) 分别为 \(r,l\) 之前的左右边界个数。这个式子的正确性可以通过“黑白段间隔出现”这个事实来说明。可以使用树状数组轻松维护。直接实现即可通过 subtask 4。
但是如果将这个做法直接应用于 subtask 6，你会发现它过不了。考虑最简单的反例，一个大矩形里面套了一个小矩形。当我们扫描到外面的矩形的上边界时，我们会认为“产生了一个黑色区域”，但是扫到里面的矩形的下边界时候，我们会错因当作“黑色区域的合并”而把这个 \(1\) 扣掉，但实际上这两边本来就是一个区域，并不是真正意义上的“合并”。思考一下这种情况出现的原因，本质上是因为矩形出现包含关系而产生了“回”字行而导致我们不能判断扫到下边界的时候是否真正进行了黑色区域的合并，但稍加思考可以发现，subtask 4 的情况就不会出现这种回字形，因此它的计算是正确的。考虑怎么规约到 subtask 4 的情况这个时候。我们需要综合前面 \(T=1\) 的情况进行处理。我们拿出前面计算连通块个数 \(C\) 的时候维护的矩形相交情况，对于每个连通块，它内部黑白区域的处理与 subtask 4 相同，可以直接扫描线，而考虑其外部那个“回”字形的区域，我们可以通过计算这个连通块的并被多少个矩形严格包含来知道这个区域是黑色还是白色，如果是黑色那说明我们算出的”黑色区域“实际上在原图中是白色区域，拿这个连通块中的区域个数减掉就行了。由于这个区域的并与其他矩形要么是包含关系，要么是不交关系，所以我们实际上只用计算这个矩形的左下角被多少个矩形严格包含，这是简单的二维偏序问题，直接树状数组做行了。这样我们就解决了这个问题。
const int MAXN=2e5;
int n,opt,f[MAXN+5],belx[MAXN+5],bely[MAXN+5];
pii x[MAXN+5],y[MAXN+5];ll sum=0,cmp=0,cntb=0;
struct bar{int x1,y1,x2,y2;}a[MAXN+5];
int find(int x){return (!f[x])?x:f[x]=find(f[x]);}
void merge(int x,int y){x=find(x);y=find(y);if(x!=y)f[x]=y;}
vector<int>vec[MAXN+5];bool is[MAXN+5];
ll tot[MAXN+5],s[MAXN+5];
struct fenwick{
int t[MAXN+5];
void init(){memset(t,0,sizeof(t));}
fenwick(){init();}
void add(int x,int v){for(int i=x;i<=n*2;i+=(i&(-i)))t[i]+=v;}
int query(int x){int ret=0;for(int i=x;i;i&=(i-1))ret+=t[i];return ret;}
}T;
vector<tuple<int,int,int> >pv[MAXN+5];
vector<pii>qv[MAXN+5];
int main(){
scanf("%d%d",&n,&opt);
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
x[a[i].x1]=x[a[i].x2]=mp(a[i].y1,a[i].y2);
y[a[i].y1]=y[a[i].y2]=mp(a[i].x1,a[i].x2);
belx[a[i].x1]=belx[a[i].x2]=bely[a[i].y1]=bely[a[i].y2]=i;
}
set<int>st;
for(int i=1;i<=n*2;i++){
int l=x[i].fi,r=x[i].se;
while(1){
set<int>::iterator it=st.upper_bound(l);
if(it==st.end()||(*it)>=r)break;
int p=*it;merge(belx[i],bely[p]);st.erase(st.find(p));
}
if(is[l]){
if(st.find(l)!=st.end())st.erase(st.find(l));
if(st.find(r)!=st.end())st.erase(st.find(r));
is[l]=is[r]=0;
}else{
st.insert(l);st.insert(r);
is[l]=is[r]=1;
}
}
for(int i=1;i<=n;i++)vec[find(i)].pb(i);
for(int i=1;i<=n;i++)if(!vec[i].empty()){
cmp++;vector<int>vx;bool tt=0;
for(int t:vec[i])vx.pb(a[t].x1),vx.pb(a[t].x2);
sort(vx.begin(),vx.end());
for(int j:vx){
int l=x[j].fi,r=x[j].se,flg=is[l];
if(!is[l]){
is[l]^=1,is[r]^=1;T.add(l,1),T.add(r,1);
int sl=T.query(l),sr=T.query(r);
s[i]+=sr/2-sl/2;tot[i]+=sr-sl+1;
}else{
is[l]^=1;is[r]^=1;T.add(l,-1);T.add(r,-1);
int sl=T.query(l),sr=T.query(r);
s[i]+=sr/2-(sl+1)/2;tot[i]+=sr-sl+2;
}
}
tot[i]-=4*vec[i].size();int xl=2*n+1,yl=2*n+1;
for(int id:vec[i])chkmin(xl,a[id].x1),chkmin(yl,a[id].y1);
qv[xl].pb(mp(yl,i));sum+=tot[i];
}
for(int i=1;i<=n;i++){
pv[a[i].x1+1].pb(mt(a[i].y1+1,a[i].y2-1,1));
pv[a[i].x2].pb(mt(a[i].y1+1,a[i].y2-1,-1));
}
T.init();
for(int i=1;i<=2*n;i++){
for(auto t:pv[i]){
int L=get<0>(t),R=get<1>(t),X=get<2>(t);
T.add(L,X);T.add(R+1,-X);
}
for(pii p:qv[i]){
int y=p.fi,id=p.se;
if((T.query(y)&1))cntb+=tot[id]+1-s[id];
else cntb+=s[id];
}
}
if(opt==1)printf("%lld\n",sum+cmp+1);
else printf("%lld %lld\n",sum+cmp+1-cntb,cntb);
return 0;
}