【BZOJ4765】普通计算姬

我没救了

将\([1,n]\)分块,每次询问的就是若干整块和若干散点的\(sum\)和

对于整块,可以先预处理出每块内每个点在子树中出现的次数之和,那么一块的答案就可以直接\(O(n)\)算出;修改时只要对于分别每一块修改即可。

对于散点,只要查询子树权值和,再次对dfs序列分块,记录块内前缀和块的前缀和,就可以\(O(1)\)查询;修改只需要修改所在块的块内前缀和和后面块的块的前缀和

(断好句了应该还是能看懂的?)

(变量名花式诡异)

说点什么

1 评论 在 "【BZOJ4765】普通计算姬"

提醒
排序:   最新 | 最旧 | 得票最多
成员

Orz

wpDiscuz