题解：AT_joi2022ho_a インターカステラー (Intercastellar)

PenroseHUGO · 2025-12-16 17:18:56 · 题解

题意简述

给定若干线段，第 i 段长度为 a_i。
不断对 长度为偶数 的线段进行操作：
将其截成两条 长度相等 的线段（位置不变），直到所有线段长度均为奇数。

操作完成后，回答 q 个询问：
第 i 个询问给出 x_i，要求输出 最终从左数第 x_i 条线段的长度。

关键观察

对一条初始长度为 a 的线段：

• 每次若为偶数，就被拆成两个相同的线段
• 本质是在不断 除以 2，直到变成奇数

设：

则最终结果是：

• 该线段会变成 2^k 条
• 每条长度都是 b

问题转化

对每个初始线段 a_i：

1. 求出其奇数部分 b_i
2. 求出它最终会贡献的段数 cnt_i

这样，所有最终线段就是：

• 按顺序拼接的若干“块”
• 第 i 块包含 cnt_i 条长度为 b_i 的线段

询问处理

• 预处理每一块的前缀和： S_i = \sum_{j=1}^i cnt_j
• 对于询问 x：
  • 找到最小的 i，使 S_i \ge x
  • 输出对应的 b_i

使用二分即可。

复杂度分析

• 预处理：O(n \log a)
• 每次询问：O(\log n)
• 总复杂度：O((n+q)\log n)

参考实现（C++）

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

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

    int n;
    cin >> n;

    vector<long long> cnt, val;
    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        long long c = 1;
        while (a % 2 == 0) {
            a /= 2;
            c *= 2;
        }
        val.push_back(a);
        cnt.push_back(c);
    }

    // 前缀和
    vector<long long> pref(n);
    pref[0] = cnt[0];
    for (int i = 1; i < n; i++) {
        pref[i] = pref[i - 1] + cnt[i];
    }

    int q;
    cin >> q;
    while (q--) {
        long long x;
        cin >> x;
        int pos = lower_bound(pref.begin(), pref.end(), x) - pref.begin();
        cout << val[pos] << '\n';
    }

    return 0;
}