1 条题解
-
2
注意值域较小。 对y根号分治: - 1 y<=sqrt(v) : 对每个y统计答案 - 2 y> sqrt(v) : x/y<=sqrt(v) 枚举 x/y 考虑如何统计答案: 即需要支持对一个值查询第一个>=it的值(lower_bound)。 set可以直接做,但复杂度多个log。 考虑根号平衡一下,O(log size)插入O(log size)查询->O(sqrt v)插入O(1)查询。 对值域分块, - (1) 对每个块维护本块和后面的块的min。 - (2) 对每个值维护本块内>=它的第一个存在的元素。 查询时(2)存在则为答案,不存在答案为后面块的(1)。
- 1
信息
- ID
- 4320
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 139
- 已通过
- 20
- 上传者