大家好！我是老码农。
昨天快9点30的时候，我呼叫小码匠，问下她题做得如何了？
小码匠说：还在调试呢？
我有点小急，这小丫头又杠上了吧。
题目调试的时候要讲究方式方法，很多时候需要跳出来再跳进去，更容易发现问题。
这个是小码匠写的代码。样例都没过。
接下来我跟她一起看了下，结果几分钟就搞定了。
我们先看有问题的原版代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u << 1
#define rs u << 1 | 1
const int maxn = 2e5 + 5;
struct line {
ll l, r, w;
} t[maxn << 2];
void push_up(int u) {
t[u].w = t[ls].w + t[rs].w;
}
void build(int u, int l, int r) {
t[u].l = l;
t[u].r = r;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(u);
}
void modify(int u, int x, ll v) {
if (t[u].l == x && t[u].r == x) {
t[u].w += v;
return;
}
ll mid = (t[u].l + t[u].r) >> 1;
if (mid >= x) {
modify(ls, x, v);
} else {
modify(rs, x, v);
}
push_up(u);
}
int ask(int u, ll y) {
if (t[u].l == t[u].r) {
return t[u].l;
}
if (t[ls].w <= y) { // 我们实际上是不断的去寻找第一个小于y的值，所以如果左子树值更大，那么说明我们要找的值在左边
return ask(ls, y);
} else {
return ask(rs, y - t[ls].w); // 右边同理但是由于右子树的区间值都不包含左子树，所以要减去左边的值
}
}
int s[maxn];
struct student {
int h;
ll cnt;
} g[maxn];
void best_coder() {
int n;
cin >> n;
int cnt = 1;
for (int i = 1; i <= n; ++i) {
cin >> g[i].h >> g[i].cnt;
s[i] = g[i].h;
}
sort(s + 1, s + 1 + n);
int k = unique(s + 1, s + 1 + n) - s - 1;
for (int i = 1; i <= n; ++i) {
int idx = lower_bound(s + 1, s + 1 + k, g[i].h) - s;
g[i].h = idx;
}
build(1, 1, n);
for (int i = 1; i <= n; ++i) {
modify(1, g[i].h, g[i].cnt);
ll sum = t[1].w;
if (sum % 2 == 1) {
sum = sum / 2 + 1;
} else {
sum = sum / 2;
}
cout << s[ask(1, sum)] << '\n';
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
几个重要问题
我看了小码匠的代码，其实我是不知道哪错了的。只是凭自己的经验引导她。
首先：判断问题可能出现的点
那如何判断呢，我们先看主函数
主函数主要是best_coder这个函数，如果分析这个函数
第2行~第8行：读入数据； 第9行~第14行：离散化； 第15行：构建线段树； 第16行~第25行：这段主体的逻辑不复杂，核心是在 modify()、ask()这个函数；
void best_coder() {
int n;
cin >> n;
int cnt = 1;
for (int i = 1; i <= n; ++i) {
cin >> g[i].h >> g[i].cnt;
s[i] = g[i].h;
}
sort(s + 1, s + 1 + n);
int k = unique(s + 1, s + 1 + n) - s - 1;
for (int i = 1; i <= n; ++i) {
int idx = lower_bound(s + 1, s + 1 + k, g[i].h) - s;
g[i].h = idx;
}
build(1, 1, n);
for (int i = 1; i <= n; ++i) {
modify(1, g[i].h, g[i].cnt);
ll sum = t[1].w;
if (sum % 2 == 1) {
sum = sum / 2 + 1;
} else {
sum = sum / 2;
}
cout << s[ask(1, sum)] << '\n';
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
看完这段代码后，我问了小码匠几个问题？
第1点：离散化那里能确定一定没问题嘛？
答曰：没问题；
第2点：构建线段树能确定一定没问题嘛？
答曰：那段代码我静态检查过，处理简单，不可能写挂；
第3点：你要不要把离散化和构建线段树的值输出来确认下，有没有问题？
答曰：确认过了，没问题；
第4点：那你接下来就应该重点确认
modify()、ask()这个函数;第5点：你最好重点确认入参和条件判断是否写反了。
直插重点
小码匠瞪着代码，看了几分钟modify()、ask()这两个函数
int ask(int u, ll y) {
if (t[u].l == t[u].r) {
return t[u].l;
}
if (t[ls].w <= y) {
return ask(ls, y);
} else {
return ask(rs, y - t[ls].w);
}
}
然后随手修改了第5行，从<=改成>=，3个样例顺利通过。
然后我接着跟她说，为什么这个符号打错了呢？
是思路错了？ 还是梳理的有遗漏？
后来我跟小码匠说：对于一些复杂的逻辑或者需要分类讨论的，最好加上注释说明，加注释说明的时候无形中是有助于你的理解和梳理分支。
然后这段代码又稍微改了点。成这个样子了。
int ask(int u, ll y) {
if (t[u].l == t[u].r) {
return t[u].l;
}
if (t[ls].w >= y) { // 我们实际上是不断的去寻找第一个小于y的值，所以如果左子树值更大，那么说明我们要找的值在左边
return ask(ls, y);
} else {
return ask(rs, y - t[ls].w); // 右边同理但是由于右子树的区间值都不包含左子树，所以要减去左边的值
}
}
划重点：很多时候一旦陷进去，就如同走了个死胡同。此时，最好的方式，放松下或转移下注意力，让大脑短暂离开代码。
此路不通，龙马精神一下，回来换条路就通顺了，条条大路通罗马。
再说标签
别太迷信洛谷的标签，洛谷标签太不靠谱了。
这道题估计最早的标签是紫题，实际也就上位绿，但每个人的感受不同。
有人说也就黄题，这个还是有点过了，线段树模版都是绿题，大佬们也不能太自谦了，莫非已成大佬就忘记当年啃模版那痛苦尽头。
有时候看洛谷评论区也挺逗的，经常就吵起来了。
没有必要去纠结这些，最重要学到知识就行了。
好啦，今天就写道这里。
