每个楼房,还有单点修改操作。简单的想到用线段树来维护信息。

显然线段树只需要维护 y/x 即可,对于每一个楼房,能看见的条件就是前面楼房的 y/x 的严格小于当前楼房的 y/x。

线段树的区间修改不再赘述。

那么怎么维护可以看到的楼房数呢?

考虑在线段树的每一个节点上用一个变量 sum 来表示从这个节点的左端点向右端点看时能看到多少楼房。

假设现在有一区间:1,5,8,0,7,9。维护这个区间信息的节点编号为 x

x 的左儿子维护的区间是 1,5,8,从 18 看可以看到三个楼房,故 x 的左儿子的 sum 的值为 3

x 的右儿子维护的区间是 0,7,9,从 09 看也可以看到三个楼房,故 x 的右儿子的 sum 的值也为 3

难道 x 的 sum 值也为 3+3=6?错!

这显然是不能加在一起的,x 的 sum 的值为 4。

为什么会错呢?因为 x 的右儿子的观察视角不是从 1 开始的,是从 0 开始的。

显然 0 被前面的楼房挡住了。

首先考虑每个线段树节点在维护一个 mxmx 代表这个节点所代表的区间中所有的楼房中最高的高度。

上传时,由于两个儿子的 sum 值是已经处理好的,而左儿子的视角是跟 x 的视角一样的 (对于上面的例子来说都是 1),可以直接上传,即 sum(x)+=sum(l(x))

对于右儿子,考虑递归处理右儿子的区间,递归时带一个 Mx 变量表示 x 的左儿子 mx(右儿子再左儿子后面,原因下面解释),递归函数的返回值是当前处理区间可以被看到的楼房数 (从 x 的视角看)

对于现在处理的每一个区间:

  • 如果这个区间的最高的楼房的高度都 Mx(可以看到),那么 return 当前区间维护的 sum 值。
  • 如果这个区间只代表一个楼房,直接判断其能否被看到即可。
  • 对于剩下的情况,递归儿子,分两种情况讨论:
    • 如果左儿子的最高的楼房小于 Mx(不能对答案有任何贡献),直接递归右儿子。
    • 否则,递归左儿子,右儿子能看到的楼房个数为当前区间 sum-左儿子 sum 即可,(应为下面已经更新好了,只需要直接调用就好了。)
Code(文中的 sum 用 l 代替):
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define lson x<<1
#define rson x<<1|1
using namespace std;
const int N=1e5+2;
struct Node {
    double mx;int l;
    #define m(x) tree[x].mx
    #define l(x) tree[x].l
} tree[N<<2];
int n,m;
double val[N];
inline void pushup_max(int x) {
    m(x)=max(m(x<<1),m(x<<1|1));
}
inline int pushup_sum(double Mx,int x,int l,int r) {
    if(m(x)<Mx)return 0;
    if(val[l]>Mx)return l(x);
    if(l==r)return val[l]>Mx;
    int mid=(l+r)>>1;
    if(m(lson)<=Mx)return pushup_sum(Mx,rson,mid+1,r);
    else return pushup_sum(Mx,lson,l,mid)+l(x)-l(lson);
}
inline void change(int x,int l,int r,int pos,int value) {
    if(l==r&&l==pos){m(x)=(double)value/pos;l(x)=1;return;}
    int mid=(l+r)>>1;
    if(pos<=mid)change(lson,l,mid,pos,value);
    else if(pos>mid)change(rson,mid+1,r,pos,value);
    pushup_max(x);
    l(x)=l(lson)+pushup_sum(m(lson),rson,mid+1,r);
}
int main() {
    scanf("%d%d",&n,&m);
    for(register int x,y,i=1; i<=m; ++i) {
        scanf("%d%d",&x,&y);
        val[x]=(double)y/x;
        change(1,1,n,x,y);
        printf("%d\n",l(1));
    }
    return 0;
}
分类: 文章

Qiuly

QAQ

1 条评论

Remmina · 2019年1月6日 2:54 下午

恭喜大佬喜提权限(以后您发布文章不需要审核啦)

发表评论

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