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;
}