dododo89's blog

Interesting string problem
By dododo89, history, 5 years ago, In English

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$$$.

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There also exists an offline solution that uses only std::set and Fenwick tree.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Sounds interesting. Can you please elaborate your idea?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply