/p/77
METO说是单点更新线段树。要记录哪些点不用再更新，不太清楚具体是要怎么实现？
一个类似的想法是把n个点建一棵平衡树，每次节点变成0之后从树上移除，至多变化30n次，移除的复杂度应该比30nlogn略小一些，5e7左右。
每次更新区间的时候，在树上找到需要更新的第一个节点（upperboundL），然后不断删除再upperbound，单次更新复杂度nlogn，但每个节点实际上最多被更新30次，也就最多被upperbound30次左右。
查询和就直接一个log。
所以具体的复杂度解决2e8左右。
转载于:.html
本文发布于:2024-01-28 22:44:53，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170645309810831.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
