题解：P4198 楼房重建

· · 题解

P4198 楼房重建

题目描述

有 N 栋正在坐标轴上修建的楼房和 M 个时间节点，已知每个时间节点上会有一栋楼的高度发生变化。 问对于每个时间节点，小 A 在原点可以看到几栋楼房（基于日常生活理解）。

思路

第 i 栋楼房最高点到原点连线的斜率记作 k_i，不难发现：
如果想要看到第 i 栋楼房，则需满足 k_{i-1}< k_i。
那么我们需要求的就是斜率 k 的最长上升子序列长度，且应满足：

  2. 若 k_{i-1}<k_i 且选了 k_{i-1}，则 k_i 必须选。

考虑如何维护状态。
由于 zkw 线段树的性质，修改时直接改叶子节点即可，所以重点考虑如何合并信息。

显然地，对于一个区间，我们所选的起始楼房越靠左侧越好。所以在合并时，左区间答案始终不变，对右区间进行二分查找第一个大于左区间最大值的值。

所以我们需要记录每个区间的 k 的最大值，并且在查找右区间的过程中：

  1. 如果右区间最大值都比左区间最大值小了，那右区间对答案没有贡献；
  2. 如果右区间对答案有贡献，就继续向下查找；
  3. 当找到叶子节点时，看节点值是否大于左区间最大值。

基于 zkw 线段树的性质，其父子节点关系严格确定，所以我们不需要二次递归进行求解，只要循环模拟我们刚才所说的二分答案过程即可。

代码

//单点修改、区间查询问题都可以使用 zkw 线段树维护
//push_up过程直接当成循环模拟
//代码简洁、常数优于递归线段树，可以有效避免卡常
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<vector>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T&x){
    int w=0;x=0;
    char ch = getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9'){
        x = (x<<1)+(x<<3)+(ch^48);
        ch = getchar();
    }
    if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
    read(t);read(args...);
}
const int N = 1e5+10;
int n,m;
int P = 1,DEP = 0;
double mx[N*3];int len[N*3];//开3倍空间
inline int query(int l,double k,int dep){
    int tl = l;
    int res = 0;
    while(dep<DEP){
        if(mx[l]<=k) break;//剪枝：右区间最大值比左区间的小
        l = l<<1|(mx[l<<1]<=k);//模拟选取左右子树过程
        dep++; 
    }
    if(dep==DEP) res = (mx[l]>k);//叶子节点
    while(l!=tl){
        if(~l&1) l>>=1,res+=len[l]-len[l<<1];//累加答案
        else l>>=1;
    }
    return res;
}
inline void update(int l,double k){
    l += P;
    //直接对叶子节点进行更新
    len[l] = 1;mx[l] = k;
    int dep = DEP;
    //从下到上维护父子结点关系
    for(l>>=1,--dep; l ;l>>=1,--dep){
        mx[l] = max(mx[l<<1],mx[l<<1|1]);
        len[l] = len[l<<1]+query(l<<1|1,mx[l<<1],dep+1);
    }
}
int main(){
    read(n,m);
    while(P<=n+1) P<<=1,++DEP;//求虚点值和整棵树的深度
    int l,r;
    while(m--){
        read(l,r);
        update(l,(1.0*r)/(1.0*l));
        printf("%d\n",len[1]);//输出根节点信息
    }
    return 0;
}