线段树更新，合并左右节点时利用递归函数
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<queue> #include<map> #include<set> #include<stack> #include<list> #include<ctime> #include<ctype.h> #include<stdlib.h> #include<bitset> #include<algorithm> #include<assert.h> #include<numeric> //accumulate #define endl " " #define fi first #define se second #define FOR(i,s,t) for(int i=(s);i<=(t);++i) #define mem(a,b) memset(a,b,sizeof(a)) #define rush() int MYTESTNUM;scanf("%lld",&MYTESTNUM);while(MYTESTNUM--) #define debug(x) printf("%d ",x) #define ls o<<1 #define rs o<<1|1 #define lss ls,l,mid #define rss rs,mid+1,r using namespace std; const int maxn=100000+5; int sum[maxn<<2]; double mx[maxn<<2]; int n,m; inline int cal(double M,int o,int l,int r) { if(l==r) return M<mx[o]; int mid=l+r>>1; if(M>=mx[ls]) return cal(M,rss); return sum[o]-sum[ls]+cal(M,lss); } inline void update(int o,int l,int r,int p,double v) { if(l==r) { sum[o]=1; mx[o]=v; return ; } int mid=l+r>>1; if(mid>=p) update(lss,p,v); else update(rss,p,v); mx[o]=max(mx[ls],mx[rs]); sum[o]=sum[ls]+cal(mx[ls],rss); } int main() { cin.tie(0); cout.tie(0); //ios_base::sync_with_stdio(0); //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d%d",&n,&m); for(int x,y;m;m--) { scanf("%d%d",&x,&y); double d=1.0*y/x; update(1,1,n,x,d); printf("%d ",sum[1]); } }