力大堆飞 P3261
https://www.luogu.com.cn/problem/P3261。
虽然可以使用可并堆简单维护但这个题很显然存在一些更加丁真的做法。这个做法能强制在线地求出每个骑士在哪座城倒下。
首先如果在序列上那显然长得一脸线段树二分，所以我们考虑怎么比较好地维护这个信息。我们注意到可以把每个点的信息映射到一条有起点和终点的线段作为一个一次函数来维护（实际上维护的是两个端点），同时可以直接使用题目里保证的绝对值不超过
struct func {
int xl, xr, yl, yr;
int getk() const { return xl == xr ? 1 : (yr - yl) / (xr - xl); }
int operator()(int x) const { return (x - xl) * getk() + yl; }
};
func merge(func a, func b) {
static auto mnov = [](int x, int y) {
if (x < 0) return 0ll;
return (x + y - 1) / y;
};
if (a.xl > a.xr) return a;
if (b.xl > b.xr) return b;
int k = a.getk();
func c;
c.xl = mnov(b.xl - a.yl, k) + a.xl;
c.xr = a.xr - mnov(a.yr - b.xr, k);
if (c.xl > c.xr) return {1, 0, 0, 0};
c.yl = b(a(c.xl)), c.yr = b(a(c.xr));
return c;
}初始化直接按定义抄一遍：
if (!a) {
int xl = max(-A - min(v, 0ll), h[i]), xr = A - max(v, 0ll);
val[i] = {xl, xr, xl + v, xr + v};
} else {
int xl = h[i], xr = A / v;
val[i] = {xl, xr, xl * v, xr * v};
}这样序列上已经可以做了。然后我们考虑树上其实并没有什么不同。采用树链剖分进行维护，在每个点上求出它到重链顶的前缀和，这样就可以从起点开始一路跳重链来确定答案停在哪条重链上，然后在重链上根据 dfs 序的连续性就可以套序列上那个线段树二分了。非常雪豹。
完整代码 be like：
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 3e5 + 9, A = 1e18;
struct func {
int xl, xr, yl, yr;
int getk() const { return xl == xr ? 1 : (yr - yl) / (xr - xl); }
int operator()(int x) const { return (x - xl) * getk() + yl; }
};
func merge(func a, func b) {
static auto mnov = [](int x, int y) {
if (x < 0) return 0ll;
return (x + y - 1) / y;
};
if (a.xl > a.xr) return a;
if (b.xl > b.xr) return b;
int k = a.getk();
func c;
c.xl = mnov(b.xl - a.yl, k) + a.xl;
c.xr = a.xr - mnov(a.yr - b.xr, k);
if (c.xl > c.xr) return {1, 0, 0, 0};
c.yl = b(a(c.xl)), c.yr = b(a(c.xr));
return c;
}
int n, m, dfn[N], pos[N], top[N], fa[N], dph[N], ans[N], cnt[N];
vector<int> es[N];
func val[N], sum[N];
struct {
func f;
int l, r;
} tr[N << 2];
void init() {
int h[N];
for (int i = 1; i <= n; ++i) cin >> h[i];
val[1] = {h[1], A, h[1], A};
for (int i = 2, a, v; i <= n; ++i) {
cin >> fa[i] >> a >> v;
es[fa[i]].push_back(i);
if (!a) {
int xl = max(-A - min(v, 0ll), h[i]), xr = A - max(v, 0ll);
val[i] = {xl, xr, xl + v, xr + v};
} else {
int xl = h[i], xr = A / v;
val[i] = {xl, xr, xl * v, xr * v};
}
}
}
void build() {
int sz[N], sn[N];
function<void(int)> dfs1 = [&](int x) {
sz[x] = 1, sn[x] = 0, dph[x] = dph[fa[x]] + 1;
for (int y : es[x]) {
dfs1(y), sz[x] += sz[y];
if (!sn[x] || sz[y] > sz[sn[x]]) sn[x] = y;
}
};
dfs1(1);
function<void(int, int)> dfs2 = [&](int x, int t) {
static int tot;
pos[dfn[x] = ++tot] = x, top[x] = t, sum[x] = val[x];
if (top[x] != x) sum[x] = merge(sum[x], sum[fa[x]]);
if (int z = sn[x]) {
dfs2(z, t);
for (int y : es[x])
if (y != z) dfs2(y, y);
}
};
dfs2(1, 1);
function<void(int, int, int)> build = [&](int x, int L, int R) {
if (L == R) {
tr[x].f = val[pos[L]];
return;
}
int mid = (L + R) >> 1;
build(x << 1, L, mid), build(x << 1 | 1, mid + 1, R);
tr[x].f = merge(tr[x << 1 | 1].f, tr[x << 1].f);
};
build(1, 1, n);
}
int calc(int x, int h) {
static function<int(int, int&, int, int, int, int)> findr =
[](int x, int& h, int l, int r, int L, int R) {
if (l > R || L > r) return 0ll;
if (l <= L && R <= r) {
func f = tr[x].f;
if (h >= f.xl && h <= f.xr) return h = f(h), 0ll;
}
if (L == R) return R + 1;
int mid = (L + R) >> 1, d = findr(x << 1 | 1, h, l, r, mid + 1, R);
if (!d) d = findr(x << 1, h, l, r, L, mid);
return d;
};
while (x) {
func f = sum[x];
if (h >= f.xl && h <= f.xr) {
h = f(h), x = fa[top[x]];
continue;
}
int d = findr(1, h, dfn[top[x]], dfn[x], 1, n);
return d > dfn[x] ? x : fa[pos[d]];
}
return 0;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m, init(), build();
for (int i = 1, s, c; i <= m; ++i) {
cin >> s >> c;
int x = calc(c, s);
++cnt[x], ans[i] = dph[c] - dph[x];
}
for (int i = 1; i <= n; ++i) cout << cnt[i] << '\n';
for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
return cout << flush, 0;
}线性空间单
闲话：根据这个做法很显然骑士的路径可以改成从一个点杀到另一个点而不是固定向根，不知道有没有老哥把这个搬到谁家模拟赛去过。