Berilgan oraliqda eng katta qism oraliq yig‘indisi
Berilgan massiv .
ta ikki turdagi so‘rovlarni qayta ishlash kerak:
1 i x — ni tayinlash2 l r — oraliqsi ichida eng katta qism massiv yig‘indisini topishQism massiv bo‘sh bo‘lmasligi kerak.
struct Node kerak?Ikki oraliqni samarali birlashtirish uchun, oraliqlar daraxtining har bir tugunida quyidagilarni saqlaymiz:
sum — butun oraliqning yig‘indisipref — prefiksning maksimal yig‘indisisuf — suffiksning maksimal yig‘indisires — ichidagi ostoraliqning maksimal yig‘indisiBunday yondashuv birlashtirishni bitta comb(L, R) funksiyasi orqali amalga oshirishga imkon beradi.
Faraz qilaylik, ikkita tugun bor:
LRUnda:
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(...) funksiyasida tl > tr bo‘lganda Node() qaytariladi.
Shunday bo‘lishi kerakki:
Shuning uchun qulay:
sum = 0pref = suf = res = -INFstruct Node {
long long res;
long long pref;
long long suf;
long long sum;
Node() {
// bo‘sh tugun
// todo: implement your logic
}
Node(long long x) {
// x qiymatli tugun, argumentlarni o‘zgartirishingiz mumkin
// 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() {
// bo‘sh tugun (so‘rov uchun neytral element)
sum = 0;
pref = suf = res = NEG_INF;
}
Node(long long x) {
// barg (bitta elementdan iborat oraliq)
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;
}