【BZOJ5343】【CTSC2018】混合果汁（整体二分）

传送门

似乎主席树更简单？
将果汁权值排序后线段树维护一下前缀和
可以先加一个美味度$-1$,费用$0$,无限多的果汁
还有线段树可以记一个now表示记录了哪些，这样就不用每次暴力更改了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
inline int read(){
    int res=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
    while(isdigit(ch)) res=(res+(res<<2)<<1)+(ch^48),ch=getchar();
    return res*f;
}
const int N=100005;
struct juice{
    ll d,p,l;
    friend inline bool operator <(const juice &a,const juice &b){
        return a.d>b.d;
    }
}p[N];
const int inf=1e12;
struct ask{
    ll l,g,id;
}q[N],q1[N],q2[N];
int n,m;
#define lc (u<<1)
#define rc ((u<<1)|1)
#define mid ((l+r)>>1)
ll tr[N<<2],sum[N<<2],ans[N],now;
inline void pushup(int u){
    sum[u]=sum[lc]+sum[rc];
    tr[u]=tr[lc]+tr[rc];
}
void update(int u,int l,int r,int p,ll k){
    if(l==r){sum[u]+=k,tr[u]+=1ll*l*k;return;}
    if(p<=mid)update(lc,l,mid,p,k);
    else update(rc,mid+1,r,p,k);
    pushup(u);
}
ll query(int u,int l,int r,int p){
    if(l==r)return p*l;
    if(sum[lc]>=p)return query(lc,l,mid,p);
    else return tr[lc]+query(rc,mid+1,r,p-sum[lc]);
}
void solve(int l,int r,int st,int des){
    if(r<l||st>des)return;
    if(l==r){
        for(int i=st;i<=des;i++)ans[q[i].id]=p[l].d;
        return;
    }
    int cnt1=0,cnt2=0;
    while(now<mid)now++,update(1,1,N-5,p[now].p,p[now].l);
    while(now>mid)update(1,1,N-5,p[now].p,-p[now].l),now--;
    for(int i=st;i<=des;i++){
        if(sum[1]<q[i].l)q2[++cnt2]=q[i];
        else if(query(1,1,N-5,q[i].l)<=q[i].g)q1[++cnt1]=q[i];
        else q2[++cnt2]=q[i];
    }
    for(int i=1;i<=cnt1;i++)q[i+st-1]=q1[i];
    for(int i=1;i<=cnt2;i++)q[i+cnt1+st-1]=q2[i];
    solve(l,mid,st,st+cnt1-1),solve(mid+1,r,st+cnt1,des);
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)p[i].d=read(),p[i].p=read(),p[i].l=read();
    p[++n]=(juice){-1,0,inf};
    for(int i=1;i<=m;i++)q[i].id=i,q[i].g=read(),q[i].l=read();
    sort(p+1,p+n+1);
    solve(1,n,1,m);
    for(int i=1;i<=m;i++)cout<<ans[i]<<'
';
}