题解 P8237 [AGM 2022 资格赛] 过河

· · 题解

首先吐槽一下这个反人类定义。

根据那个反人类开区间定义，其实从岸是可以跳到 f 这根木头的。不难看出那个定义有多反人类/fn。

回归正题，这题其实可以看成一道优化建图的板题了。

考虑一个暴力 m^2 建边，枚举两个木头然后判断是否合法，合法即建边，建边后跑最短路。

但其实我们可以直接沿用 CF1557D 的做法，扫描线扫过去，碰到一根木头的左端点加入这根木头，右端点删除这根木头，不难发现有用的边只有在加入后其相邻两根木头与之的边和删除时剩余相邻两根木头中间的边，可以直接 set 维护。总边数 O(n) 就可以直接最短路了。

由于这个左开右开的原因，处理一个纵坐标的所有事件的时候要先处理删边再处理加边。

//我耳朵瞎掉拉~~
#define setI(x) freopen(x,"r",stdin)
#define setO(x) freopen(x,"w",stdout)
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 2e9
#define mod 998244353
#define int ll
#define N 500005
using namespace std;
inline char gc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
#define gc getchar
inline ll read(){char c=gc();ll su=0,f=1;for (;c<'0'||c>'9';c=gc()) if (c=='-') f=-1;for (;c>='0'&&c<='9';c=gc()) su=su*10+c-'0';return su*f;}
inline void write(ll x){if (x<0){putchar('-');write(-x);return;}if (x>=10) write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x),putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
int n,X[N],L[N],R[N],V[N];
poly G;
int dis[N];
poly I[N],E[N];
set<pa>S;
vector<pa>g[N];
priority_queue<pa>q;
bool cmp(int x,int y)
{
    return X[x]<X[y];
}
void ad(int x,int y,int w)
{
    g[x].push_back(mp(y,w));
}
void BellaKira()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        X[i]=read(),L[i]=read(),R[i]=read()-1;V[i]=read();
        G.push_back(L[i]);
        G.push_back(R[i]+1);
    }
    sort(G.begin(),G.end());
    G.erase(unique(G.begin(),G.end()),G.end());
    for (int i=1;i<=n;i++)
    {
        L[i]=lower_bound(G.begin(),G.end(),L[i])-G.begin()+1;
        R[i]=lower_bound(G.begin(),G.end(),R[i]+1)-G.begin()+1;
        I[L[i]].push_back(i);
        E[R[i]].push_back(i);
    }
    S.insert(mp(0,0));
    S.insert(mp(inf,n+1));
    for (int i=1;i<=G.size();i++)
    {
        for (auto u:E[i])
        {
            S.erase(mp(X[u],u));
        }
        for (auto u:E[i])
        {
            auto it=(S.lower_bound(mp(X[u]+1,0)));
            auto it1=(S.lower_bound(mp(X[u],0)));
            if (it1!=S.begin())
            {
                it1--;
                if (it!=S.end())
                {
                    int x=(*it1).se,y=(*it).se;
                    if (!(x==0&&y==n+1))
                    {
                        ad(x,y,V[x]);
                        ad(y,x,V[y]);
                    }
                }
            }
        }

        for (auto u:I[i])
        {
            S.insert(mp(X[u],u));
        }
        for (auto u:I[i])
        {
            auto it=(S.lower_bound(mp(X[u]+1,0)));
            auto it1=(S.lower_bound(mp(X[u],0)));
            if (it1!=S.begin())
            {
                it1--;
                int x=(*it1).se,y=u;
                ad(x,y,V[x]);
                ad(y,x,V[y]);
            }
            if (it!=S.end())
            {
                int x=(*it).se,y=u;
                ad(x,y,V[x]);
                ad(y,x,V[y]);
            }

        }
    }
    memset(dis,0x3f,sizeof(dis));
    dis[0]=0;
    q.push(mp(0,0));
    while (!q.empty())
    {
        int ds=-q.top().fi,u=q.top().se;
        q.pop();
        if (ds!=dis[u]) continue;
        for (auto U:g[u])
        {
            int v=U.fi,w=U.se;
            if (dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                q.push(mp(-dis[v],v));
            }
        }
    }
    writeln(dis[n+1]);

}
signed main()
{
    int T=1;
    while (T--)
    {
        BellaKira();
    }
}
/*

*/