题意是每组给定一个字符串，在有限查询次数内输出所要查询区间的字典序最小的子串个数。

字典序最小的子串，就是所查询区间中字典序最小的单个字符，问题就转化成了求一段区间内字典序最小的字符个数。

开始时盲目暴力，直接用桶排序的做法一段一段去求，果然t了（这种就不贴代码了）......

然后想到先扫一遍，求出从字符串首位到第 i 位的最小字符数，再用一个数组存第 0 位到第 i 位的最小字符，比较第 i 位的字符和前 i - 1 位的最小字符，第 i 位更小的话就更新最小字符和最小字符数......这样扫一遍后，问到哪个区间就比较区间左右端点的最小字符。若左侧较大，则直接输出右侧最小字符数；若两侧相等，则输出右侧的最小字符数减去左侧的最小字符数；左侧不可能小于右侧。

但是，这种想法有较大漏洞，不能说漏洞，这就是错误的想法，因为这样所记录的最小的字符未必会出现在所求区间内......

作为对自己的警示，把这种错误的东西挂出来侮辱下自己......

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <queue>
 6 #include <stack>
 7 #include <cmath>
 8 #include <map>
 9 using namespace std;
10 int num[100006];
11 char alp[100006];
12 int main()
13 {
14     std::ios::sync_with_stdio(false);
15     int t,len,m,l,r;
16     string s;
17     cin >> t;
18     for(int i = 1; i <= t; i++)
19     {
20         memset(num,0,sizeof(num));
21         cin >> len >> m;
22         cin >> s;
23         cout << "Case #"<< i <<":" << endl;
24         num[0] = 1;
25         alp[0] = s[0];
26         for(int i = 1; i < len; i++)
27         {
28             if(s[i]<alp[i-1])
29             {
30                 alp[i] = s[i];
31                 num[i] = 1;
32             }
33             else if(s[i] == alp[i-1])
34             {
35                 alp[i] = s[i];
36                 num[i] = num[i-1]+1;
37             }
38             else
39             {
40                 alp[i] = alp[i-1];
41                 num[i] = num[i-1];
42             }
43         }
44         while(m--)
45         {
46             cin >> l >> r;
47             l--;
48             r--;
49             if(l==r)
50             {
51                 cout << 1 << endl;
52                 continue;
53             }
54             if(alp[r] < alp[l])
55                 cout << num[r] << endl;
56             else if(alp[r] == alp[l])
57             {
58                 if(alp[l] < s[l] && alp[r] < s[r])
59 //      bug在此: ACBBB...BBCA 查中间，前面白算
60 
61                 if(alp[l]==s[l])
62                     cout << num[r]-num[l]+1 << endl;
63                 else
64                     cout << num[r]-num[l] << endl;
65             }
66         }
67     }
68     return 0;
69 }

View Code

接着又想到可否将最小字符出现的位置记录下来，然后发现完全是在自己哄自己开心......

借助wjy的力量，用二维数组记录位置的似桶排序的做法完成了题目，路还很长......

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 int rc[100100][26];
 5 int main()
 6 {
 7     std::ios::sync_with_stdio(false);
 8     int n,t,q,l,r,j,i;
 9     cin >> t;
10     string s;
11     for(int i=0;i<26;i++)
12     {
13         rc[0][i]=0;
14     }
15     for(int c=1;c<=t;c++)
16     {
17         cout << "Case #" << c << ":" << endl;
18         cin >> n >> q;
19         cin >> s;
20         for(i=0;s[i];i++)
21         {
22             for(j=0;j<=25;j++)
23             {
24                 rc[i+1][j]=rc[i][j];
25             }
26             rc[i+1][s[i]-'A']++;
27         }
28         for(i=0;i<q;i++)
29         {
30             cin >> l >> r;
31             int ans = 0;
32             for(j = 0;ans==0;j++)
33             {
34                 ans = rc[r][j]-rc[l-1][j];
35             }
36             cout << ans << endl;
37         }
38     }
39     return 0;
40 }

View Code