P9550

Shanganze · 2023-08-16 19:48:53 · 题解

这是一篇不用二维线段树的题解。

题意：

对于一个点 (x,y)，可以由 (i,j) 且 (l1_x\le i\le r1_x,l2_y\le j\le r2_y) 花费 a_{x,y}+a_{i,j} (a_{i,j}=k_i+k_j-i-j) 到达。初始在 (1,1) 求到达每个点的最短时间。

45 pts:

考虑暴力转移，O(n^4)，这里。

100 pts:

考虑题意，对于横坐标为 j 的一整行，都会由 l1_j-r1_j 这几行转移过来，我们可以用类似于悬线法的方式，把每一列 l1_j-r1_j 的点取 \min 归为一个点，可以用 n 个线段树来维护每一列来实现这个操作，然后对于这合并出来的 n 个点放到一棵线段树里，然后更新该行每个点答案，考虑无法到达的点答案加上 inf，由于 dis_{x,y}=dis_{i,j}+a_{i,j}+a_{x,y}，所以在更新完答案后都需加上本身的 a_{i,j}。最后答案减去自身 a_{i,j} 即可，时间复杂度 O(n^2\log n)，空间复杂度 O(n^2\log n)。

注：写横纵坐标时不要写反。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int l1[N],l2[N],r1[N],r2[N],a[N][N],k[N],dis[N][N];
struct a1{int minn;}x[N][N<<2];
void X(int i,int l,int r,int p,int a,int dis){
    if(l==r){
        x[a][p].minn+=dis;
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=i)X(i,l,mid,p<<1,a,dis);
    else X(i,mid+1,r,p<<1|1,a,dis);
    x[a][p].minn=min(x[a][p<<1].minn,x[a][p<<1|1].minn);
}
int G(int L,int R,int l,int r,int p,int a){
    if(l>=L&&r<=R)return x[a][p].minn;
    int mid=(l+r)>>1;
    int ans=1e16;
    if(mid>=L)ans=G(L,R,l,mid,p<<1,a);
    if(mid<R) ans=min(ans,G(L,R,mid+1,r,p<<1|1,a));
    return ans;
}
signed main(){
    int n;
    cin>>n;
    for(int q=1;q<=n;q++){cin>>l1[q];if(l1[q]==0)l1[q]++;}
    for(int q=1;q<=n;q++){cin>>r1[q];}
    for(int q=1;q<=n;q++){cin>>l2[q];if(l2[q]==0)l2[q]++;}
    for(int q=1;q<=n;q++){cin>>r2[q];}
    for(int q=1;q<=n;q++)cin>>k[q];
    for(int q=1;q<=n;q++){
        for(int w=1;w<=n;w++){
            a[q][w]=k[q]+k[w]-q-w;
            X(q,1,n,1,w,a[q][w]);
        }
    }
    for(int q=2;q<=n;q++)X(1,1,n,1,q,1e10);
    for(int w=2;w<=n;w++){
        for(int i=1;i<=n;i++){
            X(i,1,n,1,n+1,G(l1[w],r1[w],1,n,1,i));
        }
        for(int i=1;i<=n;i++){
            if(r2[i]!=0)X(w,1,n,1,i,G(l2[i],r2[i],1,n,1,n+1));
            else X(w,1,n,1,i,1e10);
            X(w,1,n,1,i,a[w][i]);
        }
        for(int i=1;i<=n;i++){
            X(i,1,n,1,n+1,-G(l1[w],r1[w],1,n,1,i));
        }
    }
    for(int q=1;q<=n;q++){
        for(int w=1;w<=n;w++){
            int o=G(q,q,1,n,1,w)-a[q][w];
            if(o>=1e9)cout<<"inf ";
            else cout<<o<<" ";
        }
        cout<<"\n";
    }
    return 0;
}