P4602 [CTSC2018]混合果汁

题意

显然答案是可以二分的，我们二分一个\(mid\)，\(check\)只需要将所有价值大于等于\(mid\)的按照价格从小到大排序，从头开始取，一直取到满足条件即可。

对于\(m\)组询问，我们考虑整体二分。
假设当前二分的是\(mid\)，我们用一颗线段树维护所有美味值大于等于\(mid\)的果汁的信息。

线段树的下标为价格，每个节点存两个信息：\(sum1\)表示在节点所代表的的价格区间中果汁的数量，\(sum2\)表示在节点所代表的的价格区间中果汁的总价钱。

之后对于每个询问\((g_i,l_i)\)，我们只需要在线段树上二分便可得出取\(l_i\)升美味值大于等于\(mid\)的果汁需要花费的最小价钱。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
const int maxn=100010;
const int UP=100000;
const int inf=1e18;
int n,m,now,tot;
int ans[maxn];
struct Juice{int d,p,l;}ju[maxn];
struct Query{int g,l,id;}qr[maxn],tmpl[maxn],tmpr[maxn];
struct Seg
{
    #define sum1(p) (seg[p].sum1)
    #define sum2(p) (seg[p].sum2)
    int sum1,sum2;
}seg[maxn<<2];
inline int read()
{
    char c=getchar();int res=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
inline bool cmp(Juice a,Juice b){return a.d>b.d;}
inline void up(int p)
{
    sum1(p)=sum1(ls(p))+sum1(rs(p));
    sum2(p)=sum2(ls(p))+sum2(rs(p));
}
void insert(int p,int l,int r,int k,int v)
{
    if(l==r){sum1(p)+=v;sum2(p)+=k*v;return;}
    int mid=(l+r)>>1;
    if(k<=mid)insert(ls(p),l,mid,k,v);
    else insert(rs(p),mid+1,r,k,v);
    up(p);
}
int query(int p,int l,int r,int v)
{
    if(!v)return 0;
    if(l==r)return l*v;
    int mid=(l+r)>>1;
    if(sum1(ls(p))>=v)return query(ls(p),l,mid,v);
    else return sum2(ls(p))+query(rs(p),mid+1,r,v-sum1(ls(p)));
}
inline void solve(int l,int r,int L,int R)
{
    if(L>R)return;
    if(l==r)
    {
        for(int i=L;i<=R;i++)ans[qr[i].id]=ju[l].d;
        return;
    }
    int mid=(l+r)>>1,cntl=0,cntr=0;
    while(now<mid)now++,insert(1,1,UP,ju[now].p,ju[now].l);
    while(now>mid)insert(1,1,UP,ju[now].p,-ju[now].l),now--;
    for(int i=L;i<=R;i++)
    {
        if(qr[i].l>sum1(1))tmpr[++cntr]=qr[i];
        else if(query(1,1,UP,qr[i].l)<=qr[i].g)tmpl[++cntl]=qr[i];
        else tmpr[++cntr]=qr[i];
    }
    for(int i=1;i<=cntl;i++)qr[L+i-1]=tmpl[i];
    for(int i=1;i<=cntr;i++)qr[L+cntl+i-1]=tmpr[i];
    solve(l,mid,L,L+cntl-1);solve(mid+1,r,L+cntl,R);
}
signed main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)ju[i].d=read(),ju[i].p=read(),ju[i].l=read();
    ju[++n]=(Juice){-1,0,inf};
    for(int i=1;i<=m;i++)qr[i].g=read(),qr[i].l=read(),qr[i].id=i;
    sort(ju+1,ju+n+1,cmp);
    solve(1,n,1,m);
    for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
    return 0;
}