Luogu P4602 [CTSC2018]混合果汁

题目

把果汁按美味度降序排序，以单价为下标插入主席树，记录每个节点的\(sum\)果汁升数和\(val\)果汁总价。

每次询问二分最小美味度，查询美味度大于等于\(mid\)的总体积为\(L\)的最低总价。

#include<bits/stdc++.h>

#define LL long long

using namespace std;

namespace IO

{

    char ibuf[(1<<21)+1],obuf[(1<<21)+1],st[20],*iS,*iT,*oS=obuf,*oT=obuf+(1<<21);

    char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}

    void Flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}

    void Put(char x){*oS++=x;if(oS==oT)Flush();}

    LL read(){LL x=0;char ch=Get();while(ch>57||ch<48)ch=Get();while(ch>=48&&ch<=57)x=x*10+(ch^48),ch=Get();return x;}

    void write(int x){int top=0;if(x<0)Put('-'),x=-x;if(!x)Put('0');while(x)st[++top]=(x%10)+48,x/=10;while(top)Put(st[top--]);Put('\n');}

}

using namespace IO;

#define N 100007

#define K 100000

struct node{int d,p,l;}a[N];

int operator<(node a,node b){return a.d<b.d;}

int root[N],ls[N<<5],rs[N<<5],cnt;

LL sum[N<<5],val[N<<5];

#define mid ((l+r)>>1)

void insert(int &p,int l,int r,int x,int s,LL v)

{

    ls[++cnt]=ls[p],rs[cnt]=rs[p],val[cnt]=val[p]+v,sum[cnt]=sum[p]+s,p=cnt;

    if(l==r) return ;

    x<=mid? insert(ls[p],l,mid,x,s,v):insert(rs[p],mid+1,r,x,s,v);

}

LL query(int p,int l,int r,LL s)

{

    if(l==r) return s*l;

    return s<=sum[ls[p]]? query(ls[p],l,mid,s):(val[ls[p]]+query(rs[p],mid+1,r,s-sum[ls[p]]));

}

int solve()

{

    LL g=read(),L=read();int l=0,r=K,ans=0;

    if(L>g) return -1;

    while(l<=r) (L<=sum[root[mid]]&&query(root[mid],0,K,L)<=g)? (ans=mid,l=mid+1):(r=mid-1);

    return a[ans].d;

}

int main()

{

    int n=read(),m=read(),i;

    for(a[0].d=-1,i=1;i<=n;++i) a[i].d=read(),a[i].p=read(),a[i].l=read();

    for(sort(a+1,a+n+1),i=n;i;--i) insert(root[i]=root[i+1],0,K,a[i].p,a[i].l,1ll*a[i].p*a[i].l);

    root[0]=root[1];

    while(m--) write(solve());

    return Flush(),0;

}