Radewoosh's blog

Need a link to "count different subsequences with interval queries" problem
By Radewoosh, history, 5 years 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

»
5 years ago, # |
← Rev. 2   Vote: I like it +53 Vote: I do not like it

cs academy task subsequence queries Link

→ Reply
»
5 years 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.net/contest/750/problem/E (By errichto).

→ Reply
»
5 years 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.

→ Reply