www.cnblogs.com/shaokele/
题目地址： [loj2555]: [Ctsc2018]混合果汁
题目大意： 题目很简洁了：）####
题解：
二分答案，用主席树维护贪心操作
先按 (d) 排序，二分 (ans) **
主席树操作判断是否符合**
细节注意
AC代码
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int N=1e5+5,M=1800005;
int n,Q,sz,mxd,mxp;
int ls[M],rs[M],root[M];
ll g,L;
ll s[N],sum[M],val[M];
inline ll read(){
ll x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct node{
int d,p,l;
}A[N];
bool operator < (const node &a,const node &b){
return a.d<b.d;
}
void insert(int l,int r,int &u,int pre,int p,int L){
u=++sz;
sum[u]=sum[pre];val[u]=val[pre];
ls[u]=ls[pre];rs[u]=rs[pre];
sum[u]+=L;val[u]+=1ll*p*L;
if(l==r)return;
int mid=(l+r)>>1;
if(p<=mid)insert(l,mid,ls[u],ls[pre],p,L);
else insert(mid+1,r,rs[u],rs[pre],p,L);
}
ll ask(int l,int r,int u,int pre,ll L){
if(!u)return 0;
if(l==r)return L*l;
int mid=(l+r)>>1;
ll tmp=sum[ls[u]]-sum[ls[pre]];
if(tmp>=L)return ask(l,mid,ls[u],ls[pre],L);
else return val[ls[u]]-val[ls[pre]]+ask(mid+1,r,rs[u],rs[pre],L-tmp);
}
bool check(int mid,ll g,ll L){
int pre=lower_bound(A+1,A+n+1,(node){mid,0,0})-A-1;
if(s[n]-s[pre]<L)return 0;
else return ask(1,mxp,root[n],root[pre],L)<=g;
}
int main(){
n=read(),Q=read();
for(int i=1;i<=n;i++){
A[i].d=read(),A[i].p=read(),A[i].l=read();
mxd=max(mxd,A[i].d);
mxp=max(mxp,A[i].p);
}
sort(A+1,A+n+1);
for(int i=1;i<=n;i++)
s[i]=s[i-1]+A[i].l;
for(int i=1;i<=n;i++)
insert(1,mxp,root[i],root[i-1],A[i].p,A[i].l);
while(Q--){
g=read(),L=read();
int l=1,r=mxd,ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(check(mid,g,L)){
ans=mid;
l=mid+1;
}else r=mid-1;
}
printf("%d
",ans);
}
return 0;
}