前言
同学们都是抄的这是真的吗
题解的做法真的一下子很难一步到位
非常难以理解 pushup 函数，这个函数也的确非常巧妙
所以作为一个个人做题记录的补充，这篇文章会比较详细的解释题目
如果有什么不太理解的东西可以留言
题目意思
要求维护一个可以单点修改，查询整个数组的字典序最小的最长上升子序列的数据结构
想法
首先单点修改就很像线段树，如果这个时候想到树状数组之类的东西也正常，因为单点修改仍然无法确定一个数据结构
但是看到了最长上升子序列发现这个东西是很难用普通的数据结构维护的，但是这个东西长得非常像最长上升子段，而子段是用线段树维护的，所以我们考虑使用线段树维护最长上升子序列
首先考虑最暴力的做法，就是直接记录他的最大值和区间的子序列长度，因为如果一个右区间它的最大值都小于左区间我们就没有必要去看右区间了，因为左区间的最大值一定会被取走，而右区间没有大于左区间的东西，也就是没有东西会取走，所以直接返回左区间的答案即可。
接下来考虑优化掉询问的时间复杂度，转化为修改的。
经过思索，我们发现我们只需要准备两个部分，一个修改，一个合并，建树部分只需要维护最长上升子序列长度和最大值即可，查询同理，而且查询永远是查询的最大的区间，所以不需要单独写一个函数
那么就开始一个一个考虑，先考虑修改函数
单点修改不会遗留 tag，所以不用 pushdown，所以只需要单点递归到我们需要的节点，考虑到我们要存一个答案，所以我们存下一个 \(siz\)，表示这个区间的上升子序列长度，然后考虑怎么合并两个区间的答案
现在是合并函数
首先左区间的答案是必须要取走的，然后考虑右区间，因为我们右区间有且仅有一个上升子序列长度，而没有别的东西，更何况上升子序列无法 \(O(1)\) 合并，所以尝试再开一个函数 \(count{(i,j)}\) 表示 \(i\) 号节点要求上升子序列里的每一个数字都要 \(\ge j\)，递归这个 \(count\) 该怎么求。
首先如果 \(i\) 是一个叶子节点，就看这个叶子结点的值大小是否 \(\ge j\) 即可，否则的话分类讨论，我们看他的左儿子和右儿子，记为 \(s_1,s_2\)，如果 \(s_1\) 的最大值都要 \(\le j\) 说明左儿子取不走任何东西，那么只能递归右儿子，答案为 \(count{(s_2,j)}\)，否则的话 \(s_1\) 的最大值一定会被取走，因为没有任何东西能挡住他，而 \(s_2\) 取走的东西一定要满足是上升的，所以 \(s_2\) 能取走的点一定是 \(\ge s_1\) 中最大值的点，而一开始我们计算的 \(x.siz\) 就是 \(s_1\) 取走的点加上 \(s_2\) 中满足条件能取走的点加和而成，所以 \(s_2\) 能取走的点不可能又不能取走了，所以 \(s_2\) 的贡献是 \(x.siz-s_1.siz\) 而 \(s_1\) 的贡献是 \(count{(s_1,j)}\)。
所以思路就出来了
思路
我们的线段树只用维护三个内容
- 1.修改操作，这个部分我们单点修改即可，然后最后合并
- 2.合并操作，这个部分的 \(siz\) 由左儿子和右儿子贡献，左儿子没有任何约束，所以是 \(s_1.siz\)，而右儿子的约束是每个节点大小都要比做儿子最大的节点大，也就是 \(count{(s_2,s_1.mx)}\)
- 3.\(count(x,p)\) 函数，表示 \(x\) 节点所有点都要 \(\ge p\) 的最长上升子序列，这个部分递归分讨，如果是叶子节点直接返回，否则的话看左儿子，如果左儿子最大值 \(\le j\) 说明没有利用价值了，直接递归右儿子，答案是 \(count{(s_2,j)}\)，否则的话肯定会选走左儿子的最大值，那么对右儿子不会产生影响，左儿子的贡献是 \(count{(s_1,j)}\)，右儿子的贡献是 \(x.siz-s_1.siz\)，加和就是整个 \(count{(x,p)}\) 的答案。
最后询问的时候直接输出线段树第一个结点的 \(siz\) 既可以了。
PS
题目给出的使每一个结点的高度，我们上文的所有计算都是使用的斜率，所以需要转化一下。
Code
int n,m;
struct tree{int lt,rt,siz;double mx;};
struct segment{#define lson(x) x<<1#define rson(x) x<<1|1tree tr[N<<2];inline void build(int id,int l,int r){tr[id].lt=l;tr[id].rt=r;if(l==r) return tr[id].siz=0,void();int mid=l+r>>1;build(lson(id),l,mid);build(rson(id),mid+1,r);tr[id].mx=max(tr[lson(id)].mx,tr[rson(id)].mx);}inline int count(int id,double h){if(tr[id].lt==tr[id].rt) return tr[id].mx>h;if(tr[lson(id)].mx<=h) return count(rson(id),h);else return tr[id].siz-tr[lson(id)].siz+count(lson(id),h);}inline void update(int id){tr[id].mx=max(tr[lson(id)].mx,tr[rson(id)].mx);tr[id].siz=tr[lson(id)].siz+count(rson(id),tr[lson(id)].mx);}inline void change(int id,int x,double y){if(tr[id].lt==tr[id].rt){tr[id].mx=y;tr[id].siz=1;return void();}int mid=tr[id].lt+tr[id].rt>>1;if(x<=mid) change(lson(id),x,y);else change(rson(id),x,y);update(id);}#undef lson#undef rson
}seg;int main(){cin>>n>>m;seg.build(1,1,n);for(int i=1;i<=m;i++){int x,y;cin>>x>>y;seg.change(1,x,double(y)*1.0/double(x));cout<<seg.tr[1].siz<<endl;}return 0;
}