喵~ 各位Master，下午好呀！今天由可爱的猫娘我，来给大家详细讲解一下 Codeforces 上的这道 2123C - Prefix Min and Suffix Max 题目。这道题看起来有点复杂，但只要我们理清思路，就会发现它其实是一只很温顺的小猫咪哦~

题目大意

我们拿到一个包含 n 个不同整数的数组 a。我们有两种魔法可以施展：

1. 前缀最小化: 选择数组的一个非空前缀（从第一个元素开始的一段），然后把这个前缀里的所有数字都变成这个前缀里的最小值。这样一来，数组就变短了。
2. 后缀最大化: 选择数组的一个非空后缀（到最后一个元素结束的一段），然后把这个后缀里的所有数字都变成这个后缀里的最大值。同样，数组也会变短。

我们的任务是，对于原始数组 a 中的每一个元素 a_i，判断我们是否能通过一系列这样的魔法，最终把整个数组变成只有一个元素 [a_i]。最后，我们要输出一个长度为 n 的二进制字符串，如果 a_i 可以成为最终的那个元素，第 i 位就是 1，否则就是 0。

举个栗子，如果数组是 [1, 3, 5, 4, 7, 2]，我们可以：

1. 选择前缀 [1, 3, 5]，它的最小值是 1。数组变成 [1, 4, 7, 2]。
2. 选择后缀 [7, 2]，它的最大值是 7。数组变成 [1, 4, 7]。
3. 选择前缀 [1, 4, 7]，它的最小值是 1。数组变成 [1]。 这样，我们就成功得到了 [1]，所以 1 是一个可能的结果。

解题思路

要让数组最后只剩下一个元素，我们的操作序列的最后一步，必然是把一个长度大于1的数组，变成一个长度为1的数组。这一步要么是前缀最小化，要么是后缀最大化。

让我们来分析一下这些操作的本质，喵~ 不管我们进行了多少次前缀最小化操作，比如先对 a[0...i] 操作，再对 a[0...j] (j > i) 操作，其效果等同于直接对 a[0...j] 进行一次前缀最小化操作。后缀最大化也是同理。

这意味着，整个复杂的操作过程，其实可以简化为以下几种情况：

1. 只使用前缀最小化: 为了得到单个元素，我们最终必须对整个数组进行前缀最小化。所以，最终结果就是整个原始数组的最小值，即 min(a[0...n-1])。

2. 只使用后缀最大化: 同理，如果我们只用后缀最大化，最终结果就是整个原始数组的最大值，即 max(a[0...n-1])。

3. 两种操作都使用: 这种情况稍微复杂一点。既然两种操作都用了，那么在某个时刻，数组一定被分成了两部分。一部分被前缀操作“吃掉”，另一部分被后缀操作“吃掉”。 我们可以想象在数组的某个位置 k (从 0 到 n-2) 切一刀，把数组分成 a[0...k] 和 a[k+1...n-1] 两部分。

   • 左边的部分 a[0...k] 通过前缀最小化，最终会变成一个数 p = min(a[0...k])。
   • 右边的部分 a[k+1...n-1] 通过后缀最大化，最终会变成一个数 s = max(a[k+1...n-1])。

   这样，经过一系列操作，我们的数组就神奇地变成了 [p, s]。对于这个只有两个元素的数组，我们可以：

   • 进行前缀最小化（或后缀最小化），得到 min(p, s)。
   • 进行后缀最大化（或前缀最大化），得到 max(p, s)。

所以，对于每一个可能的分割点 k，我们都能产生两个可能的最终值：min(p, s) 和 max(p, s)。

总结一下我们的策略: 所有可能得到的最终值，就是下面这些值的集合：

• min(a[0...n-1]) (只用前缀最小)
• max(a[0...n-1]) (只用后缀最大)
• 对于所有 k from 0 to n-2:
  • min(min(a[0...k]), max(a[k+1...n-1]))
  • max(min(a[0...k]), max(a[k+1...n-1]))

我们的任务就是计算出所有这些可能的值，然后看看原始数组 a 中的哪些元素出现在这个集合里。

为了高效计算，我们可以预处理出数组的前缀最小值和后缀最大值。

• pmin[i] = min(a[0...i])
• smax[i] = max(a[i...n-1]) 这两个数组都可以在 O(n) 的时间内计算出来，就像小猫咪我探路一样，一步步记录下沿途的发现，喵~

