题解：P4602 [CTSC2018] 混合果汁

· · 题解

考虑对于单次询问，显然可以二分，每次将美味度大于等于 mid 的果汁放在一起按价格排序，贪心地计算能否在 g_j 的限制内买够 L_j 的果汁。

多次询问可二分的问题，这提醒我们去做整体二分。但是有一个问题，我们无法在整体二分搜索树上的每个节点都对大于等于 mid 的果汁进行排序计算，不然显然会炸。有一个解决方案是，将一堆没有交集的搜索树节点放在一起计算，用线段树维护按美味度排序后的某个后缀果汁集合。具体地，按照美味度倒着扫，对于每个美味度在 [L,R] 的搜索树节点，我们先将 [mid+1,R] 的果汁加入线段树，然后处理节点上的询问，再将 [L,mid] 的果汁加入线段树。换言之，我们要按层遍历搜索树，并且每一层还要倒着遍历！一个方案是用 std::vector 存储当前层的搜索树节点写 bfs。时间复杂度 O((n+m)\log^2n)。

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,lsh[maxn];
ll ans[maxn];
struct jui{
    int d,p,l;
}a[maxn];
struct{
    int id;
    ll g,l;
}b[maxn],hp[maxn];
int rt,tot;
struct{
    int ls,rs,d,p,l;
    ll smp,sml;
}tr[maxn<<1];
#define ls(id) tr[id].ls
#define rs(id) tr[id].rs
#define d(id) tr[id].d
#define p(id) tr[id].p
#define l(id) tr[id].l
#define smp(id) tr[id].smp
#define sml(id) tr[id].sml
il void pushup(int id){
    smp(id)=smp(ls(id))+smp(rs(id));
    sml(id)=sml(ls(id))+sml(rs(id));
}
il void insert(int &id,int L,int R,int p,int d,int l){
    if(!id){
        id=++tot;
        ls(id)=rs(id)=0;
        d(id)=p(id)=l(id)=0;
        smp(id)=sml(id)=0;
    }
    if(L==R){
        smp(id)=lsh[p]*1ll*l;
        sml(id)=l;
        d(id)=d,p(id)=lsh[p],l(id)=l;
        return ;
    }
    int mid=(L+R)>>1;
    if(p<=mid){
        insert(ls(id),L,mid,p,d,l);
    }
    else{
        insert(rs(id),mid+1,R,p,d,l);
    }
    pushup(id);
}
il ll query(int id,int L,int R,ll g){
    if(!id){
        return 0;
    }
    if(L==R){
        return min(g/p(id),l(id)*1ll);
    }
    int mid=(L+R)>>1;
    if(smp(ls(id))>=g){
        return query(ls(id),L,mid,g);
    }
    else{
        return query(rs(id),mid+1,R,g-smp(ls(id)))+sml(ls(id));
    }
}
#undef ls
#undef rs
#undef d
#undef p
#undef l
#undef smp
#undef sml
struct node{
    int L,R,l,r;
    node(int L=0,int R=0,int l=0,int r=0):L(L),R(R),l(l),r(r){}
};
vector<node> q[2];
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].d>>a[i].p>>a[i].l;
    }
    sort(a+1,a+n+1,[](const jui &x,const jui &y){return x.p<y.p;});
    for(int i=1;i<=n;i++){
        lsh[i]=a[i].p;
        a[i].p=i;
    }
    sort(a+1,a+n+1,[](const jui &x,const jui &y){return x.d>y.d;});
    for(int i=1;i<=m;i++){
        cin>>b[i].g>>b[i].l;
        b[i].id=i;
    }
    q[0].pb(node(1,1e5,1,m));
    int cur=0;
    while(q[cur].size()){
        q[cur^1].clear();
        int now=1;
        rt=tot=0;
        for(node x:q[cur]){
            int L=x.L,R=x.R,l=x.l,r=x.r;
//          cout<<L<<" "<<R<<":\n";
//          for(int i=l;i<=r;i++){
//              cout<<b[i].id<<" ";
//          }
//          puts("");
            if(l>r){
                continue;
            }
            if(L==R){
                while(now<=n&&a[now].d>=L){
                    insert(rt,1,n,a[now].p,a[now].d,a[now].l);
                    now++;
                }
                for(int i=l;i<=r;i++){
                    if(query(rt,1,n,b[i].g)>=b[i].l){
                        ans[b[i].id]=L;
                    }
                    else{
                        ans[b[i].id]=-1;
                    }
                }
                continue;
            }
            int mid=(L+R)>>1;
            while(now<=n&&a[now].d>mid){
                insert(rt,1,n,a[now].p,a[now].d,a[now].l);
                now++;
            }
            int pl=l,pr=r;
            for(int i=l;i<=r;i++){
                if(query(rt,1,n,b[i].g)>=b[i].l){
                    hp[pr--]=b[i];
                }
                else{
                    hp[pl++]=b[i];
                }
            }
            for(int i=l;i<pl;i++){
                b[i]=hp[i];
            }
            for(int i=pl;i<=r;i++){
                b[i]=hp[i]; 
            }
            q[cur^1].pb(node(mid+1,R,pl,r));
            q[cur^1].pb(node(L,mid,l,pr));
            while(now<=n&&a[now].d>=L){
                insert(rt,1,n,a[now].p,a[now].d,a[now].l);
                now++;
            }
        }
        cur^=1;
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}
}
int main(){return asbt::main();}