luogu P4198 楼房重建

本文主要是介绍luogu P4198 楼房重建，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面传送门
大概可以算线段树单侧递归的板子。
这个东西看上去没法修改
我们考虑合并的时候怎么合并。
我们要维护每个区间的最大值和该区间的长度，那么答案显然是第一个区间的长度。
然后对于每个区间，它的左区间的答案肯定能全部选入，那么考虑右区间。
右区间选入的值肯定不能小于左区间的最大值。
我们考虑右区间的左区间的最大值，如果右区间的左区间的最大值小于左区间最大值，那么右区间的左区间显然是没有用的，我们直接考虑递归找到右区间答案。
反之，那么右区间的答案显然全部有用，那么我们递归找左区间再加上右区间答案即可。
时间复杂度\(O(nlog^2n)\)
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db double
#define N 200000
#define M 30
#define mod 1000000007
#define eps (1e-7)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
using namespace std;
int n,m,x,y,z,F[N+5<<2];db Maxn[N+5<<2];
I int Query(db x,int l,int r,int now){
	if(l==r) return Maxn[now]>x;int m=l+r>>1;return Maxn[now<<1]<=x?Query(x,m+1,r,now<<1|1):F[now]-F[now<<1]+Query(x,l,m,now<<1);
}
I void get(int x,db y,int l=1,int r=n,int now=1){
	if(l==r) return (void)(Maxn[now]=y,F[now]=1);int m=l+r>>1;x<=m?get(x,y,l,m,now<<1):get(x,y,m+1,r,now<<1|1);
	Maxn[now]=max(Maxn[now<<1],Maxn[now<<1|1]);F[now]=F[now<<1]+Query(Maxn[now<<1],m+1,r,now<<1|1);
}
int main(){
	freopen("1.in","r",stdin);
	re int i;scanf("%d%d",&n,&m);while(m--) scanf("%d%d",&x,&y),get(x,y*1.0/x),printf("%d\n",F[1]);
}

这篇关于luogu P4198 楼房重建的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！