Codeforces 835C(二维前缀和)

Codeforces 835C
注意$c$很小,每个权值开一个二维前缀和维护即可
然后每个询问按照权值求值即可

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 ""
using namespace std;
LL n, q, c;
LL a[105][105][15];
LL query(LL x1, LL y1, LL x2, LL y2, LL col) {
return a[x2][y2][col] - a[x1 - 1][y2][col] - a[x2][y1 - 1][col] + a[x1 - 1][y1 - 1][col];
}
void clean() {
ms(a, 0);
}
void solve() {
clean();
for (LL i = 1; i <= n; i++) {
LL x, y, s; scanf("%I64d%I64d%I64d", &x, &y, &s);
a[x][y][s] += 1;
}
for (LL i = 1; i <= 100; i++)
for (LL j = 1; j <= 100; j++)
for (LL k = 0; k <= c; k++) {
a[i][j][k] = a[i - 1][j][k] + a[i][j - 1][k] - a[i - 1][j - 1][k] + a[i][j][k];
}
while (q--) {
LL t, xa, ya, xb, yb;
scanf("%I64d%I64d%I64d%I64d%I64d", &t, &xa, &ya, &xb, &yb);
LL ans = 0;
for (int i = 0; i <= c; i++) {
LL num = query(xa, ya, xb, yb, i);
LL p = (t + i) % (c + 1);
ans += p * num;
}
printf("%I64d\n", ans);
}
}
int main() {
scanf("%I64d%I64d%I64d", &n, &q, &c), solve();
fclose(stdin); fclose(stdout);
return 0;
}

------ 本文结束 ------