萌新刚学OI,问一下这道题整体二分能不能做到一个 log
查看原帖
萌新刚学OI,问一下这道题整体二分能不能做到一个 log
203501
sgweo8ys楼主2022/5/1 11:40

这题大多数整体二分题解都是 O(nlog2n)O(n \log^2 n),使用的数据结构为树状数组

但对于整体二分的一个 solve 函数,我们实际要做的就是执行区间加并判断每个国家是否满足要求

这里如果使用差分的话,复杂度不就是 O(n)O(n) 了吗

至于递归后导致的问题,可以直接 基数排序+离散化 解决啊

2022/5/1 11:40
加载中...