luogu P4198 楼房重建

这道题就是用线段树维护一个斜率"强制"递增序列元素个数

其他的都不必多说，主要难点在于在pushup时怎样更新个数

当时我脑残就直接用vector保存下序列，然后二分更新，实测只有10分

其实完全不必记录序列，只要把区间内最大值记录下来即可

但这样面临的问题就是没有办法二分，于是通过看题解便想到了递归处理

具体来说增加一个count函数，用来找一个区间内的满足条件的序列元素个数

最初只需进入右区间，count(p*2+1,mx[p*2]),同时要满足限制必须大于左区间的最大值;

分几种情况：

　　当l(p)==r(p)时，递归入边界，return mx(p)>k; (k是最开始传入的mx[p*2])；

　　当mx(p*2)<=k时，只需进入右区间, return count(p*2+1,k);

　　else return len(p)-len(p*2)+count(p*2,k); (当mx[p*2]>k时，右区间内都满足条件，进入左区间递归，注意考虑左区间的遮挡，而不是len(p*2+1) );

（太难了，想不到）

上代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
struct Node{
    int l,r,len;
    double mx;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define len(x) t[x].len
    #define mx(x) t[x].mx
}t[400010];
void build(int p,int l,int r){
    l(p)=l;r(p)=r;
    if(l==r){
        return;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);build(p*2+1,mid+1,r);
}
int count(int p,double k){
    if(l(p)==r(p)) return mx(p)>k;
    if(mx(p*2)<=k) return count(p*2+1,k);
    else return len(p)-len(p*2)+count(p*2,k);
}
void change(int p,int x,double k){
    if(l(p)==r(p)){
        mx(p)=k;len(p)=1;
        return;
    }
    int mid=(l(p)+r(p))>>1;
    if(x<=mid) change(p*2,x,k);
    else change(p*2+1,x,k);
    mx(p)=max(mx(p*2),mx(p*2+1));
    len(p)=len(p*2)+count(p*2+1,mx(p*2));
}
int main(){
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--){
        double x,y;scanf("%lf%lf",&x,&y);double tan=y/x;
        change(1,x,tan);printf("%d
",len(1));
    }
    return 0;
}