P4198 楼房重建

[Luogu4198]

原题解

用线段树维护有关单调栈的问题

不要pushdown,但是pushup的时候需要特别注意.细节见代码

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f*x;
}

const int MAXN=1e5+5;

double a[MAXN];
int n,m;

struct SGT{
    int len[MAXN<<2];
    double mx[MAXN<<2];
#define ls (rt<<1)
#define rs (rt<<1|1)
    inline void pushup1(int rt){
        mx[rt]=max(mx[ls],mx[rs]);
    }
    inline int pushup2(int rt,int l,int r,double tmp){
        if(tmp>=mx[rt]) return 0;//这里必须有一个限制的变量
        if(a[l]>tmp) return len[rt];
        if(l==r) return len[l]>tmp;//分类讨论清楚:三种情况
        int mid=(l+r)>>1;
        if(mx[ls]<=tmp) return pushup2(rs,mid+1,r,tmp);
        else return pushup2(ls,l,mid,tmp)+len[rt]-len[ls];//补上右边还能继续递增的
    }
    inline void modify(int rt,int l,int r,int x,int y){
        if(l==r&&l==x){
            mx[rt]=(double)y/x;//这里不要改a[rt]...
            len[rt]=1;
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid) modify(ls,l,mid,x,y);
        else modify(rs,mid+1,r,x,y);
        pushup1(rt);
        len[rt]=len[ls]+pushup2(rs,mid+1,r,mx[ls]);
    }
#undef ls
#undef rs
}T;

int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        a[x]=(double)y/x;
        T.modify(1,1,n,x,y);
        printf("%d\n",T.len[1]);
    }
}

P4198 楼房重建

原文：https://www.cnblogs.com/lizehon/p/10573945.html