线段树维护前缀最大值(单调递增栈)
cpp
// P4198 楼房重建
struct SegmentTree{
struct Node{
int l,r,len;
double mx;
};
vector<Node> t;
SegmentTree(){}
SegmentTree(int n){
init(n);
}
void init(int n){
t=vector<Node>(n<<2);
build(1,1,n);
}
void build(int p,int l,int r){
t[p]={l,r,0,0};
if(l==r){
t[p].mx=0;
t[p].len=0;
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void pushup(int p){
t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
t[p].len=t[p<<1].len+query(p<<1|1,t[p<<1].mx);
}
void modify(int p,int x,double v){
if(t[p].l==t[p].r){
t[p].mx=v;
t[p].len=1;
return;
}
int mid=t[p].l+t[p].r>>1;
if(x<=mid)modify(p<<1,x,v);
else modify(p<<1|1,x,v);
pushup(p);
}
int query(int p,double mx){
if(t[p].mx<=mx)return 0;
if(t[p].l==t[p].r)return t[p].mx>mx;
if(t[p<<1].mx<=mx)return query(p<<1|1,mx);
return query(p<<1,mx)+t[p].len-t[p<<1].len;
}
};