题解 | #异或炸弹(hard)#

#include <vector>

using namespace std;
const int N = 6010;

int n, m;
int c[N][N];

void add(int x1, int y1, int x2, int y2){
    
    c[x1][y1]++;
    c[x1][y2 + 1]--;
    c[x2 + 1][y1]--;
    c[x2 +  1][y2 + 1]++;
}

int main(){
    cin >> n >> m;
    vector<int> x(m + 1), y(m + 1), r(m + 1);
    for(int i = 1; i <= m; i++){
        cin >> x[i] >> y[i] >> r[i];
        int x1 = x[i] + y[i];
        int y1 = x[i] - y[i] + 3000;
        add(max(1, x1 - r[i]), max(1, y1 - r[i]), min(6000, x1 + r[i]), min(6000, y1 + r[i]));
    }
    
    int ans = 0;
    //通过切比雪夫距离转换成曼哈顿距离来求答案
    for(int i = 1; i <= 6000; i++){
        for(int j = 1; j <= 6000; j++){
            c[i][j] += c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1];
            int x1 = (i + j - 3000) / 2;
            int y1 = (i - j + 3000) / 2;
//             关于这里x1为什么等于(i + j - 3000) / 2
//             设x1，y1为曼哈顿距离的坐标
//             x2, y2为曼哈顿距离转换成切比雪夫距离后的坐标
//             那么(1)x2 = x1 + y1;
//                 (2)y2 = x1 - y1 + 3000 (由于y2可能为负，坐标偏移)
//             由(2)式可得y1 = x1 - y2 + 3000
//             代入(1)式 得到x1 = (x2 + y2 - 3000) / 2;
//             同理可得y1;
            if((i + j) % 2 == 1 || x1 > n || x1 < 1 || y1 > n || y1 < 1)continue;
            if(c[i][j] & 1)ans++;
        }
    }
    
    //通过曼哈顿距离转换成切比雪夫距离来求答案
//     for(int i = 1; i <= n; i++){
//         for(int j = 1; j <= n; j++){
//             int x1 = i + j;
//             int y1 = i - j + 3000;
//             if(c[x1][y1] & 1)ans++;
//         }
//     }
    
    cout << ans << endl;
}