P3397 地毯

推薦事前閱讀：二維差分數組介紹\

思路

在寫的過程要注意，差分數組裡面不能存放原始資料，
否則會在計算每一格的數值變動時，錯誤的把原始數值也傳遞下去，導致一系列的錯誤。

程式碼

二維前綴合

#include <iostream>
#include <string.h>
using namespace std;
const int MX = 1005;
int diff[MX][MX];
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; 
    cin >> n >> m;
    int x1, y1, x2, y2;
    for(int i = 0; i < m; i++) {
        cin >> x1 >> y1 >> x2 >> y2; // 題目是 1-index 的, 不需要在這裡將座標 + 1
        diff[x1][y1]++;
        diff[x1][y2 + 1]--;
        diff[x2 + 1][y1]--;
        diff[x2 + 1][y2 + 1]++;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
        }
    }
    for(int i = 1; i <= n; i++) {
        cout << diff[i][1];
        for(int j = 2; j <= n; j++) {
            cout << " " << diff[i][j];
        }
        cout << "\n";
    }
}

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$