The 7th(2012) ACM Programming Contest of HUST - Onsite Contest(Semilive)

From: 2012-12-16 12:10:00 To: 2012-12-16 17:10:00 Now: 2017-09-20 01:10:38 Status: Public

J - Lexicographically Maximum Subsequence

Time Limit: 2s Memory Limit: 128MB

Submissions: 303 Solved: 57
Description
You've got string S and m queries. Each query asks you to calculate the hash value for the lexicographically maximum subsequence of substring S[l….r].
We'll call a non-empty string S[p1p2... pk] = sp1sp2... spk(1 ≤ p1 < p2 < ... < pk ≤ |s|) a subsequence of string s = s1s2... s|s|.
String x = x1x2... x|x| is lexicographically larger than string y = y1y2... y|y|, if either |x| > |y| and x1 = y1, x2 = y2, ... , x|y| = y|y|, or exists such number r (r < |x|, r < |y|), that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 > yr + 1. Characters in lines are compared like their ASCII codes.
The hash value for string s of length n is .
Input
There are multiple cases, process to the EOF. Each cases begins with a line contains a non-empty string s, consisting only of lowercase English letters. The string's length doesn't exceed 10^6. The second line contains an integer m(1<=m<=10^6), indicate that there are m queries. Then the next m lines contains m queries, each line describe the query with two integer l and r. 
Output
Print the hash value of lexicographically maximum subsequence of string sfor each query in separate line.
Sample Input
abeced
2
1 3
1 6
kjihgfedcba
1
1 11
Sample Output
101
514298749
888634539
Hint
Source
The 7th(2012) ACM Programming Contest of HUST Problem Setter: Shucheng Zhong