By Radewoosh, history, 15 months ago,

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?

• +18

 » 15 months ago, # | ← Rev. 2 →   +53 cs academy task subsequence queries Link
•  » » 15 months ago, # ^ |   +7 Great, thanks! If somebody has seen this task in any other place, more links would also be useful.
•  » » » 15 months ago, # ^ |   +5
 » 15 months ago, # | ← Rev. 2 →   -18 A slightly different problem but a similar type(DP + segment tree with matrix in a node) https://codeforces.com/contest/750/problem/E (By errichto).
 » 15 months ago, # | ← Rev. 2 →   +5 Do you mean problem K, Subsequence Queries from XVIII Open Cup, GP of Korea? The same statement with the problem of CSAcademy, but with constraints $N,Q\leq 10^6$ and $\vert \Sigma \vert =26$.Link to the contest: XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea.