大家好！我是老码农。
端午节3天假转瞬即逝，感觉太短了，今天又开学了。
这个假期：
- 作业比较多，大部分时间都在忙于写作业；
- 打了1场测试赛，然后大概刷了4道线段树题目；
- 1道：2维线段树，打了个树状数组，36分跑路；
- 1道：可以用线段树做，打了个暴力AC后又跑路了；
- 1道：搞了4天，终于还是修成正果；
- 1道：就是今天这道，虽然AC了，但没完全想明白。
今天继续分享今天这道题的情况。
天大的BUG
相信很多oier都用过这个工具
- https://csacademy.com/app/diffing_tool/
这个工具干嘛使的吗？就是做文件内容对比的。
孩子们在做题的时候，可以用这个工具对比自己的输出和正解是否有区别。
一直很相信这个工具，结果还是不靠谱。
当数据量小的时候，这个工具还可以，可一旦数据量大的时候，就不靠谱了。
小码匠刷的一道题，当时有4个点挂了，然后用这个工具做数据对比。
输出数据：49787行，其中有一行有差异，结果这个工具没有识别出来。
害的小码匠还发了个帖子求助，为啥输出数据一样，测试点没有通过，实则是不同的。
所以：孩子们在用这个工具的时候要慎重，可以尝试学习
- Linux下文件内容比较命令
分享下代码
这道题也调试了很长时间，线段树打起来还是比较费劲，码量会大些。
[USACO14DEC] Marathon G
代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int MAX_NUM = 1e5 5;
typedef long long ll;
struct pos {
int x, y;
} p[MAX_NUM 5];
struct line {
int l, r;
ll v;
};
//int n;
ll dis(pos a, pos b) {
return abs(a.x - b.x) abs(a.y - b.y);
}
int n;
struct SegmentTree {
vector<line> t;
vector<ll> dist;
bool opt;
SegmentTree( bool b, ll v) : t(8 * MAX_NUM), dist(MAX_NUM 1, v), opt(b) {};
void push_up(int u) {
if (opt) {
t[u].v = t[u << 1].v t[u << 1 | 1].v;
} else {
t[u].v = min(t[u << 1].v, t[u << 1 | 1].v);
}
};
void modify(int u, int x) {
if (x <= 1 || x > n) {
return;
}
if (t[u].l == x && t[u].r == x) {
t[u].v = dist[x];
} else {
int mid = (t[u].l t[u].r) >> 1;
if (x <= mid) {
modify(u << 1, x);
} else {
modify(u << 1 | 1, x);
}
push_up(u);
}
}
ll query(int u, int l, int r) {
if (t[u].l >= l && t[u].r <= r) {
return t[u].v;
} else {
ll cnt = opt ? 0 : 0x7f7f7f7f7f7f7f7f;
int mid = (t[u].l t[u].r) >> 1;
if (l <= mid) {
ll s = query(u << 1, l, r);
cnt = opt ? s : min(s, cnt);
}
if (r > mid) {
ll s = query(u << 1 | 1, l, r);
cnt = opt ? s cnt : min(s, cnt);
}
return cnt;
}
}
} sum(true, 0), least(false, 0x7f7f7f7f7f7f7f7f);
void build(int u, int l, int r) {
sum.t[u].l = l;
sum.t[u].r = r;
least.t[u].l = l;
least.t[u].r = r;
if (l == r) {
sum.t[u].v = sum.dist[l];
least.t[u].v = least.dist[l];
return;
}
int mid = (l r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid 1, r);
sum.t[u].v = sum.t[u << 1].v sum.t[u << 1 | 1].v;
least.t[u].v = min(least.t[u << 1].v, least.t[u << 1 | 1].v);
}
ll min_num(int u) {
if (u == 1 || u == n) {
return 0;
}
return dis(p[u - 1], p[u 1]) - sum.dist[u] - sum.dist[u 1];
}
void best_coder() {
int m;
cin >> n >> m;
for (int i = 1; i <= n; i) {
cin >> p[i].x >> p[i].y;
}
for (int i = 2; i <= n; i) {
sum.dist[i] = dis(p[i - 1], p[i]);
}
for (int i = 2; i < n; i) {
least.dist[i] = min_num(i);
}
build(1, 1, n);
while (m--) {
char c;
cin >> c;
if (c == 'U') {
int u;
cin >> u;
cin >> p[u].x >> p[u].y;
sum.dist[u] = dis(p[u], p[u - 1]);
sum.dist[u 1] = dis(p[u], p[u 1]);
least.dist[u - 1] = min_num(u - 1);
least.dist[u] = min_num(u);
least.dist[u 1] = min_num(u 1);
sum.modify(1, u);
sum.modify(1, u 1);
least.modify(1, u - 1);
least.modify(1, u);
least.modify(1, u 1);
} else {
int l, r;
cin >> l >> r;
cout << sum.query(1, l 1, r) least.query(1, l 1, r - 1) << 'n';
}
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// freopen("4.in", "r", stdin);
// freopen("4.out", "w", stdout);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
总结
记得「关注」、点「赞」、点「在看」支持一下老码农，感谢大家的支持！
