### inYourdreaM's blog

By inYourdreaM, history, 3 months ago, ,

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?

Thank you.

•
• +18
•

 » 3 months ago, # | ← Rev. 2 →   +26 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)
•  » » 3 months ago, # ^ |   0 Thanks rekt_n00b. I forgot that there was 26 alphabet :)
 » 3 months ago, # |   +8 did the same problem with same logic as rekt_n00b suggested... if someone is wondering about problem , here it is..558E - A Simple Task