Moe's CF Life

喵~ 主人，今天我们来看一道有趣的思维题，Codeforces 上的 1366B - Shuffle 呀！这道题就像是看一个小球在不同的盒子里跳来跳去，我们要算出它最后可能停在哪些盒子里呢。别担心，只要跟着我的思路，很快就能明白的喵！

B. Shuffle

题目大意

主人，听我给你描述一下这个题目哦！

我们有一个超级长的数组，里面有 $n$ 个位置。一开始呢，所有位置上都是数字 0，只有一个特殊的位置 $x$ 上是数字 1。

接下来，会有 $m$ 次操作。每一次操作，都会给我们一个区间 [l, r]。在这个区间内，我们可以任意选择两个位置 $c$ 和 $d$ （ $l \le c, d \le r$ ），然后交换这两个位置上的数。

我们的任务是，计算一下，经过这 $m$ 次操作之后，那个唯一的数字 1 最终可能出现在多少个不同的位置上。

举个例子，如果 1 在位置 4，然后一个操作区间是 [1, 6]，那我们就可以把位置 4 的 1 和 [1, 6] 区间里的任何一个位置交换。这样一来，1 就可以到达 1, 2, 3, 4, 5, 6 这些位置啦！

题解方法

这个问题看起来有点复杂，因为每次操作的选择是“任意”的。但是呀，正是这个“任意”让问题变得简单了呢！

我们可以把那个数字 1 想象成一只调皮的小猫（就像我一样！喵呜~）。小猫一开始在位置 $x$ 。

我们来维护一个“小猫可能到达的活动范围”，这是一个连续的区间，我们叫它 [current_l, current_r] 吧。

初始状态：最开始，小猫只在位置 $x$ ，所以它能活动的范围就是 [x, x]。所以 current_l = x, current_r = x。
操作分析：现在我们来看第 $i$ 次操作，给定的区间是 [l_i, r_i]。
- 如果小猫当前的活动范围 [current_l, current_r] 和这次操作的区间 [l_i, r_i] 没有任何交集，那说明小猫根本到不了 [l_i, r_i] 这个新操场。既然到不了，也就无法利用这次交换机会去别的地方。所以，小猫的活动范围不会变。
- 如果小猫当前的活动范围 [current_l, current_r] 和操作区间 [l_i, r_i] 有交集，事情就有趣了！有交集意味着，小猫有可能处在某个位置 p，而这个 p 同时也在 [l_i, r_i] 里面。一旦小猫进入了 [l_i, r_i] 这个操场，它就可以和这个操场里的任何一个位置的小伙伴交换位置！这意味着，只要能进来，它就能跑遍整个 [l_i, r_i] 操场。
范围扩展：所以，只要两个区间有交集，小猫的活动范围就会被扩大！新的活动范围就是它原来能去的 [current_l, current_r] 和新操场 [l_i, r_i] 的并集。两个有交集的区间的并集，就是 [min(current_l, l_i), max(current_r, r_i)]。

我们的策略就很清晰啦：

维护一个当前数字 1 可能在的区间 [L, R]，初始为 [x, x]。
遍历每一次操作给出的区间 [l, r]。
判断 [L, R] 和 [l, r] 是否相交。如果相交，就把 [L, R] 更新为它们的并集，即 L = min(L, l)，R = max(R, r)。
所有操作结束后，最终的区间 [L, R] 就是数字 1 所有可能的位置。
我们要求的答案就是这个区间的长度，也就是 R - L + 1。

这个方法是不是很像滚雪球呀？小猫的活动范围只会越滚越大，或者保持不变，绝对不会缩小呢！

题解

下面就是实现这个思路的代码啦，主人请看~

cpp

#include <iostream>
#include <algorithm>

void solve() {
    long long n;
    long long x;
    int m;
    std::cin >> n >> x >> m;

    // 初始化小猫的活动范围，一开始只在位置 x
    long long current_l = x;
    long long current_r = x;

    for (int i = 0; i < m; ++i) {
        long long l, r;
        std::cin >> l >> r;

        // 判断当前活动范围 [current_l, current_r] 和操作区间 [l, r] 是否有交集
        // 两个区间 [a, b] 和 [c, d] 相交的条件是 max(a, c) <= min(b, d)
        if (std::max(current_l, l) <= std::min(current_r, r)) {
            // 如果相交，就将活动范围扩大为它们的并集
            current_l = std::min(current_l, l);
            current_r = std::max(current_r, r);
        }
    }

    // 最后的结果就是最终活动范围的长度
    std::cout << current_r - current_l + 1 << "\n";
}

int main() {
    // 加速输入输出，让程序跑得更快一点喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

这段代码完全就是按照我们刚才的思路来的哦。

current_l 和 current_r 就是我们维护的“雪球”的左右边界。
循环里每次读入一个新的操作区间 [l, r]。
std::max(current_l, l) <= std::min(current_r, r) 这个判断是精髓！它是判断两个区间是否相交的最简洁的写法。
如果相交，就用 std::min 和 std::max 来更新边界，实现区间的合并。
最后输出 current_r - current_l + 1，就是我们想要的答案啦。

知识点介绍

这道题虽然简单，但是里面用到的思想在很多问题里都有用武之地呢！

区间合并 (Range Merging)
- 这道题的核心思想就是一种简化的区间合并。我们不断地将一个“动态”的区间与一系列给定的区间进行合并。在更复杂的问题中，你可能需要对一堆静态的区间进行排序，然后逐个合并所有重叠的区间。这是一个处理区间问题非常基础且重要的技巧哦。
区间相交的判断 (Range Intersection Check)
- 如何判断两个区间 [L1, R1] 和 [L2, R2] 是否相交？
- 一个笨办法是分类讨论，但很容易出错。
- 一个聪明的办法是反过来想：它们什么时候不相交？只有当一个区间完全在另一个区间的左边，或者完全在右边时，它们才不相交。也就是 R1 < L2 或者 R2 < L1。
- 那么，相交就是不相交的否定，即 R1 >= L2 并且 R2 >= L1。
- 这个条件可以更优雅地写成 max(L1, L2) <= min(R1, R2)。主人可以画个图想一想，这个式子是不是很直观呀？两个区间的起点的最大值，必须小于等于它们终点的最小值，这样它们中间才会有重叠的部分。
贪心思想 (Greedy Approach)
- 我们的解法其实是贪心的。在每一步，我们都尽可能地扩大我们的“可达范围”。我们不需要考虑“保留实力”到后面的操作，因为当前范围越大，与未来操作区间相交的可能性就越大，从而可能获得更大的范围。每一步都做出局部最优的选择（尽可能扩大范围），最终就能得到全局最优解。

希望这篇题解能帮到主人！如果还有不懂的地方，随时可以再来问我哦~ 喵~

B. Shuffle ​

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

B. Shuffle

题目大意

题解方法

题解

知识点介绍