百度之星1002-子串查询
度度熊的字符串课堂开始了！要以像度度熊一样的天才为目标，努力奋斗哦！
为了检验你是否具备不听课的资质，度度熊准备了一个只包含大写英文字母的字符串A[1,n]=a1a2⋯anA[1,n]=a1a2⋯an，接下来他会向你提出qq个问题(l,r)(l,r)，你需要回答字符串A[l,r]=alal+1⋯arA[l,r]=alal+1⋯ar内有多少个非空子串是A[l,r]A[l,r]的所有非空子串中字典序最小的。这里的非空子串是字符串中由至少一个位置连续的字符组成的子序列，两个子串是不同的当且仅当这两个子串内容不完全相同或者出现在不同的位置。
记|S||S|为字符串SS的长度，对于两个字符串SS和TT，定义SS的字典序比TT小，当且仅当存在非负整数k(≤min(|S|,|T|))k(≤min(|S|,|T|))使得SS的前kk个字符与TT的前kk个字符对应相同，并且要么满足|S|=k|S|=k且|T|>k|T|>k，要么满足k
Input
第一行包含一个整数TT，表示有TT组测试数据。
接下来依次描述TT组测试数据。对于每组测试数据：
第一行包含两个整数nn和qq，表示字符串的长度以及询问的次数。
第二行包含一个长为nn的只包含大写英文字母的字符串A[1,n]A[1,n]。
接下来qq行，每行包含两个整数li,rili,ri，表示第ii次询问的参数。
保证1≤T≤101≤T≤10，1≤n,q≤1051≤n,q≤105，1≤li≤ri≤n1≤li≤ri≤n。
对于每组测试数据，先输出一行信息 "Case #x:"（不含引号），其中 x 表示这是第xx组测试数据，接下来qq行，每行包含一个整数，表示字符串A[l,r]A[l,r]中字典序最小的子串个数，行末不要有多余空格。
Input
1 2 3 AB 1 1 1 2 2 2
Case #1: 1 1 1
先来看一下什么是前缀和。
此题就应用了一个前缀和知识，我们遍历一次你输入的字符串，遍历时用一个二维数组dp【maxn】【26】记录一个每个字符出现的次数。如果这个字符出现了，那么对他的记录加1。输出时，只需从0遍历一下26个字母，遇到dp【r】【26】-dp【l-1】【26】不等于0就输出即可，此时输出的字符记录值一定是字符串中最小的字符对应的记录值。
AC代码如下：
#include
using namespace std;
const int maxn = 505;
//int dp[maxn][maxn];
//int a[maxn][maxn];
int m,n;
char s[100005];
int sum[100005][26];int main()
{int t;int q;scanf("%d",&t);int k=1;while(t--){memset(sum,0,sizeof(sum));scanf("%d%d%s",&n,&q,s+1);for(int i=1;i<=n;i++){for(int j=0;j<26;j++){if(j+'A'==s[i]) sum[i][j]=sum[i-1][j]+1;else sum[i][j]=sum[i-1][j];}}printf("Case #%d:\n",k++);while(q--){int l,r;scanf("%d%d",&l,&r);for(int j=0;j<26;j++){if(sum[r][j]-sum[l-1][j]){printf("%d\n",sum[r][j]-sum[l-1][j]);break;}}}}return 0;
} 
