Предисловие:↵
↵
Я не утверждаю, что мое решение самое лучшее/простое/оптимальное и на самом деле что оно вообще работает, просто придумал и решил написать сюда. Если у вас есть другое решение, можете предложить его в комментариях. Буду считать что вам знакомы следующие темы: неявное дерево отрезков, массовые операции на дереве отрезков, персистентное дерево отрезков.↵
↵
Задача:↵
↵
Дан массив $A$, из $N$ целых чисел. Дано $Q$ запросов двух типов: $(1, L, R)$ — найти кол-во различных чисел на отрезке, (2, X, D) — заменить число на позиции X числом D. Будем считать что на запросы нельзя отвечать оффлайн. $1 <= L_i, R_i, X_i <= N, Q, <= 10 ^ 5, 1 <= A_i, D_i <= 10^9$.↵
↵
Решение:↵
↵
Для начала рассмотрим задачу без обновлений. Будем хранить массив $B$ размера $N$, где $B_i$ — индекс следующего элемента в массиве $A$ равного $A_i$, или $N+1$ если такого не существует. Более формально, $B_i = min j: j > i, A_j = A_i$, если такой существует или $N+1$ иначе. Построим на персистентное неявное дерево отрезков, назовем его $T$, его версии будут храниться в массиве $Vers$. Пройдемся по массиву для каждого $i: 1 <= i <= n$ добавим $B_i$ в $T$ и сохраним очередную версию в $Vers_i$. Теперь можно отвечать на запрос количества различных чисел на отрезке. Найдем для каждого значения присутствующего на отрезке $A[L:R]$, последнее его вхождение в отрезок. Очевидно, что количество таких чисел для всех значений на отрезке — количество различных чисел на отрезке. Найти такое значение очень просто, это лишь количество чисел $B_i$ на отрезке $[L:R]: B_i > R$. Найти такое количество можно воспользовавшись идеей префиксных сумм. Найти ответ для префикса длины $R$, и вычесть ответ на префиксе длины $L-1$. На префиксе произвольной длины $K$, можно посчитать ответ спуском по $Vers_K$ (нумерация с нуля).↵
↵
Добавим запрос обновления элемента по индексу $(2, X, D)$. Сначала поймем как меняется массив $B$. Помимо $B$, будем хранить в некотором дереве поиска $MP$ (например std::map) пары $(Value, Indices)$, где $Value$ — значение присутствующее в массиве $A$, $Indices$ — все индексы $i: A_i = Value$, в отсортированном порядке, при этом в $MP$ будет сортировка только по $Value$. Теперь изменение значения $V$ = $A_X$, равносильно удалению $MP_V$ из $MP_D$, и вставить $X$ в $MP_D$. Рассмотрим операцию удаления из $Indices$. Пусть $X1$ — число слева от $X$ в $Indices$ (если оно существует), т.е. максимально меньшее $X$, $X2$ — число справа от $X$ (если оно существует, иначе $N+1$), т.е. минимальное большее $X$. Тогда массив $B$ изменится так: $B_X1$ = $X2$. Рассмотрим операцию добавления числа в $Indices$. Пусть $X1$ — число слева от $X$ в $Indices$ (если оно существует), т.е. максимально меньшее $X$, $X2$ — число справа от $X$ (если оно существует, иначе $N+1$), т.е. минимальное большее $X$. Тогда массив $B$ изменится так: $B_X1 = X, B_X = X2$. ↵
↵
Теперь осталось научиться делать делать изменения в версиях T. На каждый запрос изменения числа в T нам необходимо изменить $O(log N)$ вершин, следовательно на запрос изменения изменится $O(log N)$ вершин. При изменении вершины будем записывать в некоторый массив, созданный для каждой вершины нулевой версии, размера равного количеству версий конкретной вершины и при запросе получения значения в вершине, просто брать сумму на префиксе до соответствующей версии. Так, нужно хранить все версии в структуре, поддерживающей следующие операции: добавление элемента в конец, получение суммы на префиксе, изменение в точке. Нам подходит дерево фенвика, каждую операцию выполняет за $O(log N)$, и не ухудшает память. ↵
По итогу, все операции мы сделаем за $O((N + Q) log^2 N)$ времени и памяти.↵
↵
P.S.↵
Задачу лень искать, мб сам сделаю потом.
↵
Я не утверждаю, что мое решение самое лучшее/простое/оптимальное и на самом деле что оно вообще работает, просто придумал и решил написать сюда. Если у вас есть другое решение, можете предложить его в комментариях. Буду считать что вам знакомы следующие темы: неявное дерево отрезков, массовые операции на дереве отрезков, персистентное дерево отрезков.↵
↵
Задача:↵
↵
Дан массив $A$, из $N$ целых чисел. Дано $Q$ запросов двух типов: $(1, L, R)$ — найти кол-во различных чисел на отрезке, (2, X, D) — заменить число на позиции X числом D. Будем считать что на запросы нельзя отвечать оффлайн. $1 <= L_i, R_i, X_i <= N, Q, <= 10 ^ 5, 1 <= A_i, D_i <= 10^9$.↵
↵
Решение:↵
↵
Для начала рассмотрим задачу без обновлений. Будем хранить массив $B$ размера $N$, где $B_i$ — индекс следующего элемента в массиве $A$ равного $A_i$, или $N+1$ если такого не существует. Более формально, $B_i = min j: j > i, A_j = A_i$, если такой существует или $N+1$ иначе. Построим на персистентное неявное дерево отрезков, назовем его $T$, его версии будут храниться в массиве $Vers$. Пройдемся по массиву для каждого $i: 1 <= i <= n$ добавим $B_i$ в $T$ и сохраним очередную версию в $Vers_i$. Теперь можно отвечать на запрос количества различных чисел на отрезке. Найдем для каждого значения присутствующего на отрезке $A[L:R]$, последнее его вхождение в отрезок. Очевидно, что количество таких чисел для всех значений на отрезке — количество различных чисел на отрезке. Найти такое значение очень просто, это лишь количество чисел $B_i$ на отрезке $[L:R]: B_i > R$. Найти такое количество можно воспользовавшись идеей префиксных сумм. Найти ответ для префикса длины $R$, и вычесть ответ на префиксе длины $L-1$. На префиксе произвольной длины $K$, можно посчитать ответ спуском по $Vers_K$ (нумерация с нуля).↵
↵
Добавим запрос обновления элемента по индексу $(2, X, D)$. Сначала поймем как меняется массив $B$. Помимо $B$, будем хранить в некотором дереве поиска $MP$ (например std::map) пары $(Value, Indices)$, где $Value$ — значение присутствующее в массиве $A$, $Indices$ — все индексы $i: A_i = Value$, в отсортированном порядке, при этом в $MP$ будет сортировка только по $Value$. Теперь изменение значения $V$ = $A_X$, равносильно удалению $MP_V$ из $MP_D$, и вставить $X$ в $MP_D$. Рассмотрим операцию удаления из $Indices$. Пусть $X1$ — число слева от $X$ в $Indices$ (если оно существует), т.е. максимально меньшее $X$, $X2$ — число справа от $X$ (если оно существует, иначе $N+1$), т.е. минимальное большее $X$. Тогда массив $B$ изменится так: $B_X1$ = $X2$. Рассмотрим операцию добавления числа в $Indices$. Пусть $X1$ — число слева от $X$ в $Indices$ (если оно существует), т.е. максимально меньшее $X$, $X2$ — число справа от $X$ (если оно существует, иначе $N+1$), т.е. минимальное большее $X$. Тогда массив $B$ изменится так: $B_X1 = X, B_X = X2$. ↵
↵
Теперь осталось научиться делать делать изменения в версиях T. На каждый запрос изменения числа в T нам необходимо изменить $O(log N)$ вершин, следовательно на запрос изменения изменится $O(log N)$ вершин. При изменении вершины будем записывать в некоторый массив, созданный для каждой вершины нулевой версии, размера равного количеству версий конкретной вершины и при запросе получения значения в вершине, просто брать сумму на префиксе до соответствующей версии. Так, нужно хранить все версии в структуре, поддерживающей следующие операции: добавление элемента в конец, получение суммы на префиксе, изменение в точке. Нам подходит дерево фенвика, каждую операцию выполняет за $O(log N)$, и не ухудшает память. ↵
По итогу, все операции мы сделаем за $O((N + Q) log^2 N)$ времени и памяти.↵
↵
P.S.↵
Задачу лень искать, мб сам сделаю потом.
