zcmimi's blog

arrow_back树链剖分共22篇文章

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

点击跳转

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

点击跳转

一看就是树剖

先设所有情报员开始搜索情报的时间(我们假设给这个情报员赋值)是q,即询问个数

对于第i个询问如果是查询,则查找值比i-c小的情报员有多少个(树剖)

参与传递的人数显然是d_x+d_y-2 \times d_{LCA(x,y)} + 1

如果是让某个情报员开始搜集,则把这个情报员赋值为i

解法一:

套个主席树应该就可以了(请参见楼下)

解法二:

离线按照权值排序添加,然后用线段树或树状数组统计就可以了)

3/3
Search
search