[ABC331D] Tile Pattern

yhx0322 · 2023-12-03 13:17:00 · 题解

Description

给你一个 10^9 \times 10^9 的矩阵，并给出字符数组 P，大小为 n \times n。

正方形中 (i,j) 格子的颜色为 P[i \bmod n][j \bmod n]。

每次询问给出四个变量 A,B,C,D，表示左上角坐标 (A,B) 和右下角坐标 (C,D) 的正方形中黑色格子的数量。

Solution

思想不难，难在代码调试与边界讨论。

对 n \times n 的矩阵记录二维前缀和 sm_{i,j}。

假设目前要求 \text{query}(x,y)，对 x,y 可以分三种情况讨论：

• 若 x \ge n,y \ge n，则答案等于

  sm_{n-1,n-1} \times \lfloor \dfrac{x}{n} \rfloor \times \lfloor \dfrac{y}{n} \rfloor+\text{query}(x \bmod n,y)+\text{query}(x-(x \bmod n)-1,y \bmod n)

• 若 x \ge n，则答案等于

  sm_{n-1,y} \times \lfloor \dfrac{x}{n} \rfloor +\text{query}(x \bmod n,y)

• 若 y \ge n，则答案等于

  sm_{x,n-1} \times \lfloor \dfrac{y}{n} \rfloor+\text{query}(x,y \bmod n)

• 否则，答案等于 sm_{x,y}。

Code

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

const int N = 1e3 + 10;
int A, B, C, D, n, p[N][N];
char s[N];
ll sm[N][N];

ll query(int x, int y) {
    if (x < 0 || y < 0) return 0;
    if (x >= n && y >= n)
        return sm[n][n] * (x / n) * (y / n) + query(x % n, y) + query(x - (x % n) - 1, y % n);
    if (x >= n)
        return sm[n][y + 1] * (x / n) + query(x % n, y);
    if (y >= n)
        return sm[x + 1][n] * (y / n) + query(x, y % n);
    return sm[x + 1][y + 1];
}

int main() {
    scanf("%d", &n);
    int q;
    scanf("%d", &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= n; ++j) {
            p[i][j] = (s[j] == 'B');
            sm[i][j] = p[i][j] + sm[i - 1][j] + sm[i][j - 1] - sm[i - 1][j - 1];
        }
    }
    while (q--) {
        scanf("%d%d%d%d", &A, &B, &C, &D);
        printf("%lld\n", query(C, D) - query(A - 1, D) - query(C, B - 1) + query(A - 1, B - 1));
    }
    return 0;
}