2018"百度之星"程序设计大赛 - 资格赛 1002 子串查询 - 开发语言

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题面又是万能的毒毒熊。。。

实在不想写了，就只写了这题

记26个前缀和查询枚举最小值直接算

实在是氵的死

而且我忘记输出Case #%d 想了很久 >_<

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il int gi(){

	int x=0,f=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*f;

}

char A[100100];

int S[26][100100];

il vd work(int yyb){

	int n=gi(),q=gi();

	scanf("%s",A+1);

	memset(S,0,sizeof S);

	for(int i=1;i<=n;++i)++S[A[i]-'A'][i];

	for(int j=0;j<26;++j)

		for(int i=1;i<=n;++i)

			S[j][i]+=S[j][i-1];

	while(q--){

		int l=gi(),r=gi();

		for(int i=0;i<26;++i)

			if(S[i][r]-S[i][l-1]){

				printf("%d\n",S[i][r]-S[i][l-1]);

				break;

			}

	}

}

int main(){

	int T=gi();

	for(int i=1;i<=T;++i)work(i);

	return 0;

}