Radewoosh's blog

By Radewoosh, history, 15 months ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +18
  • Vote: I do not like it

»
15 months ago, # |
Rev. 2   Vote: I like it +53 Vote: I do not like it

cs academy task subsequence queries Link

»
15 months ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

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   Vote: I like it +5 Vote: I do not like it

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.