BZOJ 2957 楼房重建 解题报告

2957: 楼房重建

Time Limit: 10 Sec  Memory Limit: 256 MB

Description

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

Input

　　第一行两个正整数N,M
　　接下来M行，每行两个正整数Xi,Yi

Output

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

Sample Input

3 4

2 4

3 6

1 1000000000

1 1

Sample Output

1

1

1

2

数据约定

　　对于所有的数据1<=Xi<=N，1<=Yi<=10^9

N,M<=100000

Solution

       看到这题，首先便会想到将高度转换成斜率，即$k_i=\frac{y_i}{x_i}$，能看到的房屋的斜率可以构成一个严格递增序列。为了方便讲解，我们引入连续严格递增子序列的概念。对于序列$ \{a_n\}$，从$a_1$开始向$a_n$遍历，首先将$a_1$加入子序列$\{b_n\}$，也就是$b_1=a_1$；继续遍历，当遇到第一个数字$a_i$满足$a_i>b_1$时，将$a_i$加入$\{b_n\}$；继续遍历，将$a_i$与$b_2$比较，以此类推，知道遍历完$\{a_n\}$序列。这样得到的子序列$\{b_n\}$称为序列$ \{a_n\}$的连续严格递增子序列。比如数列{1,0,4,5,2,6,15,15,7}的连续严格递增子序列为{1,4,5,6,15}。读者应该已经看出，本题正是要求动态计算$\{k_n\}$的连续严格递增子序列的长度。

       考虑使用线段树。

       设cnt为一个节点所对应区间的连续严格递增子序列的长度，tree[1].cnt就是询问的答案。现在问题只剩下区间的合并了。假设待合并的两个区间为$\lbrack l,mid\rbrack$和$\lbrack mid+1,r\rbrack$，对应的节点为tree[now<<1]和tree[now<<1|1]，区间$\lbrack l,mid\rbrack$的连续严格递增子序列一定还是合并后的区间$\lbrack l,r\rbrack$的连续严格递增子序列的前半部分，而序列的后半部分来自区间$\lbrack mid+1,r\rbrack$，但它的长度无法直接维护。不过可以肯定，它们都大于$\mbox{max}_{i=l}^{mid}k_i$（这样写可能不是很规范）。设函数upper_calc(double lowest,int now)用于计算节点tree[now]中大于lowest的数字组成的连续严格递增子序列长度，有tree[now].cnt=tree[now<<1].cnt + upper_calc(tree[now<<1].maxn,now<<1|1)，这里的maxn是区间最大值。

       upper_calc函数的实现：

int upper_calc(long double lowest, int now)

{

    //当前节点所对应的区间的所有数都小于等于lowest

    if (tree[now].maxn <= lowest)return 0;

    //当前节点是叶子节点

    if (tree[now].l == tree[now].r)return tree[now].maxn>lowest;

    //当前当前节点的左子节点所对应的所有数都小于等于lowest

    if (tree[now << 1].maxn <= lowest)return upper_calc(lowest, now << 1 | 1);

    else return upper_calc(lowest, now << 1) + upper_calc(tree[now << 1].maxn, now << 1 | 1);

}

看起来分情况讨论地很到位，但由于最后一种情况的存在，查询的复杂度是$O(n\log n)$显然不能接受。改进的方法就是去掉最后一种情况的一次递归。upper_calc(lowest, now << 1)已经无法继续改变了，但upper_calc(tree[now << 1].maxn, now << 1 | 1)可以改进。既然左区间的最大值已经大于lowest了，原区间的连续严格递增子序列后半部分也一定都是大于lowest的，直接相减便可以得到答案，即tree[now].cnt - tree[now << 1].cnt。注意，不能用tree[now << 1 | 1].cnt代替，原因非常简单但不容易解释，希望读者自行思考。其实还可以维护区间最小值进一步细分情况，以减小大$O$记号中隐藏的常数，但着实没有必要。

修改套查询的线段树比较少见，编码时要注意修改中的查询必须在已经修改完成的部分进行，否则就会出错。

时间复杂度：$O(n\log^2n)$。

Code

#include <iostream>

#include <stdio.h>

#include <algorithm>

using namespace std;

inline void read(int &x)

{

    x = 0; char ch = getchar(); bool f = 0;

    while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }

    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }

    if (f)x = -x;

}

inline void read(long long &x)

{

    x = 0; char ch = getchar(); bool f = 0;

    while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }

    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }

    if (f)x = -x;

}

struct

{

    int l, r;

    long double maxn;

    int cnt;

}tree[400005];

void build(int l, int r, int now = 1)

{

    tree[now].l = l, tree[now].r = r;

    tree[now].maxn = 0; tree[now].cnt = 0;

    if (l == r)return;

    int mid = l + r >> 1;

    build(l, mid, now << 1);

    build(mid + 1, r, now << 1 | 1);

}

int upper_calc(long double lowest, int now)

{

    if (tree[now].maxn <= lowest)return 0;

    if (tree[now].l == tree[now].r)return tree[now].maxn>lowest;

    if (tree[now << 1].maxn <= lowest)return upper_calc(lowest, now << 1 | 1);

    else return upper_calc(lowest, now << 1) + tree[now].cnt - tree[now << 1].cnt;

}

void updata(int p, long double x, int now = 1)

{

    if (tree[now].l == tree[now].r)

    {

        tree[now].maxn = x;

        if (tree[now].maxn>0)tree[now].cnt = 1;

        return;

    }

    int mid = tree[now].l + tree[now].r >> 1;

    if (p <= mid)updata(p, x, now << 1);

    else updata(p, x, now << 1 | 1);

    tree[now].maxn = max(tree[now << 1].maxn, tree[now << 1 | 1].maxn);

    tree[now].cnt = tree[now << 1].cnt + upper_calc(tree[now << 1].maxn, now << 1 | 1);

}

int main()

{

    int n, m;

    read(n); read(m);

    build(0, n + 1);

    while (m--)

    {

        int x, y;

        read(x); read(y);

        updata(x, (long double)(y) / (long double)(x));

        printf("%d\n", tree[1].cnt);

    }

    return 0;

}