Условие
Задана последовательность целых чисел [latex]a_1, a_2, \ldots, a_n[/latex] ([latex]| a_i | \le 10000[/latex], [latex]1 \le n \le 50000[/latex]). Над ней Вам следует выполнить [latex]m[/latex] ([latex]m \le 50000[/latex]) операций:
- модифицировать [latex]i[/latex]-ый элемент последовательности
- для заданных [latex]x[/latex] и [latex]y[/latex] вывести [latex]MAX[/latex] [latex]\{ a_i + a_{i+1} + \ldots + a_j[/latex], [latex]x \le i \le j \le y \}[/latex]
Входные данные
Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность [latex]a_1, a_2, \ldots, a_n[/latex]. Третья строка содержит число [latex]m[/latex]. Следующие [latex]m[/latex] строк содержат запросы вида:
- [latex]0[/latex] [latex]x[/latex] [latex]y[/latex]: изменить [latex]a_x[/latex] на [latex]y[/latex] ([latex]| y | \le 10000[/latex]).
- [latex]1[/latex] [latex]x[/latex] [latex]y[/latex]: вывести [latex]MAX[/latex] [latex]\{ a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y \}[/latex]
Код программы
|
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 |
#include <iostream> #include <cmath> using namespace std; struct data { int sum, pref, suff, ans; }; data combine (data l, data r) { data res; res.sum = l.sum + r.sum; res.pref = max (l.pref, l.sum + r.pref); res.suff = max (r.suff, r.sum + l.suff); res.ans = max (max (l.ans, r.ans), l.suff + r.pref); return res; } data make_data (int val) { data res; res.sum = val; res.pref = res.suff = res.ans = val; return res; } void build (int a[], int v, int tl, int tr, data t[]) { if (tl == tr) t[v] = make_data (a[tl]); else { int tm = (tl + tr) / 2; build (a, v*2, tl, tm, t); build (a, v*2+1, tm+1, tr, t); t[v] = combine (t[v*2], t[v*2+1]); } } void update (int v, int tl, int tr, int pos, int new_val, data t[]) { if (tl == tr) t[v] = make_data (new_val); else { int tm = (tl + tr) / 2; if (pos <= tm) update (v*2, tl, tm, pos, new_val, t); else update (v*2+1, tm+1, tr, pos, new_val, t); t[v] = combine (t[v*2], t[v*2+1]); } } data query (int v, int tl, int tr, int l, int r, data t[]) { if (l == tl && tr == r) return t[v]; int tm = (tl + tr) / 2; if (r <= tm) return query (v*2, tl, tm, l, r, t); if (l > tm) return query (v*2+1, tm+1, tr, l, r, t); return combine ( query (v*2, tl, tm, l, tm, t), query (v*2+1, tm+1, tr, tm+1, r, t) ); } int main() { int n, m, x, y; cin >> n; int* a = new int[n]; for(int i = 0; i < n; i++) { cin >> a[i]; } data* t = new data[4*n]; build(a, 1, 0, n-1, t); cin >> m ; bool oper; for(int i = 0; i < m; i++) { cin >> oper >> x >> y; if(!oper) { update (1, 0, n-1, x-1, y, t); } else if(oper) { cout << query (1, 0, n-1, x-1, y-1, t).ans << endl; } } return 0; } |
Для запроса на выполнение программы нажать здесь.
Ссылка на использованный алгоритм.
Ссылка на засчитанное решение.