HDU 7435. 树

2huk · 2024-08-13 21:56:48 · 题解

线段树合并。难点是上传。

我们维护的线段树是权值线段树，维护每个数的出现次数。

如果想求得 u 的答案，首先是 ls_u 与 rs_u 的答案的和，以及两个端点在这两个儿子的情况。

令这两个端点为 x, y。我们直到因为是值域线段树所以 x < y 是天然的。所以 \max(x, y) \times |x - y| = y \times (y - x) = y^2 - xy。所以维护信息 cnt_i, cnt_i \times i, cnt_i \times i^2 即可。