#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; } /* Main.c:1:25: fatal error: bits/stdc++.h: No such file or directory #include <bits/stdc++.h> ^ compilation terminated. */ |
Double click to view unformatted code.