题目
题目描述
小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？
输入输出格式
输入格式：
第一行两个正整数N,M
接下来M行，每行两个正整数Xi,Yi
输出格式：
M行，第i行一个整数表示第i天过后小A能看到的楼房有多少栋
输入输出样例
输入样例#1：
3 4
2 4
3 6
1 1000000000
1 1
输出样例#1：
1
1
1
2
说明
对于所有的数据1<=Xi<=N，1<=Yi<=10^9
N,M<=100000
题解
感觉这种线段树里强行二次递归求解挺常见的……最近遇到好多还是不会
考虑将一个区间分左右两区间的斜率最大值情况讨论
假设$val_{[l,r]}$表示区间$[l,r]$的对自己的贡献（$[l,r]$外的点无影响）
如果一个区间$[l,r]$左区间$[l,mid]$最大值为区间最大值，$val_{l,r}$的值就为$val_{l,mid}$，因为右区间$[mid+1,r]$都被挡住了
如果左区间最大值不是区间最大值，说明区间最大值在右区间，考虑将右区间递归求解
可以发现影响右区间的还是左区间的最大值，如果$max_{l,mid}\geq max_{l_1,r_1},mid+1\leq l_1\leq r_1\leq r$，$val_{l_1,r_1}$是没有贡献的
如果$max_{l,mid}\geq max_{l_1,mid_1}$，$val_{l_1,mid_1}$没有贡献，同时说明$max_{l_1,r_1}$存在于$[mid_1+1,r_1]$中，递归求解$[mid_1+1,r_1]$
否则修改值对$val_{mid_1+1,r_1}$没有影响，直接递归求解$[l_1,mid_1]$并加上$val_{l_1,r_1}-val_{l_1,mid_1}$
为什么不是$val_{mid_1+1,r_1}$？
$val_{l,r}$表示区间$[l,r]$的对自己的贡献，也就是忽略了区间外的影响，而我们要求的是受$[l_1,mid_1]$影响的$[mid_1+1,r_1]$贡献，所以用$val_{l_1,r_1}-val_{l_1,mid_1}$，ta们都受$[l_1,mid_1]$的影响
况且区间贡献在这里不满足区间相加性啊不然为什么要二次递归求解qaq
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
using namespace std;
const int MAX=4e5+5;
struct p{
int x;
double maxn;
}s[MAX];
int n,m;
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
double K(double x,double y)
{
return y/x;
}
int GET_ANS(int l,int r,int k,double x)
{
if(l==r) return s[k].maxn>x;
if(s[k].maxn<=x) return 0;
if(s[tl].maxn<=x) return GET_ANS(mid+1,r,tr,x);
return s[k].x-s[tl].x+GET_ANS(l,mid,tl,x);
}
void pus(int l,int r,int k)
{
s[k].x=s[tl].x;
if(s[tl].maxn>=s[tr].maxn) s[k].maxn=s[tl].maxn;
else s[k].maxn=s[tr].maxn,s[k].x+=GET_ANS(mid+1,r,tr,s[tl].maxn);
}
void change(int l,int r,int k,int x,double dis)
{
if(l==r)
{
s[k].x=1;
return void(s[k].maxn=dis);
}
if(x<=mid) change(l,mid,tl,x,dis);
else change(mid+1,r,tr,x,dis);
pus(l,r,k);
}
int main()
{
n=read(),m=read();
for(int i=1,x;i<=m;++i)
x=read(),change(1,n,1,x,K(x,read())),printf("%d\n",s[1].x);
return 0;
}
