洛谷P3350 [ZJOI2016]旅行者题解

题目链接：P3350 [ZJOI2016]旅行者

题意：

cxy 来到了一个新的城市旅行。她发现了这个城市的布局是网格状的，也就是有 $n$ 条从东到西的道路和 $m$ 条从南到北的道路，这些道路两两相交形成 $n\times m$ 个路口 $(i,j)$， $(1\leq i\leq n,1\leq j\leq m)$

她发现不同的道路路况不同，所以通过不同的路口需要不同的时间。通过调查发现，从路口 $(i,j)$ 到路口 $(i,j+1)$ 需要时间 $r(i,j)$ ，从路口 $(i,j)$ 到路口 $(i+1,j)$ 需要时间 $c(i,j)$ 。注意这里的道路是双向的。cxy 有 $q$ 个询问，她想知道从路口 $(x_1,y_1)$ 到路口 $(x_2,y_2)$ 最少需要花多少时间。

输入格式

第一行包含 2 个正整数 $n,m$ 表示城市的大小。

接下来 $n$ 行，每行包含 $m-1$ 个整数，第 $i$ 行第 $j$ 个正整数表示从一个路口到另一个路口的时间 $r(i,j)$ 。

接下来 $n-1$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个正整数表示从一个路口到另一个路口的时间 $c(i,j)$。

接下来一行，包含一个正整数 $q$，表示 cxy 的询问个数。

接下来 $q$ 行，每行包含 $4$ 个正整数 $x_1,y_1,x_2,y_2$，表示两个路口的位置。

输出格式

输出共 $q$ 行，每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。

数据范围：

$n\times m \le 2\times 10^4,~q \le 10^5,~1 \le r(i,j),c(i,j) \le 10^4$。

其实就是在网格图上查询两点最短路。

感觉在线并不是很好搞，故离线处理。

离线后，询问就变成了网格图中若干个点对的最短距离

~~是不是有点kd-tree的感觉（无端~~

考虑分治。我们用一条分界线 $l$ 将当前矩阵划分为两个块处理

两点在块内的询问递归处理即可。
两点在不同块内的情况，一定要经过分界线上的某个点

因此我们枚举分界线上每一个点，都去跑一遍最短路，尝试更新答案即可

因为要枚举分界线上的点跑最短路，所以分界线选取当前矩形的最短中线即可。

接下来是本题~~最有(dú)趣(liú)的~~复杂度分析。

~~一开始想用主定理的，然后发现是二维的好像不太好搞~~

对于第 $k$ 次分治，顶点数为 $\mathcal{O}\left(\frac{|V|}{2^k}\right)$ ，因此 $l$ 不超过 $\mathcal{O}\left(\sqrt{\frac{|V|}{2^k}}\right)$

根据 $\mathtt{Dijkstra}$ 复杂度为 $\mathcal{O}(|E| \log |V|)$ ，以及网格图中 $|E| = \mathcal{O}(|V|)$

可知每次 $\mathtt{Dijkstra}$ 的复杂度为 $\mathcal{O}\left(\frac{|V|}{2^k}\log \frac{|V|}{2^k}\right) = \mathcal{O}\left(\frac{|V|}{2^k}\log |V|\right)$

由于第 $k$ 层分治一共会出现 $2^k$ 次（根据递归树显然），则第 $k$ 层对复杂度的贡献为

$\mathcal{O}\left(2^k \times \sqrt{\frac{|V|}{2^k}}\times\frac{|V|}{2^k}\log |V|\right)$

即总复杂度为

$\begin{aligned} &\quad \mathcal{O}\left(\sum_{k=0}^{+\infty}2^k \times \sqrt{\frac{|V|}{2^k}}\times\frac{|V|}{2^k}\log |V|\right) \\&= \mathcal{O}\left(\sum_{k=0}^{+\infty} \frac{|V|^{ \frac{3}{2} } \log |V|}{2^{\frac{k}{2}}} \right) \\&=\mathcal{O}\left(|V|^{\frac{3}{2}} \log |V| \times \sum_{k=0}^{+\infty} 2^{-\frac{k}{2}}\right) \end{aligned}$

可以发现后面的东西就是个公比为 $\frac{\sqrt{2}}{2}$ 的等比数列求和，故

$\begin{aligned} &=\mathcal{O}\left(|V|^{\frac{3}{2}} \log |V| \times \frac{1 - \left(\frac{\sqrt{2}}{2}\right)^{+\infty} }{1-\frac{\sqrt{2}}{2}}\right) \\&= \mathcal{O}\left(|V|^{\frac{3}{2}} \log |V| \right) \end{aligned}$

即总时间复杂度为 $\mathcal{O}\left(|V|^{\frac{3}{2}} \log |V| \right)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e5+15))

