Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Need a link to "count different subsequences with interval queries" problem

Revision en2, by Radewoosh, 2019-07-01 22:44:35

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)