B. Index 与最大值 详细题解

问题重述

给定一个长度为 $n$ 的数组 $a$，按顺序执行 $m$ 个操作。每个操作是 + l r 或 - l r，表示将所有在 $[l, r]$ 范围内的元素加 $1$ 或减 $1$。每次操作后输出当前数组的最大值。

关键观察

观察 1：最大值的性质

设初始数组的最大值为 $M$。可以证明，$M$ 始终是数组的最大值之一，并且所有其他元素的值永远不会超过 $M$。

证明：

• 如果某个元素 $x = M$，操作后：
  • 若 $x$ 在操作范围内，则 $x$ 变为 $M \pm 1$
  • 若 $x$ 不在操作范围内，则 $x$ 保持 $M$
• 如果某个元素 $x < M$，操作后：
  • $x$ 最多增加 $1$，而 $M$ 最多也增加 $1$（如果 $M$ 在范围内）
  • 两者的差最多减少 $1$，所以 $x$ 永远无法超过 $M$

因此，我们只需要关注初始最大值 $M$ 的变化，其他元素永远不会成为新的最大值。

观察 2：问题简化

由于最大值始终由初始最大值 $M$ 产生，我们只需维护 $M$ 的值，并在每次操作中：

• 如果 $l \le M \le r$，则 $M$ 根据操作类型加 $1$ 或减 $1$
• 否则 $M$ 保持不变

输出每次操作后的 $M$ 即可。

时间复杂度

• 找初始最大值：$O(n)$
• 处理每个操作：$O(1)$
• 总复杂度：$O(n + m)$

完整代码

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        // 读取初始数组并找到最大值
        int max_val = 0;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            max_val = max(max_val, x);
        }
        
        // 处理每个操作
        for (int i = 0; i < m; i++) {
            char c;
            int l, r;
            cin >> c >> l >> r;
            
            if (l <= max_val && max_val <= r) {
                if (c == '+') {
                    max_val++;
                } else {
                    max_val--;
                }
            }
            
            cout << max_val;
            if (i < m - 1) cout << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

代码说明

1. 读取初始数组：只需找到最大值，不需要存储整个数组
2. 处理操作：
   • 读取操作符 c 和区间 [l, r]
   • 检查当前最大值是否在区间内
   • 根据操作符更新最大值
3. 输出：每次操作后输出当前最大值

示例验证

以第一个测试用例为例：

• 初始数组 $[1,2,3,2,1]$，最大值 $M = 3$
• 操作1：+ 1 3，$3 \in [1,3]$，$M = 4$，输出 $4$
• 操作2：- 2 3，$4 \notin [2,3]$，$M = 4$，输出 $4$
• 操作3：+ 1 2，$4 \notin [1,2]$，$M = 4$，输出 $4$
• 操作4：+ 2 4，$4 \in [2,4]$，$M = 5$，输出 $5$
• 操作5：- 6 8，$5 \notin [6,8]$，$M = 5$，输出 $5$

输出：4 4 4 5 5，与样例一致。

总结

本题的核心技巧：

1. 发现初始最大值始终保持为最大值
2. 将 $n$ 个元素的问题简化为 $1$ 个元素
3. 每次操作 $O(1)$ 更新，无需遍历整个数组