Как DSU «на оси» с next-указателем красит отрезок за почти O(1) на ячейку?
Классика: дан массив, приходят запросы «покрасить отрезок [l, r] в цвет c», каждая ячейка красится только первый раз (повторные покраски игнорируются). Наивно — O(n) на запрос. Слышал, что DSU с указателем «следующая непокрашенная» решает это почти за линию суммарно. Как это устроено?
2 ответа
Идея: nxt[i] — индекс ближайшей справа ещё непокрашенной ячейки (включая саму i). Покрасив ячейку, «склеиваем» её со следующей через DSU, чтобы при следующем заходе сразу перепрыгивать через все уже покрашенные.
vector<int> nxt; // DSU-родитель: куда прыгать
int find(int x){ while(x!=nxt[x]) x=nxt[x]=nxt[nxt[x]]; return x; }
void solve(int n, vector<int>& color){
nxt.resize(n+1);
iota(nxt.begin(), nxt.end(), 0); // nxt[i]=i, nxt[n]=n — «стена»
// обработка запроса покраски [l, r] цветом c:
auto paint = [&](int l, int r, int c){
for (int i = find(l); i <= r; i = find(i)) {
color[i] = c; // красим первый раз
nxt[i] = i + 1; // прыгаем дальше, минуя i
}
};
}
Каждая ячейка красится ровно один раз за всю жизнь, и амортизированно суммарная работа всех запросов — O((n + q)·α(n)), практически линейная. Поодиночке запрос может быть и O(длины отрезка), но за счёт того, что покрашенное больше не посещается, общая сумма ограничена. Память O(n). Тот же приём решает «найти первое свободное место ≥ x» (распределение ресурсов, парковка).
Если красить можно в любом направлении или цвета перекрашиваются — приём ломается, он рассчитан строго на «каждая ячейка обрабатывается один раз». Для полноценных интервальных перекрасок с откатом цвета берите дерево отрезков с присваиванием на отрезке (lazy). Ещё нюанс реализации: ставьте барьер nxt[n] = n, чтобы find не вышел за границу — иначе UB при покраске у правого края.