题目大意
(n imes m) 的网格图 这个网格图中不能往上走 要求支持如下操作：
- 修改网格图上的一条边
- 询问从第一行某个点到最后一行某个点的最短路径
(n leq 5000,m leq 200,q leq 2 imes 10^5) 修改次数 (d leq 500)。
题解
看到这个行+单点修改可以考虑维护一个线段树：令 (A_{i,j}) 表示当前块内上面第 (i) 个点到下面第 (j) 个点的最短距离，合并的时候是一个((min,+)) 的矩乘。这样是 (O(dm^3logn)) 的复杂度 不可能通过。
优化 1
考虑合并两块的时候 先固定起点 (i) 。设底行的某个点为 (j) ，与中间线上相交的点为 (k)。我们可以发现 随着 (j) 的增加 (k) 一定不会减少。于是这个有单调性 可以用类似于决策单调性分治的方法做 单次合并时间复杂度变成了 (O(m^2logm))可能卡常后足以通过此题
优化 2
[scode type="yellow"] 这可能是一个二维 dp 优化的常用套路[/scode]
我们设 (p_{i,j}) 表示上层 (i) 到下层 (j) 经过的是哪个点。容易证明有 (p_{i-1,j} leq p_{i,j} leq p_{i,j+1})
于是每次枚举第三维的时候只需要枚举 ([p_{i-1,j},p_{i,j+1}]) 就可以了。画个图发现每个 (p) 形如一个斜线 加起来近似是一个 (m imes m) 的正方形。所以复杂度是 (O(m^2)) 的。
优化 3
但是空间会爆炸怎么办呢？
线段树爆空间 一种常见的处理方法是底层暴力。
我们分块。块内暴力处理 每个块作为线段树的底层合并就可以。
暴力可以用之前写好的矩乘方便实现。
#include<bits/stdc++.h>
#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 5000+5;
const int MAXM = 205+5;
const int BLO = 16;
int R[MAXN][MAXM],D[MAXN][MAXM];
int n,m;
int blo[MAXN];
struct Matrix{
int a[MAXM][MAXM];
friend Matrix operator * (const Matrix &A,const Matrix &B){
Matrix C;
static int s[MAXM][MAXM];
FOR(i,0,m+1) FOR(j,0,m+1) s[i][j] = -1;
FOR(i,1,m){
ROF(j,m,1){
int l = 1,r = m;
if(s[i-1][j] != -1) l = std::max(l,s[i-1][j]);
if(s[i][j+1] != -1) r = std::min(r,s[i][j+1]);
C.a[i][j] = 1e9;
// DEBUG(l);DEBUG(r);
FOR(k,l,r){
if(C.a[i][j] > A.a[i][k]+B.a[k][j]){
C.a[i][j] = A.a[i][k]+B.a[k][j];
s[i][j] = k;
}
}
}
}
return C;
}
inline void debug(){
puts("--- NEW MESSAGE ---");
FOR(i,1,m) FOR(j,1,m) printf("%d%c",a[i][j],"
"[j==m]);
puts("--- END MESSAGE ---");
}
}sm[(MAXN/BLO)<<2];
inline Matrix gen(int x){// 生成第 x 行的矩阵
Matrix res;
FOR(i,1,m){
int sm = 0;
FOR(j,i,m){
res.a[i][j] = sm+D[x][j];
sm += R[x][j];
}
sm = 0;
ROF(j,i-1,1){
sm += R[x][j];
res.a[i][j] = sm+D[x][j];
}
}
return res;
}
inline Matrix rebuild(int x){// 重构第 x 块
int l = (x-1)*BLO+1,r = std::min(n,BLO*x);
Matrix res = gen(l);
// res.debug();
FOR(i,l+1,r){
res = res*gen(i);
// exit(0);
// res.debug();
}
// res.debug();
return res;
}
#define lc ((x)<<1)
#define rc ((x)<<1|1)
inline void build(int x,int l,int r){
if(l == r){
sm[x] = rebuild(l);
return;
}
int mid = (l + r) >> 1;
build(lc,l,mid);build(rc,mid+1,r);
sm[x] = sm[lc]*sm[rc];
}
inline void update(int x,int l,int r,int p){
if(l == r){
sm[x] = rebuild(l);
return;
}
int mid = (l + r) >> 1;
if(p <= mid) update(lc,l,mid,p);
else update(rc,mid+1,r,p);
sm[x] = sm[lc]*sm[rc];
}
int main(){
scanf("%d%d",&n,&m);
FOR(i,1,n) blo[i] = 1+((i-1)/BLO);
FOR(i,1,n) FOR(j,1,m-1) scanf("%d",&R[i][j]);
FOR(i,1,n-1) FOR(j,1,m) scanf("%d",&D[i][j]);
build(1,1,blo[n]);
// sm[1].debug();
int q;scanf("%d",&q);
while(q--){
int opt;scanf("%d",&opt);
if(opt == 1){
int x,y,w;scanf("%d%d%d",&x,&y,&w);++x;++y;
R[x][y] = w;update(1,1,blo[n],blo[x]);
}
if(opt == 2){
int x,y,w;scanf("%d%d%d",&x,&y,&w);++x;++y;
D[x][y] = w;update(1,1,blo[n],blo[x]);
}
if(opt == 3){
int x,y;scanf("%d%d",&x,&y);
++x;++y;
printf("%d
",sm[1].a[x][y]);
}
}
return 0;
}
/*
3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
1
3 2 1
*/