P4811

Inui_Sana · 2025-02-09 18:55:08 · 题解

我觉得这题 O((q+K)\sqrt K\log K) 非常自然而且非常可过吧，怎么题解区还没有。

一句话：每次询问枚举短的路线，在长的上二分，再记忆化可过。

考虑分析复杂度。记 k=\sum K_i。询问 x,y，令 K_x<K_y。若 K_x\le\sqrt k，显然每次不会枚举超过 O(\sqrt k) 个位置。这部分是 O(q\sqrt k\log k) 的。

否则，考虑每个位置被枚举了几次。因为 K_y>\sqrt k 所以不同的 y 最多有 \sqrt k 个。记忆化之后，每个位置就会被枚举到不超过 \sqrt k 次。所以这部分是 O(k\sqrt k\log k) 的。

于是总复杂度 O((q+k)\sqrt k\log k)。实现的不太差就能通过。最慢点跑了 2.6s。

也讲一下二分的方法。注意到两车 A,B 速度一样，所以 A 车从 u 直线到 v 的过程中，两车最多相遇一次。同时容易证明，相遇的充要条件为两车位置的大小关系发生变化。于是二分 B 车在 A 分别在 u,v 时的位置，判断大小关系是否变化即可。

代码非常清新。

code：

int n,q,c[N];
vector<int> g[N];
vector<ll> t[N];
map<pair<int,int>,int> mp;
il int getPos(int x,ll tm){
    int p=upper_bound(t[x].begin(),t[x].end(),tm)-t[x].begin()-1;
    return g[x][p+1]>g[x][p]?g[x][p]+tm-t[x][p]:g[x][p]-tm+t[x][p];
}
void Yorushika(){
    read(n,q);
    rep(i,1,n){
        read(c[i]);
        g[i].resize(c[i]+1),t[i].resize(c[i]+1);
        rep(j,1,c[i]){
            read(g[i][j]);
            t[i][j]=j==1?0:t[i][j-1]+abs(g[i][j]-g[i][j-1]);
        }
    }
    while(q--){
        int x,y;read(x,y);
        if(g[x].size()>g[y].size()||g[x].size()==g[y].size()&&x>y){
            swap(x,y);
        }
        if(mp.count(Mp(x,y))){
            printf("%d\n",mp[Mp(x,y)]);
            continue;
        }
        int ans=0;
        rep(i,1,c[x]-1){
            if(t[x][i]>=t[y][c[y]]){
                break;
            }
            ll l=t[x][i],r=min(t[x][i+1],t[y][c[y]]);
            int u1=g[x][i],v1=getPos(y,l),u2=g[x][i+1]>g[x][i]?u1+r-l:u1-r+l,v2=getPos(y,r);
            ans+=(u1>v1)^(u2>v2);
        }
        printf("%d\n",mp[Mp(x,y)]=ans);
    }
}
signed main(){
    int t=1;
    //read(t);
    while(t--){
        Yorushika();
    }
}