[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;
}