BZOJ 2957 楼房重建 (线段树)

题目链接  楼房重建

解题思路:我们可以把楼房的最高点的斜率计算出来。那么问题就转化成了实时查询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;
}
上一篇:Android Studio 将工程作为第三方类库的步骤


下一篇:【BZOJ 2957】 2957: 楼房重建 (线段树)