Codeforces Round #427 (Div. 2)C. Star sky

傳送門

題意：n個星，q組詢問，亮度最大值是c，c+1的時候亮度為0。然後重新亮。下面給你星星的坐标和初始亮度，然後q裡面是時間和矩形左下和右上的坐标，問你在這個矩形能看到多少亮度。

思路：二維字首和，或者存點二分。存點二分還沒寫，如果有空再寫。這裡給出思路。存好點之後存入結構體。注：有可能有初始亮度為0的點。

對結構體的點進行排序。x小的y小的在前面。二分符合矩形框的點。然後while處理直到不在矩形範圍。

//china no.1
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <vector>
#include <iostream>
#include <string>
#include <map>
#include <stack>
#include <cstring>
#include <queue>
#include <list>
#include <stdio.h>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <cctype>
#include <sstream>
#include <functional>
#include <stdlib.h>
#include <time.h>
#include <bitset>
using namespace std;

#define pi acos(-1)
#define endl '\n'
#define srand() srand(time(0));
#define me(x,y) memset(x,y,sizeof(x));
#define foreach(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();it++)
#define close() ios::sync_with_stdio(0); cin.tie(0);
#define FOR(x,n,i) for(int i=x;i<=n;i++)
#define FOr(x,n,i) for(int i=x;i<n;i++)
#define W while
#define sgn(x) ((x) < 0 ? -1 : (x) > 0)
#define bug printf("***********\n");
typedef long long LL;
const int INF=0x3f3f3f3f;
const LL LINF=0x3f3f3f3f3f3f3f3fLL;
const int dx[]={-1,0,1,0,1,-1,-1,1};
const int dy[]={0,1,0,-1,-1,1,-1,1};
const int maxn=1e5+10;
const int maxx=1e4+100;
const double EPS=1e-7;
const int MOD=10000007;
#define mod(x) ((x)%MOD);
template<class T>inline T min(T a,T b,T c) { return min(min(a,b),c);}
template<class T>inline T max(T a,T b,T c) { return max(max(a,b),c);}
template<class T>inline T min(T a,T b,T c,T d) { return min(min(a,b),min(c,d));}
template<class T>inline T max(T a,T b,T c,T d) { return max(max(a,b),max(c,d));}
inline int Scan()
{
    int Res=0,ch,Flag=0;
    if((ch=getchar())=='-')Flag=1;
    else if(ch>='0' && ch<='9')Res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')Res=Res*10+ch-'0';
    return Flag ? -Res : Res;
}
//freopen( "in.txt" , "r" , stdin );
//freopen( "data.out" , "w" , stdout );
//cerr << "run time is " << clock() << endl;
int n,q,c,c1;
struct node
{
    int x,y;
}Q[maxn];
LL C[22][107][107],s[22][107][107];
int t,x1,y3,x2,y2;
int main()
{
    cin>>n>>q>>c;
    for(int i=1;i<=n;i++)
    {
        //cin
        int x,y;
        x=Scan(),y=Scan();
        Q[i].x=x;Q[i].y=y;
        c1=Scan();
        C[c1][x][y]++;
    }
    for(int i=0;i<=c;i++)
        for(int k=1;k<=105;k++)
            for(int z=1;z<=105;z++)
                s[i][k][z]=s[i][k][z-1]+
                s[i][k-1][z]-s[i][k-1][z-1]+C[i][k][z];
    while(q--)
    {
        t=Scan();x1=Scan();y3=Scan();x2=Scan();y2=Scan();
        LL ans=0;
        t%=(c+1);
        for(int i=0;i<=c;i++)
            ans+=((i+t)%(c+1))*(s[i][x2][y2]-s[i][x1-1][y2]
                    +s[i][x1-1][y3-1]-s[i][x2][y3-1]);
        cout<<ans<<endl;
    }
}