踩气球TJ

发布时间 2023-09-11 16:39:49作者: cqbzwwh

踩气球

如何查看每次修改会影响的熊孩子呢?

如果只是每一次修改点的时候更改“包含这个点的所有熊孩子”,时间复杂度最大为\(O(NM)\).挂了

这道问题很像“单点修改,区间查询”。
我们知道,对每一次“修改单点”,可以转化成“修改\(\log n\)个包含这个点的区间”,复杂度为\(O(\log n)\)。那如何从区间转化成“熊孩子”。一个熊孩子是包含多个区间,就像一个区间包含多个点。特别注意到只有当熊孩子中“每一个数都为0”才可以满足,所以在没有全部区间清零之前,我们不关心哪些区间清零了,需要记录的只是有多少个区间被清零了

所以,先预处理出每个熊孩子在那些区间,并记录总共包含了多少个区间。
设包含区间\(u\)的熊孩子为\(list_u\)

将单点修改转化到修改区间。当区间\(u\)中的所有点都为 \(0\) 时,更新\(list_u\)

时间复杂度分析:

点->区间为\(O(n\log n)\)

容易知道,每个区间值为\(0\)只会有一次,更新这个区间包含的熊孩子也只会有一次。所有包含熊孩子的区间不超过\(M\log N\)个。所有区间的\(list.size\)之和也不超过\(M \log N\).又因为每个区间只会被更新一次。所以时间复杂度为\(O(M \log N)\)