累積和、いもす法(ARC089D - Checker)

atcoder.jp

まず、市松模様を並行移動していくと、縦横それぞれKずつ動かした時に塗り方としては全く同じになる。また、2Kのマスをとると完全に繰り返しになるので、座標は2Kで割った余りにして良い。
白に塗るマスの指定はどちらか方向にKずらすことで黒く塗る司令にできる。

この時、模様のパターンについては、黒い領域が始まる左下を指定することで定める。
点Nが塗られているかについては、「リクエストiが満たされる黒い領域の左下の範囲」N個分の、二次元の累積和を取れば良い。二次元の累積和を初めて使った。
このサイトを参考にした。
https://imoz.jp/algorithms/imos_method.html

気をつけなきゃいけないことは行ごとに累積和を取ってから列方向に累積和をとること、左上と右下に+1、右上と左下に-1を置くことだ。

あってるはずなんだけど、端が切れてしまうあたりがうまくいってなくてWAする…
とりあえず置いとく

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>

 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long

int xs[10004],ys[10004];
int start[4004][4004];

int main(void){
    int N,K;
    scanf("%d %d",&N,&K);
    
    rep(i,N){
        int x,y;
        char z;
        scanf("%d %d %c",&x,&y,&z);
        if(z=='W')x+=K; //convert to black
        
        
        xs[i]=x%(2*K);ys[i]=y%(2*K);
        int strx=min( (xs[i]-K+(2*K))%(2*K),(xs[i]+(2*K))%(2*K) );
        int stry=min( (ys[i]-K+(2*K))%(2*K),(ys[i]+(2*K))%(2*K) );
        int endx=max( (xs[i]-K+(2*K))%(2*K),(xs[i]+(2*K))%(2*K) )+1;
        int endy=max( (ys[i]-K+(2*K))%(2*K),(ys[i]+(2*K))%(2*K) )+1;
        start[strx][stry]++;start[strx][endy]--;
        start[endx][stry]--;start[endx][endy]++;
        start[strx+2*K][stry]++;start[strx+2*K][endy]--;
        start[endx+2*K][stry]--;start[endx+2*K][endy]++;
        start[strx+2*K][stry+2*K]++;start[strx+2*K][endy+2*K]--;
        start[endx+2*K][stry+2*K]--;start[endx+2*K][endy+2*K]++;
        start[strx][stry+2*K]++;start[strx][endy+2*K]--;
        start[endx][stry+2*K]--;start[endx][endy+2*K]++;
    }
    
    for (int y = 0; y <4*K; y++) {
      for (int x = 1; x < 4*K; x++) {
        start[y][x] += start[y][x-1];
      }
    }
    for (int y = 1; y < 4*K; y++) {
      for (int x = 0; x < 4*K; x++) {
        start[y][x] += start[y-1][x];
      }
    }
    int ans=0;
    for(int i=K;i<3*K;i++){
        for(int j=K;j<3*K;j++){
            ans=max(start[i][j],ans);
        }
    }
    printf("%d\n",ans);
}