bzoj 5343 混合果汁

Posted on | Edited on | Views:

二分答案 + 主席树.

将美味度离散化,并将所有果汁按照美味度从小到大排序.

可以用主席树维护单价区间能购买到的最大体积之和与总金额之和,对美味度可持久化.

对于每个询问,二分答案 $ans$ ,只考虑美味度 $\ge ans$ 的果汁.

显然应该贪心地选,尽可能选便宜的凑够体积.

于是查询时在主席树上将美味度 $\ge ans$ 的部分抠出来,进行二分.

若左儿子内的体积够,就返回左儿子的答案.

否则将需要的体积减去左儿子内的体积,返回右儿子的答案加上左儿子的所有价格.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
const ll inf=1e18;
int n,m,td,tp;
ll D[MAXN],P[MAXN];
struct Juice
{
	int d,p,lim;
	bool operator < (const Juice &rhs) const
	{
		return d<rhs.d;
	}
}a[MAXN];
int rt[MAXN];
struct PreSegtree
{
	int idx;
	struct node
	{
		int ls,rs;
		ll sumv,sumc;
		node(){ls=rs=sumv=sumc=0;}
	}Tree[MAXN*30];
	PreSegtree(){idx=0;}
	void upd(int &cur,int pre,int l,int r,int cost,ll v,ll c)
	{
		cur=++idx;
		Tree[cur]=Tree[pre];
		Tree[cur].sumv+=v;
		Tree[cur].sumc+=c;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		if(cost<=mid)
			upd(Tree[cur].ls,Tree[pre].ls,l,mid,cost,v,c);
		else
			upd(Tree[cur].rs,Tree[pre].rs,mid+1,r,cost,v,c);
	}
#define root1 Tree[Lrt]
#define root2 Tree[Rrt]
	ll query(int Lrt,int Rrt,int l,int r,ll tmpv)
	{
		if(root2.sumv-root1.sumv<tmpv)
			return inf;
		if(root2.sumv-root1.sumv==tmpv)
			return root2.sumc-root1.sumc;
		if(l==r)
			return tmpv*P[l];			
		int mid=(l+r)>>1;
		ll totl=Tree[root2.ls].sumv-Tree[root1.ls].sumv;
		if(totl>=tmpv)
			return query(root1.ls,root2.ls,l,mid,tmpv);
		return Tree[root2.ls].sumc-Tree[root1.ls].sumc+query(root1.rs,root2.rs,mid+1,r,tmpv-totl);
	}
}T;
int pos[MAXN];
bool check(int k,ll budget,ll tmpv)
{
	int rt1=rt[pos[k]-1],rt2=rt[n];
	ll cost=T.query(rt1,rt2,1,tp,tmpv);
	return cost<=budget;
}
void init()
{
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i)
	{
		int x=a[i].d;
		if(!pos[x])
			pos[x]=i;
		T.upd(rt[i],rt[i-1],1,tp,a[i].p,a[i].lim,1LL*a[i].lim*P[a[i].p]);
	}
}
void solve()
{
	for(int i=1;i<=m;++i)
	{
		ll budget=read(),tmpv=read();
		int L=1,R=td,res=-1;
		while(L<=R)
		{
			int mid=(L+R)>>1;
			if(check(mid,budget,tmpv))
				res=mid,L=mid+1;
			else
				R=mid-1;
		}
		if(res==-1)
			puts("-1");
		else
			printf("%lld\n",D[res]);
	}
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
	{
		D[i]=a[i].d=read();
		P[i]=a[i].p=read();
		a[i].lim=read();
	}
	sort(D+1,D+1+n);
	td=unique(D+1,D+1+n)-D-1;
	for(int i=1;i<=n;++i)
		a[i].d=lower_bound(D+1,D+1+td,a[i].d)-D;
	sort(P+1,P+1+n);
	tp=unique(P+1,P+1+n)-P-1;
	for(int i=1;i<=n;++i)
		a[i].p=lower_bound(P+1,P+1+tp,a[i].p)-P;
	init();
	solve();
	return 0;
}