inYourdreaM's blog

By inYourdreaM, history, 5 weeks ago, In English,

Given a String S with length N (N <= 50000). Given Q (Q <= 2000) queries.

1) Sort the substring [L, R] lexicographically.

2) Find the value of substring [L, R]. A value of substring is the sum of all (S[i] — 'a' + 1) for L <= i <= R.

What data structure/algorithm can solve this problem?

Any advice?

Thank you.

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

I'm assuming the alphabet is a - z. We can keep 26 segment trees representing the frequency of each character in a range. Sorting a substring can be done by computing frequency of each character in a range. Knowing frequencies is enough to know how the final sorted substring will look like, and also tells us the query answers. We can apply this update to the segment tree using lazy propagation (Set a contiguous range of values to 0/1, while maintaining sum of a range). Overall, it would be O(Q * 26 * logN)

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

did the same problem with same logic as rekt_n00b suggested... if someone is wondering about problem , here it is..558E - A Simple Task