RMQ Overkill

Range minimum query problems are getting more and more common everyday. I used to consider them as hard problems some years ago, but not anymore. So I decided to make this harder for everyone. Today you are given a sequence (with 0-based indexing) of non-negative integers which contains no more than 10000 elements and where each integer is less than 10. For each possible query (i, j) where ( 0ij < 10000) [N is the size of the sequence], you have to find the minimum integer in that range, and add the minimums for all those queries together. When you are done that, mod the sum with 1000000007 and print.

Input 

For each case : First line, an integer N ( 1N10000), the size of the array. Second line, a string of N characters where i-th character denotes the i-th element of the sequence.

Output 

Output Explanation

First case: all possible queries and there results are, (0, 0) = > 1, (0, 1) = > 1, (0, 2) = > 1, (1, 1) = > 4, (1, 2) = > 3, (2, 2) = > 3. So, R = 1 + 1 + 1 + 4 + 3 + 3 = 13.

Second case: all possible queries and there results are, (0, 0) = > 4, (0, 1) = > 1, (0, 2) = > 1, (1, 1) = > 1, (1, 2) = > 1, (2, 2) = > 3. So, R = 11.

Third case: all possible queries and there results are, (0, 0) = > 1, (0, 1) = > 1, (0, 2) = > 1, (1, 1) = > 2, (1, 2) = > 1, (2, 2) = > 1. So, R = 7.

Sample Input 

3
143
3
413
3
121

Sample Output 

13
11
7

Problem Setter: Pratyai Mazumder
Alternate Solution: Mohammad Hafiz Uddin

問最小值為 0 的個數有多少時，反過來不是 0 是有多少個？
1350432402345604：WAY[0] =
[C(n,2) + n] - [(C(3,2)+3)+(C(4,2)+4)+(C(5,2)+5)+1]
紅色區間獨立抓的時候，自然不會有答案為 0 的區間！藉此得到答案是 0 的區間數。

問最小值 <= 1 的個數有多少時，反過來不是 1 是有多少個？
1350432402345604：WAY[1] =
[C(n,2) + n] - [(C(2,2)+2)+(C(4,2)+4)+(C(5,2)+5)+1]-WAY[0]
紅色區間獨立抓的時候，自然不會有答案為 1 的區間！
記得扣掉答案是 0 的區間個數，藉此得到答案是 1 的區間數。

問最小值 <= 2 的個數有多少時，反過來不是 2 是有多少個？
1350432402345604：WAY[2] =
[C(n,2) + n] - [(C(2,2)+2)+(C(2,2)+2)+1+(C(4,2)+4)+1]-WAY[0]-WAY[1]
紅色區間獨立抓的時候，自然不會有答案為 2 的區間！
記得扣掉答案是 0,1 的區間個數，藉此得到答案是 2 的區間數。

... 類推。希望能明白。

#include <stdio.h>

int main() {
    int n;
    char s[10005];
    while(scanf("%d", &n) == 1) {
        scanf("%s", s);
        int W[10] = {}, Wtot = 0;
        long long ret = 0;
        int i, j;
        for(i = 0; i < 10; i++) {
            int tot = n*(n-1)/2 + n, cnt = 0;
            tot -= Wtot;
            for(j = 0; j <= n; j++) {
                if(s[j] > i+'0')
                    cnt++;
                else {
                    tot -= cnt*(cnt-1)/2 + cnt;
                    cnt = 0;
                }
            }
            ret += i * (tot%1000000007);
            ret %= 1000000007;
            W[i] = tot;
            Wtot += tot;
        }
        printf("%d\n", ret%1000000007);
    }
    return 0;
}