题目类型

关于差分和前缀和

主要解决思路

最主要的思路是通过差分+前缀和的方法进行数据区间的标注。 如何获取正确的次数，我们可以通过记录每一个点访问的次数来看，访问次数最多的区间范围就是最后正确数字落入的范围。最后相当于返回最大的访问次数。

特别注意

1.注意数据的范围！！！，刚开始我将最大区间长度定义为1e9发现长度不够，因此只有40%的通过率。 2.需要定义一个map<int, int> diff;优势是可以保存负数，并且占用内存小

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
#define MAX 2147483647
// int v[100010];
map<int, int> diff;
int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int num;
        char dot;
        cin >> num >> dot;

        if (dot == '.') {
            diff[num]++;
            diff[num + 1]--;
        } else if (dot == '+') {
            diff[-MAX]++;  // 相当于负无穷
            diff[num]--;
        } else if (dot == '-') {
            diff[num + 1]++;
            diff[MAX]--;   // 相当于正无穷
        }
    }
    
    int max_overlap = 0;
    int current = 0;
    
    for (auto &[pos, delta] : diff) {
        current += delta;
        max_overlap = max(max_overlap, current);
    }
    
    cout << max_overlap << endl;
    return 0;
}