-
题目链接
-
题目大意
给定一个 (n imes n) 的网格图，每个格子有一个权值 (w_{i,j}) 。
定义一个格子 (X) 可以到达 (Y) 到达当且仅当存在一条路径 (X o Y)，对于其中任意一点 (Z) ， (w_Z eq 0)，且 (i,j) 单调不减。
求所有可达的 ((X,Y)) 的 (w_X imes w_Y) 的和。
(nle 1500)
-
题解
(mathcal O(n^3)) 比较玄学，而且我也没怎么理解，就不说了。
首先看到数据范围，就想到 (mathcal O(n^2log 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 ile jle right_{x, y} $，如果 (min (bottom_i,bottom_j)<x)，则为 (infty) ，否则为 (x) ）。
然后我们需要实现一个函数 (reach(x,y,d)) ，表示 ((x,mid),(y,mid)) 共同可达的 (ile d) 的点 ((i,j)) 的个数。
接下来我们考虑一个点满足什么条件会被计入。
很显然为 (left_{i,j}le xle yle 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^2log n)) 。
-