P4198 楼房重建

小 trick。

转化为斜率。相当于维护一段区间的前缀最大值个数。尝试线段树维护，问题在于如何合并子儿子的信息，即 pushup。对于每个节点维护区间的最大值，以及答案。最大值一定会在这段区间的答案序列之中。我们每一次直接递归合并答案。我们先直接加上左儿子本身的答案，再递归求解右儿子接上的答案。如果当前递归到某个节点，左儿子的最大值小于当前左儿子的最大值，直接递归右儿子。否则，递归左儿子，再加上该节点在右儿子上的答案。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
struct Node
{
    int l,r;
    double val; 
    int len;
}tr[N<<2];
int n,m;
int get(int x,double k)
{
    if(tr[x].val<=k)return 0;
    if(tr[x].l==tr[x].r)return 1;
    int mid=tr[x].l+tr[x].r>>1;
    if(tr[x<<1].val<=k)return get(x<<1|1,k);
    return get(x<<1,k)+tr[x].len-tr[x<<1].len;
}

inline void pushup(int x)
{
    tr[x].val=max(tr[x<<1].val,tr[x<<1|1].val);
    tr[x].len=tr[x<<1].len+get(x<<1|1,tr[x<<1].val);
}
void bulid(int x,int l,int r)
{
    tr[x].l=l,tr[x].r=r;
    if(l==r)return ;
    int mid=l+r>>1;
    bulid(x<<1,l,mid),bulid(x<<1|1,mid+1,r);
}
void modify(int x,int pos,double k)
{
    if(tr[x].l==tr[x].r)return tr[x].val=k,tr[x].len=1,void();
    int mid=tr[x].l+tr[x].r>>1;
    if(pos<=mid)modify(x<<1,pos,k);
    else modify(x<<1|1,pos,k);
    pushup(x);
}
int main()
{
    read(n,m);
    bulid(1,1,n);
    while(m--)
    {
        int x,y;
        read(x,y);
        modify(1,x,1.0*y/x);
        printf("%d\n",tr[1].len);
    }
    return 0;
}