首页 > 其他分享 >RookScore

RookScore

时间:2023-06-22 15:57:33浏览次数:46  
标签:set log 复杂度 查询 单次 RookScore

[ABC298F] Rook Score

关键在于如何排除交叉位置计算两次的干扰。

首先进行离散化,行和列是独立的,所以可以分别对行和列离散化。

考虑到可以枚举每一行,而每次覆盖到的点可以在线段树中减去这一行的点,然后查询答案;最后再修改回去。

也可以直接用一个 set,然后搞一个数组存储现在的情况,方便在 set 中找到元素,复杂度应该跟线段树差不多,常数稍大。

由于点的总数是 \(O(N)\) 级别,所以修改的量级是 \(O(N)\),单次修改 \(O(\log N)\),而查询次数等于行数,最坏就是 \(O(N)\) 次,单次查询 \(O(\log N)\),所以总复杂度就是 \(O(N\log N)\)。

代码

标签:set,log,复杂度,查询,单次,RookScore
From: https://www.cnblogs.com/wscqwq/p/17497913.html

相关文章