3632

cryozwq · 2023-10-28 15:41:57 · 题解

这题为什么 n\le 10^3？

显然就是我们考虑在一个矩形上走到另外一个矩形上，那么必然要不是从一个顶点开始走到边上或者顶点，要不就是边上走到一个顶点，把所有这些关键点抓出来跑最短路即可。

具体来说，对于一个矩形的每个顶点可以朝两个方向走，对于每个顶点，我们需要找到这每个方向走第一个矩形是谁，也就容易知道会走到这个矩形哪条边的具体某个位置，在这两个点之间连边。把所有这些位置抓出来，然后把一个矩形上的所有相邻且可达的点连上边，最后跑最短路即可。（两条边之间的边权就是曼哈顿距离）

比如对于下面这个图，红色表示需要连的边，绿色表示需要建的点。

这个暴力做是 n^2 的，也可以过。但是，我们当然要精益求精对不对？容易发现这个问题事实上可以简单扫描线，就是扫过去的时候维护一个线段树，维护每个位置当前被哪个矩形覆盖。一个实现细节是，只用写从左到右的扫描线，然后每次翻转坐标系即可。

代码（并没有可读性）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
int T;
int data[maxn],dt;
int n;
int tax[maxn],tay[maxn],tbx[maxn],tby[maxn];
int ax[maxn],ay[maxn],bx[maxn],by[maxn];
int xs,ys,xt,yt;
int tot;
int id[maxn][4],idt;
bool vis[maxn];
ll dis[maxn];
struct pr{
    ll w;
    int u;
};
inline bool operator <(pr a,pr b){
    return a.w>b.w;
}
priority_queue<pr>q;
struct Edge{
    int v;
    ll w;
    int nxt;
}e[maxn];
int h[maxn],cnt;
void add(int u,int v,ll w){
//   cout<<u<<" "<<v<<" "<<w<<endl;
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=h[u];
    h[u]=cnt;
    swap(u,v);
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=h[u];
    h[u]=cnt;
}
const ll infll=1e18;
void dijkstra(int s){
    for(int i=1;i<=idt;i++){
        dis[i]=infll;
        vis[i]=0;
    }
    dis[s]=0;
    q.push((pr){0,s});
    while(q.size()){
        pr now=q.top();
        int u=now.u;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=h[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                q.push((pr){dis[v],v});
            }
        }
    }
} 
int lz[maxn];
#define ls 2*i
#define rs 2*i+1
int al[maxn];
void push_up(int i){
    if(al[ls]==al[rs])al[i]=al[ls];
    else al[i]=-1;
}
void build(int i,int l,int r){
    lz[i]=-1;
    al[i]=0;
    if(l==r)return ;
    int mid=(l+r)/2;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void push_down(int i){
    if(lz[i]==-1)return ;
    al[ls]=al[rs]=lz[i];
    lz[ls]=lz[rs]=lz[i];    
    lz[i]=-1;
}
void update(int i,int l,int r,int u,int v,int k){
    if(u<=l&&r<=v){
        al[i]=k;
        lz[i]=k;
        return ;
    }
    push_down(i);
    int mid=(l+r)/2;
    if(u<=mid)update(ls,l,mid,u,v,k);
    if(mid+1<=v)update(rs,mid+1,r,u,v,k);
    push_up(i);
}
int query(int i,int l,int r,int x){
    if(l==r)return al[i];
    push_down(i);
    int mid=(l+r)/2;
    if(x<=mid)return query(ls,l,mid,x);
    else return query(rs,mid+1,r,x);
}
map<int,int>mp[maxn];
struct node{
    int tp;
    int l,r,x;
};
vector<node>G[maxn];
int m1[maxn],m2[maxn];
void solve(){
    build(1,1,dt);
    for(int i=1;i<=tot;i++)m1[i]=m2[i]=0;
    for(int i=1;i<=dt;i++)G[i].clear();
    for(int i=1;i<=tot;i++){
        G[ax[i]].push_back((node){2,ay[i],by[i],i});
        G[bx[i]].push_back((node){1,ay[i],by[i],i});
    }
    for(int i=1;i<=dt;i++){
        for(auto v:G[i]){
            if(v.tp==1){
                // cout<<"UPDATE"<<v.l<<" "<<v.r<<" "<<v.x<<endl;
                update(1,1,dt,v.l,v.r,v.x);
            }
            if(v.tp==2){
                m1[v.x]=query(1,1,dt,v.l);
                m2[v.x]=query(1,1,dt,v.r);
            }
        }
    }
}
/*
12
03
*/
struct pit{
    int x,y;
}cr[maxn];
vector<pit>ptt[maxn]; 
int ct;
inline bool cmpx(pit a,pit b){
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
inline bool cmpy(pit a,pit b){
    if(a.y==b.y)return a.x<b.x;
    return a.y<b.y;
}
bool tag;
void lik(int ax,int ay,int bx,int by,int i=0,int j=0){
//  cout<<ax<<" "<<ay<<" "<<bx<<" "<<by<<endl;
    if(ax!=bx&&ay!=by)return ;
    if(!mp[ax][ay]){
        mp[ax][ay]=++idt;
        if(!tag)ptt[i].push_back((pit){ax,ay});
        else ptt[i].push_back((pit){ay,ax});
    }
    int A=mp[ax][ay];
    if(!mp[bx][by]){
        mp[bx][by]=++idt;
        if(!tag)ptt[j].push_back((pit){bx,by});
        else ptt[j].push_back((pit){by,bx});
    }
    int B=mp[bx][by];
    add(A,B,1ll*abs(data[bx]-data[ax])+1ll*abs(data[by]-data[ay]));
}
void link(int i,int j,int op){
    if(!j)return ;
    if(op==0){
        lik(ax[i],ay[i],bx[j],ay[i],i,j);
    }
    if(op==1){ 
        lik(ax[i],by[i],bx[j],by[i],i,j);
    }
    if(op==2){
        lik(bx[i],by[i],ax[j],by[i],i,j); 
    }
    if(op==3){
        lik(bx[i],ay[i],ax[j],ay[i],i,j);
    }
}
#define mk make_pair
#define fr first
#define sc second
vector<pair<pair<int,int>,int> >vc;
void filpxy(){
    tag^=1;
    vc.clear();
    for(int i=1;i<=dt;i++){
    for(auto vv:mp[i]){
//      cout<<i<<"-"<<vv.fr<<endl;
        vc.push_back(mk(mk(i,vv.fr),vv.sc));
    }
    }
    for(int i=1;i<=dt;i++)mp[i].clear();
    for(auto v:vc){
        mp[v.fr.sc][v.fr.fr]=v.sc;
    } 
    for(int i=1;i<=tot;i++){
        swap(ax[i],ay[i]);
        swap(bx[i],by[i]);
    }
}
void filpx(){
    for(int i=1;i<=tot;i++){
        ax[i]=dt-ax[i]+1;
        bx[i]=dt-bx[i]+1;
        swap(ax[i],bx[i]);
    }
}
int main(){ 
    scanf("%d",&T);
    while(T--){
        tag=0;
        ct=0;
        cnt=0;
        for(int i=1;i<=tot;i++)ptt[i].clear();
        for(int i=0;i<=dt;i++)mp[i].clear();
        for(int i=1;i<=idt;i++)h[i]=0;
        idt=0;
        tot=0;
        dt=0;
        scanf("%d%d%d%d",&xs,&ys,&xt,&yt);
        data[++dt]=xs;data[++dt]=ys;data[++dt]=xt;data[++dt]=yt;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d%d%d%d",&ax[i],&ay[i],&bx[i],&by[i]);
            if(ax[i]>bx[i])swap(ax[i],bx[i]);
            if(ay[i]>by[i])swap(ay[i],by[i]);
            data[++dt]=ax[i];
            data[++dt]=ay[i];
            data[++dt]=bx[i];
            data[++dt]=by[i];
        } 
        sort(data+1,data+dt+1);
        dt=unique(data+1,data+dt+1)-data-1;
        tax[n+1]=tbx[n+1]=xs;
        tay[n+1]=tby[n+1]=ys;
        tax[n+2]=tbx[n+2]=xt;
        tay[n+2]=tby[n+2]=yt;
        xs=lower_bound(data+1,data+dt+1,xs)-data;
        ys=lower_bound(data+1,data+dt+1,ys)-data;
        xt=lower_bound(data+1,data+dt+1,xt)-data;
        yt=lower_bound(data+1,data+dt+1,yt)-data;
        for(int i=1;i<=n;i++){
            ax[i]=lower_bound(data+1,data+dt+1,ax[i])-data;
            ay[i]=lower_bound(data+1,data+dt+1,ay[i])-data;
            bx[i]=lower_bound(data+1,data+dt+1,bx[i])-data;
            by[i]=lower_bound(data+1,data+dt+1,by[i])-data;
            mp[ax[i]][ay[i]]=++idt;  
            mp[ax[i]][by[i]]=++idt;
            mp[bx[i]][ay[i]]=++idt;  
            mp[bx[i]][by[i]]=++idt;
            ptt[i].push_back((pit){ax[i],ay[i]});
            ptt[i].push_back((pit){bx[i],ay[i]});
            ptt[i].push_back((pit){ax[i],by[i]});
            ptt[i].push_back((pit){bx[i],by[i]});
        }
        tot=n+2; 
        ax[n+1]=bx[n+1]=xs;
        ay[n+1]=by[n+1]=ys;
        ax[n+2]=bx[n+2]=xt;
        ay[n+2]=by[n+2]=yt;  
        mp[xs][ys]=++idt;  
        mp[xt][yt]=++idt;
        solve();
        for(int i=1;i<=tot;i++){
//          cout<<i<<" "<<m1[i]<<" "<<m2[i]<<endl;
            link(i,m1[i],0);
            link(i,m2[i],1);        
        }
        filpx();
        solve();
        filpx();
        for(int i=1;i<=tot;i++){
            // cout<<i<<" "<<m1[i]<<" "<<m2[i]<<endl;
            link(i,m1[i],3);
            link(i,m2[i],2);        
        }
        filpxy();
        solve();
        for(int i=1;i<=tot;i++){
            // cout<<i<<" "<<m1[i]<<" "<<m2[i]<<endl;
            link(i,m1[i],0);
            link(i,m2[i],1);        
        }
        filpxy();
        filpxy();
        filpx();
        solve();
        filpx();
        for(int i=1;i<=tot;i++){ 
            link(i,m1[i],3);
            link(i,m2[i],2);    
        }
        filpxy(); 
//      cout<<"trash!!!!!!!!!!!!!!!!!!!!!!!!!!!!"<<endl;
        for(int id=1;id<=tot;id++){
            ct=0;
            for(auto v:ptt[id]){
                if(v.x==ax[id]||v.x==bx[id])cr[++ct]=v;
            }
            sort(cr+1,cr+ct+1,cmpx);
            for(int i=1;i<=ct;i++){
                if(i!=1&&cr[i-1].x==cr[i].x)lik(cr[i].x,cr[i].y,cr[i-1].x,cr[i-1].y);
                if(i!=ct&&cr[i+1].x==cr[i].x)lik(cr[i].x,cr[i].y,cr[i+1].x,cr[i+1].y);
            }
            ct=0;
            for(auto v:ptt[id]){
                if(v.y==ay[id]||v.y==by[id])cr[++ct]=v;
            }
            sort(cr+1,cr+ct+1,cmpy);
            for(int i=1;i<=ct;i++){
                if(i!=1&&cr[i-1].y==cr[i].y)lik(cr[i].x,cr[i].y,cr[i-1].x,cr[i-1].y);
                if(i!=ct&&cr[i+1].y==cr[i].y)lik(cr[i].x,cr[i].y,cr[i+1].x,cr[i+1].y);
            }
        } 
//      cout<<mp[xs][ys]<<" "<<mp[xt][yt]<<endl;
        dijkstra(mp[xs][ys]);
        if(dis[mp[xt][yt]]>=infll)printf("No Path\n");
        else printf("%lld\n",dis[mp[xt][yt]]);
        // return 0;
    }
    return 0;
}