CF1795C Tea Tasting

有一排桌子，每个桌子上有 \(a_i\) 杯茶，现有 \(m\) 个人，第 \(i\) 个人在一轮喝茶中要喝 \(b_i\) 杯茶，如果桌子上不满 \(b_i\)杯茶，那他将该桌子上的茶全部喝光，初始第 \(i\) 个人在第 \(i\) 个桌子前，每轮喝茶完所有人向左移动一位，求 \(n\) 轮后每个人喝了多少杯茶

比赛的时候代码截图给同学然后寄了

考虑一个桌子上的茶一定会被某一个区间的人完整的喝光，相当于我们有一个区间加的操作，最后将剩下不满足 \(b_i\) 的一个人单独计算贡献

于是我们可以记录前缀和优化查询，然后每次二分查找能喝光的最后一个人，区间加也可以用差分优化，复杂度 \(O(n\log n)\)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using i64 = long long;

const int N = 2e6 + 10, inf = 0x3f3f3f3f;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int T; std::cin >> T;
	while (T--) {
		int n; std::cin >> n;
		std::vector<i64> a(n + 1), b(n + 1), pre(n + 1), ans(n + 2), res(n + 2);
		for (int i = 1; i <= n; i++) {
			std::cin >> a[i];
		}
		for (int i = 1; i <= n; i++) {
			std::cin >> b[i]; pre[i] = b[i] + pre[i - 1];
		}
		for (int i = 1; i <= n; i++) {
			int t = std::upper_bound(pre.begin() + i, pre.end(), a[i] + pre[i - 1]) - pre.begin();
			ans[i]++; ans[t]--; res[t] += a[i] - pre[t - 1] + pre[i - 1];
		}
		for (int i = 1; i <= n; i++) {
			ans[i] += ans[i - 1]; printf("%lld ", ans[i] * b[i] + res[i]);
		}
		printf("\n");
	}
	return 0;
}