---

题目理解

我们有一个整数 $x$，两种操作：

• 操作 1（floor）：$$x \leftarrow \left\lfloor \frac{x}{2} \right\rfloor$$
• 操作 2（ceil）：$$x \leftarrow \left\lceil \frac{x}{2} \right\rceil$$

必须恰好做 $n$ 次操作 1，$m$ 次操作 2，顺序可以任意。问最后能得到的最小值和最大值。

---

关键观察

1. 二进制表示

考虑 $x$ 的二进制表示。
每次操作相当于右移一位，但操作 2（ceil）在右移时会“向上取整”，即如果最低位是 1，右移后会加 1（相当于进位到高位）。

因此，如果把 $x$ 写成：

$$x = l \cdot 2^{n+m} + r$$

其中 $r < 2^{n+m}$ 是低 $n+m$ 位组成的数，$l$ 是高位部分。
那么经过 $n+m$ 次右移后，结果只剩下 $l$ 或者 $l+1$（取决于最后一步是否进位）。

---

2. 最大值的构造

为了得到最大值，我们希望最后一步产生进位，即最低 $n+m$ 位在最后一次 ceil 操作时能向上进位。

如果 $r$ 的高 $m$ 位（即 $r$ 的最后$m$ 次操作对应的那部分）全是 0，那么无论怎样安排，最后一次操作都不能进位，结果只能是 $l$。
否则，我们可以先做所有 floor 操作，再做所有 ceil 操作，这样在最后一次 ceil 操作时，由于前面 floor 操作已把低位清空，只剩下高位，就会发生进位，得到 $l+1$。

所以：

$$\text{最大值} = \text{先做 } n \text{ 次 floor，再做 } m \text{ 次 ceil} $$

标程中对应 C(F(x,n), m)。

---

3. 最小值的构造

为了得到最小值，我们希望避免进位，即尽量让结果变小。
这时应该先做所有 ceil 操作，再做所有 floor 操作。因为先做 ceil 会尽量把数变小（比如 3→2），然后再 floor 继续缩小，且不会有额外的进位机会。

所以：

$$\text{最小值} = \text{先做 } m \text{ 次 ceil，再做 } n \text{ 次 floor} $$

标程中对应 F(C(x, m), n)。

---

模拟的优化

由于 $n, m$可能很大（$10^9$），不能真的循环那么多次。
但是观察发现：

• 对于 floor 操作，当 $x$ 变成 0 后，再操作还是 0。
• 对于 ceil 操作，当 $x \le 1$ 后，再操作保持原值（因为 $\lceil 0/2 \rceil = 0$，$\lceil 1/2 \rceil = 1$）。

所以每个操作序列在 $O(\log x)$次后就会稳定，我们可以直接模拟到稳定为止，复杂度 $O(\log x)$。

---

标程代码解释

ll F(ll x, ll n) {  // 做 n 次 floor
    while (n--) {
        if (!x) return x;
        x = (x >> 1);   // 等价于 floor(x/2)
    }
    return x;
}

ll C(ll x, ll n) {  // 做 n 次 ceil
    while (n--) {
        if (x <= 1) return x;
        x = ((x + 1) >> 1);  // 等价于 ceil(x/2)
    }
    return x;
}

主函数中：

• 最小值：F(C(x, m), n) 先 ceil 再 floor
• 最大值：C(F(x, n), m) 先 floor 再 ceil

---

复杂度

每组数据模拟 $O(\log x)$ 次，总复杂度 $O(t \log x)$，可以轻松通过。

---

总结公式

设：

$$\text{floor}_n(x) = \left\lfloor \frac{x}{2^n} \right\rfloor $$$$\text{ceil}_m(x) = \left\lceil \frac{x}{2^m} \right\rceil $$

则：

$$\text{最小值} = \text{floor}_n(\text{ceil}_m(x))$$ $$\text{最大值} = \text{ceil}_m(\text{floor}_n(x))$$

因为 floor 和 ceil 都是单调的，且交换顺序会影响进位情况，这就是题目解法的核心。