• 线段树维护的题，关键在于合并区间答案。
• ans 数组记录每一段区间的答案。
• 然后会发现对于每一个子序列，有两种点在当前子序列中一定满足要求：
1. 子序列中的第一个点。
2. 子序列中权值最大的点。
• 而且 pushup 时，左儿子的 ans 值会被父节点全部接受。
• 通过上面两个性质便能得出 pushup 的做法。
1 #include<bits/stdc++.h> 2 #define ls u<<1 3 #define rs ls|1 4 using namespace std; 5 int n,m; 6 int x,y; 7 double tmp; 8 int ans[400050]; 9 double val[100050]; 10 double maxn[400050]; 11 int query(int u,int l,int r,double hig) 12 { 13 if(val[l]>hig) return ans[u]; 14 if(maxn[u]<=hig) return 0; 15 int mid=(l+r)>>1; 16 if(maxn[ls]<=hig) return query(rs,mid+1,r,hig); 17 else return query(ls,l,mid,hig)+ans[u]-ans[ls]; 18 } 19 void modify(int u,int l,int r) 20 { 21 if(l==r) 22 { 23 maxn[u]=val[x]; 24 ans[u]=1; 25 return ; 26 } 27 int mid=(l+r)>>1; 28 if(x<=mid) modify(ls,l,mid); 29 else modify(rs,mid+1,r); 30 maxn[u]=max(maxn[ls],maxn[rs]); 31 ans[u]=ans[ls]+query(rs,mid+1,r,maxn[ls]); 32 } 33 int main() 34 { 35 scanf("%d%d",&n,&m); 36 while(m--) 37 { 38 scanf("%d%d",&x,&y); 39 val[x]=(double)y/x; 40 modify(1,1,n); 41 printf("%d\n",ans[1]); 42 } 43 return 0; 44 }
原文：https://www.cnblogs.com/wyher/p/10434589.html
