#include "candies.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MxN = 2e5 + 5;
int n, q;
ll lz[MxN * 4];
struct node {
ll val;
pii mx, mn;
node() : val(0), mx({0, -1}), mn({0, -1}) {}
node(ll val, int idx) : val(val), mx({val, idx}), mn({val, idx}) {}
friend node operator + (const node &l, const node &r) {
node res = node();
res.val = l.val + r.val;
res.mx = max(l.mx, r.mx);
res.mn = min(l.mn, r.mn);
return res;
}
} segm[MxN * 4];
using pni = pair<node, int>;
pni operator + (pni c, node o) {
c.first = c.first + o;
return c;
}
void push (int l, int r, int idx) {
segm[idx].val += lz[idx];
segm[idx].mx.first += lz[idx];
segm[idx].mn.first += lz[idx];
if (l < r) {
lz[idx * 2 + 1] += lz[idx];
lz[idx * 2 + 2] += lz[idx];
}
lz[idx] = 0;
}
void build (int l, int r, int idx) {
if (l == r) return void(segm[idx] = node(0, l));
int mid = (l + r) >> 1;
build(l, mid, idx * 2 + 1);
build(mid + 1, r, idx * 2 + 2);
segm[idx] = segm[idx * 2 + 1] + segm[idx * 2 + 2];
}
void upd (int l, int r, int idx, int tl, int tr, ll val) {
push(l, r, idx);
if (l > tr || r < tl) return;
if (l >= tl && r <= tr) {
lz[idx] += val;
push(l, r, idx);
return;
}
int mid = (l + r) >> 1;
push(l, mid, idx * 2 + 1);
push(mid + 1, r, idx * 2 + 2);
upd(l, mid, idx * 2 + 1, tl, tr, val);
upd(mid + 1, r, idx * 2 + 2, tl, tr, val);
segm[idx] = segm[idx * 2 + 1] + segm[idx * 2 + 2];
}
pni qr (int l, int r, int idx, ll k) {
push(l, r, idx);
if (l == r) return {segm[idx], l};
int mid = (l + r) >> 1;
push(l, mid, idx * 2 + 1);
push(mid + 1, r, idx * 2 + 2);
node qrr = segm[idx * 2 + 2];
if (qrr.mx.first - qrr.mn.first > k) return qr(mid + 1, r, idx * 2 + 2, k);
else return qr(l, mid, idx * 2 + 1, k) + segm[idx * 2 + 2];
}
node oo (int l, int r, int idx, int pos) {
push(l, r, idx);
if (l == r) return segm[idx];
int mid = (l + r) >> 1;
if (pos <= mid) return oo(l, mid, idx * 2 + 1, pos);
else return oo(mid + 1, r, idx * 2 + 2, pos);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
n = c.size(); q = l.size();
std::vector<int> s(n);
vector<vector<pii>> cq(n, vector<pii>());
for (int i = 0; i < q; i++) {
cq[l[i]].emplace_back(v[i], i);
if (r[i] + 1 < n) cq[r[i] + 1].emplace_back(-v[i], i);
}
build(0, q - 1 + 2, 0);
ll cur = 0;
for (int i = 0; i < n; i++) {
for (auto &[x, y]: cq[i]) upd(0, q - 1 + 2, 0, y + 2, q - 1 + 2, x), cur += x;
// cerr << "DBG " << i << ' ' << cur << '\n';
// for (int j = 0; j < q + 2; j++) {
// auto kk = oo(0, q - 1 + 2, 0, j);
// cerr << "OO " << j << " : " << kk.mx.first << ' ' << kk.mx.second << ' ' << kk.mn.first << ' ' << kk.mn.second << '\n';
// }
auto cqr = qr(0, q - 1 + 2, 0, c[i]);
// cerr << cqr.second << '\n';
auto z = cqr.first;
// cerr << cur << ' ' << z.mx.first << ' ' << z.mx.second << ' ' << z.mn.first << ' ' << z.mn.second << ' ' << cqr.second << '\n';
// cerr << z.mx.first << ' ' << z.mx.second << ' ' << z.mn.first << ' ' << z.mn.second << '\n';
// if (!cqr.second && z.mx.first - z.mn.first <= c[i]) cerr << "AAA\n";
// else if (z.mx.second < z.mn.second) cerr << "BBB\n";
// else cerr << "CCC\n";
if (!cqr.second && z.mx.first - z.mn.first <= c[i]) s[i] = cur;
else if (z.mx.second < z.mn.second) s[i] = cur - z.mn.first;
else s[i] = cur - (z.mx.first - c[i]);
}
return s;
}
