贪心/反悔贪心|大鱼吃小鱼（fhq-treap/线段树二分+贪心）贪心

大鱼吃小鱼

description
solution
code

description 《大鱼吃小鱼》是一款经典的儿童益智类游戏，在游戏中，玩家所操控的“大鱼”只能吃掉体积严格小于自己的“小鱼”，然后玩家所操控的“大鱼”的体积就会增加“小鱼”的体积这么多的量。
知名主播 Bychaha 是《大鱼吃小鱼》这款游戏国服排行榜的前 50 名，为了辅助自己玩这款游戏，Bychaha 研发了一个脚本，该脚本能在游戏开始时快速计算出 Bychaha 需要按照什么顺序吃掉哪些鱼，才能在吃掉最少的鱼的前提下，达到通关所需的体积。在这个强大脚本的辅助下，Bychaha 很快便成功问鼎国服。
很遗憾的是，这一切都是 Bychaha 做的梦，他并不会写代码，所以他想要求助擅长写代码的你来帮助他实现这个脚本。为了降低难度，Bychaha 只需要知道他最少需要吃掉几只鱼才能达到通关的要求。
《大鱼吃小鱼》游戏总共可能发生以下三类事件：

l 1 S K 表示一局新游戏开始了，Bychaha 操控的“大鱼”的初始体积为 S，当“大鱼”的体积达到 K 或更大时，这一局游戏通关
l 2 W 表示游戏中新加入了一条体积为 W 的鱼
l 3 W 表示游戏中某条体积为 W 的鱼消失了，保证在此之前游戏中至少存在一条体积为 W 的鱼

《大鱼吃小鱼》游戏的每一关都是模拟吃鱼的过程，所以在通关之后，被吃掉的鱼并不会从游戏中消失，只有发生（3）号事件时，鱼才会真的消失。
【输入格式】
第一行一个整数 N，表示一开始游戏中存在的鱼的数量。
第二行 N 个数"，表示初始在游戏中的每条鱼的体积。
第三行一个整数 Q，表示事件的数量。
接下来 Q 行，表示发生的事件，格式如题面所述。
【输出格式】
对于每个（1）号事件，输出一个数，表示通关最少需要吃掉几只鱼，如果
无法通关，输出-1。
【样例输入输出】

4 1 4 8 1 15 1 2 3 1 2 4 1 2 5 1 3 3 1 3 5 1 3 16 1 4 16 1 8 17 1 100 101 1 100 115 1 3 9 2 2 1 3 9 3 4 1 3 9

1 2 -1 0 2 4 3 2 1 -1 3 2 -1

【提示】
游戏过程中 Bychaha 操控的“大鱼”是凭空产生的，在通关或者通关失败之后自动消失。
【数据规模与约定】
对于 10%的数据，，Q ≤ 10
对于 30%的数据，，Q ≤ 1000
另有 10%的数据，1 ≤ S，K ≤ 1012，且保证数据完全随机
另有 20%的数据，在任意时刻游戏中至多只有 100 种体积不同的鱼
对于 100%的数据，1 ≤ ≤ 3 ? 105，1 ≤ ≤ 105 1 ≤ ≤ 1012，1 ≤ S，K ≤ 1018
solution 第一遍读完题，应该就有很粗暴的思路：贪心地从能吃的最大体积鱼开始吃，一旦体积变大后可以吃新的大鱼，就又去吃新的大鱼，知道到达通关体积为止
有了主干，再修订一下细节枝叶：每次肯定是吃尽量少的鱼，体积刚好可以解锁一种新大鱼就吃新大鱼，如果新大鱼体积不小于通关体积，就只用吃到通关体积即可。
通关体积是大于等于，吃鱼必须严格大于
最后开始寻找工具实现：发现若干问题，想到用二分假模拟，利用线段树维护吃的鱼区间及个数，很不幸这非常难以实现在经过2h的调试加入新工具再维护后果断得出的结论
实际上，这种看似暴力模拟思路就是正解
直接模拟这个过程，可能会吃 n n n次鱼，考虑当前不能吃的最小体积的鱼
显然只有体积严格大鱼这种鱼的体积的时候，可吃鱼集合才会发生改变
如果这种鱼体积大于等于我们的通关体积，就只用吃到通关体积就行了
所以，我们只需要求每一步，对于不同可吃集合的鱼，需要最少吃多少条才能解锁下一步
由于贪心的吃法一定是吃一段连续的鱼（鱼体积是有序的），这个可以二分求出
【贪心/反悔贪心|大鱼吃小鱼（fhq-treap/线段树二分+贪心）】题解说的线段树二分毁了我好多温柔，还是fhq-treap大法好
接下来是时间复杂度的问题

假设现在我们的体积为 A A A，不能吃的鱼体积为 B B B，显然 A ≤ B A\le B A≤B
我们会吃掉一些鱼 x x x，得到 A + x > B A+x>B A+x>B
此时不能吃的鱼体积变为 C C C，显然 A + x ≤ C A+x\le C A+x≤C
这个时候又再次吃掉一些鱼 y y y，得到 A + x + y > C A+x+y>C A+x+y>C
且注意到 y ≥ B y\ge B y≥B，因为解锁可以吃 B B B的局面后还不能吃到 C C C，需要吃更多的鱼
所以有 A + x + y ≥ A + x + B > A + B ≥ A + A A+x+y\ge A+x+B>A+B\ge A+A A+x+y≥A+x+B>A+B≥A+A
也就是说两次二分（两个局面）就至少会翻倍最初体积，时间复杂度自然是 log ? \log log级别了

