0分求助
  • 板块P1382 楼房
  • 楼主Jacky2009
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/1/14 00:11
  • 上次更新2023/10/24 04:21:37
查看原帖
0分求助
499231
Jacky2009楼主2023/1/14 00:11
#include<bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define int long long
int l[100005],r[100005],n,hmm[100005];
int li[200005],height[200005];
struct tree{
	int maxn,lazy;
}t[800005];
void update(int now){
	t[now].maxn=max(t[ls].maxn,t[rs].maxn);	
}
void pushdown(int now){
	if(t[now].lazy){
		t[ls].lazy=max(t[ls].lazy,t[now].lazy);
		t[rs].lazy=max(t[rs].lazy,t[now].lazy);
		t[ls].maxn=max(t[ls].maxn,t[ls].lazy);
		t[rs].maxn=max(t[rs].maxn,t[rs].lazy);
		t[now].lazy=0;
	}
}
void change(int l,int r,int now,int x,int y,int v){
	if(x<=l&&r<=y){
		t[now].maxn=max(t[now].maxn,v);
		t[now].lazy=v;
		return;
	}
	pushdown(now);
	int mid=(l+r)>>1;
	if(x<=mid)change(l,mid,ls,x,y,v);
	if(y>mid)change(mid+1,r,rs,x,y,v);
	update(now);
}
void print(int l,int r,int now){
	if(l==r){
		height[l]=t[now].maxn;
		return;
	}
	pushdown(now);
	int mid=(l+r)>>1;
	print(l,mid,ls);
	print(mid+1,r,rs);
	return;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>hmm[i]>>l[i]>>r[i];
		li[i*2-1]=l[i];
		li[i*2]=r[i];
	}
	sort(li+1,li+n*2+1);
	int len=unique(li+1,li+n*2+1)-li-1;
	li[0]=0;
	li[len+1]=li[len];
	for(int i=1;i<=n;i++){
		l[i]=lower_bound(li+1,li+len+1,l[i])-li;
		r[i]=lower_bound(li+1,li+len+1,r[i])-li;
	//	cout<<l[i]<<" "<<r[i]<<endl;
		change(1,len,1,l[i],r[i]-1,hmm[i]);
	}
	int cnt=0;
	print(1,len,1);
	int ans=0;
	height[len+1]=0;
	for(int i=1;i<=len+1;i++){
		if(height[i]!=height[i-1])cnt+=2;
	}
	cout<<cnt<<endl;
	for(int i=1;i<=len+1;i++){
		if(height[i]==height[i-1])continue;
		else{
				 cout<<li[i]<<" "<<height[i-1]<<endl;
				 cout<<li[i]<<" "<<height[i]<<endl;
		}
	}
}
```cpp
2023/1/14 00:11
加载中...