C++14(g++5.4) 解法, 执行用时: 261ms, 内存消耗: 12248K, 提交时间: 2020-10-11 18:57:10
#include<bits/stdc++.h>
#define ls o*2
#define rs o*2+1
#define mid (l+r)/2
using namespace std;
struct node
{
int x,h;
}N[200005];
int h[200005];
int mx[200005*4],mi[200005*4],pos[200005*4];
void build(int o,int l,int r)
{
if(l==r)
{
mx[o]=mi[o]=h[l];
pos[o]=l;
return ;
}
build(ls,l,mid);
build(rs,mid+1,r);
mx[o]=max(mx[ls],mx[rs]);
mi[o]=min(mi[ls],mi[rs]);
pos[o]=mi[ls]<=mi[rs]?pos[ls]:pos[rs];
}
void up(int o,int l,int r,int p,int v)
{
if(l==r)
{
mx[o]=mi[o]=v;
pos[o]=l;
h[l]=v;
return ;
}
if(p<=mid) up(ls,l,mid,p,v);
else up(rs,mid+1,r,p,v);
mx[o]=max(mx[ls],mx[rs]);
mi[o]=min(mi[ls],mi[rs]);
pos[o]=mi[ls]<=mi[rs]?pos[ls]:pos[rs];
}
int findmx(int o,int l,int r,int ql,int qr,int v)
{
if(mx[o]<=v) return 0;
if(l==r&&mx[o]>v)
{
return l;
}
if(qr<=mid) return findmx(ls,l,mid,ql,qr,v);
else if(mid<ql) return findmx(rs,mid+1,r,ql,qr,v);
else
{
int po=findmx(rs,mid+1,r,ql,qr,v);
if(!po) po=findmx(ls,l,mid,ql,qr,v);
return po;
}
}
int findmi(int o,int l,int r,int ql,int qr)
{
if(ql==l&&r==qr)
{
return pos[o];
}
if(qr<=mid) return findmi(ls,l,mid,ql,qr);
else if(mid<ql) return findmi(rs,mid+1,r,ql,qr);
else
{
int ans1=findmi(ls,l,mid,ql,mid);
int ans2=findmi(rs,mid+1,r,mid+1,qr);
if(h[ans1]<=h[ans2]) return ans1;
else return ans2;
}
}
int main()
{
int n;
scanf("%d",&n);
vector<int> V;
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
V.push_back(a);
N[i]=node{a,b};
}
sort(V.begin(),V.end());
for(int i=1;i<=n;i++)
{
int id=lower_bound(V.begin(),V.end(),N[i].x)-V.begin();
id++;
N[i].x=id;
h[id]=N[i].h;
}
build(1,1,n);
for(int i=1;i<=n;i++)
{
int po;
if(N[i].x>1&&(po=findmx(1,1,n,1,N[i].x-1,h[N[i].x])))
{
// printf("i=%d po=%d\n",i,po);
// h[po]=h[N[i].x];
up(1,1,n,po,h[N[i].x]);
}
if(N[i].x<n&&!findmx(1,1,n,N[i].x+1,n,h[N[i].x]))
{
po=findmi(1,1,n,N[i].x+1,n);
// h[po]=h[N[i].x];
up(1,1,n,po,h[N[i].x]);
}
}
for(int i=1;i<=n;i++)
{
printf("%d ",h[N[i].x] );
}
puts("");
}
C++(clang++11) 解法, 执行用时: 224ms, 内存消耗: 14288K, 提交时间: 2020-10-29 10:40:05
#include<bits/stdc++.h>
#define ls p<<1,l,mid
#define rs p<<1|1,mid+1,r
using namespace std;
const int nx=2e5+5;
int ps[nx],f[nx],h[nx],mp[nx],val[nx]={0x3f3f3f3f};
int mx[nx<<2],mi[nx<<2];
bool cmp(int a,int b){
return ps[a]<ps[b];
}
inline void wk(int p){
mx[p]=val[mx[p<<1|1]]>=val[mx[p<<1]]?mx[p<<1|1]:mx[p<<1];
mi[p]=val[mi[p<<1]]<=val[mi[p<<1|1]]?mi[p<<1]:mi[p<<1|1];
}
void build(int p,int l,int r){
if(l==r){
mx[p]=mi[p]=l;
return;
}
int mid=l+r>>1;
build(ls),build(rs);
wk(p);
}
int q1(int p,int l,int r,int x,int y,int z){
int mid=l+r>>1;
if(x<=l&&r<=y){
if(l==r)return val[mx[p]]>z?l:0;
if(val[mx[p<<1|1]]>z)return q1(rs,x,y,z);
if(val[mx[p<<1]]>z)return q1(ls,x,y,z);
return 0;
}
int re=0;
if(mid<y)re=q1(rs,x,y,z);
if(!re&&x<=mid)re=q1(ls,x,y,z);
return re;
}
int q2(int p,int l,int r,int x,int y){
if(x<=l&&r<=y)return mi[p];
int mid=l+r>>1,r1=0,r2=0;
if(x<=mid)r1=q2(ls,x,y);
if(mid<y)r2=q2(rs,x,y);
return val[r1]<=val[r2]?r1:r2;
}
void up(int p,int l,int r,int x,int y){
if(l==r){val[l]=y;return;}
int mid=l+r>>1;
if(x<=mid)up(ls,x,y);
else up(rs,x,y);
wk(p);
}
int main(){
// freopen("test.txt","r",stdin);
// freopen("A.txt","w",stdout);
int n;scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",ps+i,h+i),f[i]=i;
sort(f+1,f+1+n,cmp);
for(int i=1;i<=n;++i)
val[i]=h[f[i]],mp[f[i]]=i;
build(1,1,n);
for(int i=1;i<=n;++i){
int now=mp[i],p=0;
if(now>1)p=q1(1,1,n,1,now-1,val[now]);
if(p)up(1,1,n,p,val[now]);
if(now<n){
p=q1(1,1,n,now+1,n,val[now]);
if(!p)
p=q2(1,1,n,now+1,n),up(1,1,n,p,val[now]);
}
}
for(int i=1;i<=n;++i)printf("%d ",val[mp[i]]);
}
，表示有
座山峰
都不相同）
个山峰最后的高度