WA50玄关

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls pos<<1
#define rs pos<<1|1
#define DB long double 
const int N = 1e5 + 10 ;
const DB eps = 1e-10;
int n,m; 
struct qy
{
	int x,y;
	DB tan;  
	int idx;
}q[N];   
int mx; 
bool cmp1(qy a,qy b)
{ return a.x<b.x; }
bool cmp2(qy a,qy b)
{ return a.idx<b.idx; }
struct Segment_Tree
{
	int l,r;
	DB Mx;
	int Cnt;
}tree[N*4];   
void update(int pos)
{ tree[pos].Mx=max(tree[ls].Mx,tree[rs].Mx); } 
int push_up(int pos,DB x)
{ 
	if(tree[pos].Mx-x<eps) return 0 ;
	if( tree[pos].l == tree[pos].r ) return tree[pos].Mx-x>eps ? tree[pos].Cnt : 0 ; //叶子节点
	if(tree[ls].Mx-tree[rs].Mx>eps||(tree[ls].Mx-tree[rs].Mx<eps&&tree[rs].Mx-tree[ls].Mx<eps)) return push_up(ls,x); // l_Mx >= r_Mx 递归左子树 
	return tree[pos].Cnt-tree[ls].Cnt+push_up(ls,x);//递归左子树大于x的部分 右子树的答案是重复贡献的
}
void build(int pos,int l,int r)
{
	tree[pos].l=l; tree[pos].r=r;
	if(l==r) { tree[pos].Mx=0.0;tree[pos].Cnt=0; return ; } 
	int mid = l + r >> 1 ; 
	build(ls,l,mid); build(rs,mid+1,r) ; 
	update(pos);
	tree[pos].Cnt=tree[ls].Cnt+push_up(rs,tree[ls].Mx);//不直接push_up保证了push_up内层的tree[pos]是更新好的
}
void modify(int pos,int l,int r,DB x)//单点修改
{ 
	if(tree[pos].l==tree[pos].r)
	{ 
		tree[pos].Mx = x ;
		tree[pos].Cnt = 1 ;
		return ;
	}
	int mid = tree[pos].l + tree[pos].r >> 1 ;
	if( mid >= l )   modify(ls,l,r,x);
	if( mid+1 <= r ) modify(rs,l,r,x); 
	update(pos);
	tree[pos].Cnt=tree[ls].Cnt+push_up(rs,tree[ls].Mx);
} 
DB query_tan(int pos,int x)//方便打表
{
	if(tree[pos].l==tree[pos].r) return tree[pos].Mx;
	int mid = tree[pos].l + tree[pos].r >> 1 ;
	if(x<=mid) return query_tan(ls,x);
	else return query_tan(rs,x);
}
vector<int> alls;
int Get_idx(int x) // 离散化
{ return lower_bound(alls.begin(),alls.end(),x)-alls.begin(); } 
signed main()
{ 
	scanf("%lld%lld",&n,&m);
	build(1,1,1e5); //在离散化后的轴上建树
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&q[i].x,&q[i].y);    
		q[i].tan = 1.0*q[i].y/q[i].x;  
		q[i].idx=i; 
	}   
	//离散化
	sort(q+1,q+1+m,cmp1);
	for(int i=1;i<=m;i++) alls.push_back(q[i].x);
	sort(alls.begin(),alls.end());
	alls.erase(unique(alls.begin(),alls.end()),alls.end());
	
	sort(q+1,q+1+m,cmp2);  
	for(int i=1;i<=m;i++)
	{
		int idx = Get_idx(q[i].x) + 1 ;
		modify(1,idx,idx,q[i].tan);  
		printf("%lld\n",tree[1].Cnt);  
	}
}