2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day1 [2020/09/16 12:52] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day1 [2020/09/20 21:11] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 197: | 行 197: | ||
| 修改完成后同样打上懒标记，必要时下放标记。 | 修改完成后同样打上懒标记，必要时下放标记。 | ||
| - | 显然每次修改复杂度为 $O(k\log n)$，其中 $k$ 为该次修改删除的权值线段树的叶子数。 | + | 显然每次修改复杂度为 $O(k\log^2 n)$，其中 $k$ 为该次修改删除的权值线段树的叶子数。 |
| - | 由于初始时仅有 $O(n\log n)$ 个权值线段树的叶子结点，于是修改操作的总时间复杂度为 $O(n\log^2 n)$。 | + | 由于初始时仅有 $O(n\log n)$ 个权值线段树的叶子结点，于是修改操作的总时间复杂度为 $O(n\log^3 n)$。 |
| 于是总时间复杂度 $O(n\log^3 n)$，总空间复杂度 $O(n\log^2 n)$。 | 于是总时间复杂度 $O(n\log^3 n)$，总空间复杂度 $O(n\log^2 n)$。 | ||
2020-2021/teams/legal_string/jxm2001/contest/ccpc_wannafly_winter_camp_day1.1600231926.txt.gz · 最后更改: 2020/09/16 12:52 由 jxm2001
