P10198 题解

· · 题解

Problem Link

题目大意

给定 n 个点的图，时刻 t 在 u 节点，那么 t+1 时刻会在 b_{a,t\bmod a_u} 节点，其中 a_u 是 2 的幂。

数据范围：$n,\sum a_u\le 10^5,d\le 10^{18}$。

思路分析

首先肯定需要倍增，f_{u,t,i} 表示 t 时刻从 u 出发走 2^i 步的结果，但问题是如果路程中遇到 a_v>a_u 的点，t 的信息就不够了。

但我们发现此时直接切换到 v 的位置开始倍增，那么这个过程只会进行 \mathcal O(\log A) 次，因为 a_v\ge 2a_u。

因此 f_{u,t,i} 表示从 u 出发走 2^i 步或到达 a_v>a_u 点的结果，d_{u,t,i} 表示实际运动的步数。

那么查询复杂度 \mathcal O(\log A\log T)，但预处理时需要 \mathcal O(n\log T) 次询问，难以接受。

注意到我们的瓶颈时 f_{u,t,i-1} 可能跳到一个 a_v<a_u 的点，那么就会失去 t 的信息。

那么我们不妨改变定义，直接令 f_{u,t,i} 表示经过 2^i 个 a_v=a_u 的点，或遇到 a_v>a_u 的点时停止。

那么询问时我们会用 \mathcal O(\log A) 轮倍增到达 a 最大的点，随后每轮倍增，剩余路径上 a 的最大值减小，因此倍增总轮数 \mathcal O(\log A)。

时间复杂度 \mathcal O(n\log T+q\log A\log T)。

代码呈现 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
const ll inf=2e18;
int n,q,a[MAXN];
vector <int> b[MAXN],f[MAXN][64];
vector <ll> d[MAXN][64];
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i) {
        b[i].resize(a[i]);
        for(int &p:b[i]) cin>>p;
        for(int k=0;k<=60;++k) d[i][k].resize(a[i]),f[i][k].resize(a[i]);
    }
    for(int s=1;s<MAXN;s<<=1) {
        for(int u=1;u<=n;++u) if(a[u]==s) {
            for(int i=0;i<s;++i) {
                int v=b[u][i]; ll t=1;
                while(a[v]<s&&t<inf) {
                    int w=f[v][60][(i+t)%a[v]];
                    t+=d[v][60][(i+t)%a[v]],v=w;
                }
                f[u][0][i]=v,d[u][0][i]=min(t,inf);
            }
        }
        for(int k=1;k<=60;++k) for(int u=1;u<=n;++u) if(a[u]==s) {
            for(int i=0;i<s;++i) {
                int v=f[u][k-1][i]; ll t=d[u][k-1][i];
                if(a[v]==s) {
                    f[u][k][i]=f[v][k-1][(i+t)%s];
                    d[u][k][i]=min(d[v][k-1][(i+t)%s]+t,inf);
                } else f[u][k][i]=v,d[u][k][i]=t;
            }
        }
    }
    for(int u;q--;) {
        ll dis,cur;
        cin>>u>>cur>>dis;
        while(dis) {
            for(int k=60;~k;--k) if(dis>=d[u][k][cur%a[u]]) {
                int v=f[u][k][cur%a[u]];
                ll t=d[u][k][cur%a[u]];
                if(a[v]!=a[u]) k=61;
                dis-=t,cur+=t,u=v;
            }
            if(dis) u=b[u][cur%a[u]],--dis,++cur;
        }
        cout<<u<<"\n";
    }
    return 0;
}