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?


  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)