楼房重建

题目描述

小 A 的楼房外有一大片施工工地，工地上有 \(N\) 栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。

为了简化问题，我们考虑这些事件发生在一个二维平面上。小 A 在平面上 \((0,0)\) 点的位置，第 \(i\) 栋楼房可以用一条连接 \((i,0)\) 和 \((i,H_i)\) 的线段表示，其中 \(H_i\) 为第 \(i\) 栋楼房的高度。如果这栋楼房上任何一个高度大于 \(0\) 的点与 \((0,0)\) 的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。

施工队的建造总共进行了 \(M\) 天。初始时，所有楼房都还没有开始建造，它们的高度均为 \(0\)。在第 \(i\) 天，建筑队将会将横坐标为 \(X_i\) 的房屋的高度变为 \(Y_i\)（高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做）。请你帮小 A 数数每天在建筑队完工之后，他能看到多少栋楼房？

输入格式

第一行两个正整数 \(N,M\)。

接下来 \(M\) 行，每行两个正整数 \(X_i,Y_i\)。

输出格式

\(M\) 行，第 \(i\) 行一个整数表示第 \(i\) 天过后小 A 能看到的楼房有多少栋。

样例 #1

样例输入 #1

3 4
2 4
3 6
1 1000000000
1 1

样例输出 #1

提示

对于 \(100\%\) 的数据，\(1 \le X_i \le N\)，\(1 \le Y_i \le 10^9\)，\(1\le N,M \le 10^5\)。

题解

根据题意可以看出要把\((x,y)\)转成斜率\(k\)
所以只要\(k_1 ~k_{i-1}<k_i\) 那么就可以看到第\(i\)个建筑
抽象一下这个题就是求有单点修改的最大上升子序列(即在最上层的那个上升子序列)
用线段树维护某个区间内的高度最大值\(mx\)和最大上升子序列的长度\(len\)。
修改高度的时候就是普通的线段树的操作
但是更新\(len\)即合并两个子区间比较难
一个区间\(ls , rs\)的信息是已知的(修改时会递归的到线段树的叶子节点而叶子节点的信息已知从而可以推出其他节点的信息)
\(ls\)前面没有楼挡着所以它的\(len\)不会改变直接贡献给父节点
所以只用求\(rs\)的\(len\)因为\(rs\)会被\(ls\)挡住所以要求的是\(L :\) \(rs\)中大于\(mxl\)的最大上升子序列。(\(maxl:\)左子区间\(k\)最大值)
设\(get(mxl,rs)\)为求解\(L\)的函数
父节点的\(len\)即为\(len_{ls}+ get(mxl,rs)\)
在\(get(mxl,rs)\)中可以递归求解\(rs\)中大于\(mxl\)的最大上升子序列。
设\(lss\)为右区间的左子区间,\(rss\)为右区间的右子区间

若右区间的左子区间最大值大于等于h,那么它的右子区间的个数就可以直接求出来(即\(len_{rs}-len_{lss}+get(mxl,lss))\)，继续递归\(lss\)即可。
若右区间的左子区间最大值小于h，那么他的左子区间的贡献必为0，所以继续递归右子区间即可即\((get(mxl,rss)))\)

总的时间复杂度\(O(nlogn^2)\)

std

#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N = 1e5+2;
struct tree
{
	double mx;
	int len;
	#define mx(x) t[x].mx
	#define len(x) t[x].len
}t[N<<2];
int n,m;
double a[N];
int get(double maxl,int p,int l,int r)
{
	if(mx(p)<maxl)return 0;
	if(a[l]>maxl) return len(p);
	int mid = (l+r)>>1;
	if(mx(ls)<=maxl) return get(maxl,rs,mid+1,r);
	else return get(maxl,ls,l,mid) + len(p)-len(ls);
}

void change(int p,int l,int r,int x,int v)
{
	
	if(l==r)
	{
		mx(p) = (double)v/x;
		len(p) = 1;
		return;
	}
	int mid = (l+r)>>1;
	if(x<=mid)change(ls,l,mid,x,v);
	else if(x>mid) change(rs,mid+1,r,x,v);
	
	mx(p)= max(mx(ls),mx(rs));
	len(p) = len(ls)+get(mx(ls),rs,mid+1,r);
	
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x] = (double)y/x;
		change(1,1,n,x,y);
		printf("%d\n",len(1));
		
	}
	return 0;
}

标签：递归,rs,楼房,线段,len,mxl,ls,区间,树中
From： https://www.cnblogs.com/AC7-/p/16844868.html

线段树中递归