[problem:593A]↵
------------------↵
↵
Для каждой буквы будем поддерживать суммарную длину слов ($cnt1_{c_{i}}$), в которых встречается она одна, а для каждой пары букв будем поддерживать суммарную длину слов, в которых встречаются только они($cnt2_{c_{i}, c_{j}}$).↵
↵
Для каждой строки определим количество различных букв в ней.↵
Если она одна, то добавим к этой букве длину этого слова.↵
Если их две, то добавим к этой паре букв длину этого слова.↵
↵
Переберем пару букв, которая будет ответом. Для пары букв $c_{i}, c_{j}$ ответом будет $cnt1_{c_{i}} + cnt1_{c_{j}} + cnt2_{c_{i}, c_{j}}$. Среди всех таких пар найдем максимум и выведем его.↵
↵
Решение за O(суммарная длина всех строк + 26 * 26)↵
↵
[problem:593B]↵
------------------↵
↵
Заметим, что если $i$-я прямая пересекаются с $j$-й в данной полосе, а при $x = x_{1}$ $i$-я прямая находится выше, то при $x = x_{2}$ выше окажется $j$-я прямая. ↵
↵
То есть отсортируем прямые по координате $y$ при $x = x_{1} + eps$, и при $x = x_{2} - eps$.↵
Проверим, что порядок прямых в обоих случаях совпадает.↵
Если существует такая прямая, что ее индекс в первом случае не совпадает со вторым, то выведем Yes.↵
В другом случае выведем No.↵
↵
Единственное, что может нам помешать это пересечение на границах, так как в таком случае порядок сортировки не определен. Тогда прибавим к нашей границе $x_{1}$ бесконечно малую величину $eps$, а от $x_{2}$ отнимем $eps$, и порядок сортировки будет задан однозначно.↵
↵
Решение за $O(n log n)$↵
↵
[problem:593C]↵
------------------↵
↵
Одним из ответов будет являться сумма таких выражений для каждой окружности по координате $x$ и аналогично по координате $y$:↵
$\lfloor \frac{x_{i}}{2} \rfloor * ( 1 - abs ( t - i ) + abs ( abs ( t - i ) - 1 ) )$ ↵
↵
Пусть $a = 1$, $b = abs ( t - i )$, тогда это можно записать как $\lfloor \frac{x_{i}}{2} \rfloor * ( a - b + abs (b - a ) )$ ↵
↵
Рассмотрим $a - b + abs(a - b)$:↵
↵
если $a \leq b$, то $a - b + abs(a - b) = 0$,↵
↵
если $a > b$, то $a - b + abs(a - b) = 2a - 2b$↵
↵
теперь рассмотрим, что такое $a > b$:↵
↵
$1 > abs (t - i)$↵
↵
$i > t - 1$, и $i < t + 1$.↵
↵
При целом $i$ это возможно лишь в случае $i = t$.↵
↵
То есть эта скобка не обнуляется лишь при $i = t$.↵
↵
Рассмотрим $2a - 2b = 2 - 2 * abs (t - i) = 2$.↵
Тогда $\lfloor \frac{x_{i}}{2} \rfloor * 2 $ отличается от нужной координаты не более чем на 1, но так как все радиусы не меньше 2, то эта точка принадлежит окружности.↵
↵
Решение за $O(n)$.↵
↵
[problem:593D]↵
------------------↵
↵
↵
Рассмотрим задачу без запросов второго типа. Заметим, что в графе, где все числа на ребрах $> 1$ максимальное количество присвоений $x = \lfloor \frac{x}{R_{v}} \rfloor$ до того, как $x$ превратится в $0$, не превышает $64$. ↵
Действительно, если все $R_{v} = 2$, то количество операций можно оценить как $log_{2}(x)$.↵
Подвесим дерево за какую-нибудь вершину и назовем ее корнем. ↵
↵
Научимся решать задачу при условии, что для любого $v$ $R_{v} > 1$ и нет запросов второго типа. Для каждой вершины кроме корня мы определили ее предка как соседа наиболее близкого к корню. Пусть у нас был запрос первого типа от вершины $a$ до вершины $b$ с иходным числом $x$. Разобьем путь на две вертикальные части, одна из которых приближается к корню, а другая отдаляется. Найдем все ребра на этом пути. Для этого посчитаем глубину каждой вершины как расстояние до корня. Теперь будем параллельно подниматься в дереве из обеих вершин, пока не встретимся в общей. Если в ходе такого подъема мы прошли более $64$ ребер, то в ходе замен $x = \lfloor \frac{x}{R_{v}} \rfloor$ мы получим $x = 0$ и мы можем на текущем шаге остановить алгоритм поиска. Таким образом, мы совершим не более $O(log(x))$ операций. ↵
↵
Перейдем к задаче, где $R_{v} > 0$. Заметим, что наше предыдущее решение в таком случае может работать за $O(n)$. Так как при прохождении по ребру с $R_{v} = 1$ наше значение не меняется. Сведем эту задачу к выше рассмотренной. Сожмем граф, то есть уберем все единичные ребра. Для этого запустим dfs от корня и будем хранить самое глубокое ребро на пути от корня до вершины с $R_{v} > 1$. ↵
↵
Вспомним, что у нас были запросы уменьшения $R_{v}$. Будем поддерживать ближайшего предка $P_{v}$ c $R_{P_{v}} > 1$. Воспользуемся идеей сжатия путей. При ответе на запрос первого типа будем пересчитывать $P_{v}$. ↵
Введем рекурсивную функцию $F(v)$. Которая возвращает $v$, если $R_{v} > 1$, иначе выполняет присвоение $P_{v} = F(P_{v})$ и возвращает $F(P_{v})$.↵
Каждое ребро мы удалим $1$ раз, значит суммарно вызов всех функций $F(v)$ работает $O(n)$.↵
↵
Итоговое время работы $O(log x)$ на запрос первого типа и $O(1)$ в среднем на запрос второго типа.↵
↵
↵
[problem:593E]↵
------------------↵
↵
Научимся решать задачу для маленьких t. Воспользуемся стандартной динамикой $dp_{x, y, t}$ = количеству способов попасть в клетку (x; y) в момент времени t. Пересчет это сумма по всем допустимым способам попасть в клетку (x; y) в момент времени t – 1. ↵
↵
Заметим, что такую динамику можно считать при помощи возведения матрицы в степень. Заведем матрицу переходов, $T_{i, j} = 1$, если мы можем попасть из клетки $i$ в клетку $j$. ↵
Пусть у нас был вектор G, где $G_{i}$ равно количеству способов попасть в клетку $i$. ↵
Тогда новый вектор $G'$ через $dt$ секунд $G'$ = $G$ * $(T^{dt})$.↵
↵
↵
Таким образом мы научились решать задачу без изменений за O(log $dt * S ^ 3$), где dt — момент времени, S – площадь. ↵
↵
Рассмотрим, что происходит в момент добавления и удаления кота. При таких запросах изменяется матрица переходов. Между этими запросами T постоянная, значит мы можем возводить матрицу в степень. Таким образом, в момент изменения мы пересчитываем T, а между изменениями возводим матрицу в степень. ↵
↵
Решение за O($m * S^3$ log $dt$), m – количество запросовFor each letter will maintain the total length of words ($ cnt1_ {c_ {i}} $), which found it was alone, and for each pair of letters will maintain the total length of words that contains only them ($ cnt2_ {c_ {i} , c_ {j}} $).↵
↵
For each row, count a number of different letters in it.↵
If it is one, then add this letter to the length of the word.↵
If two of them, then add to the pair of letters word`s length.↵
↵
Now find a pair of letters that will be the answer. For a pair of letters $ c_ {i}, c_ {j} $ answer is $ cnt1_ {c_ {i}} + cnt1_ {c_ {j}} + cnt2_ {c_ {i}, c_ {j}} $. Among all these pairs find the maximum. This is the answer.↵
↵
The overall complexity is O (total length of all strings + 26 * 26)↵
↵
[problem:593B]↵
------------------↵
Note that if $ a $ s line intersects with the $ j $ th in this band, and at $ x = x_ {1} $ $ i $ th line is higher, at $ x = x_ {2} $ above would be $ j $ th line.↵
Sort by $ y $ coordinate at $ x = x_ {1} + eps $, and $ x = x_ {2} - eps $.↵
Verify that the order of lines in both cases is the same.↵
If there is a line that its index in the former case does not coincide with the second, output Yes.↵
In another case, derive No.↵
The only thing that can stop us is the intersection at the borders, as in this case we don`t know the sort`s order. Then add to our border $ x_ {1} $ small $ eps $, and by $ x_ {2} $ subtract $ eps $, and the sort order is set uniquely.↵
The overall complexity is $ O (n log n) $↵
↵
[problem:593C]↵
------------------↵
One of the answers will be the amount of such expressions for each circle in the coordinate $ x $ and similarly coordinate $ y $:↵
$ \ lfloor \ frac {x_ {i}} {2} \ rfloor * (1 - abs (t - i) + abs (abs (t - i) - 1)) $↵
↵
For $ a = 1 $, $ b = abs (t - i) $, it can be written as $ \ lfloor \ frac {x_ {i}} {2} \ rfloor * (a - b + abs (b - a )) $↵
↵
Consider the $ a - b + abs (a - b) $:↵
↵
if $ a \ leq b $, then $ a - b + abs (a - b) = 0 $,↵
↵
if $ a> b $, then $ a - b + abs (a - b) = 2a - 2b $↵
↵
Now consider what means $ a> b $:↵
↵
$ 1> abs (t - i) $↵
↵
$ i> t - $ 1 and $ i <t + 1 $.↵
↵
For integer $ i $ is possible only if $ i = t $.↵
↵
That is, this bracket is not nullified only if $ i = t $.↵
↵
Consider the $ 2a - 2b = 2 - 2 * abs (t - i) = $ 2.↵
Then $ \ lfloor \ frac {x_ {i}} {2} \ rfloor * $ 2 differs from the wanted position by no more than 1, but since all the radiuses are not less than 2, then this point belongs to the circle.↵
↵
The overall complexity is $ O (n) $.↵
↵
[problem:593D]↵
------------------↵
Consider the problem ignoring the second typed requests. We note that in the column where all the numbers on the edges of $> $ 1 maximum number of assignments to $ x = \ lfloor \ frac {x} {R_ {v}} \ rfloor $ before $ x $ will turn into $ 0 $ is not exceeds $ 64 $.↵
Indeed, if all the $ R_ {v} = 2 $, the number of operations can be assessed as $ log_ {2} (x) $.↵
Hang the tree for some top and call it the root.↵
↵
Learn how to solve the problem, provided that for every $ v $ $ R_ {v}> 1 $ and no requests of the second type. For each vertex except the root, we have identified it as the ancestor of the neighbor closest to the root. Suppose we had a request of the first type from the top $ a $ to $ b $ vertices with original number $ x $. We divide the road into two vertical parts, one of which is close to the root, while the other moves away. We find all the edges in this way. To do this, we calculate the depth of each node to the root of the distance. Now we will go up in parallel to the tree of the two peaks, until he met a total. If in the course of the recovery, we have been more than $ 64 $ edges, in the substitutions $ x = \ lfloor \ frac {x} {R_ {v}} \ rfloor $ we get $ x = 0 $ and we can at the current step to stop the algorithm search. Thus, we make no more than $ O (log (x)) $ operations.↵
↵
Let`s turn to the problem, where $ R_ {v}> 0 $. We note that our previous solution in this case can work for $ O (n) $. Since the passage of the edge with $ R_ {v} = 1 $ our value does not change. We reduce this problem to the above consideration. Compress the graph, that is, remove all single edges. To do this, run by dfs root and will keep the deepest edge on the path from the root to the top with $ R_ {v}> 1 $.↵
↵
Let us remember that we have had requests to reduce $ R_ {v} $. We maintain the closest ancestor of $ P_ {v} $ c $ R_ {P_ {v}}> 1 $. We use the idea of compression paths. When answer to a request of the first type will be recalculated $ P_ {v} $.↵
We introduce a recursive function $ F (v) $. Which returns the $ v $, if $ R_ {v}> 1 $, otherwise perform the assignment of $ P_ {v} = F (P_ {v}) $ and returns $ F (P_ {v}) $.↵
Each edge we will remove $ 1 $ times, so in total the call of all functions $ F (v) $ running $ O (n) $.↵
↵
Final time is $ O (log x) $ on request of the first type and $ O (1) an average of $ request of the second type.↵
↵
↵
[problem:593E]↵
------------------↵
Learn how to solve the problem for small t. We use standard dynamic $ dp_ {x, y, t} $ = number of ways to get into the cell (x; y) at time t. Conversion is the sum of all valid ways to get into the cell (x; y) at time t — 1.↵
↵
Note that this dp can be counted by means of the construction of the power matrix. Head of the transition matrix, $ T_ {i, j} = 1 $, if we can get out of the cell $ i $ in a cell $ j $.↵
Suppose we had a vector G, where $ G_ {i} $ equal to the number of ways to get into the cell $ i $.↵
Then a new vector $ G '$ by $ dt $ second $ G' $ = $ G $ * $ (T ^ {dt}) $.↵
↵
↵
So we learned to solve the problem without changes in O (log $ dt * S ^ 3 $), where dt — at a time, S — area.↵
↵
Consider what happens when adding or removing a cat. When such requests varies transition matrix. Between these requests constant T, then we can construct a power matrix. Thus, at the moment of change is recalculated T, and between changes in the degree of erecting matrix.↵
The decision is O ($ m * S ^ 3 $ log $ dt $), m — number of requests
------------------↵
Для каждой буквы будем поддерживать суммарную длину слов ($cnt1_{c_{i}}$), в которых встречается она одна, а для каждой пары букв будем поддерживать суммарную длину слов, в которых встречаются только они($cnt2_{c_{i}, c_{j}}$).↵
↵
Для каждой строки определим количество различных букв в ней.↵
Если она одна, то добавим к этой букве длину этого слова.↵
Если их две, то добавим к этой паре букв длину этого слова.↵
↵
Переберем пару букв, которая будет ответом. Для пары букв $c_{i}, c_{j}$ ответом будет $cnt1_{c_{i}} + cnt1_{c_{j}} + cnt2_{c_{i}, c_{j}}$. Среди всех таких пар найдем максимум и выведем его.↵
↵
Решение за O(суммарная длина всех строк + 26 * 26)↵
↵
[problem:593B]↵
------------------↵
↵
Заметим, что если $i$-я прямая пересекаются с $j$-й в данной полосе, а при $x = x_{1}$ $i$-я прямая находится выше, то при $x = x_{2}$ выше окажется $j$-я прямая. ↵
↵
То есть отсортируем прямые по координате $y$ при $x = x_{1} + eps$, и при $x = x_{2} - eps$.↵
Проверим, что порядок прямых в обоих случаях совпадает.↵
Если существует такая прямая, что ее индекс в первом случае не совпадает со вторым, то выведем Yes.↵
В другом случае выведем No.↵
↵
Единственное, что может нам помешать это пересечение на границах, так как в таком случае порядок сортировки не определен. Тогда прибавим к нашей границе $x_{1}$ бесконечно малую величину $eps$, а от $x_{2}$ отнимем $eps$, и порядок сортировки будет задан однозначно.↵
↵
Решение за $O(n log n)$↵
↵
[problem:593C]↵
------------------↵
↵
Одним из ответов будет являться сумма таких выражений для каждой окружности по координате $x$ и аналогично по координате $y$:↵
$\lfloor \frac{x_{i}}{2} \rfloor * ( 1 - abs ( t - i ) + abs ( abs ( t - i ) - 1 ) )$ ↵
↵
Пусть $a = 1$, $b = abs ( t - i )$, тогда это можно записать как $\lfloor \frac{x_{i}}{2} \rfloor * ( a - b + abs (b - a ) )$ ↵
↵
Рассмотрим $a - b + abs(a - b)$:↵
↵
если $a \leq b$, то $a - b + abs(a - b) = 0$,↵
↵
если $a > b$, то $a - b + abs(a - b) = 2a - 2b$↵
↵
теперь рассмотрим, что такое $a > b$:↵
↵
$1 > abs (t - i)$↵
↵
$i > t - 1$, и $i < t + 1$.↵
↵
При целом $i$ это возможно лишь в случае $i = t$.↵
↵
То есть эта скобка не обнуляется лишь при $i = t$.↵
↵
Рассмотрим $2a - 2b = 2 - 2 * abs (t - i) = 2$.↵
Тогда $\lfloor \frac{x_{i}}{2} \rfloor * 2 $ отличается от нужной координаты не более чем на 1, но так как все радиусы не меньше 2, то эта точка принадлежит окружности.↵
↵
Решение за $O(n)$.↵
↵
[problem:593D]↵
------------------↵
↵
↵
Рассмотрим задачу без запросов второго типа. Заметим, что в графе, где все числа на ребрах $> 1$ максимальное количество присвоений $x = \lfloor \frac{x}{R_{v}} \rfloor$ до того, как $x$ превратится в $0$, не превышает $64$. ↵
Действительно, если все $R_{v} = 2$, то количество операций можно оценить как $log_{2}(x)$.↵
Подвесим дерево за какую-нибудь вершину и назовем ее корнем. ↵
↵
Научимся решать задачу при условии, что для любого $v$ $R_{v} > 1$ и нет запросов второго типа. Для каждой вершины кроме корня мы определили ее предка как соседа наиболее близкого к корню. Пусть у нас был запрос первого типа от вершины $a$ до вершины $b$ с иходным числом $x$. Разобьем путь на две вертикальные части, одна из которых приближается к корню, а другая отдаляется. Найдем все ребра на этом пути. Для этого посчитаем глубину каждой вершины как расстояние до корня. Теперь будем параллельно подниматься в дереве из обеих вершин, пока не встретимся в общей. Если в ходе такого подъема мы прошли более $64$ ребер, то в ходе замен $x = \lfloor \frac{x}{R_{v}} \rfloor$ мы получим $x = 0$ и мы можем на текущем шаге остановить алгоритм поиска. Таким образом, мы совершим не более $O(log(x))$ операций. ↵
↵
Перейдем к задаче, где $R_{v} > 0$. Заметим, что наше предыдущее решение в таком случае может работать за $O(n)$. Так как при прохождении по ребру с $R_{v} = 1$ наше значение не меняется. Сведем эту задачу к выше рассмотренной. Сожмем граф, то есть уберем все единичные ребра. Для этого запустим dfs от корня и будем хранить самое глубокое ребро на пути от корня до вершины с $R_{v} > 1$. ↵
↵
Вспомним, что у нас были запросы уменьшения $R_{v}$. Будем поддерживать ближайшего предка $P_{v}$ c $R_{P_{v}} > 1$. Воспользуемся идеей сжатия путей. При ответе на запрос первого типа будем пересчитывать $P_{v}$. ↵
Введем рекурсивную функцию $F(v)$. Которая возвращает $v$, если $R_{v} > 1$, иначе выполняет присвоение $P_{v} = F(P_{v})$ и возвращает $F(P_{v})$.↵
Каждое ребро мы удалим $1$ раз, значит суммарно вызов всех функций $F(v)$ работает $O(n)$.↵
↵
Итоговое время работы $O(log x)$ на запрос первого типа и $O(1)$ в среднем на запрос второго типа.↵
↵
↵
[problem:593E]↵
------------------↵
↵
Научимся решать задачу для маленьких t. Воспользуемся стандартной динамикой $dp_{x, y, t}$ = количеству способов попасть в клетку (x; y) в момент времени t. Пересчет это сумма по всем допустимым способам попасть в клетку (x; y) в момент времени t – 1. ↵
↵
Заметим, что такую динамику можно считать при помощи возведения матрицы в степень. Заведем матрицу переходов, $T_{i, j} = 1$, если мы можем попасть из клетки $i$ в клетку $j$. ↵
Пусть у нас был вектор G, где $G_{i}$ равно количеству способов попасть в клетку $i$. ↵
Тогда новый вектор $G'$ через $dt$ секунд $G'$ = $G$ * $(T^{dt})$.↵
↵
↵
Таким образом мы научились решать задачу без изменений за O(log $dt * S ^ 3$), где dt — момент времени, S – площадь. ↵
↵
Рассмотрим, что происходит в момент добавления и удаления кота. При таких запросах изменяется матрица переходов. Между этими запросами T постоянная, значит мы можем возводить матрицу в степень. Таким образом, в момент изменения мы пересчитываем T, а между изменениями возводим матрицу в степень. ↵
↵
Решение за O($m * S^3$ log $dt$), m – количество запросов
↵
For each row, count a number of different letters in it.↵
If it is one, then add this letter to the length of the word.↵
If two of them, then add to the pair of letters word`s length.↵
↵
Now find a pair of letters that will be the answer. For a pair of letters $ c_ {i}, c_ {j} $ answer is $ cnt1_ {c_ {i}} + cnt1_ {c_ {j}} + cnt2_ {c_ {i}, c_ {j}} $. Among all these pairs find the maximum. This is the answer.↵
↵
The overall complexity is O (total length of all strings + 26 * 26)↵
↵
[problem:593B]↵
------------------↵
Note that if $ a $ s line intersects with the $ j $ th in this band, and at $ x = x_ {1} $ $ i $ th line is higher, at $ x = x_ {2} $ above would be $ j $ th line.↵
Sort by $ y $ coordinate at $ x = x_ {1} + eps $, and $ x = x_ {2} - eps $.↵
Verify that the order of lines in both cases is the same.↵
If there is a line that its index in the former case does not coincide with the second, output Yes.↵
In another case, derive No.↵
The only thing that can stop us is the intersection at the borders, as in this case we don`t know the sort`s order. Then add to our border $ x_ {1} $ small $ eps $, and by $ x_ {2} $ subtract $ eps $, and the sort order is set uniquely.↵
The overall complexity is $ O (n log n) $↵
↵
[problem:593C]↵
------------------↵
One of the answers will be the amount of such expressions for each circle in the coordinate $ x $ and similarly coordinate $ y $:↵
$ \ lfloor \ frac {x_ {i}} {2} \ rfloor * (1 - abs (t - i) + abs (abs (t - i) - 1)) $↵
↵
For $ a = 1 $, $ b = abs (t - i) $, it can be written as $ \ lfloor \ frac {x_ {i}} {2} \ rfloor * (a - b + abs (b - a )) $↵
↵
Consider the $ a - b + abs (a - b) $:↵
↵
if $ a \ leq b $, then $ a - b + abs (a - b) = 0 $,↵
↵
if $ a> b $, then $ a - b + abs (a - b) = 2a - 2b $↵
↵
Now consider what means $ a> b $:↵
↵
$ 1> abs (t - i) $↵
↵
$ i> t - $ 1 and $ i <t + 1 $.↵
↵
For integer $ i $ is possible only if $ i = t $.↵
↵
That is, this bracket is not nullified only if $ i = t $.↵
↵
Consider the $ 2a - 2b = 2 - 2 * abs (t - i) = $ 2.↵
Then $ \ lfloor \ frac {x_ {i}} {2} \ rfloor * $ 2 differs from the wanted position by no more than 1, but since all the radiuses are not less than 2, then this point belongs to the circle.↵
↵
The overall complexity is $ O (n) $.↵
↵
[problem:593D]↵
------------------↵
Consider the problem ignoring the second typed requests. We note that in the column where all the numbers on the edges of $> $ 1 maximum number of assignments to $ x = \ lfloor \ frac {x} {R_ {v}} \ rfloor $ before $ x $ will turn into $ 0 $ is not exceeds $ 64 $.↵
Indeed, if all the $ R_ {v} = 2 $, the number of operations can be assessed as $ log_ {2} (x) $.↵
Hang the tree for some top and call it the root.↵
↵
Learn how to solve the problem, provided that for every $ v $ $ R_ {v}> 1 $ and no requests of the second type. For each vertex except the root, we have identified it as the ancestor of the neighbor closest to the root. Suppose we had a request of the first type from the top $ a $ to $ b $ vertices with original number $ x $. We divide the road into two vertical parts, one of which is close to the root, while the other moves away. We find all the edges in this way. To do this, we calculate the depth of each node to the root of the distance. Now we will go up in parallel to the tree of the two peaks, until he met a total. If in the course of the recovery, we have been more than $ 64 $ edges, in the substitutions $ x = \ lfloor \ frac {x} {R_ {v}} \ rfloor $ we get $ x = 0 $ and we can at the current step to stop the algorithm search. Thus, we make no more than $ O (log (x)) $ operations.↵
↵
Let`s turn to the problem, where $ R_ {v}> 0 $. We note that our previous solution in this case can work for $ O (n) $. Since the passage of the edge with $ R_ {v} = 1 $ our value does not change. We reduce this problem to the above consideration. Compress the graph, that is, remove all single edges. To do this, run by dfs root and will keep the deepest edge on the path from the root to the top with $ R_ {v}> 1 $.↵
↵
Let us remember that we have had requests to reduce $ R_ {v} $. We maintain the closest ancestor of $ P_ {v} $ c $ R_ {P_ {v}}> 1 $. We use the idea of compression paths. When answer to a request of the first type will be recalculated $ P_ {v} $.↵
We introduce a recursive function $ F (v) $. Which returns the $ v $, if $ R_ {v}> 1 $, otherwise perform the assignment of $ P_ {v} = F (P_ {v}) $ and returns $ F (P_ {v}) $.↵
Each edge we will remove $ 1 $ times, so in total the call of all functions $ F (v) $ running $ O (n) $.↵
↵
Final time is $ O (log x) $ on request of the first type and $ O (1) an average of $ request of the second type.↵
↵
↵
[problem:593E]↵
------------------↵
Learn how to solve the problem for small t. We use standard dynamic $ dp_ {x, y, t} $ = number of ways to get into the cell (x; y) at time t. Conversion is the sum of all valid ways to get into the cell (x; y) at time t — 1.↵
↵
Note that this dp can be counted by means of the construction of the power matrix. Head of the transition matrix, $ T_ {i, j} = 1 $, if we can get out of the cell $ i $ in a cell $ j $.↵
Suppose we had a vector G, where $ G_ {i} $ equal to the number of ways to get into the cell $ i $.↵
Then a new vector $ G '$ by $ dt $ second $ G' $ = $ G $ * $ (T ^ {dt}) $.↵
↵
↵
So we learned to solve the problem without changes in O (log $ dt * S ^ 3 $), where dt — at a time, S — area.↵
↵
Consider what happens when adding or removing a cat. When such requests varies transition matrix. Between these requests constant T, then we can construct a power matrix. Thus, at the moment of change is recalculated T, and between changes in the degree of erecting matrix.↵
The decision is O ($ m * S ^ 3 $ log $ dt $), m — number of requests
