题解 CF1311C 【Perform the Combo】
ShineEternal
2020-02-26 07:49:33
[更佳的阅读效果。](https://blog.csdn.net/kkkksc03/article/details/104504619)
## description：
- 给定一个长度为 $n$ 小写字母字符串 $s$。（这里默认下标从 $1$ 开始）
- 给定一个长度为 $m$ 的数列 $p_i$。
- 对于每一个 $p_i$，表示你要统计 $s_1\sim s_{p_i}$所对应的字母各一次。
- 最终，你还要统计整个字符串的字母各一次。
- 你需要求出 $26$ 个小写字母中每个字母被统计过的次数。
- **多组数据**，数据组数不超过 $10^4$，$2\le n\le 2\times 10^5$，$1\le m\le 2\times 10^5$。
- translate by @[ShineEternal](https://www.luogu.com.cn/user/45475)。
## solution：
数据范围比较大，我们没法一一枚举，于是可以使用前缀和。
用前缀和将每一个位置的各个字母的出现次数进行提前统计，遇到 $p_i$ 的时候 $O(1)$ 查询就行了。
## code：
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
int p[200005];
char s[200005];
int mp[200005][30];
int Mp[30];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
for(int i=1;i<=30;i++)Mp[i]=0;
int n,m;
scanf("%d%d",&n,&m);
scanf("%s",s);
//printf("%s\n",s);
for(int i=1;i<=m;i++)
{
scanf("%d",&p[i]);
}
p[m+1]=n;
m++;
for(int i=1;i<=26;i++)mp[0][i]=0;
mp[0][s[0]-'a'+1]++;
for(int i=1;i<n;i++)
{
for(int j=1;j<=26;j++)mp[i][j]=mp[i-1][j];
mp[i][s[i]-'a'+1]++;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=26;j++)
{
Mp[j]+=mp[p[i]-1][j];
}
}
for(int i=1;i<=26;i++)
{
printf("%d ",Mp[i]);
}
printf("\n");
}
return 0;
}
```