题目链接

题目大意

$n \times m$ 的网格图 这个网格图中不能往上走 要求支持如下操作：

1. 修改网格图上的一条边
2. 询问从第一行某个点到最后一行某个点的最短路径

$n \leq 5000,m \leq 200,q \leq 2\times 10^5$ 修改次数 $d \leq 500$。

题解

看到这个行+单点修改可以考虑维护一个线段树：令 $A_{i,j}$ 表示当前块内上面第 $i$ 个点到下面第 $j$ 个点的最短距离，合并的时候是一个$(\min,+)$ 的矩乘。这样是 $O(dm^3logn)$ 的复杂度 不可能通过。

优化 1

考虑合并两块的时候 先固定起点 $i$ 。设底行的某个点为 $j$ ，与中间线上相交的点为 $k$。我们可以发现 随着 $j$ 的增加 $k$ 一定不会减少。于是这个有单调性 可以用类似于决策单调性分治的方法做 单次合并时间复杂度变成了 $O(m^2logm)$可能卡常后足以通过此题

优化 2

我们设 $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\times 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]," \n"[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\n",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
*/