题解 P4150 【[WC2009]最短路问题】

Rorschachindark · 2020-04-12 10:12:15 · 题解

最短路问题

题目传送门

思路

这道题真的太妙了。

首先，我们可以发现x这么小，所以这一定是个线段树。那我们线段树需要维护什么呢？对于一段区间，我们可以维护ll[i][j],rr[i][j],lr[i][j]。表示什么呢？设线段树上这段区间为l\to r,ll[i][j]就是(i,l)\to (j,l)的最短路径长度，rr[i][j]就是(i,r)\to (j,r)的最短路径长度，lr[i][j]就是(i,l)\to (j,r)的最短路径长度。

那么，我们如何合并两个子区间呢？我们可以再维护两个数组，分别叫做lm[i][j],rm[i][j]。我们假设中点为mid,区间为l\to r,lm[i][j]就是指从(i,l)\to (j,mid)但是必须经过右区间的最短路径长度，rm[i][j]就是指(i,mid+1)\to (j,r)但是必须经过左区间的最短路径长度。

可以得到转移式:

其中ls,rs就是分别表示左右区间。

那我们如何得到大区间的值呢？其实不难列出转移式:

那我们现在就可以解决掉单点修改和建树了。那我们如何查询呢？

假设当前我们需要查询(sx,sy)\to (tx,ty)的最短路，我们可以先求出ls,mid,rs,分别表示1\to sy,sy\to ty,ty\to n这三段区间的ll,rr,lr。

我们再设t1,t2,t3

在图上表示出来就是这样的:

同理可得:

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define INF 1061109567
#define MAXN 100005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,m;

struct Node{
    int ll[6][6],rr[6][6],lr[6][6];
    Node(){
        memset (ll,0x3f,sizeof (ll));
        memset (rr,0x3f,sizeof (rr));
        memset (lr,0x3f,sizeof (lr));
    }
    bool empty()const{
        return ll[0][0] == INF;
    }
}tree[MAXN << 2];

Node operator + (const Node &ls,const Node &rs){
    static int lm[6][6],rm[6][6];
    if (ls.empty()) return rs;
    if (rs.empty()) return ls;
    memset (lm,0x3f,sizeof (lm));
    memset (rm,0x3f,sizeof (rm));
    Node a;
    for (Int k = 0;k < 6;++ k)
        for (Int i = 0;i < 6;++ i)
            for (Int j = 0;j < 6;++ j){
                lm[i][j] = min (lm[i][j],ls.lr[i][k] + rs.ll[k][j] + ls.rr[j][j]);
                rm[i][j] = min (rm[i][j],rs.ll[i][i] + ls.rr[i][k] + rs.lr[k][j]);
            }
    for (Int i = 0;i < 6;++ i)
        for (Int j = 0;j < 6;++ j){
            a.ll[i][j] = ls.ll[i][j];
            a.rr[i][j] = rs.rr[i][j];
            for (Int k = 0;k < 6;++ k){
                a.ll[i][j] = min (a.ll[i][j],lm[i][k] + ls.lr[j][k] - ls.rr[k][k]);
                a.rr[i][j] = min (a.rr[i][j],rm[k][i] + rs.lr[k][j] - rs.ll[k][k]);
                a.lr[i][j] = min (a.lr[i][j],min (lm[i][k] + rm[k][j] - ls.rr[k][k] - rs.ll[k][k],ls.lr[i][k] + rs.lr[k][j]));
            }
        }
    return a;
}

int val[6][MAXN];

void Init (int i,int l){
    int sum[6];
    for (Int j = 0;j < 6;++ j) sum[j] = (j ? sum[j - 1] : 0) + val[j][l];
    for (Int j = 0;j < 6;++ j)
        for (Int k = 0;k < 6;++ k)
            tree[i].ll[j][k] = tree[i].rr[j][k] = tree[i].lr[j][k] = 
            sum[max (j,k)] - (min (j,k) ? sum[min (j,k) - 1] : 0);
}

void build (int i,int l,int r){
    if (l == r) return Init (i,l);
    int mid = (l + r) >> 1;
    build (i << 1,l,mid),build (i << 1 | 1,mid + 1,r);
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
}

void update (int i,int l,int r,int pos){
    if (l == r) return Init (i,l);
    int mid = (l + r) >> 1;
    if (pos <= mid) update (i << 1,l,mid,pos);
    else update (i << 1 | 1,mid + 1,r,pos);
    tree[i] = tree[i << 1] + tree[i << 1 | 1]; 
}

Node query (int i,int l,int r,int tl,int tr){
    if (l >= tl && r <= tr) return tree[i];
    int mid = (l + r) >> 1;
    if (tr <= mid) return query (i << 1,l,mid,tl,tr);
    else if (tl > mid) return query (i << 1 | 1,mid + 1,r,tl,tr);
    else return query (i << 1,l,mid,tl,tr) + query (i << 1 | 1,mid + 1,r,tl,tr);
}

int query (int sx,int sy,int tx,int ty){
    Node ls = query (1,1,n,1,sy);
    Node md = query (1,1,n,sy,ty);
    Node rs = query (1,1,n,ty,n);
    int Ans = md.lr[sx][tx];
    for (Int i = 0;i < 6;++ i)
        for (Int j = 0;j < 6;++ j){
            Ans = min (Ans,md.ll[sx][i] + ls.rr[i][j] + md.lr[j][tx] - val[i][sy] - val[j][sy]);
            Ans = min (Ans,md.lr[sx][i] + rs.ll[i][j] + md.rr[j][tx] - val[i][ty] - val[j][ty]);
            Ans = min (Ans,ls.rr[sx][i] + md.lr[i][j] + rs.ll[j][tx] - val[i][sy] - val[j][ty]);
        }
    return Ans;
}

signed main()
{
    read (n);
    for (Int i = 0;i < 6;++ i)
        for (Int j = 1;j <= n;++ j)
            read (val[i][j]);
    build (1,1,n);
    read (m);
    while (m --){
        int opt;
        read (opt);
        if (opt == 1){
            int x,y,z;
            read (x,y,z);
            x --;
            val[x][y] = z;
            update (1,1,n,y);
        }
        else{
            int x,y,z,w;
            read (x,y,z,w);
            x --,z --;
            if (y > w) swap (x,z),swap (y,w);
            write (query (x,y,z,w)),putchar ('\n');
        }
    }
    return 0;
}