[ABC260G] Scalene Triangle Area 题解

题意：

我们有一个 $N \times N$ 的网格。在这个网格中，从顶部数起的第 $i$ 行、从左侧数起的第 $j$ 列的方格被称为 $(i, j)$。

网格的每个方格最多放置一个棋子。网格的状态由 $N$ 个字符串 $S_i$ 给出：

如果 $S_i$ 的第 $j$ 个字符为 0，则 $(i, j)$ 上有一个棋子；

如果 $S_i$ 的第 $j$ 个字符为 X，则 $(i, j)$ 上没有棋子。

给定一个整数 $M$。使用这个 $M$，我们定义当位于 $(s, t)$ 的棋子 $P$ 覆盖方格 $(u, v)$ 时，需要满足以下所有条件：

$s \leq u \leq N$

$t \leq v \leq N$

$(u-s)+\frac{(v-t)}{2}<M$

对于 $Q$ 个方格 $(X_i, Y_i)$，找出有多少个棋子覆盖了该方格。

输入格式：

第一行 $N,M$ ，接下来 $N$ 行 $S_1\sim S_N$ 。

下一行给定 $Q$ ，接下来 $Q$ 行 $X_i,Y_i$ 。

输出格式：

输出 $Q$ 行，表示每次询问的答案。

数据范围

$N, M, X_i, Y_i$ 和 $Q$ 是整数，$S_i$ 由 O 和 X 组成。

$1 \leq N \leq 2000,~1 \leq M \leq 2 \times N,~1 \leq Q \leq 2 \times 10^5,~1 \leq X_i, Y_i \leq N$

可以发现这个 O 可以维护的东西大概长下面这样

OOOOOO
OOOO
OO

我们可以尝试差分

1 0 0 0 0 0 -1
1 0 0 0 -1
1 0 -1

但是这样还是没有解决复杂度的问题。考虑二维差分，也就是在差分的基础上再差分一次。

注意到第一列有很多 $1$ ，以及右侧有斜线的 $-1$ 堆。显然这个不能同时维护，我们可以分两个数组维护

1 0 0 0 0 0 0			0 0 0 0 0 0 -1
0 0 0 0 0				0 0 0 0 0
0 0 0					0 0 0
-1						1

左侧就是简单的差分，右侧的话我们只需要把贡献方式改成从 $(x-1,y+2)$ 即可。

时间复杂度 $\mathcal{O}(nm)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e3 + 15))

int n,m,sum[N][N],val[2][N][N * 5];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; char c;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) {
            if(cin >> c, c == 'O')
            {
                ++val[0][i][j]; --val[0][min(n + 1, i + m)][j];
                --val[1][i][j + 2 * m]; ++val[1][min(n + 1, i + m)][j];
            }
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n + 2 * m; j++)
        {
            val[0][i][j] += val[0][i - 1][j];
            val[1][i][j] += val[1][i - 1][j + 2];
            if(j <= n) { sum[i][j] = sum[i][j - 1] + val[0][i][j] + val[1][i][j]; }
        }
    int Q; cin >> Q;
    for(int x,y; Q--; )
    {
        cin >> x >> y;
        cout << sum[x][y] << '\n';
    }
    return 0;
}