倍增前缀和

前置知识 $倍增$ https://oi-wiki.org/basic/binary-lifting/ $\\$ 题目给出的是一个类似于内向基环树的图，根据对于每个 $i,a[Next[i]]$ 跟 $a[i]$ 关系可以建立一个边权图 $\\$ 假设 $x,y$ 都是正数，那么对于每次询问的最大前缀和都是走完即可, $\\$ 接下来就是处理负数对结局的影响.类似的我们可以利用倍增的思想额外去维护这个最大前缀和 $pre$ ,前缀和就是 $sum$ , $f_{(i,j)}$ 代表第i给点恰好走 $2^j$ 步,发现对于任意的区间 $l,r$ , $f_{(l+r).sum}$ $=f_{l.sum}+f_{r.sum}$ 而最大前缀和有两种情况取 $max$ ,从左边的序列 $l$ 贡献 $f_{(l+r).pre}=max($ $f_{(l+r).pre},f_{l.pre})$ 和从右边的序列 $r$ 贡献，因为必须是前缀需要加上左边序列的元素和 $f_{(l+r).pre}=max$ $(f_{l.sum}+$ $f_{r.pre},f_{(l+r).pre})$ $\\$ 接下来就可以在倍增数组上维护 $f_{(i,j)}$ 了 $\\$

$f_{(i+j).sum}=$ $f_{(i,j-1).sum}+f_{(f_{(i,j-1)},j-1).sum}$ $\\$

编辑器加载中…

输入

预期输出（选填）

倍增前缀和

P2079.第5题-小美玩游戏

Status

Development

Support

About

Status

Development

Support

About

Login