Brief description:
。。维护一个区间。。每个位置有一个楼房。。。问一个人站在 (0, 0) 位置。。抬头最多能看到多少楼房。。
。。（。支持单点修改。
Analysis:
前略，填过的清橙 OJ。
如何能 O(1) 时空 的判断一个节点是否是叶子节点？
const int N = int(1e5) + 9;
namespace Segment_Tree {
#define lx (x<<1)
#define rx (lx|1)
#define ml (l+r>>1)
#define mr (ml+1)
#define lc lx, l, ml
#define rc rx, mr, r
#define root 1, 1, n
const int NN = 4*N;
DB mx[NN]; int jp[NN];
int a, b, n;
int Jmp(int x, int l, int r, DB h){
if (l < r) return mx[lx] < h ? Jmp(rc, h) : jp[x] - jp[lx] + Jmp(lc, h);
return h < mx[x];
}
void upd(int x, int l, int r){
mx[x] = max(mx[lx], mx[rx]);
jp[x] = jp[lx] + Jmp(rc, mx[lx]);
}
void Modify(int x, int l, int r) {
if (l == r) {
mx[x] = (DB) b / a;
jp[x] = 1;
} else {
if (a < mr) Modify(lc);
else Modify(rc);
upd(x,l,r);
}
}
} using namespace Segment_Tree;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
RD(n); Rush {
RD(a, b); Modify(root);
OT(jp[1]);
}
}
———— UPD 2021/09/10 ————
（。这个题线段树的做法有点厉害。。。以下直接贴 Seter 题解。。。
半年前和主席讨论过类似的问题，得出的结论是只能sqrtnlgn，再怎么优化也只能sqrtn。。
结果居然有线段树做法。。
首先我们把每个房屋的Y除以X，再在最左边加个0，这样的话，答案就是从0开始，每次往右边跳到严格比它大的第一个数上，直到不能跳为止，总共跳了几次。。
比如得出来是0 2 1.5 2.333，那就是跳了2次，答案就是2。
当时只想出了分块。。问了一些神犇他们都不肯好好帮忙想。。于是就搁置了。。
标程是一种线段树做法。。
首先注意到，在一段中跳，最后必定在最大的那个数上停下来。
每个点代表一个区间，维护两个东西：这个区间的最大数和这个区间的最左边加个0后从0开始往右跳能跳几次。
const int _N = 100009, N = _N * 4; int lc[N], rc[N]; DB mm[N]; int jp[N]; // 这个区间的最大数和这个区间的最左边加个 0 后从 0 开始往右跳能跳几次。 int nn; int xx, yy; DB slop; int n, root; .. .
然后每个节点再支持一个操作：假设最左边来了个x，在这个区间中，从 x 开始往右跳能跳几次。
这个操作有哪些用处呢？
第一就是x=0时，得出的答案恰好就是这个点中要维护的那个东西。
第二就是，我可以合并两个相邻区间的从0开始跳的答案了！因为我必定是从0开始跳到左儿子的最大数上，然后再从左儿子的最大数开始往右儿子跳。
void Upd(int x){
mm[x] = max(mm[lx], mm[rx]);
jp[x] = jp[lx] + Jmp(rx, mm[lx]);
}
.. .
则整个区间的答案就是，左儿子从0开始跳的答案（这个直接维护了），加上右儿子从左儿子最大数（这个也直接维护了）开始跳的答案（这个递归下去算）。
由于每次只递归右儿子，所以每个点算答案还是lgn的，这样就可以lg^2n修改了。
—————————————————————————————————————————–
那怎么才能实现这个操作呢？
我们发现，如果x比左儿子的最大数还要大，那么左儿子就是没有用的，直接返回右儿子的答案就可以了。
否则呢？难道要返回左儿子从x开始跳的答案加上右儿子从左儿子最大数开始跳的答案吗？可是这样两边都要递归了，复杂度就坏掉了。。
我们再来看看上面提到的合并区间的方法：
“则整个区间的答案就是，左儿子从0开始跳的答案（这个直接维护了），加上右儿子从左儿子最大数（这个也直接维护了）开始跳的答案（这个递归下去算）。”
换句话说，右儿子从左儿子最大数开始跳的答案，就是整个区间从0开始跳的答案减去左儿子从0开始跳的答案，而这两个答案都直接维护了！
所以这也只需要递归一个儿子即可。
int Jmp(int x, DB h){
if (lx) return mm[lx] <= h ? Jmp(rx, h) : jp[x] - jp[lx] + Jmp(lx, h);
return h < mm[x];
}
.. .
整体复杂度是lg^2n的。
