BZOJ_5343_[Ctsc2018]混合果汁_二分答案+主席树

BZOJ_5343_[Ctsc2018]混合果汁_二分答案+主席树

题意：给出每个果汁的价格p，美味度d，最多能放的体积l。定义果汁混合后的美味度为果汁的美味度的最小值。

m次询问，要求花费不大于g，总体积不小于L，求最大美味度，如果不能满足，输出-1。

---

二分答案。然后转变为求价格前L小的果汁之和。

类似任务查询系统那道题。

权值线段树维护结点总体积和全部购买的总花费。

按美味度建立主席树即可。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

#define N 100050

#define inf 100000

struct J {

	int d,p,l;

	bool operator < (const J &x) const {

		return d<x.d;

	}

}a[N];

int n,root[N],ls[N*20],rs[N*20],m,cnt;

ll siz[N*20],cost[N*20],s[N];

void insert(int l,int r,int idx,int x,int &y) {

	y=++cnt; siz[y]=siz[x]+a[idx].l; cost[y]=cost[x]+1ll*a[idx].l*a[idx].p;

	if(l==r) return ;

	int mid=(l+r)>>1;

	if(a[idx].p<=mid) rs[y]=rs[x],insert(l,mid,idx,ls[x],ls[y]);

	else ls[y]=ls[x],insert(mid+1,r,idx,rs[x],rs[y]);

}

ll query(int l,int r,ll c,int x,int y) {

	if(l==r) return c*l;

	int mid=(l+r)>>1;

	ll sizls=siz[ls[y]]-siz[ls[x]];

	if(sizls>=c) return query(l,mid,c,ls[x],ls[y]);

	else return query(mid+1,r,c-sizls,rs[x],rs[y])+cost[ls[y]]-cost[ls[x]];

}

bool check(int x,ll need,ll val) {

	if(s[n]-s[x-1]<need) return 0;

	return query(1,inf,need,root[x-1],root[n])<=val;

}

int main() {

	scanf("%d%d",&n,&m);

	int i;

	for(i=1;i<=n;i++) scanf("%d%d%d",&a[i].d,&a[i].p,&a[i].l);

	sort(a+1,a+n+1);

	for(i=1;i<=n;i++) insert(1,inf,i,root[i-1],root[i]),s[i]=s[i-1]+a[i].l;

	ll x,y;

	while(m--) {

		scanf("%lld%lld",&x,&y);

		int l=1,r=n+1;

		while(l<r) {

			int mid=(l+r)>>1;

			if(check(mid,y,x)) l=mid+1;

			else r=mid;

		}

		printf("%d\n",l-1?a[l-1].d:-1);

	}

}