Luogu4198 楼房重建

线段树

题面

带修改的区间维护最大斜率。
题面

解析

用线段树区间维护斜率。
考虑如何向上合并。
左半段一定有贡献。
如果左半段的最大斜率大于右半段，右半段无贡献。
否则，如果在右半段中，
左边大于左半段，则直接加上右边符合条件的（总$-$左，因为右边现有的是大于左边的），递归考虑左边;
否则，递归右边。
这个玩意好像不能自然想出来。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
int n,m,x,y;
struct seg
{
  double mk;int s;
}t[N<<2];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il int Query(re int now,re int l,re int r,re double k)
{
  if(t[now].mk<=k) return 0;
  if(l==r) return 1;
  re int mid=l+r>>1;
  if(t[now<<1].mk>=k) return Query(now<<1,l,mid,k)+t[now].s-t[now<<1].s;
  else return Query(now<<1|1,mid+1,r,k);
}
il void Modify(re int now,re int l,re int r,re int x,re int z)
{
  if(l==r)
    {
      t[now].mk=1.0*z/x;t[now].s=1;return;
    }
  re int mid=l+r>>1;
  if(x<=mid) Modify(now<<1,l,mid,x,z);
  else Modify(now<<1|1,mid+1,r,x,z);
  t[now].mk=max(t[now<<1].mk,t[now<<1|1].mk);
  t[now].s=t[now<<1].s+Query(now<<1|1,mid+1,r,t[now<<1].mk);
}
int main()
{
  n=gi();m=gi();
  fp(i,1,m)
    {
      x=gi();y=gi();
      Modify(1,1,n,x,y);
      printf("%d\n",t[1].s);
    }
  return 0;
}