二维前缀和

• 求二维数组里每一个数到（1，1）这个数的面积//xy分别为你要求的多大区域的面积，红色框框区域

  
  
  画的有点丑的图

模块U样例

for(int i=1;i<=x;i++)
for(int j=1;j<=y;j++){
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];

如果我们现在要求蓝色框框的面积怎么办呢，线代没白学。

• 运用分块方阵求解

  
  
  各自的面积
  
  

  （设蓝色框框右下角的元素坐标为i，j）
  要求的蓝色框框的面积=图4-图2-图3+图1//因为图1无辜地被减了两次

模板U样例

sum=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]

回到中大的题目上

标记法
对于A类矩形(x1,y1,x2,y2)，我们只需要在(x1,y1),(x2+1,y2+1)处+1，在（x1,y2+1）(x2+1,y1)处-1

explain

菜鸟版本

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define ll long long
using namespace std;

int a[1001][1001];
void qian(int x,int y){
    for(int i=1;i<=x;i++)
        for(int j=1;j<=y;j++){
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
}
int main()
{
    freopen("data","r",stdin);
    int n,m,N,M,x1,x2,y1,y2;
        scanf("%d%d",&n,&m);
        cin>>N;
        memset(a,0,sizeof(a));
        for(int i=0;i<N;i++){
            cin>>x1>>y1>>x2>>y2;
            a[x1][y1]+=1,a[x2+1][y2+1]+=1,a[x2+1][y1]-=1,a[x1][y2+1]-=1;
        }
        qian(n,m);
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                if(a[i][j]>0)
                    a[i][j]=1;
        qian(n,m);
        //接下来才是真正的求面积，然后进行比较即可
        cin>>M;
        for(int i=0;i<M;i++){
            cin>>x1>>y1>>x2>>y2;
            int sum1=(y2-y1+1)*(x2-x1+1);
            int sum2=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
            if(sum1==sum2)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }

return 0;
}

因为数组太大了，用STL的vector创建二维数组

师兄版本

#include <bits/stdc++.h>
using namespace std;

vector<vector<int> > a;//这里的两个>要分开一点
int n,m;
void add(int x1,int y1,int x2,int y2) {
    a[x1][y1]++;
    a[x2+1][y2+1]++;
    a[x1][y2+1]--;
    a[x2+1][y1]--;
}

void solve() {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);//如果用cin和cout的话会耗时，所以加这一句
    while(cin>>n>>m) {
        a.clear();
        a.resize(n+2,vector<int>(m+2,0));//二维数组初始化为0
        int p,q,x1,x2,y1,y2;
        cin>>p;
        while(p--) {
            cin>>x1>>y1>>x2>>y2;
            add(x1,y1,x2,y2);
        }
        solve();
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]) a[i][j]=1;
        solve();
        cin>>q;
        while(q--) {
            cin>>x1>>y1>>x2>>y2;
            int L=(y2-y1+1)*(x2-x1+1);
            int R=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
            if(L==R) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
}