这道题就是用线段树维护一个斜率"强制"递增序列元素个数
其他的都不必多说，主要难点在于在pushup时怎样更新个数
当时我脑残就直接用vector保存下序列，然后二分更新，实测只有10分
其实完全不必记录序列，只要把区间内最大值记录下来即可
但这样面临的问题就是没有办法二分，于是通过看题解便想到了递归处理
具体来说增加一个count函数，用来找一个区间内的满足条件的序列元素个数
最初只需进入右区间，count(p*2+1,mx[p*2]),同时要满足限制必须大于左区间的最大值;
分几种情况：
当l(p)==r(p)时，递归入边界，return mx(p)>k; (k是最开始传入的mx[p*2])；
当mx(p*2)<=k时，只需进入右区间, return count(p*2+1,k);
else return len(p)-len(p*2)+count(p*2,k); (当mx[p*2]>k时，右区间内都满足条件，进入左区间递归，注意考虑左区间的遮挡，而不是len(p*2+1) );
（太难了，想不到）
上代码：
#include<iostream> #include<cstdio> using namespace std; int n,m; struct Node{ int l,r,len; double mx; #define l(x) t[x].l #define r(x) t[x].r #define len(x) t[x].len #define mx(x) t[x].mx }t[400010]; void build(int p,int l,int r){ l(p)=l;r(p)=r; if(l==r){ return; } int mid=(l+r)>>1; build(p*2,l,mid);build(p*2+1,mid+1,r); } int count(int p,double k){ if(l(p)==r(p)) return mx(p)>k; if(mx(p*2)<=k) return count(p*2+1,k); else return len(p)-len(p*2)+count(p*2,k); } void change(int p,int x,double k){ if(l(p)==r(p)){ mx(p)=k;len(p)=1; return; } int mid=(l(p)+r(p))>>1; if(x<=mid) change(p*2,x,k); else change(p*2+1,x,k); mx(p)=max(mx(p*2),mx(p*2+1)); len(p)=len(p*2)+count(p*2+1,mx(p*2)); } int main(){ scanf("%d%d",&n,&m); build(1,1,n); while(m--){ double x,y;scanf("%lf%lf",&x,&y);double tan=y/x; change(1,x,tan);printf("%d\n",len(1)); } return 0; }
原文：https://www.cnblogs.com/SyhAKIOI/p/11617964.html