P5986 [PA2019]Szprotki i szczupaki 题解

伟大的王夫子 · 2022-08-21 19:13:57 · 题解

先考虑暴力。容易想到贪心：每次吃所有能吃的小鱼中最大的鱼，一个个暴力吃，可以得到正确答案。

我们再考虑一下如何优化贪心的过程。设鲨鱼当前重量为 s，所有他吃不了的小鱼的重量最少为 x。显然 x \ge s。容易看出，在 s \le x 时，这条鲨鱼能吃的小鱼的集合不变，我们直接统一处理即可。

我们可以用一个线段树维护当前所有的鱼，先全部读入，并且将重量离散化，每次求出大于等于当前鲨鱼重量的重量最小的鱼，若其重量为 x，那么吃完这一轮后，鲨鱼至少要将重量变为 \min(k, x +1)。若无法到达，那么一定无解（因为到达不了 x+1，吃不了其它的鱼）。

再证明一下时间复杂度。若当前鲨鱼重量为 s，大于等于当前鲨鱼重量的重量最小的鱼重量为 x。经过一步操作之后，s 的最小值为 x +1。那么再下一步，它就一定会吃一条重量 \ge x 的鱼。而刚开始时 s \le x，故这会使鲨鱼重量翻倍。因此每一次求答案，这种步骤最多重复 O(\log k) 次。其中 k 为要求达到的重量。

再加上线段树的 O(n \log n)，总复杂度为 O(n \log n \log k)。较为卡常，原题时间限制 20s，loj 7s，在一秒的时间内过就必须开 O2。

代码实现时要注意常数，否则开了 O2 仍有很大可能不过。好好想清楚，毕竟这题细节挺多的。

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
using LL = long long;
int n, m, tt;
LL b[N];
struct {
    int op;
    LL x, w;
} a[N];
struct Seg {
    struct node {
        int l, r, cnt;
        LL sum;//懒标记直接不需要，如果sum = 0则直接返回，类似永久化标记。 
    } t[N << 2];
    node stk[N << 2];
    int po[N << 2], tp;
    bool vis[N << 2];
    inline void Up(int p) {
        t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
        t[p].cnt = t[p << 1].cnt + t[p << 1 | 1].cnt;
    }
    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l == r) {
            t[p].cnt = l == tt;
            t[p].sum = (l == tt) * b[tt];
            return;
        }
        int mid(l + r >> 1);
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        Up(p);
    }
    void change(int p, int x, int v) {
        if (t[p].l == t[p].r) {
            t[p].sum += v * b[x];
            t[p].cnt += v;
            return;
        }
        int mid(t[p].l + t[p].r >> 1);
        if (x <= mid) change(p << 1, x, v);
        else change(p << 1 | 1, x, v);
        Up(p);
    }
    int ask(int p, int x) {
        if (!t[p].sum) return 0;
        if (x <= t[p].l) {
            if (t[p].l == t[p].r) return t[p].l;
            int t = ask(p << 1, x);
            if (t) return t;
            else return ask(p << 1 | 1, x);
        }
        int mid(t[p].l + t[p].r >> 1);
        if (x <= mid) {
            int t = ask(p << 1, x);
            if (t) return t;
        }
        return ask(p << 1 | 1, x);
    }
    void work(int p) {
        if (!vis[p]) vis[p] = 1, stk[++tp] = t[p], po[tp] = p;
    }
    void modify(int p, int r, LL &foo, int &cnt) {
        if (!t[p].sum || foo <= 0) return;
        work(p);
        if (t[p].r <= r) {
            if (t[p].l == t[p].r) {
                int cc = min((foo - 1) / b[t[p].l] + 1, 1ll * t[p].cnt);
                t[p].cnt -= cc;
                t[p].sum -= cc * b[t[p].l];
                cnt += cc;
                foo -= cc * b[t[p].l];
            } else {
                if (t[p << 1 | 1].sum <= foo) {
                    work(p << 1 | 1);
                    foo -= t[p << 1 | 1].sum, cnt += t[p << 1 | 1].cnt;
                    t[p << 1 | 1].sum = 0, t[p << 1 | 1].cnt = 0;
                    modify(p << 1, r, foo, cnt);
                } else modify(p << 1 | 1, r, foo, cnt);
                Up(p);//必须记得更新，否则就会少减去一些 
            }
            return;
        }
        int mid(t[p].l + t[p].r >> 1);
        if (r > mid) modify(p << 1 | 1, r, foo, cnt);
        modify(p << 1, r, foo, cnt);
        Up(p);
    }
    int calc(LL ss, LL kk) {
        if (ss >= kk) return 0;//不用吃 
        if (ss <= b[1]) return -1;//需要吃但是没得吃 
        int ans = 0;
        while (ss < kk) {
            int pos = lower_bound(b + 1, b + tt + 1, ss) - b, vv = pos;
            vv = ask(1, vv);
            LL vvv = min(b[vv] + 1, kk) - ss;//需要吃多少 t.ask(1, vv)
            int mfood = pos - 1;
            LL vvvv = vvv;
            modify(1, mfood, vvvv, ans);
            if (vvvv > 0) {
                ans = -1;
                break;
            }
            ss += vvv - vvvv;
        }
        while (tp) {
            t[po[tp]] = stk[tp], vis[po[tp]] = 0;
            --tp;
        }
        return ans;
    }
} t;
int main() { 
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        a[i].op = 2;
        scanf("%lld", &a[i].x);
        b[++tt] = a[i].x;
    }
    scanf("%d", &m);
    for (int i = n + 1; i <= n + m; ++i) {
        scanf("%d%lld", &a[i].op, &a[i].x);
        if (a[i].op == 1) scanf("%lld", &a[i].w);
        else b[++tt] = a[i].x;
    }
    b[++tt] = 2e18;
    sort(b + 1, b + tt + 1);
    tt = unique(b + 1, b + tt + 1) - b - 1;
    for (int i = 1; i <= n + m; ++i)
        if (a[i].op != 1) a[i].x = lower_bound(b + 1, b + tt + 1, a[i].x) - b;
    t.build(1, 1, tt);
    for (int i = 1; i <= n + m; ++i) {
        if (a[i].op == 1) printf("%d\n", t.calc(a[i].x, a[i].w));
        if (a[i].op == 2) t.change(1, a[i].x, 1);
        if (a[i].op == 3) t.change(1, a[i].x, -1);
    }
}