[Luogu]P4602 混合果汁
本文最后更新于 81 天前,其中的信息可能已经有所发展或是发生改变。

一道神奇的整体二分线段树二分的题目。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/lp4602/

题意

果汁有美味度、单位价格、体积限制,要求总价格不超过某值、总体积不小于某值下,选择的果汁的美味度的最小值最大。

题解

考虑如果只有一个询问,可以二分果汁的最小美味度,只选择美味度 $> mid$ 的果汁。
考虑如何检验,贪心地选择单位价格较小的果汁。
那么如何快速地检验某个询问在当前的果汁集合中是否有解呢?
贪心地从单位价格较低的果汁开始选取。
可以考虑线段树二分,下标代表价格,维护可以获得的体积与对应价格,查询指定总价格上界最多能获取多少体积,判断是否满足要求即可。
可以用可持久化线段树维护,然而可以套上整体二分。
那么在整体二分中,对于 $solve(l,r,L,R)$,需要动态维护美味度在 $[mid + 1,n]$ 中的果汁集合。
可以考虑用 cdq分治 类似的方法,向左递归时可以利用上一层的信息,而向右递归时再撤销无用信息即可。

#include <algorithm>
#include <cstdio>
#include <ctype.h>
const int bufSize = 1e6;
#define int long long
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 5e5 + 100;
int n, m, ans[maxn], H[maxn], tot;
struct node
{
    int val, cost, limit;
} A[maxn];
bool cmp(const node& a, const node& b) { return a.val < b.val; }
struct query
{
    int id, money, amount;
} B[maxn], q1[maxn], q2[maxn];
long long asum[maxn << 2], csum[maxn << 2];
#define ls p << 1
#define rs p << 1 | 1
inline void pushup(int p) { asum[p] = asum[ls] + asum[rs], csum[p] = csum[ls] + csum[rs]; }
void modify(int l, int r, int p, int pos, long long k)
{
    if (l == r) return (void)(asum[p] += k, csum[p] += k * H[l]);
    int mid = l + r >> 1;
    if (pos <= mid) modify(l, mid, ls, pos, k);
    else modify(mid + 1, r, rs, pos, k);
    pushup(p);
}
long long havemoney, canget;
void ask(int l, int r, int p)
{
    if (havemoney <= 0) return;
    if (csum[p] <= havemoney) return (void)(havemoney -= csum[p], canget += asum[p]);
    if (l == r) return (void)(canget += havemoney / H[l], havemoney = 0);
    int mid = l + r >> 1;
    ask(l, mid, ls), ask(mid + 1, r, rs);
}
void solve(int l, int r, int L, int R)
{
    if (L > R) return;
    if (l == r)
    {
        for (int i = L; i <= R; ++i) ans[B[i].id] = A[l].val;
        return;
    }
    int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
    //push [mid + 1,r] in
    for (int i = mid + 1; i <= r; ++i) modify(1, tot, 1, A[i].cost, A[i].limit);
    for (int i = L; i <= R; ++i)
    {
        havemoney = B[i].money, canget = 0, ask(1, tot, 1);
        if (canget >= B[i].amount) q2[++cnt2] = B[i];
        else q1[++cnt1] = B[i];
    }
    for (int i = 1; i <= cnt1; ++i) B[L + i - 1] = q1[i];
    for (int i = 1; i <= cnt2; ++i) B[L + cnt1 + i - 1] = q2[i];
    solve(l, mid, L, L + cnt1 - 1);
    //now cancel [mid + 1,r] to goto the right division
    for (int i = mid + 1; i <= r; ++i) modify(1, tot, 1, A[i].cost, -A[i].limit);
    solve(mid + 1, r, L + cnt1, R);
}
signed main()
{
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(A[i].val), read(A[i].cost), read(A[i].limit), H[++tot] = A[i].cost;
    for (int i = 1; i <= m; ++i) read(B[i].money), read(B[i].amount), B[i].id = i;
    std::sort(H + 1, H + 1 + tot), tot = std::unique(H + 1, H + 1 + tot) - H - 1;
    for (int i = 1; i <= n; ++i) A[i].cost = std::lower_bound(H + 1, H + 1 + tot, A[i].cost) - H;
    std::sort(A + 1, A + 1 + n, cmp);
    solve(0, n, 1, m);
    for (int i = 1; i <= m; ++i) if (ans[i]) printf("%lld\n", ans[i]); else puts("-1");
    return 0;
}

