题解：P17353 [ECNA 2025] Valley Gulls

lailai0916 · 2026-08-31 05:15:34 · 题解

题意简述

用相邻测量点之间的线段表示地形，两端为不可越过的峭壁。雨以恒定速率落下，沿坡面流入低处，水满后可以翻过山脊进入相邻山谷。

给定各鸟巢的横坐标，求每个鸟巢首次被上涨的积水淹没的时刻。

解题思路

把所有局部最高点作为分界，再加上左右端点，便得到若干初始山谷。每个区间内部的雨水都流向同一个低处。即使水面尚未覆盖整个区间，干燥坡面上的雨水也会汇入谷底，所以这个山谷接收雨水的速率是降雨速率乘以整个区间的水平宽度。

水位上涨到左右分界中较低的山脊时，就会向相邻山谷溢流。两端峭壁不能翻越，不能把端点的地面高度当成溢流高度。

困难在于：一个山谷开始向邻谷溢流，并不代表两边的水面立即等高。较高一侧暂时停在山脊高度，它以后收到的雨水流入较低一侧。直接合并为一片等高水面，会使体积与淹没时间出错。

可以在开始溢流时就合并两边的水量核算范围，同时保留每个初始山谷已经积水的最低水位。设初始山谷 i 的这一水位下界为 b_i。初始令 b_i 低于全部地面。对于一个已合并区间，设其中仍在上涨的水位为 H，则初始山谷 i 的实际水位表示为 \max(H,b_i)。

这个表示允许一部分山谷已经在高处蓄满，另一部分仍在低处上涨。当 H 后来超过原来的山脊高度，高处山谷会自然恢复上涨，无须再安排一次特殊合并。

先计算单个初始山谷积水到高度 H 所需的面积 F_i(H)。对于水平跨度为 d、两端高度较小值和较大值分别为 a,b 的一段坡面，其贡献为：

中间一种情况是水面与坡面相交形成的三角形，最后一种情况是整段坡面上方的梯形。题目保证不同测量点的高度不同，因此分母 b-a 不为 0。

对于包含若干连续初始山谷的区间 I，令其水平总宽度为 W_I，定义：

它表示该区间仍在上涨的水位达到 H 时，全部山谷合计保存的水量。

设降雨速率为 r。从开始下雨到当前时刻，区间中的雨水总量为 rW_It。每次出现跨区间溢流时，我们都会立即把接收方纳入同一个核算范围，所以范围之间没有需要另外扣除的历史流量。因此，水位达到 H 的绝对时刻为：

这里算出的是从第 0 时刻开始的总时间，不能再加上当前时刻。

现在维护这些连续区间。对于区间 I，取左右外侧山脊中较低的高度 h，它的下一次溢流时刻就是 T_I(h)。枚举所有区间，选择时刻最早的一次溢流。

设这次溢流从区间 I 流向区间 J，山脊高度为 h。将 I 内每个初始山谷的下界更新为 \max(b_i,h)，再把 I 合并到 J。接收方原来的下界保持不变。

这一步保持了水位与水量的表示。溢流发生时，供水方的各个水位已经达到 \max(b_i,h)；接收方的水位不会高于 h，否则它应当更早从同一条边界溢流。合并后，供水方暂时保留这些水位，新增雨水流向接收方。直到接收方水位追上相应下界，对应山谷才一起继续上涨。用新的 \max(H,b_i) 表示，恰好描述了这个过程。若两边同时到达山脊高度，更新同样成立。

一次合并后，外侧分界仍是两个山脊或峭壁，内部可能出现不同高度的蓄水区。因此，这个不变式可以一直保持，直至所有初始山谷纳入同一个区间。

鸟巢的高度先用线性插值求出。假设它位于初始山谷 i，高度为 z。若尚未被淹没，其所属区间上涨到 z 的时刻就是 T_I(z)。

每次执行下一次溢流前，先检查所有尚未回答的鸟巢：若它的预计淹没时刻不晚于本次溢流，就记录答案。这个时间段内区间结构和所有下界保持不变，所以计算有效；若预计时刻更晚，则先处理溢流，再用新的区间重新计算。合并时升高水位下界的那些鸟巢，已经在合并前的检查中处理，不会遗漏。

最后仅剩一个区间时，设下一次事件时刻为无穷大，便能一次回答所有剩余鸟巢。

代码中，pos 保存初始山谷的分界位置，low 保存水位下界，并查集 fa 维护区间所属关系，l 和 r 记录每个区间包含的初始山谷范围。area 按线段计算 C_I(H)。全过程无需反解三角形面积对应的水位，也无需按固定时间步长模拟。

设测量点数为 p，鸟巢数为 m。至多发生 O(p) 次区间合并，每次最多进行 m 次 O(p) 的鸟巢面积计算，寻找溢流事件总计扫描 O(p) 段坡面。总时间复杂度为 O(p^2(m+1))，空间复杂度为 O(p+m)。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=55;
const int M=105;
int x[N],y[N],pos[N],fa[N],l[N],r[N],id[M];
double low[N],h[M],ans[M];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
double area(int u,double h)
{
    double res=0;
    for(int i=l[u];i<=r[u];i++)
    {
        double val=max(h,low[i]);
        for(int j=pos[i-1];j<pos[i];j++)
        {
            int mn=min(y[j],y[j+1]),mx=max(y[j],y[j+1]);
            if(val<=mn)continue;
            if(val>=mx)res+=(val-(y[j]+y[j+1])/2.0)*(x[j+1]-x[j]);
            else res+=(val-mn)*(val-mn)/(2*(mx-mn))*(x[j+1]-x[j]);
        }
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    double v;
    cin>>n>>v>>q;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    pos[0]=1;
    int m=0;
    for(int i=2;i<n;i++)if(y[i]>y[i-1]&&y[i]>y[i+1]){m++;pos[m]=i;}
    m++;
    pos[m]=n;
    for(int i=1;i<=m;i++)
    {
        fa[i]=l[i]=r[i]=i;
        low[i]=-1001;
    }
    for(int i=1;i<=q;i++)
    {
        int z;
        cin>>z;
        int j=1;
        while(x[j+1]<z)j++;
        h[i]=y[j]+(double)(y[j+1]-y[j])*(z-x[j])/(x[j+1]-x[j]);
        id[i]=1;
        while(x[pos[id[i]]]<z)id[i]++;
        ans[i]=-1;
    }
    while(1)
    {
        int u=0,to=0;
        double t=1e100,val=0;
        for(int i=1;i<=m;i++)
        {
            if(fa[i]!=i||(l[i]==1&&r[i]==m))continue;
            int j=l[i]>1&&(r[i]==m||y[pos[l[i]-1]]<y[pos[r[i]]])?l[i]-1:r[i];
            double cur=area(i,y[pos[j]])/(v*(x[pos[r[i]]]-x[pos[l[i]-1]]));
            if(cur<t)
            {
                t=cur;
                val=y[pos[j]];
                u=i;
                to=find(j<l[i]?j:j+1);
            }
        }
        for(int i=1;i<=q;i++)
        {
            if(ans[i]>=0)continue;
            int u=find(id[i]);
            double cur=area(u,h[i])/(v*(x[pos[r[u]]]-x[pos[l[u]-1]]));
            if(cur<=t)ans[i]=cur;
        }
        if(!u)break;
        for(int i=l[u];i<=r[u];i++)low[i]=max(low[i],val);
        fa[u]=to;
        l[to]=min(l[to],l[u]);
        r[to]=max(r[to],r[u]);
    }
    for(int i=1;i<=q;i++)cout<<fixed<<setprecision(10)<<ans[i]<<'\n';
    return 0;
}