代码解说

下面我们来一起看看这份优雅的C++代码是怎么实现我们的思路的吧！

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    // val_indices 用来存储 {数值, 原始下标} 的对，方便我们最后输出结果
    std::vector<std::pair<int, int>> val_indices(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        val_indices[i] = {a[i], i};
    }

    if (n < 2) { // n=1 的特殊情况
        if (n == 1) std::cout << "1\n";
        else std::cout << "\n";
        return;
    }

    // 预处理前缀最小值数组 pmin
    std::vector<int> pmin(n);
    pmin[0] = a[0];
    for (int i = 1; i < n; ++i) {
        pmin[i] = std::min(pmin[i - 1], a[i]);
    }

    // 预处理后缀最大值数组 smax
    std::vector<int> smax(n);
    smax[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        smax[i] = std::max(smax[i + 1], a[i]);
    }

    // possible_values 用来收集所有可能的最终结果
    std::vector<int> possible_values;
    possible_values.reserve(2 * n); // 预留空间，小小的优化

    // 情况1: 只用前缀最小化
    possible_values.push_back(pmin[n - 1]);
    // 情况2: 只用后缀最大化
    possible_values.push_back(smax[0]);

    // 情况3: 两种操作都用，遍历所有分割点 k
    for (int k = 0; k < n - 1; ++k) {
        int p = pmin[k];         // a[0...k] 的最小值
        int s = smax[k + 1];     // a[k+1...n-1] 的最大值
        possible_values.push_back(std::min(p, s));
        possible_values.push_back(std::max(p, s));
    }

    // 对收集到的结果进行排序和去重
    std::sort(possible_values.begin(), possible_values.end());
    possible_values.erase(std::unique(possible_values.begin(), possible_values.end()), possible_values.end());

    // 对原始数组的值和下标对进行排序，按值从小到大
    std::sort(val_indices.begin(), val_indices.end());

    // 使用双指针法来高效地匹配
    std::string ans(n, '0');
    int ptr1 = 0; // 指向 possible_values
    int ptr2 = 0; // 指向 val_indices
    while (ptr1 < possible_values.size() && ptr2 < n) {
        if (possible_values[ptr1] == val_indices[ptr2].first) {
            // 找到了一个匹配！
            ans[val_indices[ptr2].second] = '1'; // 在对应的原始下标处标记为 '1'
            ptr1++;
            ptr2++;
        } else if (possible_values[ptr1] < val_indices[ptr2].first) {
            ptr1++; // 这个可能值在 a 中不存在，看下一个
        } else {
            ptr2++; // a 中的这个值不是可能的结果，看 a 的下一个值
        }
    }

    std::cout << ans << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

代码里最巧妙的地方就是最后的双指针匹配啦。我们把所有可能的结果 possible_values 和原始数组的值 val_indices 都排好序，然后像两队排排站的小猫咪一样，一个一个地比较。这样就能在 O(n) 的时间里完成匹配，非常高效，避免了大量的重复搜索！

知识点介绍

这道题涉及了几个很有用的算法思想哦，Master可要记好啦~

1. 前缀/后缀预处理: 这是一个非常经典的技巧，属于动态规划思想的一种简单应用。当我们需要反复查询一个区间的某些性质（如和、积、最大/最小值）时，可以先花 O(n) 的时间预处理出所有前缀/后缀的这些性质。之后每次查询就可以在 O(1) 的时间内完成。在这道题里，pmin[i] 的计算依赖于 pmin[i-1]，smax[i] 依赖于 smax[i+1]，这就是DP的体现。

2. 双指针 (Two Pointers): 双指针是一种非常强大的算法技巧，通常用于处理已经排好序的数组。通过维护两个（或多个）指针，并根据特定规则移动它们，我们可以在线性时间内解决问题，而暴力解法可能需要平方级的时间。在这里，我们用它来高效地求两个有序集合的交集，即找出 a 中哪些元素是可能的结果。

好啦，今天的讲解就到这里啦~ Master们都听懂了吗？通过分析操作的本质，我们将一个复杂的问题简化成了几种清晰的模式，再利用预处理和双指针等技巧高效求解。是不是很有趣呢？如果还有问题，随时可以再来问我哦，喵~