题解：AT_ndpc2026_h コイン拾い
manboo
·
·
题解
题意概述：
正难则反，考虑对于每个格子 $\left(i,j\right)$，对硬币数的贡献是多少，即求处于 $\left(i,j\right)$ 时，可能有多少枚硬币。
手搓一下样例，发现一件神奇的事：每个格子对硬币数的贡献是一段连续的区间！
具体来说，设从 $\left(1,1\right)$ 到 $\left(i,j\right)$ 可以拿到的最少硬币数为 $a$，最大硬币数为 $b$，则区间 $\left[a,b\right]$ 内的硬币数都是可能的。
:::info[证明]
考虑有公共边或公共点的格子：
- 从 $\left(i,j\right)$ 到 $\left(i,j+1\right)$ 有唯一路径（右），二者对硬币数的贡献差最多为 $1$。
- 从 $\left(i,j\right)$ 到 $\left(i+1,j\right)$ 有唯一路径（下），二者对硬币数的贡献差最多为 $1$。
- 从 $\left(i,j\right)$ 到 $\left(i+1,j+1\right)$ 的路径有两条（右下、下右）。由于 $\left(i,j+1\right)$ 和 $\left(i+1,j\right)$ 这两个格子上要么都没有硬币，要么一个有一个没有，要么都有，所以这两个格子上的硬币数之差最多为 $1$，所以 $\left(i,j\right)$ 对硬币数的贡献，扩展到 $\left(i+1,j+1\right)$ 对硬币数的贡献，其差最多为 $1$。
考虑其他格子，必然由以上情况组合得到。得证。
:::
因此，只需要维护从 $\left(1,1\right)$ 到 $\left(i,j\right)$ 可以拿到的最少硬币数和最大硬币数，分别为 $a,b$，然后区间加 $1$，单点查询。
等等，这不是 ~~线段树~~ 差分吗？
设差分数组为 $d$，每次将 $d_{a}$ 加 $1$，将 $d_{b+1}$ 减 $1$，最终对于每个 $x$ 的答案即为 $\sum\limits_{i=1}^x d_i$。
代码如下：
```c++
const int N=4005;
int n,d[2*N],minc[N][N],maxc[N][N];
char s[N][N];
int main()
{
n=read();
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
minc[1][1]=maxc[1][1]=0;
for(int i=2;i<=n;i++) minc[1][i]=maxc[1][i]=minc[1][i-1]+(s[1][i]=='@');
for(int i=2;i<=n;i++) minc[i][1]=maxc[i][1]=minc[i-1][1]+(s[i][1]=='@');
for(int i=2;i<=n;i++)
for(int j=2;j<=n;j++)
{
minc[i][j]=min(minc[i-1][j],minc[i][j-1])+(s[i][j]=='@');
maxc[i][j]=max(maxc[i-1][j],maxc[i][j-1])+(s[i][j]=='@');
}
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[minc[i][j]]++,d[maxc[i][j]+1]--;
print(d[0]),putchar('\n');
for(int i=1;i<=2*n-2;i++) d[i]+=d[i-1],print(d[i]),putchar('\n');
return 0;
}
```