B - 代码派对(女生赛)

B - 代码派对

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

//现在时刻,2021年10月28号00:38我终于ac了,,,,呜呜呜呜
/*解题思路 利用差分和二维前缀和求出每个格子上覆盖的区间数g[i][j]。 如果这个时候求C(g[i][j],3)的和，那么会产生很多的重复，因为同样的三个区间可以覆盖多个格子。 所以我们只保留覆盖区域左上角的那个格子，因为这个格子一定在区间的上边和左边上，所以最后答案为： 总和 - 删掉左边后的和 - 删掉上边后的和 + 删掉上边和左边后的和（前面重复减了这一块，所以加回去）。 */
#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];//求和;
        }
    }
    ll ans=0;
    for(int i=1;i<=1000;i++){
    
        for(int j=1;j<=1000;j++){
    
            ans+=c3[a[i][j]];  //一共(包扣)重叠的有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;//如果有i人选同一个格可组队情况
    }
    while(T--)
    {
    
        int n;
        cin>>n;
        memset(a1,0,sizeof(a1));//每次循环赋值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);//这用cin就超时了,以后比赛再无cin;
        a1[x1][y1]++,a1[x2+1][y1]--,a1[x1][y2+1]--,a1[x2+1][y2+1]++;
        //二维差分,给以(x1,y1)到(x2,y2)的矩阵都加1;
        a2[x1+1][y1]++,a2[x2+1][y1]--,a2[x1+1][y2+1]--,a2[x2+1][y2+1]++;
        //每个矩阵减去左边(除了第一行),x1+1;
        a3[x1][y1+1]++,a3[x2+1][y1+1]--,a3[x1][y2+1]--,a3[x2+1][y2+1]++;
        //每个矩阵减去上边(除了第一列),y1+1;
        a4[x1+1][y1+1]++,a4[x2+1][y1+1]--,a4[x1+1][y2+1]--,a4[x2+1][y2+1]++;
        //加上多减的;
        }
        cout<<wo(a1)-wo(a2)-wo(a3)+wo(a4)<<endl;
    }
 return 0;
}