int R,C,q,pos=1,head[N],ans[N],ord[N],buf[N*2 + 500];
struct query
{
    int r1,c1,r2,c2;
    query *read(){cin >> r1 >> c1 >> r2 >> c2; return this;}
}qry[N];
struct Edge{int u,v,w,next;} e[N];
void addEdge(int u,int v,int w) { e[++pos]={u,v,w,head[u]}; head[u]=pos; }
void addEdge2(int u,int v,int w) { addEdge(u,v,w); addEdge(v,u,w); }
void down(int &x,int y) { x > y ? x = y : 0; }
int Idx(int r,int c) { return (r - 1) * C + c; }
namespace SP
{
    bitset<N> vis;
    int minR,maxR,minC,maxC,d[N];
    struct Node{int u,dis;};
    bool operator<(Node a,Node b){return a.dis>b.dis;}
    priority_queue<Node> q;
    void SetBound(int a,int b,int c,int d){minR=a,maxR=b,minC=c,maxC=d;}
    void Dijkstra(int st)
    {
        while(!q.empty()) q.pop();
        for(int i=minR; i<=maxR; i++)
            for(int j=minC,t; j<=maxC; j++)
                t=Idx(i,j),vis[t]=0,d[t] = INF;
        q.push({st,0}); d[st]=0;
        while(!q.empty())
        {
            int u=q.top().u; q.pop();
            if(vis[u]) continue;
            vis[u] = 1;
            for(int i=head[u]; i; i=e[i].next)
            {
                int v=e[i].v, w=e[i].w;
                if(d[v] > d[u] + w)
                {
                    d[v] = d[u] + w;
                    q.push({v,d[v]}); 
                }
            }
        }
    }
}
void solve(int r1,int r2,int c1,int c2,int *st,int *ed)
{
    if(r1 > r2 || c1 > c2 || st == ed) return;
    int u,v,*p1 = buf,*p2 = buf+N;
    if(r2-r1 >= c2-c1) // row / 2
    {
        int mid = (r1 + r2) >> 1;
        for(int c=c1; c<=c2; c++)
        {
            SP::SetBound(r1,r2,c1,c2);
            SP::Dijkstra(Idx(mid,c));
            for(int *p=st; p!=ed; ++p)
            {
                u = Idx(qry[*p].r1, qry[*p].c1);
                v = Idx(qry[*p].r2, qry[*p].c2);
                down(ans[*p], SP::d[u] + SP::d[v]);
            }
        }
        for(int *p=st; p!=ed; ++p)
            if(qry[*p].r1 < mid && qry[*p].r2 < mid) *p1++ = *p;
            else if(qry[*p].r1 > mid && qry[*p].r2 > mid) *p2++ = *p;
        int *m1 = st + (p1 - buf), *m2 = m1 + (p2 - (buf+N));
        memcpy(st, buf, (m1 - st) * sizeof(int));
        memcpy(m1, buf+N, (m2 - m1) * sizeof(int));
        solve(r1, mid-1, c1, c2, st, m1);
        solve(mid+1, r2, c1, c2, m1, m2);
    }else
    {
        int mid = (c1 + c2) >> 1;
        for(int r=r1; r<=r2; r++)
        {
            SP::SetBound(r1,r2,c1,c2);
            SP::Dijkstra(Idx(r,mid));
            for(int *p=st; p!=ed; ++p)
            {
                u = Idx(qry[*p].r1, qry[*p].c1);
                v = Idx(qry[*p].r2, qry[*p].c2);
                down(ans[*p], SP::d[u] + SP::d[v]);
            }
        }
        for(int *p=st; p!=ed; ++p)
            if(qry[*p].c1 < mid && qry[*p].c2 < mid) *p1++ = *p;
            else if(qry[*p].c1 > mid && qry[*p].c2 > mid) *p2++ = *p;
        int *m1 = st + (p1 - buf), *m2 = m1 + (p2 - (buf+N));
        memcpy(st, buf, (m1 - st) * sizeof(int));
        memcpy(m1, buf+N, (m2 - m1) * sizeof(int));
        solve(r1, r2, c1, mid-1, st, m1);
        solve(r1, r2, mid+1, c2, m1, m2);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> R >> C;
    int t=1;
    for(int i=1; i<=R; ++i,++t)
        for(int j=1,w; j<C; ++j, ++t)
            cin >> w, addEdge2(t,t+1,w);
    t=1;
    for(int i=1; i<R; ++i)
        for(int j=1,w; j<=C; ++j, ++t)
            cin >> w,addEdge2(t,t+C,w);
    cin >> q;
    for(int i=1; i<=q; i++) qry[i].read(), ord[i]=i;
    for(int i=1; i<=q; i++) ans[i] = INF;
    solve(1, R, 1, C, ord+1, ord+1+q);
    for(int i=1; i<=q; i++) cout << ans[i] << '\n';
    return 0;
}