BZOJ2957 楼房重建 <线段树>

Problem

楼房重建

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

$\mathrm{小A}$的楼房外有一大片施工工地，工地上有$N$栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
为了简化问题，我们考虑这些事件发生在一个二维平面上。$\mathrm{小A}$在平面上$(0,0)$点的位置，第$i$栋楼房可以用一条连接$(i,0)$和$(i,H_i)$的线段表示，其中$H_i$为第$i$栋楼房的高度。如果这栋楼房上任何一个高度大于$0$的点与$(0,0)$的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
施工队的建造总共进行了$M$天。初始时，所有楼房都还没有开始建造，它们的高度均为$0$。在第$i$天，建筑队将会将横坐标为$X_i$的房屋的高度变为$Y_i$(高度可以比原来大——修建，也可以比原来小——拆除，甚至可以保持不变——建筑队这天什么事也没做)。请你帮$\mathrm{小A}$数数每天在建筑队完工之后，他能看到多少栋楼房？

Input

第一行两个正整数$N,M$。
接下来$M$行，每行两个正整数$X_i,Y_i$。

Output

$M$行，第$i$行一个整数表示第$i$天过后$\mathrm{小A}$能看到的楼房有多少栋。

Sample Input

3 4
2 4
3 6
1 1000000000
1 1

Sample Output

1
1
1
2

HINT

$N,M\le10^5$, $1\le X_i\le N$, $1\le Y_i\le10^9$

Source

中国国家队清华集训$2012-2013$第一天

标签：线段树

Solution

线段树维护极长上升序列简化版。

将每栋楼房的斜率$\frac{y}{x}$作为权值，则问题转化为单点修改，求全局极长上升序列长度。

对于线段树上的每个结点所代表的区间$[s,t]$，我们记录其极长上升序列的最后一个数$mx$和长度$cnt$。考虑合并子区间$[s,mid]$和$[mid+1,t]$来得到$[s,t]$的$mx$和$cnt$。左区间一定会取完，于是只考虑右区间从左区间的$mx$开始取时的信息。设$calc(s,t,x)$为区间$[s,t]$从$x$值开始取的极长上升序列长度，那么当前区间的$cnt$等于左区间的$cnt$加$calc(mid+1,t,左区间mx)$。

现在考虑如何实现$calc$。记当前区间$[s,t]$的两个子区间的$mx$和$cnt$分别为$mx_l,cnt_l,mx_r,cnt_r$。

• 当$mx_l\le x$时，只会在右区间有数被选中，于是答案等于$calc(mid+1,t,x)$
• 当$mx_l>x$时，在左区间和右区间都会有数被选中，但注意到此时左区间的$mx_l$是不会改变的，意味着普通情况下（没有$x$的约束），右区间选的数是不会有变化的，于是递归询问左区间，即答案等于$calc(s,mid,x)+cnt-cnt_l$

综上，在修改后重新合并子区间信息，并递归调用$calc$即可。
由于会修改$\log{n}$层的信息，而每次都会调用$calc$再递归$\log{n}$层，所以总复杂度为$O(n\log^2{n})$。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define mid ((s+t)>>1)
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int tr[MAX_N<<2]; dnt mx[MAX_N<<2];
int calc(int v, int s, int t, dnt x) {
    if (s == t) return mx[v] > x;
    if (mx[v<<1] <= x) return calc(v<<1|1, mid+1, t, x);
    return calc(v<<1, s, mid, x)+tr[v]-tr[v<<1];
}
void modify(int v, int s, int t, int p, dnt x) {
    if (s == t) {tr[v] = 1, mx[v] = x; return;}
    if (p <= mid) modify(v<<1, s, mid, p, x);
    if (p >= mid+1) modify(v<<1|1, mid+1, t, p, x);
    tr[v] = tr[v<<1]+calc(v<<1|1, mid+1, t, mx[v<<1]);
    mx[v] = max(mx[v<<1], mx[v<<1|1]);
}
int main() {
    int n, m; read(n), read(m);
    while (m--) {
        int x, y; read(x), read(y);
        modify(1, 1, n, x, (dnt)y/x);
        printf("%d\n", tr[1]);
    }
    return 0;
}