最后说说二分的实现

题解说线段树二分，结果造成了2h的无效输出，毁了我好多温柔，果然还是fhq-treap好
鱼的体积就是点的权值，一条鱼就是一个点，暴力贪心模拟
首先按现在鱼的体积分裂出能吃的鱼的集合
然后每一个局面可以知道现在体积与开启下一个局面的差，利用这个按体积和在可吃集合里分裂就能顺便知道使用了多少条鱼
接着就跳到下一个局面，如果开启不了就是 ? 1 -1 ?1
重点是吃了的鱼下一个局面需要直接跳过，我们的操作是合并是将吃的鱼暂时不合并回去，反而是将这个操作记录到栈里面
也就是说，做到了fhq-treap里面的鱼都是还未被吃掉了
最后这个询问完成后，一定要回溯操作，把模拟假装吃掉的鱼重新合并回去

code

#include #include #include using namespace std; #define int long long #define maxn 400005 struct node { int key, val, Min, sum, siz, lson, rson; }t[maxn]; int n, Q, cnt, root, top; int v[maxn], sta[maxn]; int NewNode( int x ) {int now = ++ cnt; t[now].siz = 1; t[now].key = rand(); t[now].sum = t[now].Min = t[now].val = x; return now; } void pushup( int x ) {t[x].siz = t[t[x].lson].siz + t[t[x].rson].siz + 1; t[x].sum = t[t[x].lson].sum + t[t[x].rson].sum + t[x].val; if( t[x].lson ) t[x].Min = t[t[x].lson].Min; else t[x].Min = t[x].val; } int build( int l, int r ) {if( l > r ) return 0; int mid = ( l + r ) >> 1; int now = NewNode( v[mid] ); t[now].lson = build( l, mid - 1 ); t[now].rson = build( mid + 1, r ); pushup( now ); return now; } int merge( int x, int y ) {if( ! x or ! y ) return x + y; if( t[x].key < t[y].key ) {t[x].rson = merge( t[x].rson, y ); pushup( x ); return x; } else {t[y].lson = merge( x, t[y].lson ); pushup( y ); return y; } } void split_val( int now, int val, int &x, int &y ) {if( ! now ) x = y = 0; else {if( t[now].val <= val ) x = now, split_val( t[now].rson, val, t[now].rson, y ); else y = now, split_val( t[now].lson, val, x, t[now].lson ); pushup( now ); } } void split_siz( int now, int siz, int &x, int &y ) {if( ! now ) x = y = 0; else {if( t[t[now].lson].siz >= siz ) y = now, split_siz( t[now].lson, siz, x, t[now].lson ); else x = now, split_siz( t[now].rson, siz - t[t[now].lson].siz - 1, t[now].rson, y ); pushup( now ); } } void split_sum( int now, int sum, int &x, int &y ) {if( ! now ) x = y = 0; else {if( t[t[now].rson].sum >= sum )x = now, split_sum( t[now].rson, sum, t[now].rson, y ); else y = now, split_sum( t[now].lson, sum - t[t[now].rson].sum - t[now].val, x, t[now].lson ); pushup( now ); } } void rebuild( int x, int y ) {root = merge( x, y ); while( top ) {split_val( root, t[sta[top]].val, x, y ); root = merge( merge( x, sta[top] ), y ); top --; } } void solve( int S, int T ) {int L = 0, R = root, x, y, ans = 0, nxt; while( S < T ) {split_val( R, S - 1, x, y ); L = merge( L, x ), R = y; if( ! R ) nxt = T; else nxt = min( T, t[R].Min + 1 ); if( t[L].sum + S < nxt ) {printf( "-1\n" ); rebuild( L, R ); return; } split_sum( L, nxt - S, x, y ); ans += t[y].siz, S += t[y].sum; L = x, sta[++ top] = y; } printf( "%lld\n", ans ); rebuild( L, R ); } void Insert( int val ) {int x, y; split_val( root, val, x, y ); root = merge( merge( x, NewNode( val ) ), y ); } void Delete( int val ) {int x, y, l, r; split_val( root, val, x, y ); split_siz( x, t[x].siz - 1, l, r ); root = merge( l, y ); } signed main() {scanf( "%lld", &n ); for( int i = 1; i <= n; i ++ ) scanf( "%lld", &v[i] ); sort( v + 1, v + n + 1 ); root = build( 1, n ); scanf( "%lld", &Q ); while( Q -- ) {int opt, s, k, w; scanf( "%lld", &opt ); switch( opt ) {case 1 : {scanf( "%lld %lld", &s, &k ); solve( s, k ); break; } case 2 : {scanf( "%lld", &w ); Insert( w ); break; } case 3 : {scanf( "%lld", &w ); Delete( w ); break; } } } return 0; }