题解：P12536 [XJTUPC 2025] 我永远喜欢希儿·芙乐艾

minstdfx · 2025-05-19 17:37:40 · 题解

Scarlet.: 05-09 16:46:53
哦

Scarlet.: 05-09 16:46:55
就你先

Scarlet.: 05-09 16:47:01
很套路的

Scarlet.: 05-09 16:47:11
转成子树询问单点修改

Scarlet.: 05-09 16:47:19
然后转成区间查询单点修改

Scarlet.: 05-09 16:47:22
然后

Scarlet.: 05-09 16:47:29
很套路的给A分块

Scarlet.: 05-09 16:47:55
散块修改次数nsqrtn，沿时间轴查询n

Scarlet.: 05-09 16:48:11
那就o1修改osqrtn的根分

Scarlet.: 05-09 16:48:23
整块你只需要考虑完整改掉这一整块的操作

Scarlet.: 05-09 16:49:38
枚举sqrt个块，然后sqrt个修改弄出被完整执行1次的情况，遍历询问序列每次遇到完整包含这个块的1操作cnt+1，询问就查询一下乘个cnt

Scarlet.: 05-09 16:50:01
这样就是n个修改nsqrt个查询，块内前缀和维护osqrt单点修改o1查询即可

Scarlet.: 05-09 16:50:04
然后做完了

Scarlet.: 05-09 16:50:13
非常套路