2022.11.04

P3350

非常风骚的一道分治。
这其实是我做的第一道在网格图上跑最短路的题，也让我学到了一些小技巧：

1. 给网格图附上编号

   code

   int id(int x, int y){return (x - 1) * m + y;}
   

   这样就可以用链式前向星愉快存边和跑 \(dijkstra\) 了。

2. 分治过程中可以用一个临时数组给要分类的数组作临时存储再复制回原数组

   code

   for(int i = ql; i <= qr; ++i)
       if(Q[i].y1 < mid && Q[i].y2 < mid)T[++L] = Q[i];
       else if(Q[i].y1 > mid && Q[i].y2 > mid)T[--R] = Q[i];
   int pos = L;
   for(int i = ql; i <= L; ++i)Q[i] = T[i];
   for(int i = R; i <= qr; ++i)Q[++pos] = T[i];
   solve(u, d, l, mid - 1, ql, L);
   solve(u, d, mid + 1, r, L + 1, pos);
   

   阿其实这个在之前某次 \(\color{Black}{C}\color{Red}{laris}\) 的题目中有出现过。

接下来正题，让我们来看看这个神奇的分治：
将当前矩形拦腰截开，把它较长的那一边切成两半，就像这样：

if(down - up >= right - left){
    int mid = up + down >> 1;
    ···
}else{
    int mid = left + right >> 1;
    ···
}

然后再从这条 \(mid\) 上的每一个点出发跑一次单源最短路，范围是当前的整个矩形（而不是切出来的部分），然后将整个矩形范围内的询问答案更新一遍。

for(int i = l; i <= r; ++i){//这是分成上、下两部分的例子
    dij(u, d, l, r, id(mid, i));
    for(int i = ql; i <= qr; ++i)
        ans[Q[i].id] = Min(ans[Q[i].id], dis[Q[i].p1] + dis[Q[i].p2]);
}

我们可以将范围内的询问分类讨论一下：

1. 询问的两个点在 \(mid\) 一侧
   • 两点的最短路会经过 \(mid\) ：
     会在上面的答案大更新中被更新一次。
   • 两点最短路不经过 \(mid\) ：
     没有关系，矩形会继续分割下去，它们两个总能被更新掉。
2. 询问的两个点在 \(mid\) 两侧
   那么就不用多说，直接就是答案了。

更新完当前矩阵后，继续分治下去，直到边界不合法，这题就做完了。
那么关于时间复杂度，简单理解一下，算它跑满好了：总共跑了 \(n\cdot m\) 次 \(dijkstra\)，但是基本上每次涉及的范围都减半了，大概就相当于整个大的 \(n\cdot m\) 的矩形被分了几次（一次指的是每个部分都砍成两半），就跑了几遍范围为 \(n\cdot m\) 的 \(dijkstra\)。至于具体的证明，不如康康介个blog。