hdu 6070 Dirt Ratio

二分+线段树
二分mid，然后根据式子num[L,R]+mid*L<=（R+1）*mid来建树（num记录的是区间L,R内的不同的数字个数）。线段树记录的是从该点到当前更新的i点的结果，也就是说，如下图

此时i已经更新到箭头所指的节点5，那么对于节点8来说，L是它自己，R就是节点5, 2是A[1]到A[3]之间包含的不同数的个数，K是因为8节点作为L， 值为1，所以此时以8节点（即第一个数）为L，5节点为R的区间内的num[L,R]+mid*L值为2+k。9结点同理。通过这样可以枚举到所有区间。
比如一开始i为1，只有区间[1，1]。i为2时，有了区间[1,2]和[2,2]。总之要注意的是，每个叶子节点代表的都是以它自身为L，以当前i为R的num[L,R]+mid*L值。