Максимумии суммаи зерқисм дар қитъаи додашуда
Дода шудааст массиви .
Лозим аст дархости ду навъро коркард кард:
1 i x — таъин кардан 2 l r — ёфтани суммаи максималии зермассив дар дохили порчаи Зермассив бояд холӣ набошад.
struct Node-и ҷудогона лозим аст?Барои самаранок якҷоя кардани ду порча, дар ҳар як гиреҳи дарахти порчаҳо нигоҳ медорем:
sum — суммаи тамоми порчаpref — суммаи максималии префиксsuf — суммаи максималии суффиксres — суммаи максималии зерпорча дар дохилИн гуна равиш имкон медиҳад якҷоякуниро тавассути як функсия comb(L, R) амалӣ кард.
Бигузор ду гиреҳ ҳаст:
LRОн гоҳ:
sum = L.sum + R.sumpref = max(L.pref, L.sum + R.pref)suf = max(R.suf, R.sum + L.suf)res = max(L.res, R.res, L.suf + R.pref)Дар функсияи get(...) ҳангоми tl > tr баргардонда мешавад Node().
Лозим аст, ки:
Аз ин рӯ қулай аст чунин кард:
sum = 0pref = suf = res = -INFstruct Node {
long long res;
long long pref;
long long suf;
long long sum;
Node() {
// empty node
// todo: implement your logic
}
Node(long long x) {
// node with value of x, you can change arguments
// todo: implement your logic
}
};
Node comb(const Node &L, const Node &R) {
Node cur;
// todo: implement your logic
return cur;
}
int n;
int a[N];
Node t[4 * N];
void build(int x, int l, int r) {
if (l == r) {
t[x] = Node(a[l]);
return;
}
int m = (l + r) / 2;
build(x * 2, l, m);
build(x * 2 + 1, m + 1, r);
t[x] = comb(t[x * 2], t[x * 2 + 1]);
}
void upd(int x, int l, int r, int i, int y) {
if (l == r) {
t[x] = Node(y);
return;
}
int m = (l + r) / 2;
if (i <= m) {
upd(x * 2, l, m, i, y);
} else {
upd(x * 2 + 1, m + 1, r, i, y);
}
t[x] = comb(t[x * 2], t[x * 2 + 1]);
}
Node get(int x, int l, int r, int tl, int tr) {
if (tl > tr) {
return Node();
} else if (l == tl && r == tr) {
return t[x];
}
int m = (l + r) / 2;
return comb(get(x * 2, l, m, tl, min(m, tr)),
get(x * 2 + 1, m + 1, r, max(m + 1, tl), tr));
}
const long long NEG_INF = -(1LL << 60);
struct Node {
long long res;
long long pref;
long long suf;
long long sum;
Node() {
// гиреҳи холӣ (элементи нейтралӣ барои дархост)
sum = 0;
pref = suf = res = NEG_INF;
}
Node(long long x) {
// барг (порча аз як элемент)
sum = x;
pref = suf = res = x;
}
};
Node comb(const Node &L, const Node &R) {
Node cur;
cur.sum = L.sum + R.sum;
cur.pref = max(L.pref, L.sum + R.pref);
cur.suf = max(R.suf, R.sum + L.suf);
cur.res = max({L.res, R.res, L.suf + R.pref});
return cur;
}