题解 【AT4440 [AGC028F] Reachable Cells】

> 本题的 $O(n^2\log n)$ 题解。 **题意** ： 给出一个 $n\times n$ 的矩阵 $A$，每个格子是障碍或 $1\sim 9$ 的数字。 称格子 $u$ 能到达格子 $v$ 当且仅当： - $u\neq v$ - $A_u,A_v$ 均不为障碍。 - 通过反复向右或向下移动到相邻的空单元格，可以从单元格 $u$ 到达单元格 $v$ ，且不经过障碍。 求出 $\sum_{u,v}[u\text{能到达}v]A_uA_v$，其中 $A$ 代表格子上的数码。 $n\leq 1500$ ，时限$\texttt{9s}$。 ------------ 无法理解出题人怎么想到这种东西的…… F2 $O(n^3)$ 草标是坏文明…… 本文只考虑所有数字都为 $1$ 的情况。对于一般情况，简单地由“集合大小”改为“权值和”即可。 考虑分治，每次计算跨越分界线的贡献。 若能 $O(n^2)$ 计算，则原问题可以 $O(n^2\log n)$ 计算。 ## Part1 观察性质，问题的转化 设分界线为第 $m$ 行。 考虑每次计算上半部分**某一行**为起点的贡献和，记为第 $c$ 行。 对于 $(c,i)$ ，记 $S_i$ 表示可达的第 $m$ 行的集合，记 $U=\bigcup_{i=1}^mS_i$ 。 - **性质①** ： $\min S_i,\max S_i$ 随 $i$ 单调不减。（若存在） **证明** ： 只证 $\min$ ，$\max$ 类似。 假设有 $i,j$ 满足 $i<j,\ \min S_i>\min S_j$ 。 由 $i\rightarrow \min S_i,\ j\rightarrow \min S_j$ ，有图：  路径一定会交叉，因此 $i$ 必然可以前往 $\min S_j<\min S_i$ ，矛盾。 记 $l_i=\min S_i,\ r_i=\max S_i$ - **性质②** ： 记 $U=\bigcup_{i=1}^mS_i$ （第 $c$ 行能到达的所有分界点），则 $S_i=[l_i,r_i]\cap U$。 **证明** ： 显然有 $S_i\subseteq [l_i,r_i]\cap U$ ，只需证 $S_i\supseteq [l_i,r_i]\cap U$ ，即 $p\in [l_i,r_i]\cap U\Rightarrow p\in S_i$。 （反证）对于 $p\in [l_i,r_i]\cap U$ ，假设 $p\notin S_i$ ，找出 $j\neq i$ 满足 $p\in S_j$ 。有图：  路径一定会交叉，因此 $i$ 必然可以前往 $p$ ，矛盾。 记 $T_i$ 为分界点 $(m,i)$ 能到达的下半部点集。 $(c,i)$ 能到达的下半部点集可以写作 ： $$\bigcup\limits_{j\in U\cup[l_i,r_i]}T_j$$ 从小到大考虑各个 $i$ ，由于 $l_i,r_i$ 单调不降，问题可以转化为 ： - 从右侧加入一个 $T_i$ - 从左侧删除一个 $T_i$ - 查询目前 $T$ 的并集大小。 假设目前的区间为 $[l,r]$ ，对于 $i\in[l,r]$ 记 $H_i=T_i\cap\Big(\neg\bigcup\limits_{j\in U\cup(i,r]}T_j\Big)$ ，即目前 $T_i$ 所独有，而后面的 $T$ 没有的部分。 在左侧删除时，并集大小减去 $H_l$。 在右侧加入时，考虑如何更新 $H$ 。 对于新加入的 $T_{r+1}$ ，$H_{r+1}=T_{r+1}$ 。 - **性质③** ： 记 $d_i$ 为 $\max_{(x,y)\in T_i}x$ ，即 $(m,i)$ 能到达的最大行。 对于 $i<j<k$ ，若 $\min(d_i,d_k)\leq d_j$ ，则 $T_i\cap T_k\subseteq T_j$。 即：在右侧加入 $T_k$ 不会对这样的 $T_i$ 的 $H_i$ 产生影响。 **证明** ：当 $d_i\leq d_j$ ，如图：  对于右侧的任意一个 $k$ ，$T_k$ 若强行穿过 $T_j$ 的“高墙”，则后来必然在 $T_j$ 的范围内。 若绕过“高墙”，由于无法向上回头，还是碰不到 $T_i$ 。 $d_k\leq d_j$ 的情况类似。 因此，我们可以按照 $d$ （递减地）维护一个单调队列，每次右侧加入 $T_{r+1}$ 时，只需要处理 $d_j\leq d_{r+1}$ 的 $H_j$ （也就是弹出来的 $j$），以及最后剩下的队尾的 $H$ 的的变化。这样，$H$ 的变化次数就是 $O(n)$ 的了。 观察 $H_j$ 的变化，也就是 $H_j$ 与 $H_k$ 交，且不与其他 $H_{j+1\sim r}$ 交的部分。  此处 $t\in[j+1,r]$ 是 $d_t$ 最大的 $t$ （是单调队列中的下一个）。 可以发现，$H_j\cap H_k$ 在 $>d_t$ 行，显然不可能与 $T_{j+1\sim r}$ 有交，而在 $\leq d_t$ 行，则必然与 $T_t$ 有交。 这说明了 $H_j$ 中缺少的正是 $H_j\cap H_k$ 在 $>d_t$ 行的部分。记为 $Both(a,b,d)$ 为 $T_a\cap T_b$ 在 $\geq d$ 行的部分。 综上，只需预处理 $U,l,r,d,Both$ ，即可 $O(n)$ 完成上述过程进而解决本题。 ## Part2 $\ l,r,U,d$ 的预处理 **在以下预处理过程中，为了便于考虑，将下半部所有从第 $m$ 行无法到达的位置全设置为障碍。** 将 $l,r,U$ 的定义从特定的行扩展到所有的行。 记 $l_{x,y}$ 表示 $(x,y)$ 能到达的最左 $(m,x)$ 的 $x$ 。$r$ 的定义类似。 $l,r$ 容易 $O(n^2)$ 递推计算。 记 $U_c$ 是 $c$ 行能到达的 $(m,x)$ 的集合。 计算 $U$ 时，对每个 $(m,i)$ 记 $low_i$ 表示能到达 $(m,i)$ 的 $(x,y)$ 的最小 $x$。则 $(m,i)$ 在在 $U_{low_i\sim m}$ 内，而不在 $U_{1\sim low_i-1}$ 内。$low$ 可以利用递推求出。 可以发现， $d$ 就是镜像的 $low$ ，也递推求出。 ## Part3 $Both$ 的预处理 > 我愿称之为全场最难 > 官方题解的思路比较跳跃，讲解也倒了过来 /yun > 这是和官方题解不同的思路，可能更自然 对于 $Both(a,b,d)$ ，状态数大于 $O(n^2)$ ，不可能逐个求出，只能做到预处理后 $O(1)$ 查询。 似乎无从下手，于是先用解析手段写出 $Both(a,b,d)$ 的形式，便于观察。 为了利用性质 ①②，先单独考虑每一行，记 $Both'(a,b,d)$ 为 $T_a,T_b$ 在第 $d$ 行的交。于是有 ： $$Both(a,b,d)=\sum\limits_{k\geq d}Both'(a,b,d)$$ 记 $L_{x,d}$ 为 $(m,x)$ 在第 $d$ 行可达的最左侧，类似地有 $R_{x,d}$。 根据性质 ①② ，第 $d$ 行中，$T_a,T_b$ 是一个区间中的非障碍点（还要考虑是否从 $m$ 行可达，前文我们已经删除了所有不可达的点），分别为 $[L_{a,d},R_{a,d}],[L_{b,d},R_{b,d}]$ ，则交集为 $[L_{b,d},R_{a,d}]$ ，当 $L_{b,d}>R_{a,d}$ 时为空。 这又有讨论的必要，如下图：  红线上方是满足 $L_{b,d}>R_{a,d}$ 的部分，下方是满足 $L_{b,d}\leq R_{a,d}$ 的部分，此时直接计算 $[L_{b,d},R_{a,d}]$ 的和，也就是部分和。 记 $S_{i,j}=\sum\limits_{k=1}^jA_{i,k}$ 为部分和数组。 由上图我们发现，随着 $k$ 的增大， $[L_{b,k}\leq R_{a,k}]$ 会从满足变为不满足，是单调的。其分界点就是 $meet_{a,b}$ ，为 $(x,y)\in T_i\cap T_j$ 的最小 $y$ （即 $(m,i),(m,j)$ 最靠上的汇合处）。 可以写出 $$ \begin{aligned} Both'(a,b,d)&=[L_{b,d}\leq R_{a,d}]\Big(S_{d,R_{a,d}}-S_{d,L_{b,d}-1}\Big)\\ Both(a,b,d)&=\sum\limits_{k\geq d}[L_{b,k}\leq R_{a,k}]\Big(S_{k,R_{a,k}}-S_{k,L_{b,k}-1}\Big)\\ &=\sum\limits_{k\geq \max(d,meet_{a,b})}\Big(S_{k,R_{a,k}}-S_{k,L_{b,k}-1}\Big)\\ &=\sum\limits_{k\geq \max(d,meet_{a,b})}S_{k,R_{a,k}}-\sum\limits_{k\geq \max(d,meet_{a,b})}S_{k,L_{b,k}-1}\\ \end{aligned} $$ 到这里就把 $a,b$ 拆开了，可以分别二维前缀和。 接下来只需求 $L,R,meet$ 即可。 求解 $L,R$ 时，固定 $a$ ，对 $L_{a,\_},R_{a,\_}$ 一起从上到下求解。  从行 $k$ 扩展到行 $k+1$ 时，记 $nxt_{a,b}$ 为 $(a,b)$ 向右第一个能向下走的位置，$nxt_{k,L_{a,k}}$ 即为新的 $L_{a,k+1}$。 对于 $R$ ，先取 $pre_{k,R_{a,k}}$ ，向下走之后再尽量向右。记 $to_{x,y}$ 为 $(x,y)$ 向右一直走到达的 位置，容易预处理。 求解 $meet_{a,b}$ 时，固定 $a$ ，逐渐增大 $b$ 。 由路径交叉不难证明，$b_1<b_2$ 且 $meet_{a,b_1},meet_{a,b_2}\neq \infty\Rightarrow meet_{a,b_1}\leq meet_{a,b_2}$ 。如图：  维护一个单调的 $k$ ，当 $b$ 增加时，令 $k$ 按 $meet_{a,b}$ 不断尝试增加。 若 $k\geq \min(d_a,d_b)$ 则令 $meet_{a,b}=\infty$ 并停止增加。若正常停止， $meet_{a,b}=k$ 。 由于 $k$ 单调不降，处理每个 $a$ 的复杂度为 $O(n)$。 ------------ ## Part4 代码实现 是真的难写……差点放弃 写起来是个套娃多合一，多哈希降低正确率，单个过程其实不难搞懂。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 1510 using namespace std; const int INF=1000000000; char a[MaxN][MaxN]; int l[MaxN][MaxN],r[MaxN][MaxN],d[MaxN][MaxN],D[MaxN],low[MaxN] ,nxt[MaxN][MaxN],pre[MaxN][MaxN],to[MaxN][MaxN] ,L[MaxN][MaxN],R[MaxN][MaxN] ,mp[MaxN][MaxN],oL[MaxN][MaxN],oR[MaxN][MaxN]; #define S d int n1,n2,m; void Init() { #define clr(x,y) {d[x][y]=m;l[x][y]=INF;r[x][y]=0;} for (int i=1;i<=n1;i++){clr(i,0);clr(i,n2+1);} for (int j=1;j<=n2;j++){clr(0,j);clr(n1+1,j);} //l,r for (int j=1;j<=n2;j++) if (a[m][j]==0){l[m][j]=INF;r[m][j]=0;} else l[m][j]=r[m][j]=j; for (int i=m-1;i;i--) for (int j=n2;j;j--) if (a[i][j]==0){l[i][j]=INF;r[i][j]=0;} else { l[i][j]=min(l[i+1][j],l[i][j+1]); r[i][j]=max(r[i+1][j],r[i][j+1]); } //d,low,D for (int i=1;i<=m;i++) for (int j=1;j<=n2;j++) d[i][j]=(a[i][j] ? min(i,min(d[i-1][j],d[i][j-1])) : m); for (int t=1;t<=n2;t++)low[t]=d[m][t]; for (int i=n1;i>=m;i--) for (int j=n2;j;j--) d[i][j]=(a[i][j] ? max(i,max(d[i+1][j],d[i][j+1])) : m); for (int t=1;t<=n2;t++)D[t]=d[m][t]; //to for (int i=m;i<=n1;i++){ to[i][n2+1]=0; for (int j=n2;j;j--) to[i][j]=(a[i][j] ? max(j,to[i][j+1]) : 0); } //pre,nxt,S for (int j=1;j<=n2;j++)S[m][j]=a[m][j]; for (int i=m+1;i<=n1;i++) for (int j=1;j<=n2;j++) S[i][j]=((S[i-1][j]||S[i][j-1]) ? a[i][j] : 0); for (int i=m;i<n1;i++){ nxt[i][n2+1]=INF; for (int j=n2;j;j--) nxt[i][j]=(S[i][j]&&S[i+1][j] ? j : nxt[i][j+1]); for (int j=1;j<=n2;j++) pre[i][j]=(S[i][j]&&S[i+1][j] ? j : pre[i][j-1]); } for (int i=m;i<=n1;i++) for (int j=1;j<=n2;j++) S[i][j]+=S[i][j-1]; //L,R for (int t=1;t<=n2;t++){ int tl,tr; if (!a[m][t]){tl=INF;tr=0;} else {tl=t;tr=to[m][t];} for (int k=m;k<=n1;k++){ L[t][k]=tl;R[t][k]=tr; if (tl!=INF){ tl=nxt[k][tl];tr=to[k+1][pre[k][tr]]; if (tl>tr){tl=INF;tr=0;} } } } //mp for (int a=1;a<=n2;a++){ int k=m; for (int b=a;b<=n2;b++){ while(L[b][k]!=INF&&L[b][k]>R[a][k]&&k<=n1)k++; if (L[b][k]==INF){mp[a][b]=n1+1;continue;} mp[a][b]=k; } } //oL,oR for (int t=1;t<=n2;t++){ oL[t][n1+1]=oR[t][n1+1]=0; for (int k=n1;k>=m;k--){ oL[t][k]=oL[t][k+1]+(L[t][k]!=INF ? S[k][L[t][k]-1] : 0); oR[t][k]=oR[t][k+1]+(L[t][k]!=INF ? S[k][R[t][k]] : 0); } } } int Both(int a,int b,int d){ d=max(d,mp[a][b]); if (d>n1)return 0; int lim=min(D[a],D[b]); return (oR[a][d]-oR[a][lim+1])-(oL[b][d]-oL[b][lim+1]); } int q[MaxN],st[MaxN],H[MaxN],sum,ql,qr; void add(int p) { D[q[qr+1]=0]=m-1; while(ql<=qr&&D[q[qr]]<=D[p]){ int buf=Both(q[qr],p,D[q[qr+1]]+1); H[q[qr]]-=buf;sum-=buf; qr--; } if (ql<=qr){ int buf=Both(q[qr],p,D[q[qr+1]]+1); H[q[qr]]-=buf;sum-=buf; } sum+=(H[q[++qr]=p]=Both(p,p,m)); } void del(int l) {while(ql<=qr&&q[ql]<l)ql++;} long long ans; void calc() { m=(1+n1)/2+1;Init(); int tn=0;sum=0; for (int i=1;i<m;i++){ int tr=0,tl=1;ql=1;qr=sum=0; for (int j=1;j<=n2;j++){ int L=l[i][j],R=r[i][j]; if (L==INF)continue; while(tr<R){++tr;if (low[tr]<=i)add(tr);} del(L); while(tl<L){sum-=H[tl];H[tl++]=0;} ans+=a[i][j]*sum; }for (int j=tl;j<=tr;j++)H[j]=0; } } char s[MaxN][MaxN]; void solve(int l1,int r1,int l2,int r2) { if (l1==r1&&l2==r2)return ; if (r1-l1>=r2-l2){ int mid=(l1+r1)/2; for (int i=l1;i<=r1;i++) for (int j=l2;j<=r2;j++) a[i-l1+1][j-l2+1]=s[i][j]; n1=r1-l1+1;n2=r2-l2+1;calc(); solve(l1,mid,l2,r2); solve(mid+1,r1,l2,r2); }else { int mid=(l2+r2)/2; for (int i=l1;i<=r1;i++) for (int j=l2;j<=r2;j++) a[j-l2+1][i-l1+1]=s[i][j]; n1=r2-l2+1;n2=r1-l1+1;calc(); solve(l1,r1,l2,mid); solve(l1,r1,mid+1,r2); } } int main() { int n;scanf("%d",&n); for (int i=1;i<=n;i++)scanf("%s",s[i]+1); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) s[i][j]=(s[i][j]=='#' ? 0 : s[i][j]-'0'); solve(1,n,1,n); printf("%lld\n",ans); return 0; } ``` 赠送样例： ```cpp input: 10 ########## ########## ########## ########## 1##1##1### 111111111# #11#111111 #11#11##11 ##1111#11# #####1111# output: 370 ```