CTSC2018 混合果汁（整体二分+线段树）

发表于 |
字数统计: 1,334字 | 阅读时长 ≈ 7min

问题描述

小 R 热衷于做黑暗料理，尤其是混合果汁。

商店里有 $n$ 种果汁，编号为 $0, 1, 2, . . . , n − 1$。$i$ 号果汁的美味度是 $d_i$，每升价格为 $p_i$。小 R 在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，$i$ 号果汁最多只能添加 $l_i$ 升。

现在有 $m$ 个小朋友过来找小 R 要混合果汁喝，他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中，第 $j$ 个小朋友希望他得到的混合果汁总价格不大于 $g_j$，体积不小于 $L_j$。在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

输入格式

输入第一行包含两个正整数 $n, m$，表示果汁的种数和小朋友的数量。接下来 $n$ 行，每行三个正整数 $d_i, p_i, l_i$，表示 $i$ 号果汁的美味度为 $d_i$，每升价格为$p_i$，在一瓶果汁中的添加上限为 $l_i$。

接下来 $m$ 行依次描述所有小朋友：每行两个数正整数 $g_j, L_j$ 描述一个小朋友，表示他最多能支付 $g_j$ 元钱，他想要至少 $L_j$ 升果汁。

输出格式

对于所有小朋友依次输出：对于每个小朋友，输出一行，包含一个整数，表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求，则输出 $−1$。

样例输入

1
2
3
4
5
6
7
8
3 4
1 3 5
2 1 3
3 2 5
6 3
5 3
10 10
20 10

样例输出

1
2
3
4
3
2
-1
1

提示

对于所有的测试数据，保证 $n, m \le 100000$，$1 \le d_i, p_i, l_i \le 10^5，1 \le g_j, L_j \le 10^{18}$。

测试点编号 $n=$ $m=$ 其他限制
$1,2,3$ $10$ $10$ 无
$4,5,6$ $500$ $500$ 无
$7,8,9$ $5000$ $5000$ 无
$10,11,12$ $100000$ $100000$ $p_i=1$
$13,14,15$ $100000$ $100000$ $l_i=1$
$16,17,18,19,20$ $100000$ $100000$ 无

容易想到对询问二分答案，那么只能选择美味度大于 $mid$ 的果汁，然后就贪心的选便宜的就行了，这个贪心可以用线段树完成，按价格建线段树，然后记录每个价格的可用体积，查询就在线段树上二分即可得到最低价格

处理多次询问考虑整体二分，这里跟 $Meteors$ 那题很像，整体二分过程中维护一颗全局线段树就行了

复杂度 $O(n\log^2n)$

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 100005
#define ll long long
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
inline ll _R()
{
    char t=GC;ll x=0;
    while(t<48||t>57)t=GC;
    for(;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
    return x;
}
struct juice{ll p,l;int d;}A[N];
struct query{ll g,l;int id;}Q[N],q[N];
bool operator<(juice a,juice b){return a.d>b.d;}
int n,m,Ans[N],cur;
struct node
{
    node *ls,*rs;
    ll suml,sump;
}seg[N<<1],*rt,*tl,*null;
void Init()
{
    rt=tl=null=seg;
    null->ls=null->rs=null;
}
void build(node *&p,int l,int r)
{
    p=++tl;p->ls=p->rs=null;
    if(l==r)return;
    int mid=l+r>>1;
    build(p->ls,l,mid);
    build(p->rs,mid+1,r);
}
void update(node *p)
{
    node *l=p->ls,*r=p->rs;
    p->sump=l->sump+r->sump;
    p->suml=l->suml+r->suml;
}
void modify(node *p,int l,int r,int k,ll d)
{
    if(l==r){p->suml+=d;p->sump=p->suml*l;return;}
    int mid=l+r>>1;
    if(k<=mid)modify(p->ls,l,mid,k,d);
    else modify(p->rs,mid+1,r,k,d);
    update(p);
}
ll getmin(node *p,int l,int r,ll d)
{
    if(d==0)return 0;
    if(l==r)return d*l;
    int mid=l+r>>1;
    if(p->ls->suml>=d)return getmin(p->ls,l,mid,d);
    return p->ls->sump+getmin(p->rs,mid+1,r,d-p->ls->suml);
}
void solve(int l,int r,int ql,int qr)
{
    if(ql>qr)return;
    if(l==r&&r!=n){for(int i=ql;i<=qr;i++)Ans[Q[i].id]=A[l].d;return;}
    int mid=l+r>>1,pl=ql-1,pr=qr+1;
    while(cur<mid)cur++,modify(rt,1,1e5,A[cur].p,A[cur].l);
    while(cur>mid)modify(rt,1,1e5,A[cur].p,-A[cur].l),cur--;
    for(int i=ql;i<=qr;i++)q[i]=Q[i];
    for(int i=ql;i<=qr;i++)
    {
        if(q[i].l>rt->suml)Q[--pr]=q[i];
        else if(getmin(rt,1,1e5,q[i].l)<=q[i].g)Q[++pl]=q[i];
        else Q[--pr]=q[i];
    }
    if(l==r)
    {
        for(int i=ql;i<=pl;i++)Ans[Q[i].id]=A[l].d;
        for(int i=pr;i<=qr;i++)Ans[Q[i].id]=-1;return;
    }
    solve(l,mid,ql,pl);solve(mid+1,r,pr,qr);
}
int main()
{
    int i,j,k,x,y,z;
    n=_R();m=_R();
    for(i=1;i<=n;i++)A[i].d=_R(),A[i].p=_R(),A[i].l=_R();
    for(i=1;i<=m;i++)Q[i].g=_R(),Q[i].l=_R(),Q[i].id=i;
    sort(A+1,A+n+1);
    Init();build(rt,1,1e5);
    solve(1,n,1,m);
    for(i=1;i<=m;i++)printf("%d\n",Ans[i]);
}