动态开点线段树,永久标记不下传MLE
  • 板块P1382 楼房
  • 楼主panyanppyy
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/4/15 11:27
  • 上次更新2023/10/28 03:43:24
查看原帖
动态开点线段树,永久标记不下传MLE
262322
panyanppyy楼主2022/4/15 11:27
#include<bits/stdc++.h>
#define ll long long
#define ri register
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+1,_=1e9+1,M=4e6+1;
int n,cnt,rot,B,S=_<<1,t[M],ls[M],rs[M];
struct qjc{
	int l,r,h;
}a[N];
vector<int>s;
vector<pair<int,int>>ans;
inline void nw(int&rt){if(!rt)rt=++cnt,assert(cnt<M);}
inline void f(int&rt,int k){t[rt]=max(t[rt],k);}
inline void update(int L,int R,int k,int l,int r,int&rt){
	nw(rt);
	if(L<=l&&r<=R)return f(rt,k);
	int mid=(l+r)>>1;
	if(L<=mid)update(L,R,k,l,mid,ls[rt]);
	if(R>mid)update(L,R,k,mid+1,r,rs[rt]);
}
inline int query(int x,int sum,int l,int r,int&rt){
	if(!rt)return sum;
	if(l==r)return max(sum,t[rt]);
	int mid=(l+r)>>1;
	if(x<=mid)return query(x,max(sum,t[rt]),l,mid,ls[rt]);
	else return query(x,max(sum,t[rt]),mid+1,r,rs[rt]);
}
int main(){
	scanf("%d",&n);
	for(int i=1,l,r,h;i<=n;i++){
		scanf("%d%d%d",&h,&l,&r),l+=_,r+=_;
		a[i]={l,r,h},S=min(S,l),B=max(B,r-1);
		s.emplace_back(l),s.emplace_back(r);
	}
	s.erase((sort(all(s)),unique(all(s))),s.end());
	for(int i=1;i<=n;i++)update(a[i].l,a[i].r-1,a[i].h,S,B,rot);
	ans.emplace_back(s[0],0);
	for(int i=0,w,lst=0;i<(int)s.size()-1;i++){
		w=query(s[i],0,S,B,rot);
		if(lst^w){
			ans.emplace_back(s[i],w);
			ans.emplace_back(s[i+1],w);
		}
		else ans.back().first=s[i+1];
		lst=w;
	}
	ans.emplace_back(s.back(),0);
	printf("%d\n",(int)ans.size());
	for(auto i:ans)printf("%d %d\n",i.first-_,i.second);
	return 0;
}
2022/4/15 11:27
加载中...