# 小红的第16版方案

暴力解法：（数据量已经出最大了，C++能过，java、python、go都过不了）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    int l, r;
    cin >> n >> m;
    vector<int> a(n + 1);
    vector<int> angry(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) {
        cin >> l >> r;
        for (int j = l; j <= r; j++) {
            angry[j]++;
            if (angry[j] > a[j]) {
                cout << i - 1 << endl;
                return 0;
            }
        }
    }
    cout << m << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

使用差分数组，代码如下：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<int> diff(n + 1, 0); // 差分数组，多一个元素用于处理边界情况

    int l, r;
    for (int i = 1; i <= m; ++i) {
        cin >> l >> r;
        diff[l]++;
        if (r + 1 <= n) diff[r + 1]--;
    }

    int current_anger = 0;   // 当前的愤怒值
    for (int i = 1; i <= n; ++i) {
        current_anger += diff[i];  // 计算差分数组的前缀和，得到最终的愤怒值
        if (current_anger > a[i]) {
            cout << i - 1 << endl;  // 如果当前的愤怒值超过阈值，输出最后一个没有问题的方案编号
            return 0;
        }
    }

    cout << m << endl;  // 如果所有修改完成后都没有超过阈值，返回最后一个方案的编号
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

过不了，因为差分数组只能知道是哪个人超过了阈值，不能知道是第几次修改超过的

最后优化思路：

差分数组（Difference Array）：依然使用差分数组来处理区间更新。
二分查找：通过二分查找来确定最早发生愤怒值超出阈值的操作，而不是逐次模拟每一次修改。

步骤：

创建一个差分数组 diff 用于处理区间增加操作。
在 [1, m] 的范围内进行二分查找，确定导致某个人愤怒值超过阈值的最早的修改次数。
对每个二分查找的中间值 mid，我们累积应用前 mid 次操作，然后检查是否有任何人的愤怒值超过了阈值。
如果 mid 之前没有超标，则继续向右查找；否则向左缩小范围。
在二分查找完成后，输出找到的第一个导致愤怒值超标的操作次数。

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

using namespace std;

bool isValid(const vector<int>& a, const vector<int>& diff, int n, int m) {
    vector<int> anger(n + 1, 0);
    int current_anger = 0;
    for (int i = 1; i <= n; ++i) {
        current_anger += diff[i];
        if (current_anger > a[i]) {
            return false;  // 超出愤怒阈值
        }
    }
    return true;  // 没有任何人超出愤怒阈值
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);  // 愤怒阈值数组
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<pair<int, int>> operations(m + 1);  // 保存每次操作的区间
    for (int i = 1; i <= m; ++i) {
        int l, r;
        cin >> l >> r;
        operations[i] = {l, r};
    }

    int left = 1, right = m, result = m;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        // 构建差分数组，只考虑前 mid 次操作
        vector<int> diff(n + 2, 0);
        for (int i = 1; i <= mid; ++i) {
            int l = operations[i].first;
            int r = operations[i].second;
            diff[l]++;
            if (r + 1 <= n) {
                diff[r + 1]--;
            }
        }

        if (isValid(a, diff, n, mid)) {
            left = mid + 1;  // 如果在mid次操作后没有超标，继续向右搜索
        } else {
            result = mid - 1;  // 如果在mid次操作后超标，向左搜索
            right = mid - 1;
        }
    }

    cout << result << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

时间复杂度：O(n + m * log m)，其中 n 是成员数量，m 是操作次数。二分查找的时间复杂度为 O(log m)，每次二分查找中通过差分数组检查愤怒值的复杂度为 O(n)。
空间复杂度：O(n + m)，主要用于存储差分数组和操作数组。