[GxOI]一闪一闪亮晶晶

题目

题目背景

著名神犇fcj热爱看星星，有一天，她买下了哈勃望远镜，邀请你来看星星，但是在观察之后要让你给出一份报告，否则就无法使用哈勃望远镜，作为一个天文爱好者，你必须完美解决这份报告问题。

题目描述

哈勃望远镜的视野辽阔，以致于你可以看见三体的舰队，在雪地中，你可以看见nn艘飞船，第i艘飞船有一个坐标(xi,yi)。我们有一个最大能量值maxcmaxc，表示对于所有飞船，它们的能量值最大不超过maxc，

每一艘飞船刚开始有一个能量值$$z_i(0 \leq z_i \leq maxc )$$，飞船总是在不停地进行聚变反应，在00时刻第ii艘飞船有zizi的能量值。假设，tt时刻有一艘飞船的能量值是x，那么(t+1)时刻，这艘飞船的能量值将会是x+1，但是如果x+1 > maxc 下一秒它的能量值就是0。

夜色美好，但是你必须被fcj强迫着去看q次飞船，每一次你会在titi时刻看一眼美好的夜空，然后看见一个矩形，左下角是(x1i,y1i)，右上角是(x2i,y2i)，对于每一次看天，为了世界和平，伟大的fcj总要让你记录下来这个观察到的矩形的能量值之和。

（矩形包括边界）

输入输出格式

输入格式

第一行3个整数，n,q,maxc，具体意义如题面所示。

接下来n行，每行有3个整数，分别为坐标xi,yi,和当前飞船的能量值zi。

接下来q行，每一行5个整数，分别代表观察时间ti，观察矩形$$x{1i},y{1i},x{2i},y{2i}$$

输出格式：

输出q行，每一行一个整数，表示答案。

输入输出样例

输入样例1

2 3 3
1 1 1
3 2 0
2 1 1 2 2
0 2 1 4 5
5 1 1 5 5

输出样例1

3
0
3

输入样例2

3 4 5
1 1 2
2 3 0
3 3 1
0 1 1 100 100
1 2 2 4 4
2 2 1 4 7
1 50 50 51 51

输出样例2

3
3
5
0

数据范围

$$n,q \leq 10^5,0 \leq maxc \leq 10$$

$$1 \leq x_i,y_i \leq 100,0 \leq z_i \leq 10$$
​$$0 \leq t_i \leq 10^9$$

思路

二维前缀和+容斥

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100000+5;
inline long long read() {
    long long sum=0,flag=1;
    char c=getchar();
    while(c<'0' || c>'9') {
        if(c=='-')
            flag=-1;
        c=getchar();
    }
    while(c>='0' && c<='9') {
        sum=sum*10+(long long)(c-'0');
        c=getchar();
    }
    return sum*flag;
}
int n,q,maxc;
struct C {
    int x,y,s;
} a[maxn];
int map[15][105][105]= {0};
int main() {
    ios::sync_with_stdio(false);
    n=read(),q=read(),maxc=read();
    for(int i=1; i<=n; i++)
        a[i].x=read(),a[i].y=read(),a[i].s=read();
    for(int j=0; j<=maxc; j++) {
        for(int i=1; i<=n; i++) {
            map[j][a[i].x][a[i].y]+=(a[i].s+j)%(maxc+1);
        }
    }
    for(int i=0; i<=maxc; i++) { 
        for(int j=1; j<=104; j++) {
            for(int k=1; k<=104; k++) {
                map[i][j][k]+=map[i][j-1][k]+map[i][j][k-1]-map[i][j-1][k-1];
            }
        }
    }
    for(int i=1; i<=q; i++) {
        int t,x1,x2,y1,y2;
        t=read(),x1=read(),y1=read(),x2=read(),y2=read();
        t%=(maxc+1);
        int ans=map[t][x2][y2]-map[t][x1-1][y2]-map[t][x2][y1-1]+map[t][x1-1][y1-1];
        cout<<ans<<endl;
    }
    return 0;
}

——代码来自YQH