自动搬运

查看原文

来自洛谷，原作者为

	yxy666 J O K E R

搬运于2025-08-24 22:20:35，当前版本为作者最后更新于2023-10-26 21:20:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

凌驾于算法之上的思路：

对于第 x 行，在它之前的第 $1$ 行有 $1$ 个元素，第 $2$ 行 有 $2$ 个元素，第 $x-1$ 行有 $x-1$ 个元素。那么显然易见，第 $x$ 行开头元素的下标即为 $x\times (x-1)/2+1 \mod m$，但是这里仍然要注意最后取模等于零的情况。

细节：

直接求 $x\times (x-1)/2+1$ 中途会爆 long long，所以我们要提前取模，但是后面还有一个除法运算，与模运算不相匹配，所以还需要判断数字的奇偶性情况提前除掉。

那么我们就可以刷暴力了。但是很明显，会超时。令 $m$ 等于串长，手玩数据，于是我们发现对于较大的数据，除了开头一段和末尾一段，中间是有连续的一段 $1-m$，那就好处理了。

PS ：这题卡空间，所以需要分成一个一个字母处理。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
long long n,m,Ans[50005];
int q,Q,sum[maxn];
char a[maxn];
struct yxy{
	int id;long long x;char C;
	bool operator<(const yxy b)const{return C<b.C;}
}t[50005];
long long read(){
	long long ret=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch))ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
void calc(int k){
	char ch=t[k].C;
	long long L,R,S;
	
	if(t[k].x&1)L=(long long)((t[k].x%m))*((t[k].x-1)/2%m);
	else L=(long long)((t[k].x/2%m))*((t[k].x-1)%m);
	L++;
	L%=m;if(L==0)L=m;
	if(L+t[k].x-1<=m){
		Ans[t[k].id]=sum[L+t[k].x-1]-sum[L-1];
//		if(L+t[k].x-1>m)Ans[t[k].id]+=sum[t[k].x-m+L-1];
	}//t[k].x -(m-L+1)==t[k].x-m+L-1
	else {
		Ans[t[k].id]=sum[m]-sum[L-1];
		t[k].x-=(m-L+1);L=1;
		long long size=t[k].x/m;
		Ans[t[k].id]+=(long long)size*sum[m];
		R=t[k].x%m;
		if(R!=0)Ans[t[k].id]+=sum[R];
	}
}
int main(){
	n=read();
	scanf("%s",a+1); m=strlen(a+1);
//	for(int i=1;i<=m;i++){
//		for(int j=0;j<26;j++)sum[i][j]=sum[i-1][j];
//		sum[i][a[i]-'A']++;
//	}
	q=read();
	while(q--){
		long long x=read();
		char C=getchar();
		while(C<'A'||C>'Z')C=getchar();
		t[++Q]=(yxy){Q,x,C};
	}
	sort(t+1,t+1+Q);
	for(int i=1;i<=Q;){
		int j=i;
		for(int K=1;K<=m;K++)sum[K]=sum[K-1]+(a[K]==t[i].C);
		while(t[i].C==t[j].C)calc(j),j++;
		i=j;
	}
	for(int i=1;i<=Q;i++)printf("%lld\n",Ans[i]);
	return 0;
}