Codefores 835C-Star sky

835C-Star sky

思路：dp，预处理一下c+1层前缀和。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
const int INF=0x3f3f3f3f;
const int N=105;
int mp[12][N][N];
int dp[12][N][N]={0};
int main()
{
    /*ios::sync_with_stdio(false);
    cin.tie(0);*/
    int n,q,x,y,s,c;
    memset(mp,-1,sizeof(mp));
    scanf("%d%d%d",&n,&q,&c);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&s);
        for(int i=0;i<c+1;i++)
        {
            dp[i][x][y]+=(s+i)%(c+1);//注意同一点有多颗星星的情况
        }
    }
    for(int i=0;i<c+1;i++)
    {
        for(int j=1;j<=100;j++)
        {
            for(int k=1;k<=100;k++)
            dp[i][j][k]+=dp[i][j-1][k]+dp[i][j][k-1]-dp[i][j-1][k-1];//容斥一下
        }
    }
    while(q--)
    {
        int t,x1,x2,y1,y2;
        scanf("%d%d%d%d%d",&t,&x1,&y1,&x2,&y2);
        t=t%(c+1);
        printf("%d
",dp[t][x2][y2]+dp[t][x1-1][y1-1]-dp[t][x2][y1-1]-dp[t][x1-1][y2]);//容斥一下
    }
    return 0;
}