问题描述

小A在平面上 $(0,0)$ 点的位置,第 $i$ 栋楼房可以用一条连接 $(i,0)$ 和 $(i,H_i)$ 的线段表示,其中 $Hi$为第 $i$ 栋楼房的高度。如果这栋楼房上任何一个高度大于 $0$ 的点与 $(0,0)$ 的连线没有与之前的线段相交,那么这栋楼房就被认为是可见的。

施工队的建造总共进行了 $M$ 天。初始时,所有楼房都还没有开始建造,它们的高度均为 $0$。在第 $i$ 天,建筑队将会将横坐标为 $X_i$ 的房屋的高度变为 $Y_i$ (高度可以比原来大—修建,也可以比原来小—拆除,甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后,他能看到多少栋楼房?

输入

第一行两个正整数 $N,M$

接下来 $M$ 行,每行两个正整数 $X_i,Y_i$

输出

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

思路

如果从分块的角度入手,思路会比较简单。对于每一个块维护一个栈,栈内存放这一个块中能够看见的楼房(不考虑该块外部的楼房)。对于修改操作,直接将所在块的栈删去重构;对于询问操作,以前面的最大值在每一个栈中二分。当每一块大小为 $\sqrt{n \log size}$ 时,复杂度为 $n\sqrt{n\log size}$。

其实这个也可以用线段树维护。每一个节点维护区间最大值和该区间中的答案,考虑如果将两个区间的答案合并。左区间的答案肯定要全部算上,而右区间的答案就与左区间最大值有关,我们设这个值为 $val$。如果右区间的左子区间的最大值小于 $val$,显然这个区间的答案为 $0$,我们只需要递归计算右区间的答案;如果右区间的左子区间的最大值大于 $val$,那么原先右区间的贡献不会变,我们只需要递归计算左区间的答案。因此对于每一个区间都需要向下再递归 $\log n$ 层合并答案,那么总复杂度就是 $O(n\log^2 n)$。

代码

分块:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
#define P 998244353
#define INF 0x3f3f3f3f
#define eps 1e-11
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, siz, bel[MAXN], top[400];
LD h[MAXN], sta[400][405];

int main()
{
    scanf("%d%d", &n, &m);
    siz=400;
    for(rint i=1; i<=n; ++i) bel[i]=(i-1)/siz+1;
    for(rint i=1, x, y; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        int pos=bel[x], ans=0;
        top[pos]=0, h[x]=1.0*y/x;
        for(rint j=(pos-1)*siz+1; j<=pos*siz; ++j)
            if(h[j]>sta[pos][top[pos]]) sta[pos][++top[pos]]=h[j];
        LD maxn=0;
        /*
        for(rint j=1; j<=bel[n]; ++j)
        {
            printf("%d:", j);
            for(rint k=1; k<=top[j]; ++k) printf("%lf ", sta[j][k]);
            printf("\n");
        }
        */
        for(rint j=1; j<=bel[n]; ++j)
        {
            int l=1, r=top[j], p=top[j]+1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(sta[j][mid]>maxn+eps) p=mid, r=mid-1;
                else l=mid+1;
            }
            ans+=top[j]-p+1;
            maxn=max(maxn, sta[j][top[j]]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

线段树:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
#define P 998244353
#define INF 0x3f3f3f3f
#define eps 1e-11
#define rint register int
#define LL long long
#define LD long double
#define ls (root<<1)
#define rs (root<<1|1)
#define mid ((l+r)>>1)
using namespace std;

int n, m, sum[MAXN*4];
LD maxn[MAXN*4];

int cal(int root, int l, int r, LD k)
{
    if(l==r) return maxn[root]>k;
    if(maxn[ls]>k) return cal(ls, l, mid, k)+sum[root]-sum[ls];
    else return cal(rs, mid+1, r, k);
}

void update(int root, int l, int r, int x, LD k)
{
    if(l==r)
    {
        sum[root]=1, maxn[root]=k;
        return;
    }
    if(x<=mid) update(ls, l, mid, x, k);
    else update(rs, mid+1, r, x, k);
    maxn[root]=max(maxn[ls], maxn[rs]);
    sum[root]=sum[ls]+cal(rs, mid+1, r, maxn[ls]);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(rint i=1, x, y; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        update(1, 1, n, x, 1.0*y/x);
        printf("%d\n", sum[1]);
    }
    return 0;
}

1 对 “BZOJ2957 楼房重建 [分块/线段树]”的想法;

发表评论

邮箱地址不会被公开。 必填项已用*标注