526互联

P4198 楼房重建

发布时间 2023-10-26 21:05:54作者: lava__44

P4198 楼房重建(RE:题解再改造!!)

码

#include<bits/stdc++.h>
#define MAXN 2000010
using namespace std;
int n,m;
int x[MAXN],y[MAXN],ans[MAXN];
double K[MAXN];
int query(int p,int l,int r,double maxn){
    if(K[p]<=maxn) return 0;
    if(l==r) return K[p]>maxn;
    else if(K[p*2]<=maxn) return query(p*2+1,((l+r)>>1)+1,r,maxn);
    return query(p*2,l,(l+r)>>1,maxn)+ans[p]-ans[p*2];
}
void Change(int p,int l,int r,int limit,double v){
    if(l==limit&&limit==r){
        ans[p]=1,K[p]=v;
        return ;
    }
    int mid=(l+r)>>1;
    if(limit<=mid) Change(p*2,l,mid,limit,v);
    else Change(p*2+1,mid+1,r,limit,v);
    K[p]=max(K[p*2],K[p*2+1]);
    ans[p]=ans[p*2]+query(p*2+1,mid+1,r,K[p*2]);
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x[i]>>y[i];
        Change(1,1,n,x[i],(double)y[i]/x[i]);
        cout<<ans[1]<<"\n";
    }
    return 0;
}

正文

  1. 对于某栋楼的高度的修改:单点修改

  2. 对于从零开始的可视个数:区间查询

所以可以将此题转化成线段树

每一个叶子节点:最大值为该点斜率,可视个数为1

仅用检查是否大于查询的maxn(斜率值)即可

if(l==r) return K[p]>maxn;

右区间:

  1. 右区间的左子区间的最大值

    1. 小于左区间最大值:右的左子区间一定不可见,递归右区间的左子节点.

    2. 大于左区间最大值:加上右区间答案,递归右区间的左子区间.右区间的左子区间可能覆盖右子区间

赞美一些动开线段树

ans[p]=ans[p*2]+query(p*2+1,mid+1,r,ma[p*2]);

区间答案即为左区间的答案+右区间斜率合法的所有楼房数.

对于每一个区间存储最大值可以使query的效率大大优化,玄学优化

致谢

Nemlit大佬%%%