错题的价值不只是得到一次 AC，更重要的是记录自己当时为什么没有想到、关键转化在哪里，以及以后遇到相似模型时该如何识别。

本文整理近期遇到的四类题目：

  1. 01 字符串反转与伪差分
  2. 双堆维护滑动窗口中位数
  3. 二分答案与线段贪心
  4. 二维前缀和与枚举降维

一、01 字符串反转与伪差分

题目链接

牛客竞赛 D 题

考察知识点

  • 伪差分
  • 相邻状态维护
  • 区间反转

核心思路

因为字符串中只有 0 和 1，所以对某个区间进行反转时，区间内部相邻字符之间的“相同/不同”关系不会发生变化。

真正可能影响全局答案的，只有区间的两个端点。

可以构造一个状态数组 diff：

  • diff[i] = 1：相邻两个字符不同
  • diff[i] = 0：相邻两个字符相同

每次反转一个区间时，只需要处理左右端点对应的状态，而不需要真正把整个区间翻转一遍。

关键转化：区间操作看似影响很多字符，实际上只有边界状态发生变化。

AC 代码

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

const int N = 2e5 + 5;
int n, m;
ll tree[N];

inline int lowbit(int x) {
    return (-x) & x;
}

void add(int x, ll val) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tree[i] += val;
    }
}

ll pre(int x) {
    ll sum = 0;
    for (int i = x; i >= 1; i -= lowbit(i)) {
        sum += tree[i];
    }
    return sum;
}

void solve() {
    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;

    int ans = 0;
    vector<int> diff(n + 1, 0);

    for (int i = 0; i < n; i++) {
        int next_i = (i + 1) % n;
        if (s[i] != s[next_i]) {
            diff[i] = 1;
            ans++;
        }
    }

    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;

        if (l == r) {
            continue;
        }

        diff[l] ^= 1;
        diff[r] ^= 1;

        if (diff[l] == diff[l + 1]) {
            if (s[l] == s[l + 1]) {
                ans--;
            } else {
                ans++;
            }
        } else {
            if (s[l] != s[l + 1]) {
                ans--;
            } else {
                ans++;
            }
        }

        if (diff[r] == diff[r + 1]) {
            if (s[r] == s[r + 1]) {
                ans--;
            } else {
                ans++;
            }
        } else {
            if (s[r] != s[r + 1]) {
                ans--;
            } else {
                ans++;
            }
        }

        cout << ans << '\n';
    }
}

