【题解】楼房重建

Problem

( ext{Solution:})

分析题目，我们看不到一个房子，当且仅当它的斜率严格不大于前面的房子斜率。

题目让我们求的就是：强制选择出严格单调递增的序列长度最大值，全局询问，单点修改。

看着很线段树，但是区间的信息怎么去合并呢？

开始的思路：首先长度必须要维护，然后维护一个最大值，这样合并的时候如果右边最大值小于等于左边的就可以直接跳过了。但是剩下的部分怎么维护？

忽略掉了线段树的本质：分治。

我们可以将右区间划分为两个区间来降低问题复杂度。它被我们分成左右两个区间后：

若被划分左区间的最大值要大于当前需要大于的值，我们就去递归左区间，拼接上右边的答案：(len[x]-len[ls[x]].) 注意不是 (len[rs[x]]) 是因为有些右区间的值在整体计算的时候是不能被计算的。

那么如果被划分的左区间最大值小于等于当前需要大于的值，我们就跳过左区间直接去右区间。

这样，我们通过分治成功将问题规模缩小一半，进行一次更新的复杂度是 (O(log n).)

于是总复杂度就是：(O(mlog^2 n).)

关于精度问题：我用 ( ext{long double}) 才卡过去。不知道有没有什么好方法，欢迎指教。

有很多细节：比如 pushup 函数实现的时候，需要大于的那个值是不需要改变这个参数的。每次我们都进入一个新区间去计算它，但需要大于的值没有变。

建树的时候由于没有任何一座楼房，所以 len 应该初始成 (0.)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+10;
int ls[MAXN],rs[MAXN],tot,n,m;
int L[MAXN],R[MAXN],rt,len[MAXN];
long double maxn[MAXN]; 
const long double eps=1e-12;
inline long double Max(long double x,long double y){return x-y>eps?x:y;}
inline void pushupmax(int x){maxn[x]=Max(maxn[ls[x]],maxn[rs[x]]);}
inline int pushup(long double v,int x){
	if(maxn[x]<=v)return 0;
	if(L[x]==R[x]){
		if(maxn[x]>v)return 1;
	}
	int s1=ls[x],s2=rs[x];
	if(maxn[s1]<=v)return pushup(v,s2);
	else{
		return pushup(v,s1)+len[x]-len[s1];
	}
}
void build(int &x,int l,int r){
	x=++tot;
	L[x]=l;R[x]=r;
	if(l==r){
		maxn[x]=0;
		len[x]=0;
		return;
	}
	int mid=(l+r)>>1;
	build(ls[x],l,mid);
	build(rs[x],mid+1,r);
	pushupmax(x);
	len[x]=len[ls[x]]+pushup(maxn[ls[x]],rs[x]);
}
void change(int x,int l,int r,long double v){
	if(L[x]==R[x]){
		maxn[x]=v;
		len[x]=1;
		return;
	}
	int mid=(L[x]+R[x])>>1;
	if(l<=mid)change(ls[x],l,r,v);
	if(mid<r)change(rs[x],l,r,v);
	pushupmax(x);
	len[x]=len[ls[x]]+pushup(maxn[ls[x]],rs[x]); 
}
int main(){
	//freopen("P4198_5.in","r",stdin);
	//freopen("My.out","w",stdout);
	scanf("%d%d",&n,&m);
	build(rt,1,n);
	for(int i=1;i<=m;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		change(rt,x,x,(long double)(1.0*y/x));
		printf("%d
",len[rt]);
	}
	return 0;
}