按照所有柱子的外径排序降序,如果外径相同就按照内径降序,从前往后维护一个个计算最大值,用线段树维护最大值,因为外径降序,所以,所以只需要查看内径比外径小的最大值,就能找到当前柱子可以建成的最高。
ll tree[100005*8],lazy[100005*8];
void push_up(int k){
if(lazy[k]!=-1){
lazy[ls]=max(lazy[k],lazy[ls]);
lazy[rs]=max(lazy[k],lazy[rs]);
tree[ls]=max(tree[ls],lazy[k]);
tree[rs]=max(tree[rs],lazy[k]);
lazy[k]=-1;
}
}
void build(int l,int r,int k){
lazy[k]=-1;
if(l==r)
return;
MID;
build(lson);
build(rson);
}
void change(int l,int r,int k,int L,int R,ll va){
if(L<=l&&r<=R){
tree[k]=max(tree[k],va);
lazy[k]=max(lazy[k],va);
return;
}
push_up(k);
MID;
if(L<=mid)
change(lson,L,R,va);
if(R>mid)
change(rson,L,R,va);
tree[k]=max(tree[ls],tree[rs]);
}
ll query(int l,int r,int k,int L,int R){
if(R<L) return 0;
if(L<=l&&r<=R){
return tree[k];
}
push_up(k);
MID;
ll ans=0;
if(L<=mid){
ans=max(ans,query(lson,L,R));
}
if(R>mid)
ans=max(ans,query(rson,L,R));
return ans;
}
struct node{
int x,y,z;
}a[100005];
int c[200005];
int cnt=0;
bool cmp(node x,node y){
if(x.y==y.y)
return x.x>y.x;
return x.y>y.y;
}
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y>>a[i].z;
c[++cnt]=a[i].x;
c[++cnt]=a[i].y;
}
sort(c+1,c+1+cnt);
cnt=unique(c+1,c+1+cnt)-(c+1);
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
a[i].x=lower_bound(c+1,c+1+cnt,a[i].x)-c;
a[i].y=lower_bound(c+1,c+1+cnt,a[i].y)-c;
}
build(1,cnt+1,1);
//cout<<cnt<<endl;
ll ans=0;
for(int i=1;i<=n;i++){
ll sum=query(1,cnt+1,1,1,a[i].y);
sum+=a[i].z;
ans=max(sum,ans);
change(1,cnt+1,1,a[i].x+1,cnt+1,sum);
}
cout<<ans<<endl;
}