zcmimi's blog

arrow_back根号分治共3篇文章

avatar
zcmimi
2020-09-25 20:10:32

根号分治是一种

练习

LG 5901 [IOI2009]regions

avatar
zc
2020-10-07 20:03:39

查看原题

点击跳转

题意:

n个节点的树,有r种属性,每个点属于一种属性.有q次询问,每次询问给r_1,r_2,问有多少对点(e_1, e_2)满足e_1属性为 r_1,e_2属性为r_2,且e_1e_2的祖先. (n,q \le 2 \times 10^5, r \le 25000,时限5s)

首先将询问离线

不管枚举e_1统计子树中e_2的数量

还是枚举e_2统计到根节点路径上e_1的数量

都是\mathcal O(nr)

可以考虑将两种方法结合,使用根号分治

r_2的总数目为S

S\ge \sqrt n,枚举e_2,统计e_1(不超过\sqrt n个),复杂度\mathcal O(q\sqrt n)

否则枚举e_1,统计e_2(子树中的r_2不会超过\sqrt n个),复杂度\mathcal O(n\sqrt n)

具体看代码

avatar
zc
2020-09-25 20:03:00

查看原题

点击跳转

根号分治论文题

题意

给一个序列序列A,单点修改,

查询\displaystyle \sum_{i\mod p=k} A_i

1/1
Search
search