codeforces 835C(二维前缀和)

题意：给出一些点的值，查询在一个时间点一段区间的值。点的值会随时间每次增加一，然后取(k + 1)的模。

思路：以为k是<=10，所以可以把每个时刻每一段的前缀和弄出来，然后查询的时候就行。

PS：一个点不只是一个值，在这个地方被卡。二维前缀和的构造和维护可以复习一下。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int maxn = 100000 + 10;
typedef long long ll;
#define INF 0x3f3f3f3f

int a[12][maxn];
P b[maxn];
int sum[12][110][110];
int maze[12][110][110];
int main()
{
    int n,m,k;
    while(  ~ scanf("%d%d%d",&n,&m,&k))
    {
        memset(sum,0,sizeof(sum));
        memset(maze,0,sizeof(maze));
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d%d%d",&b[i].first,&b[i].second,&a[0][i]);
        }
        for(int i = 0; i <= k; i ++)
        {
            for(int j = 1; j <= n; j ++)
            {
                maze[i][b[j].first][b[j].second] += (a[0][j] + i) % (k + 1);
            }
        }

        for(int ks = 0;ks <= k; ks ++)
        {
            for(int i = 1; i < 110; i ++)
            {
                for(int j = 1; j < 110; j ++)
                {
                    sum[ks][i][j] = sum[ks][i][j - 1] + sum[ks][i - 1][j] - sum[ks][i - 1][j - 1] + maze[ks][i][j];
                }
            }
        }
        for(int i = 1; i <= m; i ++)
        {
            int t,x1,y1,x2,y2;scanf("%d%d%d%d%d",&t,&x1,&y1,&x2,&y2);
            printf("%d\n",sum[t % (k + 1)][x2][y2] - sum[t % (k + 1)][x2][y1 - 1] - sum[t % (k + 1)][x1 - 1][y2] + sum[t % (k + 1)][x1 - 1][y1 - 1] );
        }
    }
    return 0;
}