CodeForces - 777E

按照所有柱子的外径排序降序,如果外径相同就按照内径降序,从前往后维护一个个计算最大值,用线段树维护最大值,因为外径降序,所以,所以只需要查看内径比外径小的最大值,就能找到当前柱子可以建成的最高。

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;
}
上一篇:设计模式——创建型之单例模式


下一篇:POJ 2970 The lazy programmer(优先队列)