维护一个长为 nnn 的数列,支持区间加,区间下取整开根,查询区间和。
使用线段树,每个节点额外维护最大值 mxmxmx 和最小值 mnmnmn。
区间加,查询区间和正常做。
开根操作时,如果当前节点满足 mx=mnmx=mnmx=mn 或 mx−1=mn,⌊mx⌋−1=⌊mn⌋mx-1=mn,\lfloor\sqrt{mx}\rfloor-1=\lfloor\sqrt{mn}\rfloormx−1=mn,⌊mx⌋−1=⌊mn⌋,那么在当前节点做区间减,否则下传至两个儿子节点修改。
求这个做法的时间复杂度 xvx