对于这种题肯定想到的是前缀和,但是有个问题是我们发现每个星星的颜色不一定一样,这样就多出一个变量不好控制
因此我们想到dp状态 f[k][i][j]表示能量为k的星星的前缀和,这样就方便维护了。因为我们发现星星的能量不超过10
#include<iostream> #include<cstring> #include<cstdio> #include<map> #include<algorithm> #define ull unsigned long long using namespace std; typedef long long ll; const int N=1e5+10; int f[12][110][110]; int main(){ int n; cin>>n; int q,c; cin>>q>>c; int k,i,j; for(i=1;i<=n;i++){ int x,y,s; scanf("%d%d%d",&x,&y,&s); f[s][x][y]++; } for(k=0;k<=c;k++){ for(i=1;i<=110;i++){ for(j=1;j<=110;j++){ f[k][i][j]+=(f[k][i-1][j]+f[k][i][j-1]-f[k][i-1][j-1]); } } } ll ans=0; while(q--){ ans=0; int t,x1,y1,x2,y2; scanf("%d%d%d%d%d",&t,&x1,&y1,&x2,&y2); ll res=0; for(i=0;i<=c;i++){ res=f[i][x2][y2]-f[i][x1-1][y2]-f[i][x2][y1-1]+f[i][x1-1][y1-1]; ans+=res*((i+t)%(c+1)); } cout<<ans<<endl; } }