Hey codeforces,↵
↵
I found an old blog about an interesting problem about persistent lists: ↵
[Old blog](https://mirror.codeforces.com/blog/entry/51136?) ↵
[Problem and submit on e-olymp](https://www.e-olymp.com/en/problems/2957)↵
↵
In this problem you start with a bunch of lists of integers (all with length 1 at the start). There are three operations:↵
↵
- merge i j: Make a brand new list that is the concatenation of list i and list j. (i and j could be the same)↵
↵
- head i: Make two new lists: One with the first element (the head) of list i and one with all the other values↵
↵
- tail i: Make two new lists: One with all the elements except the last, and one with all the other values.↵
↵
After each operation you have to report the sum of numbers in all the newly created lists modulo $10^9 + 7$.↵
↵
Constraints are: number of starting lists with one number inside $\leq 10^5$ and number of operations $\leq 10^5$↵
↵
The difficulty of this problem lies in the fact that with the operation merge, you can double the size of the largest array every time. This means that a list can have a size of $2^{10^5}$. Another difficulty is that you have to remember all the previous lists and only make copies of them.↵
↵
I tried my hands at it and came up with a solution, inspired by the old blog. ↵
↵
For each list we keep track of its sum, and we keep track of the first $10^5$ elements and the last $10^5$ elements. This is all we need because the head and tail operations will only remove one element from the front or back at a time. For fast split and concatenation of the remaining head and tail elements I used persistent treaps. There is also a special case for when the size of one of the lists is still smaller than $2 \cdot 10^5$. Then, I store the whole list in one treap. ↵
↵
↵
With my persistent treaps, split and merge can be done in $O(log(n))$ expected time and with $O(log(n))$ extra nodes created per operation. With persistence all previous versions of the data structure stay intact, so this makes it possible to do the merge, head and tail operations. (head and tail can be simulated by splitting the treap into a piece of length 1 and length n-1). Because there are $m$ operations and each operation does a constant number of splits and merges on a persistent treap of size at most $2*m$, the total time and space complexity becomes $O(n + m log(m))$, where $n$ is the number of initial lists.↵
You can check out my code here: https://ideone.com/GVwY1W.
↵
I found an old blog about an interesting problem about persistent lists: ↵
[Old blog](https://mirror.codeforces.com/blog/entry/51136?) ↵
[Problem and submit on e-olymp](https://www.e-olymp.com/en/problems/2957)↵
↵
In this problem you start with a bunch of lists of integers (all with length 1 at the start). There are three operations:↵
↵
- merge i j: Make a brand new list that is the concatenation of list i and list j. (i and j could be the same)↵
↵
- head i: Make two new lists: One with the first element (the head) of list i and one with all the other values↵
↵
- tail i: Make two new lists: One with all the elements except the last, and one with all the other values.↵
↵
After each operation you have to report the sum of numbers in all the newly created lists modulo $10^9 + 7$.↵
↵
Constraints are: number of starting lists with one number inside $\leq 10^5$ and number of operations $\leq 10^5$↵
↵
The difficulty of this problem lies in the fact that with the operation merge, you can double the size of the largest array every time. This means that a list can have a size of $2^{10^5}$. Another difficulty is that you have to remember all the previous lists and only make copies of them.↵
↵
I tried my hands at it and came up with a solution, inspired by the old blog. ↵
↵
For each list we keep track of its sum, and we keep track of the first $10^5$ elements and the last $10^5$ elements. This is all we need because the head and tail operations will only remove one element from the front or back at a time. For fast split and concatenation of the remaining head and tail elements I used persistent treaps. There is also a special case for when the size of one of the lists is still smaller than $2 \cdot 10^5$. Then, I store the whole list in one treap. ↵
↵
↵
With my persistent treaps, split and merge can be done in $O(log(n))$ expected time and with $O(log(n))$ extra nodes created per operation. With persistence all previous versions of the data structure stay intact, so this makes it possible to do the merge, head and tail operations. (head and tail can be simulated by splitting the treap into a piece of length 1 and length n-1). Because there are $m$ operations and each operation does a constant number of splits and merges on a persistent treap of size at most $2*m$, the total time and space complexity becomes $O(n + m log(m))$, where $n$ is the number of initial lists.↵
You can check out my code here: https://ideone.com/GVwY1W.
