### inYourdreaM's blog

By inYourdreaM, history, 5 weeks 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
•

 » 5 weeks 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)
•  » » 5 weeks ago, # ^ |   0 Thanks rekt_n00b. I forgot that there was 26 alphabet :)
 » 5 weeks 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