Life has its own fate, and meeting may not be accidental.

0%

HDU6345-子串查询(前缀和)

发表于 更新于 分类于   |   字数统计: 746(字)   |   阅读时长: 3(分) Valine：

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。

前缀和，差分。其实可以一起学的哈哈。

推荐这个博主写的文章：

X丶

题目

度度熊的字符串课堂开始了！要以像度度熊一样的天才为目标，努力奋斗哦！
为了检验你是否具备不听课的资质，度度熊准备了一个只包含大写英文字母的字符串 A[1,n]=a1a2⋯an，接下来他会向你提出 q 个问题 (l,r)，你需要回答字符串 A[l,r]=alal+1⋯ar 内有多少个非空子串是 A[l,r] 的所有非空子串中字典序最小的。这里的非空子串是字符串中由至少一个位置连续的字符组成的子序列，两个子串是不同的当且仅当这两个子串内容不完全相同或者出现在不同的位置。
记 |S| 为字符串 S 的长度，对于两个字符串 S 和 T ，定义 S 的字典序比 T 小，当且仅当存在非负整数 k(≤min(|S|,|T|)) 使得 S 的前 k 个字符与 T 的前 k 个字符对应相同，并且要么满足 |S|=k 且 |T|>k，要么满足 k<min(|S|,|T|) 且 S 的第 k+1 个字符比 T 的第 k+1 个字符小。例如 “AA” 的字典序比 “AAA” 小，”AB” 的字典序比 “BA” 小。

输入格式

第一行包含一个整数 T，表示有 T 组测试数据。
接下来依次描述 T 组测试数据。对于每组测试数据：
第一行包含两个整数 n 和 q，表示字符串的长度以及询问的次数。
第二行包含一个长为 n 的只包含大写英文字母的字符串 A[1,n]。
接下来 q 行，每行包含两个整数 li,ri，表示第 i 次询问的参数。
保证 1≤T≤10，1≤n,q≤105，1≤li≤ri≤n。

输出格式

对于每组测试数据，先输出一行信息 “Case #x:”（不含引号），其中 x 表示这是第 x 组测试数据，接下来 q 行，每行包含一个整数，表示字符串A[l,r]中字典序最小的子串个数，行末不要有多余空格。

样例输入：

1
2
3
4
5
6
1
2 3
AB
1 1
1 2
2 2

样例输出：

1
2
3
4
Case #1:
1
1
1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int t,n,m,a,b;
int sum[30][100100];
char s[100100];
int main(){
	while(scanf("%d",&t)!=EOF){
		int num=1;
		while(t--){
			scanf("%d %d",&n,&m);
			scanf("%s",s+1);
			memset(sum,0,sizeof(sum));
			for(int i=1;i<=n;i++){
				for(int j=0;j<26;j++){
					sum[j][i]=sum[j][i-1];
				}
				sum[s[i]-'A'][i]++;
			}
			printf("Case #%d:\n",num++);
			while(m--){
				scanf("%d %d",&a,&b);
				for(int i=0;i<26;i++){
					if(sum[i][b]-sum[i][a-1]!=0){
						printf("%d\n",sum[i][b]-sum[i][a-1]);
						break;
					}
				}
			}
		}
	}
	return 0;
}