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
|
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
struct { ll v, lazy; bool cov; Node() { v = lazy = 0; cov = false; } } T[maxn << 2];
ll a[maxn], k[maxn];
void build(int i, int l, int r) { if (l == r) { T[i].v = a[l]; return; } int mid = (l + r) / 2; build(i << 1, l, mid); build(i << 1 | 1, mid + 1, r); T[i].v = T[i << 1].v + T[i << 1 | 1].v; }
void pushdown(int i, int l, int r) { if (T[i].cov) { int m = (l + r) / 2, ls = (m - l + 1), rs = (r - m); T[i << 1].v = T[i].lazy * ls; T[i << 1 | 1].v = T[i].lazy * rs; T[i << 1].lazy = T[i << 1 | 1].lazy = T[i].lazy; T[i << 1].cov = T[i << 1 | 1].cov = true; T[i].cov = false; } }
void modify(int L, int R, ll x, int i, int l, int r) { if (L > R || l > r) return; if (L <= l && r <= R) { T[i].v = (r - l + 1) * x; T[i].lazy = x, T[i].cov = true; return; } pushdown(i, l, r); int mid = (l + r) / 2; if (R <= mid) modify(L, R, x, i << 1, l, mid); else if (mid < L) modify(L, R, x, i << 1 | 1, mid + 1, r); else { modify(L, R, x, i << 1, l, mid); modify(L, R, x, i << 1 | 1, mid + 1, r); } T[i].v = T[i << 1].v + T[i << 1 | 1].v; }
ll query(int L, int R, int i, int l, int r) { if (L <= l && r <= R) { return T[i].v; } pushdown(i, l, r); int mid = (l + r) / 2; if (R <= mid) return query(L, R, i << 1, l, mid); else if (mid < L) return query(L, R, i << 1 | 1, mid + 1, r); else { return query(L, R, i << 1, l, mid) + query(L, R, i << 1 | 1, mid + 1, r); } }
int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 2; i <= n; i++) { cin >> k[i], k[i] += k[i - 1]; } for (int i = 1; i <= n; i++) { a[i] -= k[i]; } for (int i = 1; i <= n; i++) { k[i] += k[i - 1]; } build(1, 1, n); int q; cin >> q; while (q--) { char opt; cin >> opt; if (opt == '+') { int p, x; cin >> p >> x; ll v = query(p, p, 1, 1, n) + x; int r = 0; for (int i = 17; i >= 0; i--) { int pos = r | (1 << i); if (pos > n || pos == 0) { continue; } if (query(pos, pos, 1, 1, n) < v) { r |= (1 << i); } } modify(p, r, v, 1, 1, n); } else { int l, r; cin >> l >> r; cout << query(l, r, 1, 1, n) + k[r] - k[l - 1] << "n"; } } }
|
近期评论