[BZOJ5343]混合果汁

传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=5343

这种最大值里面的最小值问题显然考虑二分233

现在二分出一个美味度之后

问题就是大于这个美味度的所有值里面取出前L个价格最小的和能不能<=g

这个主席树维护一下就行了

#include <bits/stdc++.h>
using namespace std;
int cnt,Lson[5000005],Rson[5000005],N,M,rt[5000005];
long long Sum[5000005],Size[5000005];
struct Node{
    long long d,p,l;
}a[5000005];
int Temp(Node x,Node y){
    return x.d<y.d;
}
int Insert(int rt1,int l,int r,long long P,long long L){
    int Id=++cnt;
    Lson[Id]=Lson[rt1];
    Rson[Id]=Rson[rt1];
    if (l==r) {Sum[Id]=Sum[rt1]+1ll*P*1ll*L,Size[Id]=Size[rt1]+L;return Id;}
    int mid=(l+r)>>1;
    if (P<=mid) Lson[Id]=Insert(Lson[rt1],l,mid,P,L);
    else Rson[Id]=Insert(Rson[rt1],mid+1,r,P,L);
    Sum[Id]=Sum[Lson[Id]]+Sum[Rson[Id]];
    Size[Id]=Size[Lson[Id]]+Size[Rson[Id]];
    return Id;
}
long long query(int rt1,int rt2,int l,int r,int Ned){
    if (l==r) return 1ll*l*1ll*Ned;
    int mid=(l+r)>>1;
    if (Size[Lson[rt2]]-Size[Lson[rt1]]>=Ned) return query(Lson[rt1],Lson[rt2],l,mid,Ned);
    else return Sum[Lson[rt2]]-Sum[Lson[rt1]]+query(Rson[rt1],Rson[rt2],mid+1,r,(Ned-(Size[Lson[rt2]]-Size[Lson[rt1]])));
}
int temp(Node x,Node y){
    return x.d<y.d;
}
int main(){
    scanf("%d%d",&N,&M);
    long long qwq=0;
    for (int i=1;i<=N;i++){
        scanf("%lld%lld%lld",&a[i].d,&a[i].p,&a[i].l);
        qwq=max(qwq,a[i].p);
    }
    sort(a+1,a+N+1,temp);
    for (int i=1;i<=N;i++)
    rt[i]=Insert(rt[i-1],1,qwq,a[i].p,a[i].l);
    while (M--){
        long long  g,L;
        scanf("%lld%lld",&g,&L);
        int l=1,r=N,ans=-1;
        while (l<=r){
            int mid=(l+r)>>1;
            if (Size[rt[N]]-Size[rt[mid-1]]>=L&&query(rt[mid-1],rt[N],1,qwq,L)<=g)
             ans=a[mid].d,l=mid+1;
             else r=mid-1;
        }
        printf("%d
",ans);
    }
    return 0;
}