P4198 楼房重建

---

集中写博客= =

首先把高度变成斜率

然后就比较玄学了，首先用线段树维护一个区间的斜率最大值，和只看这个区间时能看见的楼房个数ans

然后更新时先更新max，再处理神奇的ans

如果max[ls]>=max[rs]，那么右区间都被遮住了可以不考虑，答案是ans[ls]

否则考虑右区间，写一个函数calc(x,h)表示x区间的最左边有一栋高h的楼房，此时x区间能看见几栋楼房，所以这时答案是ans[ls]+calc(rs,max[ls])

然后下面是calc(x,h)的实现

如果现在max[rs.ls]<=max[ls]，那么只需递归考虑右区间的右区间,calc(rs,h)

最后就是max[rs.ls]>max[ls]，那么右边能看到的依然能看到，只需要重新考虑左边区间,ans[x]-ans[ls]+calc(ls,h)

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il int gi(){

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-')f=-1;

        ch=getchar();

    }

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

    return x*f;

}

int ans[100010<<2];

double max[100010<<2];

#define mid ((l+r)>>1)

#define ls (x<<1)

#define rs (x<<1|1)

il double calc(int x,int l,int r,double&h){

    if(l==r)return max[x]>h;

    if(max[ls]<=h)return calc(rs,mid+1,r,h);

    else return ans[x]-ans[ls]+calc(ls,l,mid,h);

}

il vd update(int x,int l,int r,int&p,double&h){

    if(l==r){max[x]=h;ans[x]=1;return;}

    if(p<=mid)update(ls,l,mid,p,h);

    else update(rs,mid+1,r,p,h);

    max[x]=std::max(max[ls],max[rs]);

    if(max[rs]<=max[ls])ans[x]=ans[ls];

    else ans[x]=ans[ls]+calc(rs,mid+1,r,max[ls]);

}

int main(){

    int n=gi(),m=gi();

    for(int i=1;i<=m;++i){

        int x=gi();

        double y=gi()*1.00/x;

        update(1,1,n,x,y);

        printf("%d\n",ans[1]);

    }

    return 0;

}