自动搬运

查看原文

来自洛谷，原作者为

	伟大的王夫子 hanser忠实粉丝，爱好ACG、古风

搬运于2025-08-24 22:16:13，当前版本为作者最后更新于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);
	}
}