萌新求卡常

RT

loj轻松跑过，luogu卡常卡疯

火车头啥的好像没用（

加了inline好像更慢（

#include<bits/stdc++.h>
#define MAXN 100010
#define mp make_pair
using namespace std;
char gc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int read()
{
    int num=0,fl=1;char c=gc();
    while(!isdigit(c)){if(c=='-')fl=-1;c=gc();}
    while(isdigit(c)){num=num*10+c-48;c=gc();}
    return num*fl;
}
int n,m;
struct Node{int x[2],y[2],q;}que[MAXN],tmp[MAXN];
struct node{int to,next,val;}Edge[MAXN<<1];
int Head[MAXN],cnt_Edge;
void Add_Edge(int u,int v,int w){Edge[++cnt_Edge]={v,Head[u],w};Head[u]=cnt_Edge;}
int ans[MAXN];
int get(int x,int y){return (x-1)*m+y;}
int dis[20010];bool vis[20010],tag[20010];
void dijkstra(int sx,int sy,int xl,int xr,int yl,int yr)
{
    priority_queue<pair<int,int> >Q;
    for(int i=xl;i<=xr;i++)
        for(int j=yl;j<=yr;j++)
            vis[get(i,j)]=false,dis[get(i,j)]=0x3f3f3f3f;
    int s=get(sx,sy);Q.push(mp(0,s));dis[s]=0;
    while(!Q.empty())
    {
        int u=Q.top().second;Q.pop();
        if(vis[u])continue;vis[u]=true;
        for(int i=Head[u];i;i=Edge[i].next)
        {
            int v=Edge[i].to,w=Edge[i].val;
            if(tag[v])continue;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                Q.push(mp(-dis[v],v));
            }
        }
    }
}
void cdq(int xl,int xr,int yl,int yr,int ql,int qr)
{
    if(xl>xr)return;if(yl>yr)return;if(ql>qr)return;
    if(xr-xl>yr-yl)
    {
        int mid=xr+xl>>1;
        for(int i=yl;i<=yr;i++)
        {
            dijkstra(mid,i,xl,xr,yl,yr);tag[get(mid,i)]=true;
            for(int j=ql;j<=qr;j++)
                ans[que[j].q]=min(ans[que[j].q],dis[get(que[j].x[1],que[j].y[1])]+
                                            dis[get(que[j].x[0],que[j].y[0])]);
        }
        int l=ql-1,r=qr+1;
        for(int i=ql;i<=qr;i++)
        {
            if(que[i].x[1]<mid&&que[i].x[0]<mid)tmp[++l]=que[i];
            if(que[i].x[1]>mid&&que[i].x[0]>mid)tmp[--r]=que[i];
        }
        for(int i=ql;i<=l;i++)que[i]=tmp[i];for(int i=r;i<=qr;i++)que[i]=tmp[i];
        cdq(xl,mid-1,yl,yr,ql,l);cdq(mid+1,xr,yl,yr,r,qr);
    }else
    {
        int mid=yr+yl>>1;
        for(int i=xl;i<=xr;i++)
        {
            dijkstra(i,mid,xl,xr,yl,yr);tag[get(i,mid)]=true;
            for(int j=ql;j<=qr;j++)
                ans[que[j].q]=min(ans[que[j].q],dis[get(que[j].x[1],que[j].y[1])]+
                                            dis[get(que[j].x[0],que[j].y[0])]);
        }
        int l=ql-1,r=qr+1;
        for(int i=ql;i<=qr;i++)
        {
            if(que[i].y[1]<mid&&que[i].y[0]<mid)tmp[++l]=que[i];
            if(que[i].y[1]>mid&&que[i].y[0]>mid)tmp[--r]=que[i];
        }
        for(int i=ql;i<=l;i++)que[i]=tmp[i];for(int i=r;i<=qr;i++)que[i]=tmp[i];
        cdq(xl,xr,yl,mid-1,ql,l);cdq(xl,xr,mid+1,yr,r,qr);
    }
}
int main()
{
    n=read();m=read();
    memset(ans,0x3f,sizeof(ans));
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
        {
            int x=read();int u=get(i,j),v=get(i,j+1);
            Add_Edge(u,v,x);Add_Edge(v,u,x);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
        {
            int x=read();int u=get(i,j),v=get(i+1,j);
            Add_Edge(u,v,x);Add_Edge(v,u,x);
        }
    int T=read();
    for(int i=1;i<=T;i++)
        que[i].x[1]=read(),que[i].y[1]=read(),que[i].x[0]=read(),que[i].y[0]=read(),que[i].q=i;
    cdq(1,n,1,m,1,T);for(int i=1;i<=T;i++)printf("%d\n",ans[i]);
    return 0;
}

或许是我写假了/kk