洛谷题目链接:
题目描述
小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？
输入输出格式
输入格式：
第一行两个正整数N,M
接下来M行，每行两个正整数Xi,Yi
输出格式：
M行，第i行一个整数表示第i天过后小A能看到的楼房有多少栋
输入输出样例
输入样例#1：
3 4
2 4 3 6 1 1000000000 1 1输出样例#1：
1
1 1 2说明
对于所有的数据1<=Xi<=N，1<=Yi<=10^9
N,M<=100000
题解: 这题可以用线段树来做.
首先建树,修改的操作都是模板,因为是单点修改,所以不用\(pushdown\),这里就不多说了,关键是如何写\(push\_up\)函数.
首先我们对每个线段树上的节点需要记录一个\(sum\)表示总共能够看到的楼房数量,还需要记录一个\(mx\)表示该区间内最大的斜率.
首先我们考虑将一个区间分成两部分之后能看到的是哪些部分.我们需要记录一个在递归的时候左边的最大斜率,记为\(lmx\),那么会有这样几种情况:
- 左边的节点的\(mx\)小于\(lmx\),左边没有楼房可以被看到,递归右半边.
- 左边的节点的\(mx\)大于\(lmx\),那么右边原本能被看到的楼房在加入了左边之后也一定能被看到,递归左半边并加上右半边的答案.
这样操作之后\(pushdown\)所需要的时间从\(O(1)\)变成了\(O(logn)\).
具体实现就是这样的:
int up1(double lmx, int x){ if(t[x].mx <= lmx) return 0; if(k[t[x].l] > lmx) return t[x].sum; if(t[x].l == t[x].r) return t[x].mx > lmx; if(t[ll(x)].mx <= lmx) return up1(lmx, rr(x)); return up1(lmx, ll(x))+t[x].sum-t[ll(x)].sum;} 放一下完整代码:
#include#define ll(x) (x << 1)#define rr(x) (x << 1 | 1)using namespace std;const int N = 1e5+5;int n, m;double k[N];struct SegmentTree{ int l, r, sum; double mx; }t[N*4];int up1(double lmx, int x){ if(t[x].mx <= lmx) return 0; if(k[t[x].l] > lmx) return t[x].sum; if(t[x].l == t[x].r) return t[x].mx > lmx; if(t[ll(x)].mx <= lmx) return up1(lmx, rr(x)); return up1(lmx, ll(x))+t[x].sum-t[ll(x)].sum;}void up(int x){ t[x].mx = max(t[ll(x)].mx, t[rr(x)].mx); t[x].sum = t[ll(x)].sum+up1(t[ll(x)].mx, rr(x));}void build(int l, int r, int x = 1){ t[x].l = l, t[x].r = r; if(l == r) return; int mid = (l+r>>1); build(l, mid, ll(x)), build(mid+1, r, rr(x));}void update(int pos, int a, int b, int x = 1){ if(t[x].l == t[x].r){ t[x].mx = (double)b*1.0/a, t[x].sum = 1; return; } int mid = (t[x].l+t[x].r>>1); if(pos <= mid) update(pos, a, b, ll(x)); else update(pos, a, b, rr(x)); up(x);}int main(){ int x, y; cin >> n >> m, build(1, n); for(int i = 1; i <= m; i++){ cin >> x >> y; k[x] = (double)y*1.0/x; update(x, x, y); cout << t[1].sum << endl; } return 0;}