首先考虑$m=1$的情况，这个时候显然直接二分+按价格贪心就可以了. 如果直接把这个算法应用到原题，复杂度是$\mathcal O(nm\log^2 n)$. 结果我就开始想整体二分，想复杂了.
事实上这种情况下还有一种优化复杂度的思路，就是使用某个数据结构加速单次的查询，即要支持：
- 在果汁集合确定的情况下，快速查询某个$(g,L)$是否可行
- 可持久化地加入一种果汁
不考虑可持久化的情况下，我的第一反应是按价格顺序维护平衡树然后在上面二分. 这么做的话要可持久化会比较复杂，一个很自然的思路是想办法用线段树去维护它.
线段树相比平衡树一个很大的缺陷就是不能从中间插入，同样有一个很自然的思路就是预先留好空间，但是一开始存的是0，要插入的时候再将其激活.
最后复杂度是$\mathcal O(n\log n+m\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
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
using namespace std;
struct jc{
ele d,p,l;
inline bool operator<(jc b)const{
return p<b.p;
}
}a[maxn];
template<class T>
struct mempool{
T *s,*t;
mempool():s(NULL),t(NULL){}
inline T* alloc(){
return s==t && (t=(s=new T[K])+K),s++;
}
};
struct node{
ele sl,sp;
node *l,*r;
};
ele n,m,b[maxn];
node *T[maxn];
mempool<node> np;
inline bool cmp(ele i,ele j){
return a[i].d>a[j].d;
}
node* build(ele l,ele r){
node *p=np.alloc();
p->sl=p->sp=0;
if (l==r) p->l=p->r=NULL;
else{
ele mid=(l+r)>>1;
p->l=build(l,mid);
p->r=build(mid+1,r);
}
return p;
}
inline void maintain(node *x){
x->sl=x->l->sl+x->r->sl;
x->sp=x->l->sp+x->r->sp;
}
node* upd(node *x,ele u,ele v,ele i){
node *p=np.alloc(); *p=*x;
if (u==v){
p->sl=a[u].l;
p->sp=a[u].l*a[u].p;
}
else{
ele mid=(u+v)>>1;
if (i<=mid) p->l=upd(p->l,u,mid,i);
else p->r=upd(p->r,mid+1,v,i);
maintain(p);
}
return p;
}
ele qry(node *x,ele u,ele v,ele k){
if (u==v) return k*a[u].p;
ele mid=(u+v)>>1;
if (k<=x->l->sl) return qry(x->l,u,mid,k);
return qry(x->r,mid+1,v,k-x->l->sl)+x->l->sp;
}
inline bool test(ele r,ele g,ele L){
return T[r]->sl>=L && qry(T[r],0,n-1,L)<=g;
}
int main(){
scanf("%lld%lld",&n,&m);
for (int i=0; i<n; ++i){
ele d,p,l;
scanf("%lld%lld%lld",&d,&p,&l);
a[i]=(jc){d,p,l};
}
sort(a,a+n);
for (int i=0; i<n; ++i) b[i]=i;
sort(b,b+n,cmp);
T[0]=build(0,n-1);
for (int i=0; i<n; ++i) T[i+1]=upd(T[i],0,n-1,b[i]);
while (m--){
ele g,L;
scanf("%lld%lld",&g,&L);
if (T[n]->sl<L) puts("-1");
else{
ele l=0,r=n;
while (r-l>1){
ele mid=(l+r)>>1;
if (test(mid,g,L)) r=mid; else l=mid;
}
if (test(r,g,L)) printf("%lld\n",a[b[r-1]].d);
else puts("-1");
}
}
return 0;
}