题意
有 $n$ 栋楼，第 $i$ 栋楼的高度为 $H_i$。在坐标轴上用一条 $\left(i, 0\right)$ 到 $\left(i, H_i\right)$ 的线段表示。称第 $i$ 栋楼可以被看到，当且仅当从 $\left(0, 0\right)$ 到 $\left(i, H_i\right)$ 的线段上，与 $\left[1, i - 1\right]$ 的楼均没有交点（交在端点上也算相交）。
最初每栋楼的高度都为 $0$。$m$ 次操作，每次给定 $X$ 和 $Y$，表示把第 $X$ 栋楼的高度修改为 $Y$。每次操作后输出有几个看得到的楼。
题解
用线段树维护区间答案和区间最大斜率，合并时，左边答案不变，在右边找第一个斜率大于左边最大斜率的点开始重新计算。这样单次合并是 $O\left(\log len\right)$ 的。于是总复杂度为 $O\left(n \log^2 n\right)$。
代码
int VOID([[maybe_unused]] unsigned long long int TEST_NUMBER) {
tp n, m; cin >> n >> m;
struct frac {
tp a, b;
frac(tp a = 0, tp b = 1) : a(a), b(b) {}
bool operator<(frac c) const { return c.b * a < c.a * b; }
bool operator<=(frac c) const { return c.b * a <= c.a * b; }
bool operator>(frac c) const { return c.b * a > c.a * b; }
bool operator>=(frac c) const { return c.b * a >= c.a * b; }
};
struct like {
tp tar;
frac k;
like() = default;
like(tp tar, frac k) : tar(tar), k(k) {}
};
vector<like> t(n * 4 + 1);
auto query = lexp([&](auto $, tp x, tp l, tp r, frac k) -> tp {
if (t[x].k <= k) return 0;
if (l == r) return t[x].k > k;
tp mid = (l + r) / 2;
if (t[x * 2].k > k) return $(x * 2, l, mid, k) + t[x].tar - t[x * 2].tar;
else return $(x * 2 + 1, mid + 1, r, k);
});
auto modify = lexp([&](auto $, tp x, tp l, tp r, tp g, tp d) -> void {
if (l == r) {
t[x] = like(1, frac(d, g));
return;
}
tp mid = (l + r) / 2;
if (g <= mid) $(x * 2, l, mid, g, d);
else $(x * 2 + 1, mid + 1, r, g, d);
t[x].k = max(t[x * 2].k, t[x * 2 + 1].k);
t[x].tar = t[x * 2].tar + query(x * 2 + 1, mid + 1, r, t[x * 2].k);
});
while (m--) {
tp x, y; cin >> x >> y;
modify(1, 1, n, x, y);
cout << t[1].tar << '\n';
}
return 0;
}