题解：P13787 地毯 加强版

· · 题解

问题分析

本题要求计算 n \times n 网格中每个点被多少个地毯覆盖，然后计算所有点 (i+j) \oplus F_{i,j} 的总和（其中 F_{i,j} 是该点被覆盖的次数）。

算法思路

一眼二维差分+前缀和，具体思路见注释

代码实现

#include<iostream>
#include<vector>
using namespace std;
int main(){
    // 关闭输入输出同步，加速cin/cout
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,m;cin>>n>>m; // n:网格大小，m:地毯数量
    // 二维差分矩阵，大小(n+2)x(n+2)避免边界越界
    vector<vector<int>>d(n+2,vector<int>(n+2,0));

    // 处理每个地毯的区域标记
    while(m--){
        int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2; // 地毯的左上角和右下角坐标
        // 差分矩阵更新：对矩形区域[x1,y1]-[x2,y2]做+1标记
        d[x1][y1]++;         // 左上角+1
        d[x1][y2+1]--;       // 右上角右侧-1（抵消多余部分）
        d[x2+1][y1]--;       // 左下角下方-1（抵消多余部分）
        d[x2+1][y2+1]++;     // 右下角右下方+1（恢复抵消）
    }

    // 计算行前缀和：将每行的差分累积，得到临时覆盖次数
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            d[i][j]+=d[i][j-1];

    // 计算列前缀和：将每列的差分累积，得到最终覆盖次数F[i][j]
    for(int j=1;j<=n;j++)
        for(int i=1;i<=n;i++)
            d[i][j]+=d[i-1][j];

    // 计算结果：累加所有(i+j)异或F[i][j]
    long long r=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            r+=(i+j)^d[i][j]; // ^表示异或运算

    cout<<r; // 输出总和
    return 0; //完美结束
}