首先答案显然可以二分。
于是问题变成给定 \(mid\)，求所有美味度不小于 \(mid\) 的果汁种类中混合出至少 \(L_i\) 升的最小总价格。
其实是个人都能看出来这个地方的至少是没用的，最优解肯定是恰好这么多……
如果只看不小于 \(mid\) 的果汁种类，可以以每一种果汁的单价建一棵权值线段树，每个结点保存总体积与总价。
于是直接权值线段树上二分即可求得最小总价格。
实际上用了两个二分，于是复杂度是 \(O(\log^2 n)\) 的。
然鹅我们还要多组询问，与其离线整体二分，不如直接把线段树可持久化了。
代码： 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
using namespace std;
const int N = 1e5;
int n,m;
struct note
{
int d,p,l;
} a[N + 5];
vector<int> p[N + 5];
struct node
{
long long cnt,sum;
int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5];
void insert(int x,int k,int &p,int tl,int tr)
{
static int tot = 0;
seg[++tot] = seg[p],seg[p = tot].cnt += k,seg[p].sum += (long long)x * k;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
}
long long query(int p,int tl,int tr,long long L)
{
if(!p || tl == tr)
return L * tl;
int mid = tl + tr >> 1;
return L <= seg[seg[p].ls].cnt ? query(seg[p].ls,tl,mid,L) : seg[seg[p].ls].sum + query(seg[p].rs,mid + 1,tr,L - seg[seg[p].ls].cnt);
}
inline int query(long long g,long long L)
{
int l = 1,r = N,mid,ret = -1;
while(l <= r)
{
mid = l + r >> 1;
L <= seg[rt[mid]].cnt && query(rt[mid],1,N,L) <= g ? (ret = mid,l = mid + 1) : r = mid - 1;
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
scanf("%d%d%d",&a[i].d,&a[i].p,&a[i].l),p[a[i].d].push_back(i);
for(register int i = N;i && (rt[i] = rt[i + 1],1);--i)
for(register int j = 0;j < p[i].size();++j)
insert(a[p[i][j]].p,a[p[i][j]].l,rt[i],1,N);
long long g,L;
for(;m;--m)
scanf("%lld%lld",&g,&L),printf("%d\n",query(g,L));
}