当前位置：首页 > news >正文

[bzoj2957]楼房重建

news 来源：原创 2024/4/26 0:38:14

来自FallDream的博客，未经允许，请勿转载，谢谢。

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

n,m<=10^5

省队集训讲到了这东西是个经典模型我听的一脸懵赶紧补一发

简单点说就是要动态维护上升子序列长度

考虑线段树，每个线段记录只考虑这个区间的答案顺便记下区间最大值

考虑合并

如果右区间最大值小等于左区间，那么显然右区间不会贡献答案。

不然的话考虑右区间的两个子区间L,R在左区间的限制下能产生的贡献

如果右区间的左区间L的最大值也小等于左区间的最大值，那么直接递归区间R考虑即可。

不然的话，递归考虑区间L，这时候左区间相当于对区间R没有限制，所以这时候区间R贡献的答案是右区间的答案减去区间L的答案。

复杂度显然是nlog^2n的

#include<iostream>
#include<cstdio>
#define MN 100000
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
struct{int l,r,ans;double mx;}T[MN*4+5];
int n,m;

int Calc(int x,double v)
{
    if(T[x].l==T[x].r) return T[x].mx>v;
    if(T[x<<1].mx>v) return Calc(x<<1,v)+T[x].ans-T[x<<1].ans;
    else return Calc(x<<1|1,v);
}

void update(int x)
{
    int l=x<<1,r=x<<1|1;
    T[x].ans=T[l].ans;
    T[x].mx=max(T[l].mx,T[r].mx);
    if(T[r].mx>T[l].mx) T[x].ans+=Calc(r,T[l].mx);
}

void Build(int x,int l,int r)
{
    T[x].mx=0;T[x].ans=1;
    if((T[x].l=l)==(T[x].r=r))return;
    int mid=l+r>>1;
    Build(x<<1,l,mid);
    Build(x<<1|1,mid+1,r);
}

void Modify(int x,int k,double v)
{
    if(T[x].l==T[x].r){T[x].mx=v;return;}
    int mid=T[x].l+T[x].r>>1;
    Modify(x<<1|(k>mid),k,v);
    update(x);
}

int main()
{
    n=read();m=read();
    Build(1,0,n);
    for(int i=1,j;i<=m;++i)
        j=read(),Modify(1,j,(double)read()/j),printf("%d\n",T[1].ans-1);
    return 0;
}