P13787 二维差分模板

· · 题解

题目传送门：P13787 地毯 加强版

题目解法

二维差分板子。根据题目，如果有一个地毯的左上角 (x_1,y_1) 满足 x_1 \leqslant i 且 y_1 \leqslant j，则其会为 f_{i,j} 贡献 1。因此我们用二维前缀和推 f_{i,j} 的话，就要在 (x_1,y_1) 处加上 1。

现在我们发现，如果 x_2 > i 或 y_2 > j，这块地毯其实不应该贡献（但贡献了），那么我们需要在 (x_1,y_2+1) 和 (x_2+1,y_1) 处各减 1。

现在我们又发现，如果 x_2 > i 且 y_2 > j，这块地毯虽然不应该贡献，但它被删了两次，因此我们还需要在 (x_2+1,y_2+1) 处再加回来。

现在再二维前缀和，得到的就是正确的结果了。

二维前缀和：我们设 f_{x,y} 为所有 i \leqslant x 且 j \leqslant y 的 d_{i,j} 之和，则可以找出递推关系。

若让 f_{i,j} 为 f_{i-1,j}+f_{i,j-1}，则 f_{i-1,j-1} 会贡献两次，因此再减掉它即可。

代码实现

#include<iostream>
using namespace std;
const int N=5003;
int n,m,d[N][N],f[N][N];
long long ans;
int main(){
    cin>>n>>m;
    while(m--){
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        d[x1][y1]++;
        d[x1][y2+1]--;
        d[x2+1][y1]--;
        d[x2+1][y2+1]++;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+d[i][j];
            ans+=i+j^f[i][j];
        }
    }
    cout<<ans;
    return 0;
}

AC 记录。