兔队线段树

这是一种使用线段树维护前缀最值的算法。

我们从楼房重建这道题入手。

给定长为 $n$ 的序列 $h$，初始全为 $0$，支持单点修改。
定义 $s_i = \frac{h_i}{i}$。
每次查询求满足 $h_i > 0$ 且 $s_i > \max_{1 \leq j < i} s_j$ 的 $i$ 的个数。

查询的条件可以等价理解为 $i$ 合法意味着 $s_i$ 是前缀严格最大值。

我们使用线段树维护，对于每个区间，保存如下信息。

• 区间内的 $s_i$ 最大值。
• 不考虑区间外信息的情况下，区间内的答案。

设其分别为 $maxs$ 与 $cnt$，$maxs$ 是好维护的，重点在于 $cnt$ 如何维护。设现在要从 $u$ 的子树转移到 $u$，如果用左右子树的信息直接相加显然是错的，因为没有考虑左子树对右子树的影响。左子树的信息是可以直接继承的，右子树利用左子树的信息重新计算即可。

int calc(int u,int l,int r,ld pre){
    if(l==r){
        return tr[u].mx>pre;
    }
    int mid=(l+r)/2;
    if(tr[u*2].mx>pre){
        return calc(u*2,l,mid,pre)+tr[u].cnt-tr[u*2].cnt;
    }
    return calc(u*2+1,mid+1,r,pre);
}

void pushUp(int u,int l,int r){
    int mid=(l+r)/2;
    tr[u].mx = max(tr[u*2].mx,tr[u*2+1].mx);
    tr[u].cnt = tr[u*2].cnt+calc(u*2+1,mid+1,r,tr[u*2].mx);
}