Author: | Utkarsh Gupta |
Solved by: | |
First to solve: | UBB_Zalau00 |
Note that to compare two strings, we just have to know the first position where they differ, and which string at that position has a larger character.
Let's go from right to left, keeping the last met position where and are different — , and a boolean variable , which is if s[last]<t[last] and otherwise. Initially there is no such position, so set to some undefined position (for example, ).
When we are at position , we update , if s[l]\neq t[l] first. After that, if is defined and is , we add n+1-last to the answer: for all pairs (l, r) with r\ge last, s_ls_{l+1}s_{l+2}\ldots s_r will be lexicographically smaller than t_lt_{l+1}t_{l+2}\ldots t_r, and for smaller they will be equal.
Total complexity is .