BZOJ5343【CTSC2018】混合果汁 <整体二分+线段树>

Problem

【CTSC2018】混合果汁

$\mathrm{Time\;Limit:\;40\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

$\mathrm{小R}$热衷于做黑暗料理，尤其是混合果汁。
商店里有$n$种果汁，编号为$0,1,2,\cdots,n-1$。$i$号果汁的美味度是$d_i$每升价格为$p_i$。$\mathrm{小R}$在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，$i$号果汁最多只能添加$l_i$升。
现在有$m$个小朋友过来找$\mathrm{小R}$要混合果汁喝，他们都希望$\mathrm{小R}$用商店里的果汁制作成一瓶混合果汁。其中，第$j$个小朋友希望他得到的混合果汁总价格不大于$g_j$，体积不小于$L_j$。
在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

Input

输入第一行包含两个正整数$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$升果汁。

Output

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

Sample Input

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

Sample Output

3
2
-1
1

HINT

对于所有的测试数据，保证$n,m\le10^5$，$1\le d_i,p_i,l_i\le10^5$，$1\le g_j,L_j\le10^{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$	无

标签：整体二分 线段树

Solution

整体二分常规题，考场上居然没做起签到题$\mathrm{QAQ}$

考虑对每个询问二分答案，对于当前答案$tans$，将所有美味度大于等于$tans$的果汁提出来，从花费小的往花费大的贪心选判断钱是否够即可。这样复杂度是$O(nm\log{n})$。
优化方式有两种：

1. 二分判断用主席树优化。首先将所有果汁按美味度从大到小排序并构建以$p$值为下标的值域线段树，存储的信息为价格在当前区间内的所有果汁的总体积以及总价格。在主席树上二分即可找到最小花费，这样$check$复杂度为$\log{p_{max}}$，总复杂度$O(m\log{n}\log{p_{max}})$
2. 对所有询问进行整体二分，中间用值域线段树维护。整体二分过程需要支持动态插入一种果汁，在线段树上二分得到最小花费。总复杂度$O(m\log{n}\log{p_{max}})$。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, sz, val[MAX_N+5], ans[MAX_N+5];
struct juice {int d, p, v;} a[MAX_N+5];
struct query {int id; lnt w, v;} q[MAX_N+5], tq[MAX_N+5];
struct node {lnt p, v;} tr[MAX_N<<2]; bool mrk[MAX_N+5];
bool cmpd(const juice &a, const juice &b) {return a.d > b.d;}
bool cmpp(const juice &a, const juice &b) {return a.p < b.p;}
void update(int v) {
    tr[v].p = tr[v<<1].p+tr[v<<1|1].p;
    tr[v].v = tr[v<<1].v+tr[v<<1|1].v;
}
void modify(int v, int s, int t, int p, int x) {
    if (s == t) {tr[v].p += 1LL*p*x, tr[v].v += x; return;}
    if (p <= mid) modify(v<<1, s, mid, p, x), update(v);
    else modify(v<<1|1, mid+1, t, p, x), update(v);
}
lnt query(int v, int s, int t, lnt x) {
    if (s == t) return 1LL*s*x;
    if (x <= tr[v<<1].v) return query(v<<1, s, mid, x);
    return tr[v<<1].p+query(v<<1|1, mid+1, t, x-tr[v<<1].v);
}
void bi_solve(int l, int r, int s, int t) {
    if (s > t) return;
    if (s == t) {
        for (int i = l; i <= r; i++)
            ans[q[i].id] = a[s].d;
        return;
    }
    int lsz = 0;
    for (int i = s; i <= mid; i++)
        modify(1, 1, MAX_N, a[i].p, a[i].v);
    for (int i = l; i <= r; i++)
        if (tr[1].v < q[i].v) mrk[i] = false;
        else {
            lnt tot = query(1, 1, MAX_N, q[i].v);
            mrk[i] = q[i].w >= tot, lsz += mrk[i];
        }
    for (int i = l, p1 = l, p2 = l+lsz; i <= r; i++)
        if (mrk[i]) tq[p1++] = q[i]; else tq[p2++] = q[i];
    for (int i = l; i <= r; i++) q[i] = tq[i];
    bi_solve(l+lsz, r, mid+1, t);
    for (int i = s; i <= mid; i++)
        modify(1, 1, MAX_N, a[i].p, -a[i].v);
    bi_solve(l, l+lsz-1, s, mid);
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(a[i].d), read(a[i].p), read(a[i].v);
    for (int i = 1; i <= m; i++) q[i].id = i, read(q[i].w), read(q[i].v);
    sort(a+1, a+n+1, cmpd), a[n+1].d = -1; bi_solve(1, m, 1, n+1);
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0;
}