(luogu4198) 楼房重建

原题链接

思路:

首先，由题意可以看出， 需要寻找的是从第一个有值的点开始的最长的斜率严格递增的序列长度.

考虑使用线段树解决，询问的答案即为根节点的值，同时修改只有单点修改， 所以只需要考虑区间的合并.

至于合并，假设每个区间都储存了一个序列:

该序列是只考虑该区间时的最长递增序列.

首先左区间序列里的所有值都是可见的， 而右区间只有比左区间最大值更大的值才可见. 这些值在右区间序列是连续的.

若右区间长度为 1 则直接判断返回即可， 否则将右区间分为两段 (称为左右区间和右右区间). 然后分类讨论:

• 若左右区间的最大值小于等于左区间的最大值， 说明可见的分界点在右右区间中，递归到右右区间寻找.

• 否则说明分界点在左右区间中，右右区间中在右区间序列中的值均可见， 统计上该部分值后递归到左区间寻找.

这样便在 O (log n) 的时间内实现了区间的合并.

代码:

#include <cstdio>
#include <cctype>
#include<algorithm>
using namespace std;
const int Mn(100500);
template<typename T> void qrd(T& x) {
    x = 0;
    int c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c - '0';
        c = getchar();
    }
}
template<typename T, typename... Ts> void qrd(T& x,Ts&... xs) {
    qrd(x); qrd(xs...);
}

int n,m;
struct Td { //线段树节点
    double mx;  //最大斜率
    int len;    //最大序列长度
} t[Mn<<2];
int calc(int p,int l,int r,double qx) { //计算右区间贡献
    if(l==r) {
        return (t[p].mx>qx);
    }
    int mid((l+r)/2);
    if(t[p<<1].mx<=qx) {    //情况1
        return calc(p<<1|1,mid+1,r,qx); //递归右区间计算
    } else {
        return calc(p<<1,l,mid,qx) + t[p].len - t[p<<1].len;    //递归左区间计算并加上右区间贡献(注意不是t[p<<1|1].len)
    }
}
void mtn(int p,int l,int r) {   //合并
    t[p].mx = max(t[p<<1].mx, t[p<<1|1].mx);
    int mid((l+r)/2);
    int rl = calc(p<<1|1,mid+1,r,t[p<<1].mx);   //计算右区间可见数量
    t[p].len = t[p<<1].len + rl;
}
void mdf(int mp,double mx,int p=1,int l=1,int r=n) {    //线段树修改
    if(l==r) {
        t[p] = {mx,1};
        return;
    }
    int mid((l+r)/2);
    if(mp<=mid) {
        mdf(mp,mx,p<<1,l,mid);
    } else {
        mdf(mp,mx,p<<1|1,mid+1,r);
    }
    mtn(p,l,r);
}

int main() {
    qrd(n,m);
    while(m--) {
        int x,y;
        qrd(x,y);
        double k = 1.*y/x;  //斜率计算
        mdf(x,k);
        printf("%d\n",t[1].len);    //答案输出
    }
    return 0;
}