Ҷустуҷӯи бинарии параллелӣ
Ҷустуҷӯи бинарии параллелӣ
Намунаи масъала
Ба шумо нафар одамон ва қитъаи замин дода шудааст. Ҳар як замини () соҳиби () дорад, ва ҳар як одам сатҳи ҳадафии захираҳо дорад.
Ҷустуҷӯи бинарии параллелӣ
Ба шумо нафар одамон ва қитъаи замин дода шудааст. Ҳар як замини () соҳиби () дорад, ва ҳар як одам сатҳи ҳадафии захираҳо дорад.
рӯйдод пайдарпай рух медиҳанд. Ҳар як рӯйдод бо сегонаи дода мешавад ва маънои онро дорад, ки заминҳо аз то захира тавлид мекунанд.
Қайд мекунем, ки метавонад аз калон бошад, зеро заминҳо дар давра ҷойгир шудаанд.
Агар одам дар порчаи қитъаи замин дошта бошад, пас ӯ захира мегирад.
Барои ҳар як одам бояд муайян кард, ки пас аз кадом рӯйдод ӯ ба сатҳи ҳадафии захираҳои худ мерасад. Агар ин имконнопазир бошад, -1-ро бароред.
Барои ҳар як одам метавон масъаларо ҷудогона бо истифода аз ҷустуҷӯи бинарӣ аз рӯи ҷавоб ҳал кард.
Бигзор can(x, m) = true, агар одам тавонад миқдори лозимии захираҳоро пас аз аввалин рӯйдод ҷамъ кунад.
Барои ҷавоб додан ба can(x, m), бояд тавонем зуд аввалин рӯйдодро илова кунем ва саҳмро аз рӯи заминҳои ин одам ҳисоб кунем. Инро метавон бо ёрии дарахти Фенвик ё дарахти порчаҳо анҷом дод.
Идея барои як одам:
Мушкил дар он аст, ки мо бисёр маротиба ҳамон рӯйдодҳоро илова ва хориҷ мекунем.
Идеяи асосӣ: ба ҷустуҷӯи бинарӣ якбора барои ҳамаи одамон ҷавоб додан.
Функсияи can(x, m) худ ба худ ба қадри кофӣ зуд кор мекунад, аммо сустӣ маҳз дар илова/хориҷкунии такрории рӯйдодҳост.
Аз ин рӯ мо одамонро аз рӯи ҷавоб дар миёна тақсим карда, гурӯҳҳоро рекурсивӣ коркард мекунем.
Ҳамин тавр мо шумораи навсозиҳои такрориро кам мекунем ва асимптотикаи хуб мегирем.
Ҳамин идеяро метавон ба шакли итеративӣ навишт.
Барои ҳар як одам ҳудудҳои ҷустуҷӯи бинариро нигоҳ медорем:
tl[x] — ҳудуди чапtr[x] — ҳудуди ростДар оғоз барои ҳама:
tl[x] = 0tr[x] = K + 1Дар ҳар итератсия одамонро аз рӯи миёнаи онҳо (tl[x] + tr[x]) / 2 гурӯҳбандӣ мекунем, пайдарпай рӯйдодҳоро илова мекунем ва can(x, m)-ро месанҷем.
int solve(int x) {
int l = 0, r = K + 1;
while (l < r) {
int m = (l + r) / 2;
add_updates(1, m);
if (can(x, m)) {
r = m;
} else {
l = m + 1;
}
remove_updates(1, m);
}
if (l == K + 1) return -1;
return l;
}
void solve(int l, int r, vector<int> can_x) {
if (can_x.empty()) {
return;
} else if (l == r) {
for (int x: can_x) {
if (l == K + 1) {
res[x] = -1;
} else {
res[x] = l;
}
}
return;
}
int m = (l + r) / 2;
add_updates(l, m);
vector<int> can_l, can_r;
for (int x: can_x) {
if (can(x, m)) {
can_l.push_back(x);
} else {
can_r.push_back(x);
}
}
remove_updates(l, m);
solve(l, m, can_l);
solve(m + 1, r, can_r);
}
void solve() {
for (int i = 1; i <= n; i++) {
tl[i] = 0;
tr[i] = K + 1;
}
for (int it = 0; it < LOG_K; it++) {
for (int i = 0; i <= K; i++) {
query[i].clear();
}
for (int i = 1; i <= n; i++) {
query[(tl[i] + tr[i]) / 2].push_back(i);
}
for (int m = 0; m <= K; m++) {
if (m > 0) {
add_updates(m, m);
}
for (int x : query[m]) {
if (can(x, m)) {
tr[x] = m;
} else {
tl[x] = m + 1;
}
}
}
remove_updates(1, K);
}
}