题目链接

agc028f

题目大意

给定一个 \(n\times n\) 的网格图，每个格子有一个权值 \(w_{i,j}\) 。

定义一个格子 \(X\) 可以到达 \(Y\) 到达当且仅当存在一条路径 \(X\to Y\)，对于其中任意一点 \(Z\) ， \(w_Z\neq 0\)，且 \(i,j\) 单调不减。

求所有可达的 \((X,Y)\) 的 \(w_X\times w_Y\) 的和。

\(n\le 1500\)

题解

\(\mathcal O(n^3)\) 比较玄学，而且我也没怎么理解，就不说了。

首先看到数据范围，就想到 \(\mathcal O(n^2\log n)\) 的复杂度，所以我们考虑分治。

不妨令所有 \(w_{i,j}=1\) ，这没有影响。

我们取一条线为分界，统计经过这条线的答案。

设分界线的 \(y\) 坐标为 \(mid\) 。

接下来我们以下半部分为例，定义一些东西：

• \(left_{i,j}:\) 表示可达 \((i,j)\) 的 \((x,mid)\) 的 \(\min x\) 。

• \(right_{i,j}:\) 表示可达 \((i,j)\) 的 \((x,mid)\) 的 \(\max x\) 。

• \(bottom_i:\) 表示 \((i,mid)\) 可达的 \((x,y)\) 的 \(\max x\) 。

这些都可以直接 \(\mathcal O (n^2)\) 递推出来。

然后我们可以知道两个点 \((i,mid)\) 和 \((j,mid)\) 可以共同达到的 \((x,y)\) 的 \(\min x\) 。

这个我们记为 \(mp_{i,j}\) （具体计算方法是找到一个 \(\min x\) 的 \((x,y)\) 使得 $left_{x,y}\le i\le j\le right_{x, y} $，如果 \(\min (bottom_i,bottom_j)<x\)，则为 \(\infty\) ，否则为 \(x\) ）。

然后我们需要实现一个函数 \(reach(x,y,d)\) ，表示 \((x,mid),(y,mid)\) 共同可达的 \(i\le d\) 的点 \((i,j)\) 的个数。

接下来我们考虑一个点满足什么条件会被计入。

很显然为 \(left_{i,j}\le x\le y\le right_{i,j}\) 。

那么我们直接容斥，先加上 \(left_{i,j}\le x\) 的，再减去 \(right_{i,j}<y\) 的，最后加上 \(x<left_{i,j}\le right_{i,j}<y\) 的部分。

但是最后一部分很不好做。

然而我们能够发现，当点 \((i,j)\) 满足 \(j<mp_{x,y}\) 时才会被加上，并且这部分直接用 \(right_{i,j}<y\) 的减去 \(left_{i,j}\le x\) 的即可。

这样利用前缀和可以做到 \(\mathcal O(1)\) 实现。

接下来我们遍历整个上半部分，计算每个点的贡献。

显然我们可以发现，同一行中的 \(left_{i,j}\) 与 \(right_{i,j}\) 单调不减，那么这个可以抽象成这样：

• 有一个集合 \(S\) 与若干区间，满足区间的 \(l,r\) 单调不减，集合中的元素覆盖若干点，求每个区间 \([l,r]\) 中的元素覆盖的点的个数。

那么我们需要支持：

• 删除一个点的贡献。

• 加入一个点的贡献并去重。

• 统计答案。

令 \(has_j\) 表示在询问区间中，所有满足 \((i,mid)\) 可达且 \(\forall\ j>i,(j,mid)\) 不可达的点的数目。

那么显然删除就直接减去 \(has_j\) ，接下来考虑加入一个点。

通过画图我们能够发现，对于一个点 \((i,mid)\) ，若在序列中存在一个点 \((j,mid)\) 满足 \(j>i\ \and\ bottom_j>bottom_i\)，那么再怎么加入点，点 \((i,mid)\) 的答案都不会改变。

那么考虑维护一个单调队列，只修改其中的贡献。

令加入的点为 \((x,mid)\) ，那么\(has_x=reach(x,x,bottom_x)\)。每次修改队列中的 \((y_i,mid)\) ，直接 \(has_{y_i}-=reach(x,y_i,\min(bottom_{y_i},bottom_x))-reach(x,y_{i},bottom_{y_{i+1}})\) 即可。

这样一行的答案就可以在 \(\mathcal O(n)\) 的复杂度内完成，统计的复杂度是 \(\mathcal O(n^2)\) 。

总复杂度 \(\mathcal O(n^2\log n)\) 。