关于莫队的块长......
查看原帖
关于莫队的块长......
379113
dtrthg楼主2024/8/23 23:30

设每组询问的左端点、右端点为l,r,设t为时间,有此三关键字排序:

  1. 首先按l所在的块从小到大排序;

  2. 若l所在块相同,则按r所在的块从小到大排序

  3. 若l,r所在的块都相同,则按t从小到大排序

有一种块长推导大致是这样的:

设块长为a,询问m次,原数列长n,则l,r,t指针的移动次数约为:

  1. l:aml:am

  2. r:am+n2ar:am+\frac {n^2} {a}

  3. t:tn2a2t:t\frac {n^2} {a^2}

由3可知 a≥na\ge \sqrt{n} ,否则不能使t的移动次数不多于 ntnt ,导致超时。因为有 a≥na\ge \sqrt{n} ,所以 am≥n2aam\ge \frac{n^2} {a}。 所以三者的移动次数大约为:

  1. l:aml:am

  2. r:amr:am

  3. t:tn2a2t:t\frac {n^2} {a^2}

n与m同级,amam 与 tn2a2t\frac {n^2} {a^2} 取等,得:

a=nt3a=\sqrt[3]{nt}

燃鹅这块长并不是非常出色,甚至t飞了一个点

有第二种块长为 n23\sqrt[3]{n^2} ,非常出色,峰值只到了1.06s。

所以第一种块长劣在何处,为什么第二种块长比第一种块长优qwq

2024/8/23 23:30
加载中...