题外话

其实线段树二分可以用树状数组倍增代替,而且常数奇小,这里也放上代码:

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 1e5 + 100;
int n, m, ans[maxn], H[maxn], hcnt, lg[maxn];
struct juice
{
    int taste, cost, limit;
} A[maxn];
bool cmp(const juice& a, const juice& b) { return a.taste < b.taste; }
struct query
{
    int id;
    long long money, need;
} B[maxn], q1[maxn], q2[maxn];
long long costsum[maxn], limitsum[maxn];
inline void add(int cost, int limit)
{
    long long totalcost = 1ll * H[cost] * limit;
    for (; cost <= hcnt; cost += cost & -cost) costsum[cost] += totalcost, limitsum[cost] += limit;
}
void solve(int l, int r, int L, int R)
{
    if(L > R) return;
    if(l == r)
    {
        for (int i = L; i <= R; ++i) ans[B[i].id] = A[l].taste;
        return;
    }
    int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
    for (int i = mid + 1; i <= r; ++i) add(A[i].cost, A[i].limit);
    for (int i = L; i <= R; ++i)
    {
        long long nowcost = 0, nowlimit = 0;
        int p = 0;
        for (int j = lg[hcnt - p]; j >= 0; j = std::min(j - 1, lg[hcnt - p]))
        {
            if (p + (1 << j) <= hcnt && nowcost + costsum[p + (1 << j)] <= B[i].money)
            {
                nowcost += costsum[p += (1 << j)], nowlimit += limitsum[p];
                if(nowlimit >= B[i].need) { q2[++cnt2] = B[i]; goto end; }
            }
        }
        if (limitsum[p + 1] + nowlimit >= B[i].need && (B[i].need - nowlimit) * H[p + 1] <= B[i].money - nowcost) q2[++cnt2] = B[i];
        else q1[++cnt1] = B[i];
        end: ;
    }
    for (int i = 1; i <= cnt1; ++i) B[L + i - 1] = q1[i];
    for (int i = 1; i <= cnt2; ++i) B[L + cnt1 + i - 1] = q2[i];
    solve(l, mid, L, L + cnt1 - 1);
    for (int i = mid + 1; i <= r; ++i) add(A[i].cost, -A[i].limit);
    solve(mid + 1, r, L + cnt1, R);
}
signed main()
{
    read(n), read(m);
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) read(A[i].taste), read(A[i].cost), read(A[i].limit), H[++hcnt] = A[i].cost;
    std::sort(H + 1, H + 1 + hcnt), hcnt = std::unique(H + 1, H + 1 + hcnt) - H - 1;
    for (int i = 1; i <= n; ++i) A[i].cost = std::lower_bound(H + 1, H + 1 + hcnt, A[i].cost) - H;
    for (int i = 1; i <= m; ++i) read(B[i].money), read(B[i].need), B[i].id = i;
    std::sort(A + 1, A + 1 + n, cmp);
    solve(0, n, 1, m);
    for (int i = 1; i <= m; ++i) if (ans[i]) printf("%d\n", ans[i]); else puts("-1");
    return 0;
}
本文标题:[Luogu]P4602 混合果汁
本文作者:Clouder
本文链接: https://www.codein.icu/lp4602/
转载请标明。

评论

  1. 3月前
    2020-10-27 12:48:23

    orz 整体二分之神clouder

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