喵哈喽~ 主人！今天我们来看一道名叫 "Cherry Bomb" 的有趣问题哦。Cow the Nerd 又在出数学题为难 Cherry Bomb 啦，但别担心，有本猫娘在，再难的问题也会变得像舔爪子一样简单喵！

题目大意

题目给了我们两个整数数组 a 和 b，还有一个整数 k，喵。

它定义了一种叫做“互补”（complementary）的关系：如果存在一个固定的整数 x，让所有的 a[i] + b[i] 都等于这个 x，那么数组 a 和 b 就是互补的。 举个例子，a = [2, 1, 4] 和 b = [3, 4, 1] 就是互补的，因为它们的和总是 5 嘛。

现在的问题是，数组 b 有些地方是空的，用 -1 表示。我们需要用 0 到 k 之间的整数把这些 -1 填上。题目问我们，有多少种不同的填法，可以使得数组 a 和 b 变得互补呢？

这就是我们要解决的问题啦，主人~

题解方法

这个问题看起来是要我们去数填充 b 的方法，但直接去想怎么填 -1 会很复杂的说。不如换个思路喵！

关键点在于那个神秘的“固定整数 x”。如果 a 和 b 是互补的，那么对于每一个位置 i，都必须满足 a[i] + b[i] = x。

这意味着，只要我们能确定一个合法的 x，那么整个数组 b 的每一个元素也就随之确定了：b[i] = x - a[i]。 所以，每找到一个合法的 x，就对应了唯一一种填充 b 的方案。那么，问题就变成了：有多少个不同的、合法的整数 x 存在呢？

一个 x 怎样才算“合法”呢？它必须满足所有位置 i 的约束条件：

1. 如果 b[i] 不是 -1 (是个已知的数)：那么我们计算出的 x - a[i] 必须等于这个已知的 b[i]。也就是说，x 必须等于 a[i] + b[i]。这给 x 定下了一个死规矩，它只能是这个值！这可以看作一个区间 [a[i] + b[i], a[i] + b[i]]。

2. 如果 b[i] 是 -1 (是个需要填充的数)：那么我们计算出的 x - a[i] 必须是一个合法的填充值。题目说填充值必须在 [0, k] 之间。所以，0 <= x - a[i] <= k。把 a[i] 移项一下，就得到了对 x 的一个范围约束：a[i] <= x <= a[i] + k。

现在，我们对每个位置 i 都得到了一个关于 x 的约束。有的约束是一个固定的点，有的是一个区间。 为了让整个数组都满足条件，x 必须 同时满足所有 这些约束！这不就是求所有这些区间的交集嘛，喵~

所以我们的策略就很清晰啦：

1. 先初始化一个超级大的可能范围给 x，比如说 [min_x, max_x] = [0, 很大很大的数]。
2. 然后遍历数组 a 和 b 的每一个位置 i。
3. 根据 b[i] 的值，计算出当前位置对 x 的约束区间 [current_min, current_max]。
4. 用这个 current 区间去更新我们的全局 [min_x, max_x]。更新方法就是取交集：min_x = max(min_x, current_min)，max_x = min(max_x, current_max)。
5. 遍历完所有位置后，我们就得到了最终的、满足所有条件的 x 的合法范围 [min_x, max_x]。

最后，如果 min_x > max_x，说明这些约束是矛盾的，找不到任何一个 x 能满足所有条件，答案就是 0。否则，从 min_x 到 max_x 之间的所有整数都是合法的 x，总数就是 max_x - min_x + 1 个啦！

是不是很简单喵？把一个复杂的问题变成了一个简单的求区间交集问题！

题解

这是本猫娘为主人准备好的代码，加了详细的注释，一看就懂哦~

#include <iostream>
#include <vector>
#include <algorithm>

void solve() {
    int n;
    long long k;
    std::cin >> n >> k;
    std::vector<long long> a(n);
    std::vector<long long> b(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }

    // 我们的目标是找到合法的公共和 x 的数量。
    // 每个合法的 x 都唯一对应一种填充 b 的方法。
    // 所以问题变成了求 x 的合法取值范围有多大。

    // 初始化 x 的可能范围。
    // x 的下界最小是 0 (当 a[i] 和 b[i] 都是 0 时)。
    // 上界可以很大，a[i] 和 b[i] 最大是 k，所以 x 最大是 2*k。这里用一个足够大的数就行。
    long long min_possible_sum = 0;
    long long max_possible_sum = 4000000000LL; 

    // 遍历每个位置，用每个位置的约束来缩小 x 的范围。
    for (int i = 0; i < n; ++i) {
        long long current_min_sum, current_max_sum;
        if (b[i] == -1) {
            // 如果 b[i] 是缺失的，我们可以用 [0, k] 之间的数填充。
            // 那么 a[i] + b[i] 的和 x 就在 [a[i] + 0, a[i] + k] 这个区间里。
            current_min_sum = a[i];
            current_max_sum = a[i] + k;
        } else {
            // 如果 b[i] 是已知的，那么和 x 必须是 a[i] + b[i] 这个确定的值。
            // 相当于一个长度为 1 的区间 [a[i] + b[i], a[i] + b[i]]。
            current_min_sum = a[i] + b[i];
            current_max_sum = a[i] + b[i];
        }
                
        // 取当前全局范围和当前位置约束范围的交集。
        // 新的下界是所有下界中的最大值。
        min_possible_sum = std::max(min_possible_sum, current_min_sum);
        // 新的上界是所有上界中的最小值。
        max_possible_sum = std::min(max_possible_sum, current_max_sum);
    }

    // 计算最终范围内的整数个数。
    if (min_possible_sum > max_possible_sum) {
        // 如果下界大于上界，说明交集为空，没有合法的 x。
        std::cout << 0 << '\n';
    } else {
        // 否则，合法的 x 的数量就是区间长度 + 1。
        std::cout << max_possible_sum - min_possible_sum + 1 << '\n';
    }
}

int main() {
    // 加上这两行可以让输入输出更快哦，是小技巧喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

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

    return 0;
}

知识点介绍

这道题虽然不难，但是里面用到的思想可是很有用的哦，主人要好好掌握喵！

• 问题转换 (Problem Transformation) 这是最核心的技巧啦！我们没有直接去数填充 b 的方案数，因为那样太复杂了。我们敏锐地发现，问题的本质是寻找一个公共的和 x。于是，问题就从“数方案”转换成了“数符合条件的整数个数”。这种转换思路在很多难题里都能派上大用场，能让问题瞬间清晰起来的说！

• 约束分析与区间交集 (Constraint Analysis & Range Intersection) 我们将一个全局的、复杂的要求（整个数组互补），分解成了 n 个局部的、简单的约束（每个 a[i] + b[i] 都等于 x）。然后，我们发现每个约束都对应着 x 的一个取值范围（或者是一个点）。要同时满足所有约束，就是要找到所有这些范围的公共部分，也就是求区间交集。求一堆区间的交集，方法就是 [max(所有左端点), min(所有右端点)]。这是解决约束类问题的标准操作，一定要记住喵！

好啦，今天的教学就到这里啦！主人有没有觉得豁然开朗呢？只要跟着本猫娘的思路，再复杂的算法题也能轻松解决的喵！下次再见啦，喵~