楼房重建

单点修改+区间合并

ans[k]=ans[i]+cask(i|1,mid+1,r,tree[i])

若该区间最大值小于base，return 0

若该区间为单点，return tree[k]>base

若该区间左区间最大值小于base，return cask(i|1,mid+1,r,base)

否则return ans[k]-ans[l]+cask(i,l,mid,base)

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
using namespace std;

const int MAXN=1<<17;

int n,m;
int ans[MAXN<<1];
double tree[MAXN<<1];

int cask(int k,int l,int r,double base)
{
	if(tree[k]<=base) return 0;
	if(l==r) return tree[k]>base;
	int i=k<<1,mid=l+r>>1;
	if(tree[i]<=base) return cask(i|1,mid+1,r,base);
	return ans[k]-ans[i]+cask(i,l,mid,base);
}

void cchg(int k,int l,int r,int x,double y)
{
	if(l==r){
		tree[k]=y;
		ans[k]=1;
		return;
	}int i=k<<1,mid=l+r>>1;
	if(x<=mid) cchg(i,l,mid,x,y);
	else cchg(i|1,mid+1,r,x,y);
	tree[k]=max(tree[i],tree[i|1]);
	ans[k]=ans[i]+cask(i|1,mid+1,r,tree[i]);
	return;
}

int main()
{
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;scanf("%d%d",&x,&y);
		cchg(1,1,n,x,(double)y/x);
		printf("%d
",ans[1]);
	}return 0;
}