Brief description：
x 轴上分布着 n 各村庄，坐标 x_i。在第 i 各村庄，建设基站的费用为 c_i，
。。村庄的【被覆盖半径】为 r_i，表示覆盖 i 村庄的条件是，在 [x_i – r_i, x_i + r_i] 范围内有村庄建设了基站。。
。。每个村庄未被覆盖的惩罚代价是 w_i。。。求建设至多 nn 个基站最小费用。
Brief description：
朴素：
f[ii][i]: 前 i 个村庄，第 ii 个基站建立基站 。。。
f[ii][i] = min(f[ii-1][j] + w(j, i) | ii-1 <= j < i)
这里的代价函数较为复杂：
[cpp]
int w(int l, int r){
int res = 0; FOR(i, l+1, r) if (l < ll[i] && rr[i] < r) res += _w[i];
return res;
}
[/cpp]
考察 r 的增加。。只会因为发生
rr[i] == r -> rr[i] < r+1
这样的变化。。而导致代价的增加。。
于是。。我们考虑做一个线段树维护 w(i, j)。。。
。。我们枚举所有 rr[i] = b 的点。
。。将 [0, ll[i]) 这段区间 （也就是满足 l < ll[i]）+= _w[i]。。。
http://www.lydsy.com/JudgeOnline/problem.php?id=1835
http://y4612s.logdown.com/posts/189827-solution-bzoj1835-zjoi2010base-base-station-location
https://gist.github.com/lychees/7773b7d7da611f4602e6
