问题
在使用 C++ 做一个算法题的时候，发现一个莫名其妙的现象，所以准备使用 gdb 跟踪调试一下变量的变化。代码和原题也放在最后面了。
过程
1、编译程序
1
g++ -g test.cpp -o test
2、调试
1
2
3
4
5
6
7
8
9
10
gdb test
break 70 # 断点，可简写为 b 70
info breakpoints # 查看所有断点
run # 开始运行，可简写为 r
next # 下一步（不进入函数），可简写为 n
step # 下一步（进入函数），可简写为 s
print lcnt # 打印 lcnt 变量
coutinue # 继续执行到下一个断点，可简写为 c
backtrace # 查看当前调用栈
display lcnt # 持续显示变量值
最终发现修改的地方如下：
总结：因为 right 和 lcnt 是一段连续的内存，在 update 里边的 while 设置的是 x <= n 是不对的，应该设置为 x <= idx。因为 right 的大小就是 idx，而 n > idx，那么超出 idx 的部分就写在了 lcnt 里边。
原题
具体题目记不得了，大概题意：给一个长度为 n 的数组，可以通过交换任意相邻元素转换为以任意元素为顶点，前边的部分非递减，后边的部分非递增。
我使用的树状数组，时间复杂度是 \(O(nlogn)\)。在测试的时候有一个自己想的样例发现很奇怪的现象：代码的70行会莫名修改 lcnt 的值。
1
2
12
4 5 5 1 5 2 2 2 2 2 2 2
代码
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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <functional>
using namespace std;
int lowbit(int x) {
return x & -x;
}
int main() {
int n;
scanf("%d", &n);
vector<int> a(n);
vector<int> b(n);
for (int i = 0; i < n; ++ i) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b.begin(), b.end());
unordered_map<int, int> um;
int idx = 1;
for (int i = 0; i < n; ++ i) {
if (!um.count(b[i])) {
um[b[i]] = idx ++;
}
}
for (int i = 0; i < n; ++ i) {
a[i] = um[a[i]];
// cout << a[i] << ' ' ;
}
vector<int> left(idx + 1, 0), right(idx + 1, 0);
vector<int> lcnt(n, 0), rcnt(n, 0);
function<void(int, vector<int>&)> update = [&](int x, vector<int> &tree) {
int val = 1;
while (x <= n) {
tree[x] += val;
x += lowbit(x);
}
};
function<int(int, vector<int>&)> query = [&](int x, vector<int> &tree) -> int {
int res = 0;
while (x > 0) {
res += tree[x];
x -= lowbit(x);
}
return res;
};
auto print = [&](vector<int> &arr) {
for (int i = 0; i < n; ++ i) {
cout << arr[i] << ' ';
} cout << endl;
};
for (int i = 0; i < n; ++ i) {
lcnt[i] = i - query(a[i], left);
// print(lcnt);
update(a[i], left);
}
// print(lcnt);
for (int i = n - 1; i >= 0; -- i) {
// print(lcnt);
// print(rcnt);
rcnt[i] = n - 1 - i - query(a[i], right);
update(a[i], right);
}
// print(lcnt);
// print(rcnt);
cout << " test" << endl;
long long ans = 0;
for (int i = 0; i < n; ++ i) {
// cout << lcnt[i] << ' ' << rcnt[i] << endl;
ans += min((long long)lcnt[i], (long long)rcnt[i]);
}
printf("%lld\n", ans);
cout << "test3" << endl;
return 0;
cout << "test2" << endl;
}
// 64 位输出请用 printf("%lld")
// 12
// 4 5 5 1 5 2 2 2 2 2 2 2
