1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
| #include <bits/stdc++.h> using namespace std; typedef long long ll;
template<typename T> void read(T &x) { x = 0; T f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0'); x *= f; }
int n, m; ll a[500005], ans;
struct segtree{ struct tree{ int l, r; ll sum, spd, day, mn, mnspd; ll tagd, tagb; } tr[2000005]; #define lson ind<<1 #define rson ind<<1|1 inline void pushup(int ind) { tr[ind].day = tr[rson].day; tr[ind].spd = tr[lson].spd + tr[rson].spd; tr[ind].mnspd = tr[lson].mnspd; tr[ind].sum = tr[lson].sum + (tr[ind].day - tr[lson].day) * tr[lson].spd + tr[rson].sum + (tr[ind].day - tr[rson].day) * tr[rson].spd; tr[ind].mn = tr[lson].mn + (tr[rson].day - tr[lson].day) * tr[lson].mnspd; } inline void add(int ind, ll d, ll b) { tr[ind].day = d + 1; tr[ind].sum = 1ll * (tr[ind].r - tr[ind].l + 1) * b; tr[ind].mn = b; tr[ind].tagd = d; tr[ind].tagb = b; } inline void pushdown(int ind) { if (!tr[ind].tagd) return; add(lson, tr[ind].tagd, tr[ind].tagb); add(rson, tr[ind].tagd, tr[ind].tagb); tr[ind].tagd = tr[ind].tagb = 0; } void build(int ind, int l, int r) { tr[ind].l = l, tr[ind].r = r, tr[ind].sum = tr[ind].mn = 0, tr[ind].day = 1; if (l == r) { tr[ind].spd = a[l]; tr[ind].mnspd = a[l]; return; } int mid = (l + r) >> 1; build(lson, l, mid); build(rson, mid + 1, r); pushup(ind); } int find(int ind, ll d, ll b) { int l = tr[ind].l, r = tr[ind].r; if (l == r) { if (tr[ind].mn + (d - tr[ind].day + 1) * tr[ind].mnspd > b) return l; else return l + 1; } pushdown(ind); if (tr[rson].mn + (d - tr[rson].day + 1) * tr[rson].mnspd > b) return find(lson, d, b); else return find(rson, d, b); } ll query(int ind, int x, int y, ll d, ll b) { if (x > y) return 0ll; int l = tr[ind].l, r = tr[ind].r; if (x <= l && r <= y) { return tr[ind].sum + (d - tr[ind].day + 1) * tr[ind].spd - 1ll * (r - l + 1) * b; } pushdown(ind); int mid = (l + r) >> 1; ll ret = 0; if (x <= mid) ret += query(lson, x, y, d, b); if (mid < y) ret += query(rson, x, y, d, b); return ret; } void update(int ind, int x, int y, ll d, ll b) { if (x > y) return; int l = tr[ind].l, r = tr[ind].r; if (x <= l && r <= y) { add(ind, d, b); return; } pushdown(ind); int mid = (l + r) >> 1; if (x <= mid) update(lson, x, y, d, b); if (mid < y) update(rson, x, y, d, b); pushup(ind); } } T;
int main() { read(n); read(m); for (int i = 1; i <= n; i++) { read(a[i]); } sort(a + 1, a + n + 1); T.build(1, 1, n); for (int i = 1; i <= m; i++) { ll d, b; read(d); read(b); int st = T.find(1, d, b); ans = T.query(1, st, n, d, b); printf("%lld\n", ans); T.update(1, st, n, d, b); } return 0; }
|