题解:
考虑每次取矩形较大那一维的中线,跑dij求出每个点到中线上的点的最短距离。
对于每个询问,都枚举中线上每个点为中转点问一下,按照在左边还是右边分治下去,写起来类似整体二分。
可以分析出来矩形面积*中线长度极限是当\(n=m\)时取\(nm\times \sqrt{nm}\),再乘上堆优化dij的复杂度即是极限复杂度。
每个询问的复杂度是\(log*min(n,m)\)。
Code:
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;
const int N = 20005;
int n, m;
#define V vector<int>
#define re resize
#define pb push_back
#define si size()
V a[N], b[N];
int Q;
struct P {
int x1, y1, x2, y2;
} q[100005];
int ans[100005];
vector<int> f[N], us[N];
const int inf = 1e9;
struct nod {
int z, x, y;
};
bool operator < (nod a, nod b) { return a.z > b.z;}
namespace sub {
priority_queue<nod> q;
void gx(int z, int x, int y) {
if(z < f[x][y]) {
f[x][y] = z;
q.push((nod) {z, x, y});
}
}
void dp(int x1, int x2, int y1, int y2, int x, int y) {
fo(i, x1, x2) fo(j, y1, y2) f[i][j] = inf, us[i][j] = 0;
f[x][y] = 0; q.push((nod) {0, x, y});
while(q.size()) {
nod c;
while(q.size()) {
c = q.top(), q.pop();
if(us[c.x][c.y]) continue;
break;
}
if(us[c.x][c.y]) break;
us[c.x][c.y] = 1;
if(c.x > x1) gx(c.z + b[c.x - 1][c.y], c.x - 1, c.y);
if(c.x < x2) gx(c.z + b[c.x][c.y], c.x + 1, c.y);
if(c.y > y1) gx(c.z + a[c.x][c.y - 1], c.x, c.y - 1);
if(c.y < y2) gx(c.z + a[c.x][c.y], c.x, c.y + 1);
}
}
}
void dg(int x1, int x2, int y1, int y2, V w) {
if(x1 > x2 || y1 > y2) return;
if(w.empty()) return;
if(x1 == x2 && y1 == y2) {
ff(i, 0, w.si) ans[w[i]] = 0;
return;
}
V t, wl, wr;
if(x2 - x1 >= y2 - y1) {
int mid = x1 + x2 >> 1;
ff(i, 0, w.si) {
int x = w[i];
if(q[x].x1 > q[x].x2) {
swap(q[x].x1, q[x].x2);
swap(q[x].y1, q[x].y2);
}
if(q[x].x1 <= mid && q[x].x2 >= mid) {
t.pb(x);
} else
if(q[x].x2 <= mid)
wl.pb(x); else wr.pb(x);
}
fo(y, y1, y2) {
sub :: dp(x1, x2, y1, y2, mid, y);
ff(_i, 0, w.si) {
int i = w[_i];
ans[i] = min(ans[i], f[q[i].x1][q[i].y1] + f[q[i].x2][q[i].y2]);
}
}
dg(x1, mid, y1, y2, wl);
dg(mid + 1, x2, y1, y2, wr);
} else {
int mid = y1 + y2 >> 1;
ff(i, 0, w.si) {
int x = w[i];
if(q[x].y1 > q[x].y2) {
swap(q[x].x1, q[x].x2);
swap(q[x].y1, q[x].y2);
}
if(q[x].y1 <= mid && q[x].y2 >= mid) {
t.pb(x);
} else
if(q[x].y2 <= mid)
wl.pb(x); else wr.pb(x);
}
fo(x, x1, x2) {
sub :: dp(x1, x2, y1, y2, x, mid);
ff(_i, 0, w.si) {
int i = w[_i];
ans[i] = min(ans[i], f[q[i].x1][q[i].y1] + f[q[i].x2][q[i].y2]);
}
}
dg(x1, x2, y1, mid, wl);
dg(x1, x2, mid + 1, y2, wr);
}
}
int main() {
scanf("%d %d", &n, &m);
fo(i, 1, n) {
a[i].re(m);
fo(j, 1, m - 1) scanf("%d", &a[i][j]);
}
fo(i, 1, n - 1) {
b[i].re(m + 1);
fo(j, 1, m) scanf("%d", &b[i][j]);
}
scanf("%d", &Q);
V w;
fo(i, 1, Q) {
scanf("%d %d %d %d", &q[i].x1, &q[i].y1, &q[i].x2, &q[i].y2);
w.pb(i);
ans[i] = inf;
}
fo(i, 1, n) f[i].re(m + 1), us[i].re(m + 1);
dg(1, n, 1, m, w);
fo(i, 1, Q) pp("%d\n", ans[i]);
}