BZOJ2957 楼房重建 <线段树>

Problem

楼房重建

Description

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

Input

第一行两个正整数。
接下来行，每行两个正整数。

Output

行，第行一个整数表示第天过后能看到的楼房有多少栋。

Sample Input

3 4
2 4
3 6
1 1000000000
1 1

Sample Output

HINT

, ,

Source

中国国家队清华集训第一天

标签：线段树

Solution

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

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

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

现在考虑如何实现。记当前区间的两个子区间的和分别为。

当时，只会在右区间有数被选中，于是答案等于
当时，在左区间和右区间都会有数被选中，但注意到此时左区间的是不会改变的，意味着普通情况下（没有的约束），右区间选的数是不会有变化的，于是递归询问左区间，即答案等于

综上，在修改后重新合并子区间信息，并递归调用即可。
由于会修改层的信息，而每次都会调用再递归层，所以总复杂度为。

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;
}