题目链接 楼房重建
解题思路：我们可以把楼房的最高点的斜率计算出来。那么问题就转化成了实时查询x的个数，满足数列x的左边没有大于等于x的数。
我们可以用线段树维护
设t[i]为如果只看这个区间，可以看到的楼房数量有多少。
f[i]为这个区间的x的最大值
更新的时候我们递归讨论。
计算t[i]时，区间的前一半直接套t[i << 1]的结果，但是后一半受前一半区间的最大值的影响，要分开求解。
query(i, L, R, val)为当前区间中大于val的数的个数（val并不在这个区间内而在这个区间的左边）
然后输出t[1]（即整个数列的满足题意的个数）即可。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define lson i << 1, L, mid
#define rson i << 1 | 1, mid + 1, R typedef long long LL; const int N = 4e5 + 10; double x, y;
int n, m;
double f[N];
int t[N]; int query(int i, int L, int R, double val){
if (L == R) return val < f[i];
int mid = (L + R) >> 1;
if (val >= f[i << 1]) return query(rson, val);
return t[i] - t[i << 1] + query(lson, val); //巧妙的分类讨论
} void update(int i, int L, int R, int x, double val){
if (L == R){
t[i] = 1;
f[i] = val;
return;
} int mid = (L + R) >> 1;
if (x <= mid) update(lson, x, val);
else update(rson, x, val);
f[i] = max(f[i << 1], f[i << 1 | 1]); //更新该区间的最大值
t[i] = t[i << 1] + query(i << 1 | 1, mid + 1, R, f[i << 1]); //更新该区间的符合题意的数量
} int main(){ scanf("%d%d", &n, &m);
rep(i, 1, m){
scanf("%lf%lf", &x, &y);
update(1, 1, n, (int)(x + 0.5), y / x); //更新
printf("%d\n", t[1]);
} return 0;
}