1 条题解

  • 2
    @ 2021-8-10 16:44:23
    注意值域较小。 
    对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)。
    

    code

    • 1

    信息

    ID
    4320
    时间
    1000ms
    内存
    128MiB
    难度
    8
    标签
    (无)
    递交数
    139
    已通过
    20
    上传者