题目分析

我们需要处理一个蛋糕分段问题：每次将最右边的偶数长度蛋糕段对半切分，直到所有段长度都为奇数。然后回答第 $X_i$ 段蛋糕的长度。

关键观察

1. 数学性质：任何偶数都可以表示为 $2^k \times m$ 的形式，其中 $m$ 是奇数
2. 切分规律：长度为 $A_i$ 的蛋糕段最终会被切分成 $2^k$ 段长度为 $m$ 的蛋糕
3. 前缀和定位：通过前缀和可以快速定位第 $X_i$ 段属于哪个原始蛋糕段

算法思路

1. 预处理阶段

对于每个原始蛋糕段 $A_i$：

• 不断除以 2 直到得到奇数 $a[i]$
• 记录切分次数 $k$，则该段会被切分成 $cnt[i] = 2^k$ 段
• 计算前缀和 $s[i] = s[i-1] + cnt[i]$

2. 查询阶段

对于每个查询 $X_i$：

• 使用二分查找在前缀和数组中找到第一个 $s[pos] \geq X_i$ 的位置
• 答案就是 $a[pos]$（该位置对应的奇数长度）

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
int n, cnt[N], a[N];
ll s[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt[i] = 1;
        // 分解为 2^k * 奇数的形式
        while (a[i] % 2 == 0) {
            a[i] /= 2;
            cnt[i] *= 2;
        }
        s[i] = s[i - 1] + cnt[i]; // 前缀和
    }
    
    int q;
    cin >> q;
    while (q--) {
        ll x;
        cin >> x;
        // 二分查找定位
        int pos = lower_bound(s + 1, s + n + 1, x) - s;
        cout << a[pos] << '\n';
    }
    return 0;
}

算法正确性

以样例1为例：

• $A = [14, 9, 8, 12]$
• 分解后：
  • $14 = 2^1 \times 7$ → 切分成2段长度为7
  • $9 = 2^0 \times 9$ → 切分成1段长度为9
  • $8 = 2^3 \times 1$ → 切分成8段长度为1
  • $12 = 2^2 \times 3$ → 切分成4段长度为3
• 前缀和：$s = [2, 3, 11, 15]$
• 查询 $X_i = 3$ 时，找到 $s[2] = 3 \geq 3$，答案为 $a[2] = 9$

复杂度分析

• 预处理：$O(N \log A_i)$，每个数最多除 $\log A_i$ 次
• 每次查询：$O(\log N)$，二分查找
• 总复杂度：$O(N \log A_i + Q \log N)$

算法优势

1. 避免显式模拟：通过数学分析直接计算结果
2. 高效查询：利用前缀和和二分快速定位
3. 处理大数据：支持 $X_i$ 达到 $10^{15}$ 的查询

该算法巧妙利用了问题的数学性质，将复杂的切分过程转化为简单的数学计算，实现了高效求解。