题目
题解
倍增做法
假设起点在左边，终点在右边。
首先最优的走法一定是能往右走就往右走，不能往右走了，我们就称“撞墙”了。
考虑一次撞墙事件，撞墙后，你一定会跑到新区间的上端点或者下端点，然后继续走。
那么撞墙一次之后，我们就可以倍增了。设 $f_{i, j}$ 表示从 $i$ 点出发，撞墙 $2^j$ 后到达的点，$g_{i, j}$ 表示花费的步数。
于是现在问题变成了求第一次撞墙撞在哪，在 ST 上二分或者线段树二分可以做到 $\log n$。
总复杂度 $O\left(n \log n + q \log n\right)$。
代码
代码
/* C++17 is required!
* By Koicy (https://koicy.ly)
* Email n@rbtr.ee
* I've reached the end of my fantasy.
__ __ __ _
_____/ /_ / /_________ ___ / /______ (_)______ __
/ ___/ __ \/ __/ ___/ _ \/ _ \ ______ / //_/ __ \/ / ___/ / / /
/ / / /_/ / /_/ / / __/ __/ /_____/ / ,< / /_/ / / /__/ /_/ /
/_/ /_.___/\__/_/ \___/\___/ /_/|_|\____/_/\___/\__, /
SIGN /___*/
#ifndef XCODE
constexpr bool _CONSOLE = false;
#else
constexpr bool _CONSOLE = true;
#endif
#define __NO_MAIN__ false
#define __ENABLE_RBLIB__ true
constexpr bool _MTS = false, SPC_MTS = false;
constexpr char EFILE[] = "";
#define FULL(arg) arg.begin(), arg.end()
// :/
signed STRUGGLING([[maybe_unused]] unsigned long TEST_NUMBER) {
tp n = bin;
vector<tp> u(n + 1), d(n + 1);
for (tp i = 1; i <= n; ++i) bin >> u[i] >> d[i];
vector jmp(n * 2 + 2, vector<pair<tp, tp>>(19));
struct MAX { tp operator()(tp a, tp b) { return max(a, b); } };
struct MIN { tp operator()(tp a, tp b) { return min(a, b); } };
lib::ST<tp, MAX> mav(u);
lib::ST<tp, MIN> miv(d);
auto gos = [&](tp t, tp s, tp b) {
tp l = s, r = b, tar = s;
while (l <= r) {
tp mid = (l + r) / 2;
if (mav(s, mid) <= t && miv(s, mid) >= t) {
tar = mid;
l = mid + 1;
} else r = mid - 1;
}
return tar;
};
[&]() {
for (tp i = 1; i <= n; ++i) {
if (mav(i, n) <= u[i] && miv(i, n) >= u[i]) jmp[i * 2][0] = make_pair(2 * n + 2, 0);
else {
tp tar = gos(u[i], i, n) + 1;
if (abs(u[i] - u[tar]) <= abs(u[i] - d[tar])) {
jmp[i * 2][0] = make_pair(tar * 2, abs(u[i] - u[tar]));
} else jmp[i * 2][0] = make_pair(tar * 2 + 1, abs(u[i] - d[tar]));
}
if (mav(i, n) <= d[i] && miv(i, n) >= d[i]) jmp[i * 2 + 1][0] = make_pair(2 * n + 2, 0);
else {
tp tar = gos(d[i], i, n) + 1;
if (abs(d[i] - u[tar]) <= abs(d[i] - d[tar])) {
jmp[i * 2 + 1][0] = make_pair(tar * 2, abs(d[i] - u[tar]));
} else jmp[i * 2 + 1][0] = make_pair(tar * 2 + 1, abs(d[i] - d[tar]));
}
}
}();
for (tp i = 1; i < 19; ++i) {
for (tp j = 2; j <= n * 2 + 1; ++j) {
if (jmp[j][i - 1].first <= n * 2 + 1) {
jmp[j][i].first = jmp[jmp[j][i - 1].first][i - 1].first;
jmp[j][i].second = jmp[j][i - 1].second + jmp[jmp[j][i - 1].first][i - 1].second;
} else jmp[j][i] = jmp[j][i - 1];
}
}
tp q = bin;
while (q--) [&]() {
tp xs, ys, xt, yt;
bin >> xs >> ys >> xt >> yt;
if (xs > xt) {
swap(xs, xt);
swap(ys, yt);
}
if (mav(xs, xt) <= ys && miv(xs, xt) >= ys) {
bin << abs(ys - yt) + abs(xt - xs) << '\n';
return;
}
tp tar = abs(xt - xs);
[&]() {
tp p = gos(ys, xs, xt) + 1;
tp ud = abs(ys - u[p]) > abs(ys - d[p]);
tar += min(abs(ys - u[p]), abs(ys - d[p]));
for (tp i = 18; i >= 0; --i) {
if (jmp[p * 2 + ud][i].first / 2 <= xt) {
tar += jmp[p * 2 + ud][i].second;
tp t = jmp[p * 2 + ud][i].first;
p = t / 2;
ud = t % 2;
}
}
tar += abs((ud ? d[p] : u[p]) - yt);
}();
bin << tar << '\n';
}();
return 0;
}
void MIST() {
}
// :\ */线段树做法
这题有一个加强版 LOJ 3038，带修改，这样我们的倍增就不管用了。
我们发现这个其实可以合并的。对于一段路来说，有两种可能：撞过墙，或者没撞过墙。如果没撞过墙，我们只需要维护完美的区间（即一直往右也不会撞墙的区间）。如果撞过墙，我们需要维护路径的起点终点和花费。由于撞过墙，于是这个路径是唯一确定的。分类讨论合并。
代码
/* C++17 is required!
* By Koicy (https://koicy.ly)
* Email n@rbtr.ee
* I've reached the end of my fantasy.
__ __ __ _
_____/ /_ / /_________ ___ / /______ (_)______ __
/ ___/ __ \/ __/ ___/ _ \/ _ \ ______ / //_/ __ \/ / ___/ / / /
/ / / /_/ / /_/ / / __/ __/ /_____/ / ,< / /_/ / / /__/ /_/ /
/_/ /_.___/\__/_/ \___/\___/ /_/|_|\____/_/\___/\__, /
SIGN /___*/
#ifndef XCODE
constexpr bool _CONSOLE = false;
#else
constexpr bool _CONSOLE = true;
#endif
#define __NO_MAIN__ false
#define __ENABLE_RBLIB__ true
constexpr bool _MTS = false, SPC_MTS = false;
constexpr char EFILE[] = "";
#define FULL(arg) arg.begin(), arg.end()
#define LOAD5($1, $2, $3, $4, $5, ...) $5
#define __FOR1(b) for (tp _COUNTER_ = 0; _COUNTER_ < tp(b); ++_COUNTER_)
#define __FOR2(i, b) for (tp i = 0; i < tp(b); ++i)
#define __FOR3(i, a, b) for (tp i = tp(a); i < tp(b); ++i)
#define __FOR4(i, a, b, c) for (tp i = tp(a); i < tp(b); i += tp(c))
#define gor(...) LOAD5(__VA_ARGS__, __FOR4, __FOR3, __FOR2, __FOR1)(__VA_ARGS__)
// :/
signed STRUGGLING([[maybe_unused]] unsigned long TEST_NUMBER) {
struct S {
tp l, r, c;
S() : l(-INF), r(INF), c(-1) {};
S(tp l, tp r, tp c = -1) : l(l), r(r), c(c) {};
static S op(S p, S q) {
if (p.c == -1 && q.c == -1) {
if (max(p.l, q.l) <= min(p.r, q.r)) return S(max(p.l, q.l), min(p.r, q.r));
else {
if (p.r < q.l) return S(p.r, q.l, q.l - p.r);
else return S(p.l, q.r, p.l - q.r);
}
} else if (p.c == -1) {
if (p.l <= q.l && q.l <= p.r) return q;
else {
if (p.l > q.l) return S(p.l, q.r, q.c + p.l - q.l);
else return S(p.r, q.r, q.c + q.l - p.r);
}
} else if (q.c == -1) {
if (q.l <= p.r && p.r <= q.r) return p;
else {
if (q.l > p.r) return S(p.l, q.l, p.c + q.l - p.r);
else return S(p.l, q.r, p.c + p.r - q.r);
}
} else return S(p.l, q.r, p.c + abs(p.r - q.l) + q.c);
}
static S e() { return S(); }
};
tp n, q; bin >> n >> q; --n;
vector<tp> u(n), d(n);
lib::Light_Segtree<S, S::op, S::e> o(n);
gor(i, n) bin >> u[i] >> d[i];
gor(i, n) o.set(i, S(u[i], d[i]));
gor(q) {
tp op = bin;
if (op == 1) {
tp x, u, d; bin >> x >> u >> d;
o.set(x - 1, S(u, d));
} else {
tp xs, ys, xt, yt; bin >> xs >> ys >> xt >> yt;
if (xs > xt) {
swap(xs, xt);
swap(ys, yt);
}
S ret = S::op(S::op(S(ys, ys), o.prod(xs - 1, xt - 1)), S(yt, yt));
bin << xt - xs + max(ZERO, ret.c) << '\n';
}
}
return 0;
}
void MIST() {
}
// :\ */分治做法
这题有个分治做法，好像还挺好写的，等会学一下。