楼房重建

Abstract: 给你一堆数，求其从左往右单调上升的单调栈大小。会有修改元素大小的操作。

Ideas: 可以考虑分治。假设我们求出了一段区间的左半段的单调栈，以及右半段的单调栈，我们现在可以快速合并得到这段区间的单调栈。首先，左半段的全部元素都在新的单调栈里，右半段的元素如果比左半段的最大值要小，则不在新的单调栈里，反之在。所以我们需要在右半段里二分出第一个比左半段的最大值大的元素，其后面的元素都在新的单调栈里。

由于要修改，所以我们需要动态维护这个分治的过程。现在唯一不好办的就是二分的过程。这个也不难，我们定义一个函数 $f(l,r,h)$表示查询子区间 $[l,r]$的单调栈内有多少元素比 $h$大。不难发现这个函数是可以递归进行的。

现在严格定义一下 $f$的具体内容：
$$
f(l,r,h)=\begin{cases}
f(l,mid,h)+f(mid+1,r,max{[l,mid]}) & (h<max{[l,mid]})\\
f(mid+1,r,h)& (h\geq max{[l,mid]})
\end{cases}
$$
由于第一种情况下 $T(n)=2T(\frac{n}{2})+O(1)​$，所以这样的 $f​$在递归时的时间复杂度是 $O(n)​$的。实际上，我们可以对每个分治区间保存 $f(mid+1,r,max{[l,mid]})​$，这样时间复杂度就变成​$O(\log n)​$了。

每一次修改操作，我们需要在修改节点头顶的 $O(\log n)$个节点处二分，因此总复杂度是 $O(\log^2 n)$。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 100005

using namespace std;

template <typename T> void read(T& x)
{
    bool f = 0; x = 0; char c = getchar();
    while(!isdigit(c) && c!='-') c = getchar();
    if(c == '-') f = 1, c = getchar();
    while(isdigit(c)) x = x*10+c-'0', c = getchar();
    if(f) x = -x;
}

struct NODE
{
    double mx;
    int sm, rn;
};

struct SEGT
{
    #define ls (a<<1)
    #define rs (a<<1|1)
    #define mid ((l+r)>>1)

    NODE tre[MX*4];

    int qur(int a, int l, int r, double h)
    {
        if(l == r) return tre[a].mx > h;
        else if(tre[ls].mx > h) return qur(ls, l, mid, h) + tre[a].rn;
        else return qur(rs, mid+1, r, h);
    }

    void upd(int a, int l, int r)
    {
        tre[a].rn = qur(rs, mid+1, r, tre[ls].mx);
        tre[a].sm = tre[ls].sm + tre[a].rn;
        tre[a].mx = max(tre[ls].mx, tre[rs].mx);
    }

    void mdf(int a, int l, int r, int p, double h)
    {
        if(l == r) tre[a].mx = h, tre[a].sm = 1;
        else if(p <= mid) mdf(ls, l, mid, p, h), upd(a, l, r);
        else mdf(rs, mid+1, r, p, h), upd(a, l, r);
    }

    #undef ls
    #undef rs
    #undef mid
} T;

int n, m;

int main()
{
    read(n); read(m);
    for(int i=1; i<=m; i++)
    {
        int x, y;
        read(x); read(y);
        double k = 1.0*y/x;
        T.mdf(1, 1, n, x, k);
        printf("%d\n", T.tre[1].sm);
    }
    return 0;
}