Need a link to a problem

Revision en1, by Radewoosh, 2019-07-01 22:25:17

If you've already seen this task somewhere, I'd be grateful for the link.

You are given a string of length about $$$10^5$$$. There are many queries about intervals of this string and for each interval, you have to calculate the number of distinct subsequences (not necessarily contiguous) of this interval.

The solution builds a segment tree and keeps matrices in each node. Have you seen this problem?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Radewoosh 2019-07-01 22:44:35 51
en1 English Radewoosh 2019-07-01 22:25:17 428 Initial revision (published)