p4117专题

P4117 [Ynoi2018] 五彩斑斓的世界

分析第一个操作 朴素的做法,遍历一遍大于x就-=x,极限复杂度O(mn) 分块做法 整块:我们维护一个最大值,从mx到x遍历一遍(减去x)用并查集操作merge(i,i-x),考虑mx=100001,x=1,极限复杂度O(mV) 我们可以分析 1.x>(mx/2),从mx到x遍历一遍,应该是最优的复杂度O(mx-x) 2.x<(mx/2),最优的复杂度应该是O(x),因此思考在这种