OceanEye's Blog

是时候表演真正的技术了!

@OceanEye2月前

05/3
19:03
OI

BZOJ4012

某码农题
动态点分治[或者说点分树?]
转化一下[差分一下]就可以看出
要维护一棵树
可以在log~log方的时间复杂度内跑完整棵树的前缀和[1,l-1],[1,r]
于是用了点分树
树链剖分可不可以还没想过,目测是不行的
用了vector来控制空间
当然有大佬愿意写动态开点线段树或者平衡树也是很强的orz

BZOJ4012