qbxt 4220: 矿泉水

原题

一行人，共有 \(n\) 个人，排成一排，在等待你发放矿泉水。
你会发放 \(m\) 轮矿泉水，第 \(i\) 次，你会给前 \(a_i\) 个人发放矿泉水，然后你会发放 \(b_i\) 瓶矿泉水。
具体的，你每次会一瓶一瓶的发矿泉水，每一轮发放 \(b_i\) 次。
每次，你会把矿泉水给最需要的人，即前 \(a_i\) 个人中，当前拥有的矿泉水最少的人，如果有多个人拥有数量相同，你会发给编号靠前的人。
最终，你想知道每个人获得的矿泉水数量。
\(n,m \leq 10^5\)

首先，我们看答案是单调不降的，因此我们可以线段树 \(+\) 二分，而不是树套树之类的

从来没做过在线段树某个前缀 \(or\) 区间上二分的问题，学到了

LL k;
int search(int x, int p = 1){
	int l = tr[ p ].l, r = tr[ p ].r;
	if(r <= x && (LL)tr[ p ].maxs * (x - l + 1) - tr[ p ].sum <= k){
		k += tr[ p ].sum;
		return l;
	}
	if(l == r) return r + 1;
	PushDown(p); int mid = l + r >> 1;
	if(x <= mid) return search(x, ls);
	int rt = search(x, rs);
	if(rt == mid + 1) return search(x, ls);
	return rt;
}

大致就是判断右边如果能放就放右边，否则放左边

最终复杂度 \(O(n \log n)\)