M_sea

洛谷4602 [CTSC2018]混合果汁
LuoguBZOJ分析二分答案+主席树。首先二分最大美味度 $d$ 。显然可以选择所有美味度 $>d$ 的果...
扫描右侧二维码阅读全文
25
2019/03

洛谷4602 [CTSC2018]混合果汁

Luogu

BZOJ

分析

二分答案+主席树。

首先二分最大美味度 $d$ 。显然可以选择所有美味度 $>d$ 的果汁。

有一个显然的贪心是,按照价格从小到大选。

于是可以用可持久化权值线段树来维护。

以价格为下标建立主席树,然后把所有果汁按 $d$ 降序排列,插入主席树中。

每次二分一个 $i$ ,也就是说美味度是 $d_i$ ,那么能选的果汁就在 $1\sim i$ 中 。

每个节点维护一个 $\sum l$ 和 $\sum l\times p$ ,然后主席树上查询就行了。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,tot=0;
int rt[N];
struct juice { int d,p,l; } a[N];
inline int cmp(juice a,juice b) { return a.d>b.d; }

struct President_Tree {
    int ls[N*30],rs[N*30]; ll cnt[N*30],sum[N*30];
    
    inline void build(int& o,int l,int r) {
        o=++tot; if (l==r) return;
        int mid=(l+r)>>1;
        build(ls[o],l,mid),build(rs[o],mid+1,r);
    }
    
    inline int modify(int o,int l,int r,int k,int w) {
        int p=++tot; ls[p]=ls[o],rs[p]=rs[o],cnt[p]=cnt[o],sum[p]=sum[o];
        if (l==r) { cnt[p]+=w,sum[p]+=1ll*w*l; return p; }
        int mid=(l+r)>>1;
        if (k<=mid) ls[p]=modify(ls[o],l,mid,k,w);
        else rs[p]=modify(rs[o],mid+1,r,k,w);
        cnt[p]=cnt[ls[p]]+cnt[rs[p]],sum[p]=sum[ls[p]]+sum[rs[p]];
        return p;
    }

    inline int query(int o,int l,int r,ll g,ll L) {
        if (L>cnt[o]) return 0;
        if (g>sum[o]) return 1;
        if (l==r) return 1ll*L*l<=g;
        int mid=(l+r)>>1;
        if (L<=cnt[ls[o]]) return query(ls[o],l,mid,g,L);
        else return query(rs[o],mid+1,r,g-sum[ls[o]],L-cnt[ls[o]]);
    }
} T;

int main() {
    n=read(),m=read(); int mx=0;
    for (re int i=1;i<=n;++i) {
        a[i]=(juice){read(),read(),read()};
        mx=max(mx,a[i].p);
    }
    sort(a+1,a+n+1,cmp); T.build(rt[0],1,mx);
    for (re int i=1;i<=n;++i)
        rt[i]=T.modify(rt[i-1],1,mx,a[i].p,a[i].l);
    for (re int i=1;i<=m;++i) {
        ll g=read(),L=read();
        int l=1,r=n,ans=-1;
        while (l<=r) {
            int mid=(l+r)>>1;
            if (T.query(rt[mid],1,mx,g,L)) ans=mid,r=mid-1;
            else l=mid+1;
        }
        if (~ans) printf("%d\n",a[ans].d);
        else puts("-1");
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 22 PM

发表评论