题目理解

我们有一条长度为 $X$ 的沙滩，有 $n$ 个固定位置的毯子（整数位置，包括 $0$ 和 $X$）。
接着会来 $k$ 个新游客（Bajtazar 是最后一个下车），每个新游客会选择距离最近毯子最远的位置，如果有多个这样的位置，选最靠左的。
新游客的位置可以是实数。
给定 $z$ 个询问，每个询问给出 $k_i$，问 Bajtazar 最终铺毯子的位置（输出不可约分数形式）。

核心思路

这是一个模拟插点的问题，但 $k$ 可以很大（$10^9$），不能直接模拟。

观察：
初始时，$n$ 个固定毯子把沙滩分成 $n-1$ 个区间。
每个区间 $[x_i, x_{i+1}]$ 的长度为 $L_i = x_{i+1} - x_i$。
在区间中间插入新毯子时，会把区间分成两半，每半的长度是 $L_i/2$。

关键：

• 每次选择插入的区间是当前所有区间中长度最大的，长度相同则选最靠左的。
• 插入后，该区间长度减半，变成两个新区间（长度相等）。

数据结构与算法

我们可以把每个区间表示成一个结构：

• 长度 $d$（实际存储可能放大 $2^{30}$ 来避免浮点误差）
• 起点 $a$
• 该区间当前被重复的次数 $t$（因为可能有多个相同长度、起点的区间）

每次我们取长度最大的区间（长度相同按起点排序），然后：

1. 处理掉这个区间的前 $t$ 次插入（对应 $t$ 个新游客）
2. 把区间长度减半，重复次数翻倍（因为每个区间一分为二，数量翻倍）

代码解析

1. 输入与初始化

cin >> n >> m >> q;
F(i, 1, n) cin >> a[i], a[i] <<= 30;

这里把坐标左移 30 位，相当于乘以 $2^{30}$，这样可以用整数运算避免浮点误差。

2. 初始区间

F(i, 1, n - 1) s[i] = {a[i + 1] - a[i] >> 1, a[i], 1};

区间长度取 (a[i+1] - a[i]) >> 1，因为新游客会插在区间中点，所以可用长度是区间长度的一半（到两边的距离）。

3. 排序

sort(s + 1, s + n);

自定义比较：先按长度 $d$ 降序，长度相等按起点 $a$ 升序。

4. 处理询问

dF(i, 60, 0) {
    F(j, 1, n - 1) {
        auto &[d, a, t] = s[j];
        if (d < 1ll << i) continue;
        ...
    }
}

这里从高位到低位（60 到 0）处理区间长度。
如果区间长度 $d \ge 2^i$，则处理这个区间。

5. 计算插入位置

while (now <= q) {
    auto [x, id] = qu[now];
    if (x <= tot + t)
        ans[id] = a + Cal(x - tot, t) * d, ++now;
    else
        break;
}

tot 是已经处理过的游客总数。
Cal(x - tot, t) 计算在这个区间内的第几个位置插入。

6. Cal 函数

int Cal(int x, int t) {
    if (t == 1) return 1;
    if (x <= t >> 1) return Cal(x, t >> 1);
    else return t + Cal(x - (t >> 1), t >> 1);
}

这是一个递归函数，用于确定在 $t$ 个相同区间中，第 $x$ 个插入的位置编号。
它实际上是在一个完全二叉树的叶节点中找第 $x$ 个位置，保持左右平衡。

7. 输出

LL a = ans[i], b = 1ll << 30, g = Gcd(a, b);
cout << a / g << "/" << b / g << "\n";

因为坐标放大了 $2^{30}$，所以分母是 $2^{30}$，要约分。

算法标签

• 贪心（Greedy）
• 模拟
• 分数处理
• 排序
• 递归/分治
• 整数运算放大法（避免浮点误差）

复杂度分析

• 排序初始区间：$O(n \log n)$
• 处理区间时，每个区间最多被处理 $O(\log X)$ 次
• 总复杂度约 $O(n \log X + q \log q)$

总结

这道题的关键在于：

1. 把问题转化为在若干区间中反复取最大长度区间插入
2. 用整数放大避免浮点误差
3. 用 Cal 函数快速计算在多个相同区间中的插入顺序
4. 按长度分层处理，保证高效性

这样就能在 $k$ 很大时依然快速求出 Bajtazar 的位置。