****# 0.前言

前缀最大值就是指从序列开头到某个位置，所有元素的最大值喵~ ——Deepseek

即如下

max⁡j=1iaj\max\limits_{j=1}^i a_j

比如序列[3,1,4,1,5][3, 1, 4, 1, 5]，它的前缀最大值序列就是[3,3,4,4,5][3, 3, 4, 4, 5]。

1.正文

看如下题
P4198

小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？

我们把样例画出来，左图任何情况下都只为1，第二种为2。

题目问的是线段不相交即可，而且又连向原点，我们可以考虑正比例函数的关系式$$y=kx$$
那么对于线段相交，只需要判断k1≥k2k_{1\ge}k_2是否成立即可（我们设1节点在2节点之前），若成立，则第二个点被覆盖不能看到。

那么我们可以将问题转化为求最长递增的斜率序列（注意这里不是最长上升子序列！），而且原题有单点修改斜率这一操作，并且求[1,n][1,n]的答案，我们显然可以想到线段树维护这一数据结构。

我们怎么设计呢，我们可以线段树节点维护2个信息，第一个显然是最长递增的斜率序列长度，第二个是当前序列的最大值。

建树和easy，但…pushup不会写啊！

如果直接合并2个区间，那么一定会炸。所有O(1)O(1)的合并肯定会爆炸。

我们如何合并最长递增序列？显然第一项肯定在这个序列里，区间最大值一定在这里面。

2个子区间的值已经处理好了，可知左儿子内序列每一项一定在这个大区间内（因为如果左边不选那么右边肯定都会被覆盖啊）所以只需要处理右儿子区间和左儿子区间最大值的关系。这个值（我们设lmaxlmax）当作右儿子区间选出的节点的值必须大于lmaxlmax。

我们设计一个queryquery函数用于处理：

  • 如果l==rl==r，那么是叶子节点，如果val>lmaxval>lmax，则返回1，否则返回0
  • 劈2半，设lsls区间与rsrs区间
    • 如果ls.max<lmaxls.max<lmax，那么左孩子肯定都被覆盖了，去右孩子找。
    • 如果ls.max>lmaxls.max>lmax，那么右孩子在序列中的值一定会被贡献上，递归左孩子。注意右孩子的贡献是root.len−ls.lenroot.len-ls.len，因为右孩子的最长序列中所有值不一定都在这个根节点的序列中存在。看下图：

那么query函数如下:

1
2
3
4
5
6
7
8
9
int query(int p,double maxx){
    if(maxx>=t[p].mk) return 0;
    if(t[p].l==t[p].r){
        return t[p].mk>maxx;
    }
    else if(t[ls].mk<=maxx){
        return query(rs,maxx);
    }else return query(ls,maxx)+t[p].sum-t[ls].sum;
}

pushup也就像上文那么写：

1
2
3
4
void pushup(int p){
    t[p].mk=max(t[ls].mk,t[rs].mk);
    t[p].sum=t[ls].sum+query(rs,t[ls].mk);
}

那么代码单点修改也很好写，那么所有代码也就如下，注意一下浮点数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int MN=1e5+15;
int n,m;
struct segtree
{
    int l,r,sum;
    double mk;
}t[MN<<2];
void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        return;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
int query(int p,double maxx){
    if(maxx>=t[p].mk) return 0;
    if(t[p].l==t[p].r){
        return t[p].mk>maxx;
    }
    else if(t[ls].mk<=maxx){
        return query(rs,maxx);
    }else return query(ls,maxx)+t[p].sum-t[ls].sum;
}
void pushup(int p){
    t[p].mk=max(t[ls].mk,t[rs].mk);
    t[p].sum=t[ls].sum+query(rs,t[ls].mk);
}
void change(int p,int pos,double k){
    if(t[p].l==t[p].r){
        t[p].sum=1;
        t[p].mk=k;
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(mid>=pos) change(ls,pos,k);
    else change(rs,pos,k);
    pushup(p);
}
int main(){
    cin>>n>>m;
    build(1,1,n);
    int fl,fr;
    while (m--)
    {
        cin>>fl>>fr;
        change(1,fl,(double)fr/fl);
        cout<<t[1].sum<<'\n';
    }
    
    return 0;
}