求复杂度分析
  • 板块学术版
  • 楼主xxseven
  • 当前回复6
  • 已保存回复7
  • 发布时间2024/9/10 10:34
  • 上次更新2024/9/10 19:08:49
查看原帖
求复杂度分析
988025
xxseven楼主2024/9/10 10:34

维护一个长为 nn 的数列,支持区间加,区间下取整开根,查询区间和。

使用线段树,每个节点额外维护最大值 mxmx 和最小值 mnmn

区间加,查询区间和正常做。

开根操作时,如果当前节点满足 mx=mnmx=mnmx1=mnmx1=mnmx-1=mn,\lfloor\sqrt{mx}\rfloor-1=\lfloor\sqrt{mn}\rfloor,那么在当前节点做区间减,否则下传至两个儿子节点修改。

求这个做法的时间复杂度 xvx

2024/9/10 10:34
加载中...