zcmimi's blog

categories/刷题记录/共659篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

用所有总数减掉不符合的

hash或马拉车

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

倍增找k级祖先+dsu on tree静态链分治

设当前节点为x

如果d_x < k,那么答案当然为0 可以找到第k级祖先,然后在k级祖先上添加一组询问(求它子树中深度为d_x的节点数)

因为这个还算上了x本身,所以把结果-1就是答案了

统计区间中各个深度的点有多少个就直接tot[d_x]+=(1\text{或}-1)就可以了

上代码:

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

直接建立20棵线段树统计1,2,4,8,...,2^20就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

直接树剖即可

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

静态链分治 参见模板

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

线段树解法:

我们记录d_x表示x的深度还有dfs

每个点修改的时候把它的子树都加上val

因为记录了深度,所以d_{x'}如果和d_x同奇偶则加上val,否则减去val

树状数组解法:

60/66
Search
search