题解：P16558 [ICPC 2026 LAC] Late and Disobedient

lailai0916 · 2026-08-31 07:08:54 · 题解

题意简述

有 n 个行人，第 i 人在时刻 t 的位置为 x_i+v_it。对每个给定的整数时刻，判断线段 [0,L] 内是否存在长度至少为 C 的空隙。空隙端点可以有行人，内部不能有行人。

询问时刻递增，询问数可达 2\times10^6。

解题思路

逐次询问排序行人位置需要 O(qn\log n)，不能接受。反过来考虑：先求出所有可以通过的整数时刻区间，再统一回答询问。

只需考虑以下两类位置作为空隙左端点：线段左端点 0，以及某个行人的位置。

因为任何合法空隙都可以向左扩展，直到碰到最近的行人或边界 0。扩展后的空隙仍然合法，也不会变短。从这个左端点开始取长度 C，就得到我们要找的区间。

加入一个位置始终为 0 的虚拟点，记为 x_0=v_0=0。固定左端点编号 i，令其位置为 s_i(t)=x_i+v_it。首先必须保证整个长度为 C 的区间都在线段内：

这是关于 t 的一次不等式，结合 0\le t\le10^9，可以求得一个允许的整数时间区间 [l,r]。若区间为空，跳过这个左端点。

行人 j 挡住当前区间，当且仅当它严格位于两端点之间：

所有初始位置、速度和询问时刻都是整数，因此行人位置也是整数。严格不等式可以精确地改写为闭区间条件：

由此得到行人 j 的禁止时间区间，再与 [l,r] 取交。两端相等的位置不会被排除，符合题目允许空隙恰好宽为 C 的要求。多个行人重合、相向运动或者速度相同，也都包含在这个判断中。

对固定的 i，一共有至多 n 个禁止区间。按左端点排序并扫描它们的并集，未被覆盖的整数时刻就是以 s_i(t) 为左端点的可行时刻。

具体维护第一个尚未处理的时刻 p，代码中用 pos 表示。遇到禁止区间 [u,w] 时，若 p<u，就将 [p,u-1] 加入答案；然后令 p=\max(p,w+1)。所有区间处理完后，若 p\le r，还要加入末尾区间 [p,r]。

这样得到的每个时间区间都有一个确定的合法左端点，因此不会产生误判；而任何可以通过的时刻至少有一个前述左端点，也必定出现在某个可行区间中，所以没有遗漏。

代码用 get 将条件 a\le x+vt\le b 与当前时间区间求交。若 v<0，将整个不等式取负并交换上下界，转为正速度；若 v=0，条件要么始终成立，要么始终不成立。正速度时使用以下边界：

C++ 的整数除法向 0 截断，不能直接当作向下取整。对于正分母，余数为正时给商加 1 得到上取整，余数为负时给商减 1 得到下取整。整个过程不使用浮点数，避免在恰好接触行人的时刻判断错误。

将所有左端点产生的可行时间区间汇总，按左端点排序。询问时刻递增，可以用一个指针跳过右端点小于当前时刻的区间。剩余的第一个区间若左端点不大于询问时刻，则回答 Y，否则回答 N。不必预先合并重叠区间：被跳过的区间不可能覆盖当前或之后的询问，而其余区间的左端点只会更大。

每个左端点至多产生 n+1 个可行区间，总数为 O(n^2)。时间复杂度为 O(n^2\log n+q)，空间复杂度为 O(n^2)。

参考代码

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

using ll=long long;
using pll=pair<ll,ll>;
const int N=1005;
ll x[N],v[N];
void get(ll x,ll v,ll a,ll b,ll &l,ll &r)
{
    if(v<0)
    {
        x=-x;
        v=-v;
        ll t=a;
        a=-b;
        b=-t;
    }
    if(!v)
    {
        if(x<a||x>b)l=1,r=0;
        return;
    }
    l=max(l,(a-x)/v+((a-x)%v>0));
    r=min(r,(b-x)/v-((b-x)%v<0));
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,c,len;
    cin>>n>>c>>len;
    for(int i=1;i<=n;i++)cin>>x[i]>>v[i];
    vector<pll> a;
    for(int i=0;i<=n;i++)
    {
        ll l=0,r=1000000000;
        get(x[i],v[i],0,len-c,l,r);
        if(l>r)continue;
        vector<pll> b;
        for(int j=1;j<=n;j++)
        {
            ll u=l,w=r;
            get(x[j]-x[i],v[j]-v[i],1,c-1,u,w);
            if(u<=w)b.push_back({u,w});
        }
        sort(b.begin(),b.end());
        ll pos=l;
        for(auto t:b)
        {
            if(pos<t.first)a.push_back({pos,t.first-1});
            pos=max(pos,t.second+1);
        }
        if(pos<=r)a.push_back({pos,r});
    }
    sort(a.begin(),a.end());
    int q;
    cin>>q;
    int pos=0;
    while(q--)
    {
        ll t;
        cin>>t;
        while(pos<a.size()&&a[pos].second<t)pos++;
        cout<<(pos<a.size()&&a[pos].first<=t?'Y':'N')<<'\n';
    }
    return 0;
}