Codeforces Round #427 (Div. 2)-C. Star sky(二维前缀和)
题意：
给定n个星星(可能会重)，q次查询，最大的亮度c(<=10)，然后每个星星都在一个平面上(<=100×100)，星星从初始亮度si到c一个时刻一个时刻地变换(si=c+1时,si变为0)，每次查询在t时间从(x1,y1)到(x2,y2)矩形内的所有星星的亮度总和。
思路：
在平面上建立前缀和，因为至多有c+1种时刻，而c<=10，所以完全可以建立c+1个前缀和。在查询时，通过t找到相对应的时刻，然后矩形内的亮度和就等于sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
代码：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+5;
struct node
{
int x, y, w;
} num[maxn];
int sum[15][105][105], a[105][105];
int n, q, c;
void init()
{
memset(sum, 0, sizeof sum);
for(int t = 0; t <= 10; ++t)
{
memset(a, 0, sizeof a);
for(int i = 1; i <= n; ++i)
a[num[i].x][num[i].y] += num[i].w;
for(int i = 1; i <= 100; ++i)
for(int j = 1; j <= 100; ++j)
{
sum[t][i][j] = sum[t][i-1][j]+sum[t][i][j-1]-sum[t][i-1][j-1]+a[i][j];
}
for(int i = 1; i <= n; ++i)
{
++num[i].w;
num[i].w %= (c+1);
}
}
}
int main()
{
int x1, y1, x2, y2, w, t, ans;
scanf("%d %d %d", &n, &q, &c);
for(int i = 1; i <= n; ++i)
scanf("%d %d %d", &num[i].x, &num[i].y, &num[i].w);
init();
for(int _ = 1; _ <= q; ++_)
{
scanf("%d %d %d %d %d", &t, &x1, &y1, &x2, &y2);
t %= (c+1);
ans = sum[t][x2][y2]-sum[t][x2][y1-1]-sum[t][x1-1][y2]+sum[t][x1-1][y1-1];
printf("%d\n", ans);
}
return 0;
}继续加油~