BZOJ2957: 楼房重建【线段树】

2957: 楼房重建

【题目描述】

传送门

【题解】

这题是一道线段树维护单调区间的经典问题。
计下最大值MaxH,和当前区间内的上升序列长度Ans。
对于修改(x,y),有影响的肯定在x之后的一段。
所以我们每次就只要对右子树修改Ans就可以了。
对于右子树如何修改呢?
如果右子树的左子树MaxH小于左子树的MaxH,那么肯定没有贡献,所以只需要递归右子树就可以了。
否则递归左子树,因为当前的修改对右子树没有影响,最后加上右子树的答案就可以了。

代码如下

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100005;
struct Tree{
    int Ans;double MaxH;
}Tre[MAXN<<2];
int n,m;
int Change(int rt,int L,int R,double H){
    if(L==R) return Tre[rt].MaxH>H;
    int mid=(R+L)>>1;
    if(Tre[rt<<1].MaxH<=H) return Change(rt<<1|1,mid+1,R,H);
    else return Change(rt<<1,L,mid,H)+Tre[rt].Ans-Tre[rt<<1].Ans;
}
void Insert(int rt,int L,int R,int p,double H){
    if(L==R){Tre[rt].Ans=1;Tre[rt].MaxH=H;return;}
    int mid=(R+L)>>1;
    if(p<=mid)Insert(rt<<1,L,mid,p,H);
    else Insert(rt<<1|1,mid+1,R,p,H);
    Tre[rt].MaxH=max(Tre[rt<<1].MaxH,Tre[rt<<1|1].MaxH);
    Tre[rt].Ans=Tre[rt<<1].Ans+Change(rt<<1|1,mid+1,R,Tre[rt<<1].MaxH);
}
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret*10+ch-48);
    return f?ret:-ret;
}
int main(){
    n=read();m=read();
    while(m--){
        int x=read(),y=read();
        Insert(1,1,n,x,(double)y/x);
        printf("%d\n",Tre[1].Ans);
    }
    return 0;
}

发表评论

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

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部