题目题解

问题理解

给定一个由互不相同整数组成的数组 $a$。
允许两种操作：

1. 选择一个非空前缀，将其替换为该前缀的最小值。
2. 选择一个非空后缀，将其替换为该后缀的最大值。

对于每个 $a_i$，判断是否能通过一系列操作将数组变为仅包含 $a_i$ 的单一元素数组 $[a_i]$。

---

第一步：基础情况

当 $n = 2$ 时，两种操作都可以得到单一元素：

• 选择整个数组作为前缀，得到 $[\min(a_1, a_2)]$。
• 选择整个数组作为后缀，得到 $[\max(a_1, a_2)]$。

因此，对于 $n=2$，两个元素都可以成为最终元素。

---

第二步：充分条件

若 $a_i$ 是前缀最小值，则存在操作序列将其变为 $[a_i]$。

构造方法：

1. 选择前缀 $[a_1, \dots, a_i]$，将其替换为最小值 $a_i$。
   此时数组变为 $[a_i, a_{i+1}, \dots, a_n]$。
2. 若数组长度 $> 1$，选择后缀 $[a_{i+1}, \dots, a_n]$（即除了第一个元素外的所有元素），将其替换为最大值。
   此时数组变为 $[a_i, M]$，其中 $M = \max(a_{i+1}, \dots, a_n)$。
3. 现在数组长度为 $2$，根据第一步的结论，可以将其变为 $[a_i]$。

同理：若 $a_i$ 是后缀最大值，也可通过对称操作变为 $[a_i]$。

---

第三步：必要条件

假设 $a_i$ 既不是前缀最小值，也不是后缀最大值。
设：

• $p < i$ 是前缀 $[a_1, \dots, a_i]$ 中最小值 $a_p$ 的位置。
• $s > i$ 是后缀 $[a_i, \dots, a_n]$ 中最大值 $a_s$ 的位置。

显然 $a_p < a_i < a_s$。

断言：不可能在不移除 $a_i$ 的情况下移除 $a_p$ 或 $a_s$。

证明：考虑第一次操作移除 $a_p$、$a_i$ 或 $a_s$ 中的至少一个。

• 若通过选择前缀移除 $a_p$：
  该前缀必须包含一个比 $a_p$ 更小的元素。由于 $a_p$ 是 $[a_1, \dots, a_i]$ 的最小值，该前缀必须包含 $a_i$ 之后的元素。但此时该前缀也包含 $a_i$，而 $a_i$ 不是该前缀的最小值（因为有比它小的 $a_p$ 存在），因此 $a_i$ 也会被移除。

• 若通过选择后缀移除 $a_p$：
  该后缀必须包含 $a_p$，因此也包含 $a_i$ 和 $a_s$。由于 $a_i$ 不是该后缀的最大值（因为有更大的 $a_s$），$a_i$ 也会被移除。

对称地，若第一次操作移除 $a_s$，同样会导致 $a_i$ 被移除。

因此，任何试图移除 $a_p$ 或 $a_s$ 的操作都会同时移除 $a_i$。
故无法在不移除 $a_i$ 的情况下单独保留它，从而不可能将数组变为 $[a_i]$。

---

最终结论

$$\text{ans}_i = \begin{cases} 1, & \text{if } a_i = \min(a_1, \dots, a_i) \text{ 或 } a_i = \max(a_i, \dots, a_n), \\ 0, & \text{otherwise}. \end{cases} $$

---

算法步骤

1. 预处理前缀最小值数组 pre[i] = min(a[1..i])。
2. 预处理后缀最大值数组 suf[i] = max(a[i..n])。
3. 对于每个 $i$，若 a[i] == pre[i] 或 a[i] == suf[i]，输出 '1'，否则输出 '0'。

---

时间复杂度

• 预处理 $O(n)$。
• 总复杂度 $O(\sum n) \le 2 \times 10^5$，满足要求。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<int> pre(n + 1, INT_MAX);
    vector<int> suf(n + 2, INT_MIN);
    
    for (int i = 1; i <= n; i++) {
        pre[i] = min(pre[i - 1], a[i]);
    }
    for (int i = n; i >= 1; i--) {
        suf[i] = max(suf[i + 1], a[i]);
    }
    
    for (int i = 1; i <= n; i++) {
        if (a[i] == pre[i] || a[i] == suf[i]) {
            cout << '1';
        } else {
            cout << '0';
        }
    }
    cout << '\n';
}

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

---

验证样例

测试用例	数组	前缀最小值	后缀最大值	结果
1	$[1,3,5,4,7,2]$	$1,1,1,1,1,1$	$7,7,7,7,2,2$	$1,0,0,0,1,1$
2	$[13,10,12,20]$	$13,10,10,10$	$20,20,20,20$	$1,1,0,1$
3	$[1,2,3,4,5,6,7]$	$1,1,1,1,1,1,1$	$7,7,7,7,7,7,7$	$1,0,0,0,0,0,1$

与题目输出一致。

---

总结

本题的关键在于：

1. 识别出前缀最小值和后缀最大值是可行的充分条件。
2. 证明非前缀最小值且非后缀最大值的元素一定不可行（通过引入左侧更小值和右侧更大值，并分析首次操作）。
3. 最终得到简单的 $O(n)$ 判断方法。