题解：P16397 [ECUSTPC 2026 Spring] 右灯左行

· · 题解

本来觉得是很有意思的 dp，结果发现 n\le 10^5，那不直接大力线段树？

发现对于一段区间，我们只需要知道其矩形四个顶点两两之间的最短路，其余信息是不需要维护的。合并两个节点时，讨论一下从中间哪个点可以优化路径就行，常数不大。最终将区间两旁的矩形也拉进来看看是否可以优化路径。复杂度 O(n\log n)，略有常数。

对于细节实现方面，id_x=id_y 特判一下；如果点数不多不想分讨直接 Floyd；四个角编号成下图这样会比较方便。

#include<bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=1e5+5;
char cx,cy;int T,n,q;
int a[N],b[N],c[N],d[N],o[N];
struct node{ll s[4][4];}t[N<<2];
void Min(ll&x,ll y){if(y<x)x=y;}
node operator+(node x,node y){
    node z;memset(z.s,0x3f,sizeof(z));
    F(i,0,1)F(j,2,3)
        Min(z.s[i][j],min(x.s[i][2]+y.s[0][j],x.s[i][3]+y.s[1][j])),
        Min(z.s[j][i],min(y.s[j][0]+x.s[2][i],y.s[j][1]+x.s[3][i]));
    F(i,0,1)
        Min(z.s[i][i^1],x.s[i][i^1]),
        Min(z.s[i][i^1],x.s[i][2]+y.s[0][1]+x.s[3][i^1]),
        Min(z.s[i][i^1],x.s[i][3]+y.s[1][0]+x.s[2][i^1]);
    F(i,2,3)
        Min(z.s[i][i^1],y.s[i][i^1]),
        Min(z.s[i][i^1],y.s[i][0]+x.s[2][3]+y.s[1][i^1]),
        Min(z.s[i][i^1],y.s[i][1]+x.s[3][2]+y.s[0][i^1]);
    F(i,0,3)z.s[i][i]=0;
    return z;
}void bd(int p,int l,int r){
    if(l==r){
        mem(t[p].s,0x3f);F(i,0,3)t[p].s[i][i]=0;
        if(o[l])t[p].s[0][2]=a[l],t[p].s[3][1]=b[l],t[p].s[1][0]=c[l],t[p].s[2][3]=d[l];
        else    t[p].s[2][0]=a[l],t[p].s[1][3]=b[l],t[p].s[0][1]=c[l],t[p].s[3][2]=d[l];
        F(k,0,3)F(i,0,3)F(j,0,3)if(i!=j&&i!=k&&j!=k)
            Min(t[p].s[i][j],t[p].s[i][k]+t[p].s[k][j]);
        return;
    }bd(p*2,l,mid),bd(p*2+1,mid+1,r);
    t[p]=t[p*2]+t[p*2+1];
}node ask(int p,int l,int r,int L,int R){
    if(L>R){node z;mem(z.s,0x3f);return z;}
    if(L<=l&&r<=R)return t[p];
    if(R<=mid)return ask(p*2,l,mid,L,R);
    if(mid<L)return ask(p*2+1,mid+1,r,L,R);
    return ask(p*2,l,mid,L,R)+ask(p*2+1,mid+1,r,L,R);
}void solve(){
    cin>>n>>q;
    for(int i=1;i<n;++i)
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    for(int i=1;i<n;++i)
        cin>>cx,o[i]=(cx=='O');
    bd(1,1,n-1);
    for(int x,y,l,r;q;--q){
        cin>>cx>>x>>cy>>y;
        l=min(x,y),r=max(x,y);
        node a=ask(1,1,n-1,1,l-1);
        node b=ask(1,1,n-1,l,r-1);
        node c=ask(1,1,n-1,r,n-1);
        if(x==y){
            cout<<min(a.s[2+(cx=='S')][2+(cy=='S')],c.s[cx=='S'][cy=='S'])<<'\n';
            continue;
        }ll d[4][4];mem(d,0x3f);
        F(i,0,3)F(j,0,3)
            d[i][j]=b.s[i][j];
        Min(d[0][1],a.s[2][3]);
        Min(d[1][0],a.s[3][2]);
        Min(d[2][3],c.s[0][1]);
        Min(d[3][2],c.s[1][0]);
        F(k,0,3)F(i,0,3)F(j,0,3)if(i!=j&&i!=k&&j!=k)
            Min(d[i][j],d[i][k]+d[k][j]);
        cout<<d[(x==r)*2+(cx=='S')][(y==r)*2+(cy=='S')]<<'\n';
    }
}signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    for(cin>>T;T;--T)solve();
    return 0;
}