B - Code Party (girls' competition)

B - Code Party

Sample Input
2
3
3 1 3 1
1 1 2 3
2 1 3 2
5
1 1 4 5
2 1 3 2
2 2 3 3
4 5 4 5
1 2 2 4
Sample Output
0
4

// Now it's time ,2021 year 10 month 28 Number 00:38 I finally ac 了 ,,,, Woo woo 
/* Their thinking   Using the difference and two-dimensional prefix sum, the number of intervals covered on each lattice is calculated g[i][j].  If you ask at this time C(g[i][j],3) And , Then there will be a lot of repetition , Because the same three intervals can cover multiple grids .  So we only keep the grid in the upper left corner of the coverage area , Because this grid must be on the top and left of the interval , So the final answer is ：  The sum of the  -  Delete the sum after the left  -  Delete the sum after the top  +  Delete the sum after the top and left （ This piece has been repeatedly reduced in the front , So add it back ）. */
#include<iostream>
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#define N 1005
using namespace std;
typedef long long ll;
int a1[N][N],a2[N][N],a3[N][N],a4[N][N];
ll c3[100005];
ll wo(int a[N][N])
{
    
    for(int i=1;i<=1000;i++){
    
        for(int j=1;j<=1000;j++){
    
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];// Sum up ;
        }
    }
    ll ans=0;
    for(int i=1;i<=1000;i++){
    
        for(int j=1;j<=1000;j++){
    
            ans+=c3[a[i][j]];  // altogether ( Buckle ) Overlapping ans;
        }
    }
    return ans;
}
int main(){
    
    int T;
    c3[3]=1;
     cin>>T;
    for(int i=4;i<=100000;i++){
    
        c3[i]=(ll)i*(i-1)*(i-2)/6;// If there is i The situation of the same Geke team 
    }
    while(T--)
    {
    
        int n;
        cin>>n;
        memset(a1,0,sizeof(a1));// Each cycle assignment 0;
        memset(a2,0,sizeof(a2));
        memset(a3,0,sizeof(a3));
        memset(a4,0,sizeof(a4));
        int x1,y1,x2,y2;
        for(int i=1;i<=n;i++){
    
         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);// It works cin It's over time , There will be no competition in the future cin;
        a1[x1][y1]++,a1[x2+1][y1]--,a1[x1][y2+1]--,a1[x2+1][y2+1]++;
        // Two dimensional difference , Give (x1,y1) To (x2,y2) Add 1;
        a2[x1+1][y1]++,a2[x2+1][y1]--,a2[x1+1][y2+1]--,a2[x2+1][y2+1]++;
        // Subtract the left from each matrix ( Except for the first line ),x1+1;
        a3[x1][y1+1]++,a3[x2+1][y1+1]--,a3[x1][y2+1]--,a3[x2+1][y2+1]++;
        // Subtract the upper edge from each matrix ( Except for the first column ),y1+1;
        a4[x1+1][y1+1]++,a4[x2+1][y1+1]--,a4[x1+1][y2+1]--,a4[x2+1][y2+1]++;
        // Plus plus minus ;
        }
        cout<<wo(a1)-wo(a2)-wo(a3)+wo(a4)<<endl;
    }
 return 0;
}