【BZOJ4765】普通计算姬

我没救了

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

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

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

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

(变量名花式诡异)

1
说点什么

1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
成员
LCF

Orz