M_sea

洛谷4198 楼房重建
LuoguBZOJ分析很神仙的线段树。每个节点维护区间的最大斜率 $s$ ,和只考虑这个区间的答案 $ans$ 。...
扫描右侧二维码阅读全文
07
2019/03

洛谷4198 楼房重建

Luogu

BZOJ

分析

很神仙的线段树。

每个节点维护区间的最大斜率 $s$ ,和只考虑这个区间的答案 $ans$ 。

仍然考虑怎么合并两个区间。

显然左区间的 $ans$ 包括的楼房全都能看到,重点考虑右区间的贡献。

显然,如果右区间的 $s$ 小于左区间的 $s$ ,那么右区间贡献为 $0$ 。

否则,把右区间平均分成 $l$ 和 $r$ 两部分。

如果 $l$ 的 $s$ 大于左区间的 $s$ ,那么直接加上 $r$ 的贡献,然后递归处理 $l$。

否则直接递归处理 $r$ 。

上面这么说比较抽象,可以结合代码理解一下。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct segment_tree {
    struct node { double s; int ans; } t[N<<2];

#define ls (o<<1)
#define rs (o<<1|1)
    
    inline int query(int o,int l,int r,double k) {
        if (t[o].s<=k) return 0;
        if (l==r) return 1;
        int mid=(l+r)>>1;
        if (t[ls].s>=k) return query(ls,l,mid,k)+t[o].ans-t[ls].ans;
        else return query(rs,mid+1,r,k);
    }

    inline void pushup(int o,int l,int r) {
        int mid=(l+r)>>1;
        t[o].s=max(t[ls].s,t[rs].s);
        t[o].ans=t[ls].ans+query(rs,mid+1,r,t[ls].s);
    }
    
    inline void modify(int o,int l,int r,int p,int v) {
        if (l==r) { t[o].s=1.0*v/p,t[o].ans=1; return; }
        int mid=(l+r)>>1;
        if (p<=mid) modify(ls,l,mid,p,v);
        else modify(rs,mid+1,r,p,v);
        pushup(o,l,r);
    }
} T;

int main() {
    int n=read(),m=read();
    while (m--) {
        int x=read(),y=read();
        T.modify(1,1,n,x,y);
        printf("%d\n",T.t[1].ans);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 07 PM

发表评论