把矩形有交看成有边，无交看成无边。
这个三元无边不太好弄，有边才是好做的，所以起手先容斥，设 \(f_p\) 为原图中有多少个 \((i,j,k)\) 满足 \(1\le i<j<k\le n\) 且两两之间恰好有 \(p\) 条边。
为了寻找一些等量关系，我们再记 \(d_i\) 表示有多少个 \(j\) 满足 \(j\neq i\) 且 \(i,j\) 之间有边。
首先第一行那个式子是我们用来算答案用的，所以不能要。
看后面两个，我们需要知道至少两个东西才能解出这个方程，所以 \(d_i\) 是一定要知道的，而剩下的 \(f_1,f_2,f_3\) 中，\(f_3\) 限制最严，是最好算的，所以现在我们只需要算 \(d_i\) 与 \(f_3\)。
\(d_i\) 怎么算呢，考虑从下往上扫描线，扫两遍。
第一遍正常扫，遇到下边界时统计与下边界有交的边数，有交边数可以单步容斥求变成 \(l>qr\) 的数量 \(r<ql\) 的数量，用线段树维护即可。
第二遍扫的时候，遇到上边界时不删除，遇到上下边界时都统计与上下边界有交的边数，然后将上边界的答案减去下边界的答案算入 \(d_i\)。
画图容易发现这样扫两边即可不重不漏地算出 \(d_i\)。当然不这么智慧的做法也有，可以通过容斥拆成 \(4\) 个二位偏序，但是非常史。
接下来考虑算 \(f_3\)。
还是正常扫描线，对于一个三元组 \((i,j,k)\)，我们只在下边界最大的那个矩阵上统计他们的贡献。
由于是在扫描线过程中统计，那么 \(y\) 轴自然就相交了，此时两个矩阵相交等价于他们的 \(x\) 轴相交。
所以我们再使用单步容斥，将 \((i,j,k)\) 两两有交的方案数变成 \((i,j),(i,k)\) 有交减去 \((i,j),(i,k)\) 有交但 \((j,k)\) 无交的方案数。
这个东西还是考虑线段树维护，其实就是左区间的 \(r\) 个数乘右区间的 \(l\) 个数，并且 \(l,r\) 都在下边界范围内，这个容易用线段树维护，看不懂的可以看代码。
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=600010;
int x[N],y[N],a[N],b[N],c[N],d[N],e[N];
struct node{int l,r,id;
};
vector<node>g1[N],g2[N];
int ans[N];
struct Tree{int tr[N<<1];void clear(){memset(tr,0,sizeof(tr));}void update(int l,int r,int p,int x,int v){if(l==r){tr[p]+=v;return;}int mid=(l+r)>>1;if(x<=mid)update(l,mid,p<<1,x,v);else update(mid+1,r,p<<1|1,x,v);tr[p]=tr[p<<1]+tr[p<<1|1];}int query(int l,int r,int p,int a,int b){if(l>b||r<a)return 0;if(a<=l&&r<=b)return tr[p];int mid=(l+r)>>1;return query(l,mid,p<<1,a,b)+query(mid+1,r,p<<1|1,a,b);}
}T1,T2;
int s[N<<1];
void upd(int l,int r,int p,int x){if(l==r)return;int mid=(l+r)>>1;if(x<=mid)upd(l,mid,p<<1,x);else upd(mid+1,r,p<<1|1,x);s[p]=s[p<<1]+s[p<<1|1]+T2.tr[p<<1]*T1.tr[p<<1|1];
}
node qry(int l,int r,int p,int a,int b){if(l>b||r<a)return {0,0,0};if(a<=l&&r<=b)return {s[p],T1.tr[p],T2.tr[p]};int mid=(l+r)>>1;node ls=qry(l,mid,p<<1,a,b);node rs=qry(mid+1,r,p<<1|1,a,b);return {ls.l+rs.l+ls.id*rs.r,ls.r+rs.r,ls.id+rs.id};
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;int totx=0,toty=0;for(int i=1;i<=n;i++){cin>>a[i]>>c[i]>>b[i]>>d[i];x[++totx]=a[i];x[++totx]=c[i];y[++toty]=b[i];y[++toty]=d[i];y[++toty]=d[i]+1;}sort(x+1,x+totx+1);sort(y+1,y+toty+1);for(int i=1;i<=n;i++){a[i]=lower_bound(x+1,x+totx+1,a[i])-x;b[i]=lower_bound(y+1,y+toty+1,b[i])-y;c[i]=lower_bound(x+1,x+totx+1,c[i])-x;e[i]=lower_bound(y+1,y+toty+1,d[i]+1)-y;d[i]=lower_bound(y+1,y+toty+1,d[i])-y;}for(int i=1;i<=n;i++){g2[e[i]].push_back({a[i],c[i],i});g1[b[i]].push_back({a[i],c[i],i});}int cnt=0;for(int i=1;i<=toty;i++){for(auto v:g2[i]){T1.update(1,totx,1,v.l,-1);T2.update(1,totx,1,v.r,-1);cnt--;}for(auto v:g1[i]){T1.update(1,totx,1,v.l,1);T2.update(1,totx,1,v.r,1);cnt++;}for(auto v:g1[i])ans[v.id]+=cnt-1-T1.query(1,totx,1,v.r+1,totx)-T2.query(1,totx,1,1,v.l-1);}T1.clear();T2.clear();cnt=0;for(int i=1;i<=toty;i++){for(auto v:g2[i]){ans[v.id]+=cnt-1-T1.query(1,totx,1,v.r+1,totx)-T2.query(1,totx,1,1,v.l-1);}for(auto v:g1[i]){T1.update(1,totx,1,v.l,1);T2.update(1,totx,1,v.r,1);cnt++;}for(auto v:g1[i])ans[v.id]-=cnt-1-T1.query(1,totx,1,v.r+1,totx)-T2.query(1,totx,1,1,v.l-1);}T1.clear();T2.clear();cnt=0;int val=0;for(int i=1;i<=toty;i++){for(auto v:g2[i]){T1.update(1,totx,1,v.l,-1);T2.update(1,totx,1,v.r,-1);upd(1,totx,1,v.l);upd(1,totx,1,v.r);cnt--;}for(auto v:g1[i]){T1.update(1,totx,1,v.l,1);T2.update(1,totx,1,v.r,1);upd(1,totx,1,v.l);upd(1,totx,1,v.r);cnt++;}for(auto v:g1[i]){int tmp=cnt-1-T1.query(1,totx,1,v.r+1,totx)-T2.query(1,totx,1,1,v.l-1);val+=tmp*(tmp-1)/2-qry(1,totx,1,v.l,v.r).l;}}int tmp1=0,tmp2=0;for(int i=1;i<=n;i++){tmp1+=(n-2)*ans[i];tmp2+=ans[i]*(ans[i]-1)/2;}tmp1/=2;cout<<n*(n-1)*(n-2)/6-(tmp1-tmp2)-val<<'\n';return 0;
}