专栏文章

我咋叕写挂简单题了。

llzyqwq
P14588题解参与者 3已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@min1jngs
此快照首次捕获于
2025/12/01 19:03
3 个月前
此快照最后确认于
2025/12/01 19:03
3 个月前
查看原文
这个题 800 吧。
  • 给你一棵 nn 个点的有根树，根为 11，边带权。每个点有点权 aia_i，初始 ai=0a_i=0。记 dis(x,y)\text{dis}(x,y) 表示 x,yx,y 简单路径上的边权和。
  • qq 次操作：
    • 1 x y：对于 xx 子树内的点 uu，au←au+dis(u,y)a_u\leftarrow a_u+\text{dis}(u,y)。
    • 2 x：查询 xx 子树内的点的点权和。
  • n,q≤5×105n,q\le 5\times 10^5。时限 44 秒。
省流：
记 fuf_u 为 uu 的父亲，wuw_u 为 u→fuu\rightarrow f_u 这条边的权值，不妨 f1=0f_1=0；sxs_x 为以 xx 为根的子树大小。直接考虑每个点的点权变化没那么容易，但是注意到在一个修改操作中，fuf_u 和 uu 点权变化量总是差一个 wuw_u 或 −wu-w_u。这启示我们将点权做差分。
令 di=au−afud_i=a_{u}-a_{f_u}，记 uu 根链上的点依次是 p1=1,…,pk=up_1=1,\dots,p_k=u。那么 au=∑i=1kdpia_u=\sum\limits_{i=1}^kd_{p_i}。
先考虑比较简单的情形，即 yy 在 xx 子树外。此时 dxd_x 增加 dis(x,y)\text{dis}(x,y)。对于 xx 子树内的其他点 uu，dud_u 增加 wuw_u。
再考虑 yy 在 xx 子树内的情况，也就是省流的那张图。我们发现不在 x⇝yx\rightsquigarrow y 路径上的点 uu，dud_u 仍然增加 wuw_u。而在路径上的点（不包括 xx），dud_u 会减少 wuw_u。
考虑我们要查询什么，即子树内所有点的根链 dd 值和的和。考虑每个点 uu 的 dud_u 会对哪些点产生贡献。若 uu 在 1⇝x1\rightsquigarrow x 上，那么会对整棵子树的点都产生贡献，为 dusxd_us_x。若其在 xx 子树内，它会对以 uu 为根的子树内的点产生贡献，为 dusud_us_u。
现在问题来链、子树 dud_u 加 kwu+bkw_u+b，链查 ∑du\sum d_u，子树查 ∑dusu\sum d_us_u。重链剖分，问题变为区间 dud_u 加 kwu+bkw_u+b，区间查 ∑du\sum d_u 和 ∑dusu\sum d_us_u。使用你喜欢的数据结构维护即可。我是用的是树状数组。
怎么维护
相当于给出三个数列 di,si,wid_i,s_i,w_i，其中 wi,siw_i,s_i 为常数列。did_i 要支持的操作为区间加 Awi+BAw_i+B，求区间 ∑disi\sum d_is_i。∑du\sum d_u 就是的 su=1s_u=1 的情况。
直接维护 disid_is_i 前缀和 DS⁡i\operatorname{DS}_i。考虑一个操作对前缀和序列造成哪些影响。假设操作区间为 [l,r][l,r]。
记 SiS_i 为 sis_i 的前缀和，WS⁡i\operatorname{WS}_i 为 wisiw_is_i 的前缀和。
对于 i∈[r+1,n]i\in [r+1,n] 这部分，PiP_i 的增量为 dlsl∼drsrd_ls_l\sim d_rs_r 的增量之和，为 B(Sr−Sl−1)+A(WS⁡r−WS⁡l−1)B(S_r-S_{l-1})+A(\operatorname{WS}_r-\operatorname{WS}_{l-1})。
对于 i∈[l,r]i\in [l,r] 这部分，PiP_i 的增量为 dlsl∼disid_ls_l\sim d_is_i 的增量之和，为 B(Si−Sl−1)+A(WS⁡i−WS⁡l−1)B(S_i-S_{l-1})+A(\operatorname{WS}_i-\operatorname{WS}_{l-1})。
我们维护 Pi=AiWS⁡i+BiSi+CiP_i=A_i\operatorname{WS}_i+B_iS_i+C_i，则操作可以表示为 Ai,Bi,CiA_i,B_i,C_i 的区间加。由于维护的是前缀和数组，求原数组的区间和只需要单点查。所以只需要区间加、单点查。就可以树状数组维护了。
认为 n,qn,q 同阶，时间复杂度 O(qlog⁡2n)\mathcal{O}\left(q\log^2 n\right)，空间复杂度 O(n)\mathcal{O}(n)。常数比线段树小，跑到了最优解。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...