BZOJ2957 楼房重建

线段树

Lydsy

如果 $x$ 的楼顶连到原点的线的斜率大于等于 $y$ 的楼顶连到原点的线的斜率，就说明 $x$ 挡住了 $y$ 。那么我们就用线段树来维护每个区间不考虑区间外的楼的答案以及最大的斜率，现在来考虑一下如何合并两个区间（子树）的答案。首先，左子树维护的区间的答案肯定不会被影响，但是右边的区间可能会有一部分被阻挡，所以我们直接递归处理一下右区间的答案。这样子单次修改+查询的复杂度是 $\mathcal O(\log ^ 2 n)$ 的。

#include <iostream>
#include <cstdio>
int n, m;
struct Segtree {
    Segtree *ch[2];
    int ansv;
    double maxv;
    Segtree() {
        maxv = ansv = 0;
        ch[0] = ch[1] = NULL;
    }
} *root;
inline int read() {
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
void Build(Segtree *&o, int l, int r) {
    o = new Segtree;
    if(l == r) return;
    int mid = (l + r) >> 1;
    Build(o -> ch[0], l, mid);
    Build(o -> ch[1], mid + 1, r);
}
int calc(Segtree *o, int l, int r, double v) {
    if(l == r) return o -> maxv > v;
    int mid = (l + r) >> 1;
    if(o -> ch[0] -> maxv <= v) return calc(o -> ch[1], mid + 1, r, v);
    else return calc(o -> ch[0], l, mid, v) + o -> ansv - o -> ch[0] -> ansv; 
}
void Modify(Segtree *o, int l, int r, int w, double k) {
    if(l == r) {
        o -> maxv = k;
        o -> ansv = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if(w <= mid) Modify(o -> ch[0], l, mid, w, k);
    else Modify(o -> ch[1], mid + 1, r, w, k);
    o -> maxv = std::max(o -> ch[0] -> maxv, o -> ch[1] -> maxv);
    o -> ansv = o -> ch[0] -> ansv + calc(o -> ch[1], mid + 1, r, o -> ch[0] -> maxv);
}
int main() {
    n = read();
    m = read();
    Build(root, 1, n);
    while(m--) {
        int x = read(), y = read();
        Modify(root, 1, n, x, double(y) / double(x));
        printf("%d\n", root -> ansv);
    }
    return 0;
}