@[critnos](/user/203623) 不需要底层分块吧。
https://www.luogu.com.cn/record/99599746
by Pulsating_Dust @ 2023-08-05 08:46:40
@[Pulsating_Dust](/user/746640) 艹你常数怎么这么小
能云剪切板给个代码吗
by critnos @ 2023-08-05 08:51:33
@[critnos](/user/203623) https://www.luogu.com.cn/paste/fzvtptsh
by Pulsating_Dust @ 2023-08-05 08:54:15
thx
by critnos @ 2023-08-05 08:54:52
您这好像只有把结构体展开了,我试试
by critnos @ 2023-08-05 08:58:35
p.s. 把除法换成预处理区间长度倒数会快不少
by critnos @ 2023-08-05 09:00:00
@[critnos](/user/203623) /bx 话说您认为这种ktt的复杂度要如何分析啊,1个log我不会证,但是也卡不满。
by Pulsating_Dust @ 2023-08-05 09:10:14
我不会啊()
by critnos @ 2023-08-05 09:10:53
@[Pulsating_Dust](/user/746640) 我也不太清楚,可能可以证2个log吧
by 142857cs @ 2023-08-05 09:17:18
@[142857cs](/user/35760) 因为是全局修改,因此一次击败事件发生一定会增加区间的最大子段和总长度,而线段树节点总长度和是 $n\log n$ 级别的,每次线段树操作带一个$\log n$,复杂度肯定不超过 $n\log^2n$。
by Pulsating_Dust @ 2023-08-05 09:24:09