https://ac.nowcoder.com/acm/contest/317/E

C++版本一

std 

题解:差分

由于n, m只有1000,且没有修改操作。
那么考虑二维差分。直接上可以不太好实现,我们菱形分为上下两部分
对于上半部分来说:把标记分为两种(向左下放/向右下放),首先在最顶端打上+1的标记,再分别在
最下端的两边打上-1的标记
每次分别下放即可
注意不要越界,一个不错的解决方法是对所有操作加一个偏移量,最后只统计原矩形的贡献
时间复杂度:𝑂(𝑞 + 𝑛2)

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int MAXN = 1e6 + 10, MAX = 5001, INF = 1e9 + 10, base = 1201;
void chmin(int &a, int b) {a = (a < b ? a : b);}
void chmax(int &a, int b) {a = (a > b ? a : b);}
int sqr(int x) {return x * x;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, Q, type[MAXN], a[MAX][MAX], opt[MAX][MAX][2], b[MAX][MAX], xx[MAXN], yy[MAXN], ll[MAXN]; 
void solve1(int x, int y, int len) {
    len /= 2;
    a[x - len][y]++;
    if(len == 0) return ;
    opt[x - len + 1][y - 1][0]++; 
    opt[x - len + 1][y + 2][1]--;
    opt[x + 1][y - len - 1][0]--;
    opt[x + 1][y + len + 2][1]++;
}
void solve2(int x, int y, int len) {
    len /= 2;
    if(len == 0) return ;
    a[x + len][y]++;
    opt[x + len - 1][y - 1][0]++;
    opt[x + len - 1][y + 2][1]--;
    opt[x][y - len][0]--;
    opt[x][y + len + 1][1]++;
}
void print() {
    puts("");
    for(int i = 0; i <= N + base * 2; i++, puts(""))
        for(int j = 0; j <= M + base * 2; j++)
            printf("%d ", a[i][j] + b[i][j]);
}
signed main() {
    //freopen("a.in", "r", stdin);
    N = read(); M = read(); Q = read();
    for(int i = 1; i <= Q; i++) type[i] = read(), xx[i] = read() + base, yy[i] = read() + base, ll[i] = read();
    for(int i = 1; i <= Q; i++) solve1(xx[i], yy[i], ll[i]);
    for(int i = 0; i <= N + 2 * base; i++) {
        int sum = 0;
        for(int j = 0; j <= M + 2 * base; j++) {
            sum += opt[i][j][0] + opt[i][j][1];
            a[i][j] += sum;
            opt[i + 1][j - 1][0] += opt[i][j][0];
            opt[i + 1][j + 1][1] += opt[i][j][1];
        }	
    }
    memcpy(b, a, sizeof(a));
    memset(a, 0, sizeof(a));
    memset(opt, 0, sizeof(opt));
    for(int i = 1; i <= Q; i++) if(type[i] == 1) solve2(xx[i], yy[i], ll[i]);
    for(int i = N + base * 2; i >= 0; i--) {
        int sum = 0;
        for(int j = 0; j <= M + 2 * base; j++) {
            sum += opt[i][j][0] + opt[i][j][1];
            a[i][j] += sum;
            opt[i - 1][j - 1][0] += opt[i][j][0];
            opt[i - 1][j + 1][1] += opt[i][j][1];
        }
    }
    //print();
    int ans = 0;
    for(int i = 1 + base; i <= N + base; i++)
        for(int j = 1 + base; j <= M + base; j++)
            ans ^= (a[i][j] + b[i][j]);
    cout << ans;
    return 0;
}