You have an array $$$A$$$ of $$$N$$$ empty strings and $$$M$$$ queries ($$$1 <= N, M <= 2*10^5$$$). There are two types queries:
1) You are given two numbers $$$L, R (1<=l<=R<=N)$$$ and a string $$$S$$$. You need to push back string $$$S$$$ to all strings in array's segment from $$$L$$$ to $$$R$$$.
2) You are given three numbers $$$I, L, R (1<=I<=N, L<=R<= |a[I]|)$$$. You need to print the substring $$$[L; R]$$$ of the string $$$A[I]$$$.
The sum of string lengths is less than $$$10^6$$$.
You're from Russia and tried to get into Tinkoff. Am I correct?
This is a pretty easy problem to solve with persistent segment tree, but it's way too hard if you're green. Tags are: Binary Search, Persistent Segment tree. So here you go, I gave you a hint.
There also exists an offline solution that uses only std::set and Fenwick tree.
Sounds interesting. Can you please elaborate your idea?
fenwick tree is very complicated data structure but easy to use and very easy to implement that (in less than 20 lines) but i think its better to use partial sum and some tricks to update it in better order but fenwick tree is completely correct