View Code of Problem 3829

#include <bits/stdc++.h>
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
#define meminf(a) memset(a, 0x3f, sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pI;
typedef vector<ll> vI;
const ll mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f;
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
// head

const int maxn(1e5+7);
ll n, x, y, s;
ll a[maxn], b[maxn], c[maxn], ans[maxn << 4], lazy[maxn << 4];

//(1)更新结点信息
void PushUp(int rt) {
	ans[rt] = ans[rt << 1] + ans[rt << 1 | 1];
}

//(2)建树
void Build(int l, int r, int rt) {
	if (l == r) {
		ans[rt] = 0;
		return;
	}
	int mid = (l + r) >> 1;
	Build(l, mid, rt << 1);
	Build(mid + 1, r, rt << 1 | 1);
	PushUp(rt);
}

//(3)下推懒惰标记
//ln表示左子树元素结点个数，rn表示右子树结点个数
void PushDown(int rt, int ln, int rn) {
	if (lazy[rt]) {
		lazy[rt << 1] += lazy[rt];
		lazy[rt << 1 | 1] += lazy[rt];
		ans[rt << 1] += lazy[rt] * ln;
		ans[rt << 1 | 1] += lazy[rt] * rn;
		lazy[rt] = 0;
	}
}

//(5)区间更新
void Update(int L, int R, ll C, int l, int r, int rt) {
	if (L <= l && r <= R) {
		ans[rt] += C * (r - l + 1);
		lazy[rt] += C;
		return;
	}
	int mid = (l + r) >> 1;
	PushDown(rt, mid - l + 1, r - mid);
	if (L <= mid) { Update(L, R, C, l, mid, rt << 1); }
	if (R > mid) { Update(L, R, C, mid + 1, r, rt << 1 | 1); }
	PushUp(rt);
}

//(6)区间查询
ll Query(int L, int R, int l, int r, int rt) {
	if (L <= l && r <= R)
		return ans[rt];
	int mid = (l + r) >> 1;
	PushDown(rt, mid - l + 1, r - mid);//若更新只有点更新，不需要这句
	ll ANS = 0;
	if (L <= mid) { ANS += Query(L, R, l, mid, rt << 1); }
	if (R > mid) { ANS += Query(L, R, mid + 1, r, rt << 1 | 1); }
	return ANS;
}

/*
若只涉及区间更新的题，需用(1)(2)(3)(5)(6)
*/
int main() {
	ios_base::sync_with_stdio(false);
	while (cin >> n) {
		per(i, 0, n) { cin >> a[i]; }
		b[0] = 0;
		per(i, 1, n+1) { cin >> b[i]; b[i] += b[i - 1]; }
		Build(1, n, 1);
		mem0(c);
		per(i, 0, n) {
			s = (lower_bound(b + i, b + (n + 1), b[i] + a[i]) - b);
			if (i + 1 <= s - 1) {
				Update(i + 1, s - 1, 1, 1, n, 1);
			}
			c[s] += a[i] + b[i] - b[s-1];
		}
		/*per(i, 1, n + 1) {
			cout << Query(i, i, 1, n, 1) << " \n"[i == n];
		}*/
		per(i, 1, n+1) {
			cout << Query(i, i, 1, n, 1)*(b[i]-b[i-1])+c[i] << " \n"[i == n];
		}
	}
	return 0;
}