传送门
解题思路
动态维护区间里面单调递增斜率的长度
需要维护两个信息：上述长度，和区间最大值（合并时需要）
难点在于两个子区间的合并。
左区间的楼房一定都能看见（没有遮挡），所以要在右区间二分，找到左面最大值 lmax 在右区间的位置，然后进行合并。
复杂度两个log。
AC代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!(c>='0'&&c<='9')) {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=100005;
double a[maxn],d[maxn*4];
int len[maxn*4],n,m;
int getans(int id,int l,int r,double x){
if(l==r) return a[l]>x;
if(d[id]<=x) return 0;
int mid=(l+r)/2;
if(d[id*2]>x) return len[id]-len[id*2]+getans(id*2,l,mid,x);
else return getans(id*2+1,mid+1,r,x);
}
void pushup(int id,int l,int r){
d[id]=max(d[id*2],d[id*2+1]);
int mid=(l+r)/2;
len[id]=len[id*2]+getans(id*2+1,mid+1,r,d[id*2]);
}
void add(int id,int l,int r,int x,double v){
if(l==r){
d[id]=v;
len[id]=1;
return;
}
int mid=(l+r)/2;
if(x<=mid) add(id*2,l,mid,x,v);
else add(id*2+1,mid+1,r,x,v);
pushup(id,l,r);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
a[x]=1.0*y/x;
add(1,1,n,x,a[x]);
printf("%d\n",len[1]);
}
return 0;
}