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

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

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