题意理解 我们有一个特殊的完全二叉树结构：

树有 $n+1$ 层，第 $i$ 层有 $i$ 个节点

节点编号规则：第 $i$ 层节点编号从 $\frac{i(i-1)}{2} + 1$ 到 $\frac{i(i+1)}{2}$

有一个序列 $a_1, a_2, \dots, a_n$，其中 $a_i$ 是第 $i$ 层的一个特殊节点

特殊节点 $a_i$ 有两个儿子，同一层的其他节点只有一个儿子

关键点：这实际上定义了一棵非完全二叉树，特殊节点会"分裂"出额外的分支。

树的结构分析

1. 编号系统 第 $i$ 层的节点编号范围： 从 i ( i − 1 ) 2

1 到 i ( i + 1 ) 2 从
2 i(i−1) ​ +1 到
2 i(i+1) ​

总节点数： ( n + 1 ) ( n + 2 ) 2 2 (n+1)(n+2) ​

2. 父子关系 对于第 $i$ 层第 $j$ 个节点（$j$ 从 1 到 $i$）：

如果 $j < a_i - \frac{i(i-1)}{2}$：父节点是第 $i-1$ 层第 $j$ 个节点

如果 $j = a_i - \frac{i(i-1)}{2}$：父节点是 $a_i$（特殊节点）

如果 $j > a_i - \frac{i(i-1)}{2}$：父节点是第 $i-1$ 层第 $j-1$ 个节点

核心思路 方法1：路径追踪法 对于任意节点 $x$，我们可以找到它所在的层 $d$ 和在该层的位置 $p$：

通过二分查找找到满足 $\frac{d(d+1)}{2} \geq x$ 的最小 $d$

位置 $p = x - \frac{d(d-1)}{2}$

然后不断向上追溯父节点，直到根节点。对 $x$ 和 $y$ 都这样做，找到它们路径上的最后一个公共节点。

方法2：数学映射法 观察发现，这棵树可以看作是在一个完全二叉树的基础上，通过特殊节点引入额外的分支。

我们可以建立从"虚拟完全二叉树"到实际树的映射关系，然后利用完全二叉树的性质快速计算LCA。

高效算法实现 步骤1：预处理 cpp vector layer_start(n+2); for (int i = 0; i <= n+1; i++) { layer_start[i] = i * (i-1) / 2 + 1; } 步骤2：节点定位 cpp pair<int, int> locate(int x) { int d = lower_bound(layer_start.begin(), layer_start.end(), x + 1) - layer_start.begin() - 1; int pos = x - layer_start[d] + 1; return {d, pos}; } 步骤3：父节点计算 cpp int get_parent(int d, int pos) { if (d == 1) return 1; // 根节点

int special_pos = a[d-1] - layer_start[d-1] + 1;

if (pos < special_pos) {
    return layer_start[d-1] + pos - 1;
} else if (pos == special_pos) {
    return a[d-1];
} else {
    return layer_start[d-1] + pos - 2;
}

} 步骤4：LCA计算 cpp int lca(int x, int y) { if (x == y) return x;

auto [dx, px] = locate(x);
auto [dy, py] = locate(y);

// 提到同一深度
while (dx > dy) {
    x = get_parent(dx, px);
    auto new_pos = locate(x);
    dx = new_pos.first;
    px = new_pos.second;
}
while (dy > dx) {
    y = get_parent(dy, py);
    auto new_pos = locate(y);
    dy = new_pos.first;
    py = new_pos.second;
}

// 同时向上
while (x != y) {
    x = get_parent(dx, px);
    y = get_parent(dy, py);
    auto pos_x = locate(x);
    auto pos_y = locate(y);
    dx = pos_x.first; px = pos_x.second;
    dy = pos_y.first; py = pos_y.second;
}

return x;

} 复杂度优化 问题 直接实现上述算法最坏复杂度 $O(q \cdot n)$，对于 $n,q \leq 2\times 10^5$ 会超时。

优化方案 方案1：二进制提升（倍增法） 预处理每个节点的 $2^k$ 级祖先，这样可以在 $O(\log n)$ 时间内完成LCA查询。

cpp // 预处理倍增数组 void preprocess() { for (int k = 1; k < LOG; k++) { for (int i = 1; i <= total_nodes; i++) { parent[i][k] = parent[parent[i][k-1]][k-1]; } } }

// 倍增LCA int lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v);

// 提到同一深度
for (int k = LOG-1; k >= 0; k--) {
    if (depth[u] - (1<<k) >= depth[v]) {
        u = parent[u][k];
    }
}

if (u == v) return u;

// 同时向上跳
for (int k = LOG-1; k >= 0; k--) {
    if (parent[u][k] != parent[v][k]) {
        u = parent[u][k];
        v = parent[v][k];
    }
}

return parent[u][0];

} 方案2：欧拉序+RMQ 将树转化为欧拉序列，然后用RMQ求解LCA。

完整代码框架 cpp #include <bits/stdc++.h> using namespace std; #define int long long

const int MAXN = 200010; const int LOG = 20;

int n, q, t; int a[MAXN]; int total_nodes; int depth[MAXN * 3]; int parent[MAXN * 3][LOG];

// 节点定位、父节点计算、预处理、LCA查询... // 具体实现参考上述算法

signed main() { ios::sync_with_stdio(false); cin.tie(nullptr);

cin >> n >> q >> t;
for (int i = 1; i <= n; i++) {
    cin >> a[i];
}

total_nodes = (n+1) * (n+2) / 2;

// 构建树结构
build_tree();

// 预处理LCA
preprocess();

int lst = 0;
while (q--) {
    int x, y;
    cin >> x >> y;
    
    if (t == 1) {
        x = (x - 1 + lst) % total_nodes + 1;
        y = (y - 1 + lst) % total_nodes + 1;
    }
    
    lst = query_lca(x, y);
    cout << lst << "\n";
}

return 0;

} 总结 这道题的关键在于：

理解特殊的树结构：基于完全二叉树，通过特殊节点引入分支

高效的节点定位：利用数学公式快速确定节点所在层和位置

LCA算法选择：根据数据规模选择合适的LCA算法（倍增法或欧拉序+RMQ）

通过合理的预处理和算法选择，可以在规定时间内解决这个问题。