设每组询问的左端点、右端点为l,r,设t为时间,有此三关键字排序:
-
首先按l所在的块从小到大排序;
-
若l所在块相同,则按r所在的块从小到大排序
-
若l,r所在的块都相同,则按t从小到大排序
有一种块长推导大致是这样的:
设块长为a,询问m次,原数列长n,则l,r,t指针的移动次数约为:
-
l:am
-
r:am+an2
-
t:ta2n2
由3可知 a≥n ,否则不能使t的移动次数不多于 nt ,导致超时。因为有 a≥n ,所以 am≥an2。
所以三者的移动次数大约为:
-
l:am
-
r:am
-
t:ta2n2
n与m同级,am 与 ta2n2 取等,得:
a=3nt
燃鹅这块长并不是非常出色,甚至t飞了一个点
有第二种块长为 3n2 ,非常出色,峰值只到了1.06s。
所以第一种块长劣在何处,为什么第二种块长比第一种块长优qwq