Блог пользователя AppleZ

Автор AppleZ, 10 лет назад, По-русски

Здравствуйте!! я недавно решал одну задачу, но не смог понять решение... можете помочь??? заранее спасибо! и не могли бы вы дать задачи на тему DSU+SQRTDECOMOSITION+QUERIES? THX

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Будем использовать DSU "с откатами" т.е. такой DSU который умеет вернуться к предыдущему состоянию. возьмём K порядка sqrt(E). Разобъём рёбра на блоки длины K. Все запросы оба конца которых лежат в одном блоке решим влоб с помощью DSU — O(K) на запрос. Остальные запросы обработаем так:

for (int i = 0; i < E / K; ++i)
{
    int cL = i * K;
    int cR = cL + K;
    DSU dsu;
    for (int R = cR; R < N; ++R) 
    {
        dsu.addEdge(edge[R]);
        для всех запросов q таких что cL <= q.L < cR && q.R == R
        {
            //все рёбра таких запросов уже добавлены в DSU, за исключением не более K
            запомнить состояние dsu
            for (int j = q.L; j < cR; ++j)
                dsu.addEdge(edge[j]);
            q.Answer = dsu.GetAnswer();   
            восстановить состояние dsu  
        }
    }
}