题解：Infinite Adventure

问题分析

• 有 $N$ 个城市，每个城市 $i$ 有传送周期 $T_i$（$2$ 的幂）
• 若在日期 $t$ 进入城市 $i$ 的传送门，会立即出现在城市 $c_{i, t \bmod T_i}$
• 每个询问 $(v, t, \Delta)$ 要求：从城市 $v$ 出发，在日期 $t$ 开始执行 $\Delta$ 次操作（进入传送门 + 等待1天），求最终所在城市
• 约束：$N \leq 10^5$，$Q \leq 5 \times 10^4$，$T_i$ 为 $2$ 的幂，$\Delta$ 可达 $10^{18}$

核心思路

1. 快速幂思想：由于 $\Delta$ 极大，需用二进制 lifting 技术加速状态转移
2. 状态定义：
   • $f[k][o]$：从状态 $k$ 出发，执行 $2^o$ 步操作后的目标城市
   • $g[k][o]$：从状态 $k$ 出发，执行 $2^o$ 步操作所需的总天数
3. 状态转移：利用 $2$ 的幂特性构建倍增表，实现 $\log \Delta$ 级别的查询处理

算法实现

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

int fi[101000];  // 前缀和数组，记录每个城市的传送表起始索引
int q, t[101000], n;  // t[i]是城市i的周期
#define ll long long
int c[101000];  // 存储所有城市的传送表
int f[100100][62];  // f[k][o]：状态k经过2^o步后的城市
ll g[101000][62];  // g[k][o]：状态k经过2^o步的天数
const ll I = 1e18 + 20;  // 最大天数限制

// 计算状态索引：城市x在时间o时的状态
int iz(int x, ll o) {
    return fi[x] + (o & (t[x] - 1));  // 利用位运算计算o mod t[x]
}

int main() {
    scanf("%d%d", &n, &q);

    // 读取每个城市的周期
    for (int i = 1; i <= n; i++)
        scanf("%d", &t[i]);

    // 读取传送表并构建前缀和索引
    fi[1] = 0;  // 第一个城市的传送表从索引0开始
    for (int i = 1; i <= n; i++) {
        fi[i + 1] = fi[i] + t[i];  // 计算下一个城市的起始索引
        
        // 读取当前城市的传送表
        for (int j = fi[i]; j < fi[i + 1]; j++)
            scanf("%d", &c[j]);
    }

    // 预处理二进制lifting表
    // 按周期大小处理（周期是2的幂）
    for (int j = 1; j < (1 << 20); j <<= 1) {  // j是2的幂次
        for (int o = 0; o <= 60; o++) {  // o是log2步数
            for (int i = 1; i <= n; i++) {
                if (t[i] == j) {  // 只处理周期为j的城市
                    for (int k = fi[i]; k < fi[i + 1]; k++) {  // k是状态索引
                        if (!o) {  // 基础情况：2^0 = 1步
                            int z = k - fi[i];  // 周期内的偏移量
                            int x = c[k];  // 一步到达的城市
                            ll e = 1;  // 步数（初始为1）
                            
                            // 处理连续小周期的快速跳转
                            while (t[x] < j && e < I) {
                                int v = f[iz(x, e + z)][60];  // 预存的快速跳转
                                e += g[iz(x, e + z)][60];  // 累加天数
                                x = v;  // 更新当前城市
                            }
                            
                            f[k][0] = x;  // 记录1步后的城市
                            g[k][0] = e;  // 记录1步的总天数
                            continue;
                        }
                        
                        // 高阶状态（2^o步）
                        int z = k - fi[i];  // 周期内的偏移量
                        int v = f[k][o - 1];  // 先跳2^(o-1)步
                        
                        if (t[v] != j) {  // 目标城市周期不同，无法继续倍增
                            f[k][o] = v;
                            g[k][o] = g[k][o - 1];
                        } else {  // 目标城市周期相同，继续倍增
                            v = iz(v, g[k][o - 1] + z);  // 计算新状态
                            f[k][o] = f[v][o - 1];  // 合并两次2^(o-1)步
                            g[k][o] = min(g[k][o - 1] + g[v][o - 1], I);  // 累加天数
                        }
                    }
                }
            }
        }
    }

    // 处理查询
    for (int i = 1; i <= q; i++) {
        int x;  // 起始城市
        ll e, v;  // e是起始时间，v是剩余步数
        scanf("%d%lld%lld", &x, &e, &v);
        
        while (v) {  // 当还有步数剩余
            // 尝试最大的2^j步跳转
            for (int j = 60; j >= 0 && v; j--) {
                ll pv = g[iz(x, e)][j];  // 2^j步需要的天数
                
                if (pv <= v) {  // 如果可以跳这么多步
                    int nx = f[iz(x, e)][j];  // 跳转后的城市
                    bool same_period = (t[x] == t[nx]);  // 周期是否相同
                    x = nx;  // 更新当前城市
                    e += pv;  // 更新当前时间
                    v -= pv;  // 减少剩余步数
                    
                    if (!same_period) j = 61;  // 周期变化，重新从最大步开始尝试
                }
            }
            
            // 处理剩余的1步
            if (v) {
                x = c[iz(x, e)];  // 执行1步传送
                e++;  // 时间+1
                v--;  // 剩余步数-1
            }
        }
        
        printf("%d\n", x);  // 输出最终城市
    }

    return 0;
}

算法解析

1. 状态编码：每个状态用 (城市, 时间 mod 周期) 表示，通过前缀和数组 fi 映射为唯一索引
2. 二进制 lifting 表构建：
   • 基础情况（$2^0 = 1$ 步）：处理连续小周期的快速跳转，减少状态数
   • 高阶情况（$2^o$ 步）：通过合并两个 $2^{o-1}$ 步的结果构建，利用周期为 $2$ 的幂的特性
3. 查询处理：从最大步长开始尝试跳转，逐步减小步长，直到完成所有 $\Delta$ 步，时间复杂度为 $O(\log \Delta)$ 每查询

该算法利用 $2$ 的幂周期特性和二进制 lifting 技术，高效处理了超大步数的查询，完美适配题目约束。