P4198 楼房重建

P4198 楼房重建

题意

考虑在一个二维平面上，x 轴表示在一条直线上大楼排列的坐标，y 轴表示大楼的高度，那么第 $i$ 栋大楼可以用 $(i,h_i)$ 表示。如果第 $i$ 栋大楼与第 $j$ 栋大楼满足 $i<j$ 且 $\frac{h_i}{i}\geq\frac{h_j}{j}$，那么第 $j$ 栋大楼被第 $i$ 栋大楼挡住而不可视见。求从 $(0,0)$ 最多能看到的大楼数量。

Sol

我们现在考虑一个很劣的做法：考虑将可视的大楼打上标记，那么在区间中记录两条信息：标记数目、楼房最大斜率 $\frac{h_i}{i}$ 以及对应的懒标记。那么每次单点修改就分类讨论是否会影响到标记，然后对应修改，查询则输出 $[1,n]$ 的标记和，复杂度比较劣（而且感觉很假）。

然而这样的做法代码难写难调（我只过了 30 pts，应该是哪里写挂了）。

现在我们考虑直接合并两个区间的答案。此时我们可以将区间视为一个单调上升的子序列，合并两个序列一定是将右区间全部包含而左区间选择最大值不超过右区间最小值的一段（从左到右严格单调）。

那么考虑每个区间对应记录下最大可视数和斜率最大值。然后查询时调用区间 $[1,n]$ 的最大可视数即可。那么对于单点修改对答案的影响合并时分类讨论：

1. 如果该区间的最大值小于等于当前斜率，那么贡献为 0。
2. 如果区间长度为 1 则在判断是否大于当前斜率，贡献 0 或 1。
3. 如果左子区间最大值小于等于当前斜率，递归返回右子区间的答案。
4. 如果左子区间最大值大于当前斜率，递归左子区间，返回答案加上右子区间的最大可视数。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=1e5+1e1;
const lint INF=1e18+1e9;
const double eps=1e-8;

struct Node{
	int l,r,w;
	double h;
};

double h[MAXN];
int n,m;

struct SegmentTree{
	Node tree[MAXN<<2];

	void Build(int l,int r,int x){
		tree[x].l=l,tree[x].r=r;
		if(l!=r){
			int mid=l+r>>1;
			Build(l,mid,x<<1),Build(mid+1,r,x<<1|1);
		}
		return;
	}

	void Update(int p,int x){
		int l=tree[x].l,r=tree[x].r,mid=l+r>>1;
		if(p<l || r<p) return;
		if(p==l && p==r) tree[x].w=1,tree[x].h=h[p];
		else{
			Update(p,x<<1),Update(p,x<<1|1);
			tree[x].h=max(tree[x<<1].h,tree[x<<1|1].h);
			tree[x].w=tree[x<<1].w+Query(mid+1,r,tree[x<<1].h,1);
		}
		return;
	}

	int Query(int ql,int qr,double k,int x){
		int l=tree[x].l,r=tree[x].r,mid=l+r>>1,res=0;
		if(qr<l || r<ql) return res;
		if(ql<=l && r<=qr){
			if(tree[x].h<=k) return res;
			if(l==r) return 1;
			if(tree[x<<1].h<=k) return Query(ql,qr,k,x<<1|1);
			else return tree[x].w-tree[x<<1].w+Query(ql,qr,k,x<<1);
		}
		else res+=Query(ql,qr,k,x<<1)+Query(ql,qr,k,x<<1|1);
		return res;
	}
}st;

int main(void){

	scanf("%d%d",&n,&m),st.Build(1,n,1);
	while(m--){
		int i=readint,hi=readint;
		h[i]=1.0*hi/i;
		st.Update(i,1);
		printf("%d\n",st.tree[1].w);
	}

	return 0;
}