signed main() {
    IOS;

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

复盘

以后遇到区间翻转、区间异或等操作时，可以优先思考：

  • 区间内部的某种关系是否保持不变？
  • 是否只有左右端点会改变答案？
  • 能否维护“相邻关系”，而不是直接维护原数组？

二、双堆维护滑动窗口中位数

题目链接

牛客竞赛 E 题

考察知识点

  • 双堆思想
  • multiset
  • 滑动窗口
  • 动态维护中位数
  • 动态维护第 k 大元素

这是此前没有遇到过的一类模板。

核心思路

使用两个 multiset：

  • L：保存较小的一半元素
  • R：保存较大的一半元素

始终维持：

1
2
L 中的所有元素 ≤ R 中的所有元素
L.size() = 总元素数 / 2

中位数的判断方式：

元素数量 中位数
奇数 R 中的最小值
偶数 L 中最大值与 R 中最小值的平均值

然后配合滑动窗口：

  1. 初始化第一个窗口
  2. 每次加入一个新元素
  3. 删除一个离开窗口的元素
  4. 重新平衡两个集合
  5. 检查当前中位数是否满足要求

双堆模板与 AC 代码

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

multiset<ll> L, R;
ll target_x;

void rebalance() {
    size_t total_size = L.size() + R.size();
    size_t expected_L_size = total_size / 2;

    while (L.size() < expected_L_size) {
        L.insert(*R.begin());
        R.erase(R.begin());
    }

    while (L.size() > expected_L_size) {
        R.insert(*L.rbegin());
        auto it = prev(L.end());
        L.erase(it);
    }
}

void add_val(ll val) {
    if (L.empty() || val <= *L.rbegin()) {
        L.insert(val);
    } else {
        R.insert(val);
    }

    rebalance();
}

void del_val(ll val) {
    if (!L.empty() && val <= *L.rbegin()) {
        auto it = L.find(val);
        L.erase(it);
    } else {
        auto it = R.find(val);
        R.erase(it);
    }

    rebalance();
}

bool check_median() {
    size_t total_size = L.size() + R.size();

    if (total_size == 0) {
        return target_x == 0;
    }

    if (total_size % 2 != 0) {
        return *R.begin() == target_x;
    }

    return (*L.rbegin() + *R.begin()) == 2LL * target_x;
}

void solve() {
    int n, k;
    cin >> n >> k >> target_x;

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

    L.clear();
    R.clear();

    int m = n - k;
    if (m == 0) {
        cout << (target_x == 0) << '\n';
        return;
    }

    for (int i = k + 1; i <= n; i++) {
        add_val(a[i]);
    }

    int ans = check_median();

    for (int i = 2; i <= n - k + 1; i++) {
        add_val(a[i - 1]);
        del_val(a[i + k - 1]);

        if (check_median()) {
            ans++;
        }
    }

    cout << ans << '\n';
}

signed main() {
    IOS;

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

复盘

双堆模型适合处理：

  • 滑动窗口中位数
  • 动态中位数
  • 动态维护第 k 大或第 k 小
  • 需要频繁插入、删除和查询中间位置元素的问题

使用 multiset 时，删除元素应先用 find() 找到一个迭代器，再删除该迭代器，避免一次删除所有相同值。

三、二分答案与线段贪心

题目链接

AtCoder ABC463 D

考察知识点

  • 二分答案
  • 线段排序
  • 区间贪心
  • 可行性检查

核心思路

这道题可以较快看出需要二分答案，但在线段覆盖类问题中，排序方式非常关键。

自定义排序时，应该：

  1. 优先按照右端点从小到大排序
  2. 右端点相同时，再按照左端点从小到大排序

而不是只按照左端点排序。

在 check(mid) 中，需要记录上一个已经选中的线段位置。对于当前线段：

  • 如果它与上一个选择不冲突
  • 且二者之间的距离至少为 mid

就可以选择当前线段，并更新记录位置。

这种做法能够保证选择过程尽量靠前，为后续线段留下更多空间。

关键点：区间贪心常以右端点作为排序依据。右端点越小，留给后续选择的空间通常越大。

AC 代码

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
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int n, k;
const int N = 3e5 + 5;
vector<pair<int, int>> a(N + 1);

bool check(ll mid) {
    ll sum = 1;
    ll idx = 1;

    for (int i = 2; i <= n; i++) {
        if (a[idx].second < a[i].first) {
            ll curr = a[i].first - a[idx].second;
            if (curr >= mid) {
                sum++;
                idx = i;
            }
        }
    }

    return sum >= k;
}

bool cmp(const pair<int, int>& A, const pair<int, int>& B) {
    if (A.second != B.second) {
        return A.second < B.second;
    }

    return A.first < B.first;
}

void solve() {
    cin >> n >> k;

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

    sort(a.begin() + 1, a.begin() + n + 1, cmp);

    ll l = 0;
    ll r = 1e18;
    ll ans = -1;

    while (l <= r) {
        ll mid = (r - l) / 2 + l;

        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << ans << '\n';
}

signed main() {
    IOS;

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

复盘

看到“最大化最小值”或“最小化最大值”时，应优先考虑二分答案。

常见判断信号：

  • 答案具有单调性
  • 给定一个候选答案后，可以快速判断是否合法
  • 直接求最优值较难，但验证某个值较容易

四、二维前缀和与枚举降维

题目链接

AtCoder ABC461 D

考察知识点

  • 二维前缀和
  • 枚举降维
  • 前缀和计数
  • 子矩形统计

二维前缀和模板

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<vector<int>> pre(h + 1, vector<int>(w + 1, 0));

for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
        pre[i][j] = pre[i][j - 1]
                  + pre[i - 1][j]
                  - pre[i - 1][j - 1];

        if (grid[i][j] == '1') {
            pre[i][j]++;
        }
    }
}

二维前缀和可以在 O(1) 时间内求出任意子矩形的元素和。

枚举降维思想

如果直接枚举矩形的上、下、左、右四条边，时间复杂度通常过高。

可以先枚举矩形的上下边界：

1
2
枚举上边界 r1
枚举下边界 r2

固定上下边界后，二维问题就被压缩成了一维问题。此时每一列在 [r1, r2] 范围内的和，可以视为一维数组中的一个元素。

接下来需要统计和为 k 的连续区间数量。

如果此前出现过前缀和 p，当前前缀和为 p + k，那么二者之间的区间和一定为 k。

如果 p 此前出现了多次，就可以产生多个合法区间。

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> have(h * w + 1, 0);

for (int r1 = 1; r1 <= h; r1++) {
    for (int r2 = r1; r2 <= h; r2++) {
        have[0] = 1;

        for (int c1 = 1; c1 <= w; c1++) {
            int curr_sum = pre[r2][c1] - pre[r1 - 1][c1];

            if (curr_sum >= k) {
                ans += have[curr_sum - k];
            }

            have[curr_sum]++;
        }

        for (int c = 1; c <= w; c++) {
            int current_sum = pre[r2][c] - pre[r1 - 1][c];
            have[current_sum]--;
        }
    }
}

cout << ans << '\n';

复杂度分析

如果枚举上下边界，再线性扫描每一列，复杂度约为：

1
O(h² × w)

如果 w < h，可以考虑交换行列方向，将复杂度优化为：

1
O(min(h, w)² × max(h, w))

具体运行速度会受到语言、编译优化、常数和评测机器影响，不能仅凭固定的“每秒运算次数”判断是否超时，最终应结合数据范围进行复杂度分析。

复盘

遇到二维子矩形统计时，可以按以下顺序思考：

  1. 能否使用二维前缀和快速查询矩形和？
  2. 能否固定两条边，把二维问题压缩成一维问题？
  3. 压缩后是否能使用一维前缀和、哈希表或计数数组？
  4. 能否让平方复杂度落在较小的维度上？

五、本次错题总结

题目类型 关键识别点 核心方法
01 字符串区间反转 区间内部关系不变，只有端点变化 伪差分、边界维护
滑动窗口中位数 动态插入、删除并查询中位数 双 multiset、平衡结构
最大化最小距离 答案具有单调性 二分答案、区间贪心
子矩形计数 四边枚举复杂度过高 二维前缀和、枚举降维

这几道题的共同点是：不要直接维护题目表面描述的对象，而要寻找操作背后真正发生变化的状态。

  • 区间反转 → 维护边界
  • 动态中位数 → 维护左右两半
  • 最大化最小值 → 二分可行答案
  • 二维矩形 → 固定两边后降成一维

做完题后真正值得记录的，不是代码本身，而是从原问题到数据结构或算法模型的那一步转化。