思维/差分： Perform the Combo

暴力思维代码：

#include<bits/stdc++.h>
#include<string.h>
using namespace std;
const int maxn=3e5;
int main()
{
    std::ios::sync_with_stdio(false);int t;cin>>t;while(t--){
    int a,b;cin>>a>>b;char s[maxn];for(int i=1;i<=a;i++)cin>>s[i];//for(int i=1;i<=b;i++)cin>>st[i];//sort(st+1,st+i+1); int stt[maxn];memset(stt,0,sizeof(stt));for(int i=1;i<=b;i++){
    int k;cin>>k;stt[k]+=1;	}stt[a]=1;int se[26];memset(se,0,sizeof(se));long long ans=0;for(int i=a;i>=1;i--){
    ans+=stt[i];se[s[i]-'a']+=ans;}for(int i=0;i<26;i++)cout<<se[i]<<" ";cout<<endl;
}return 0;
}

差分代码实现：

#include<bits/stdc++.h>
#include<string.h>
using namespace std;
const int maxn=3e5;
int st[maxn];
int se[maxn];
int an[maxn];
void chafen(int l,int r,int p,int *se){
    se[l]+=p;se[r+1]-=p;
}
int main()
{
    std::ios::sync_with_stdio(false);int t;cin>>t;while(t--){
    memset(st,0,sizeof(st));memset(se,0,sizeof(se));memset(an,0,sizeof(an));int a,b;cin>>a>>b;string s;cin>>s;for(int i=1;i<=b;i++)cin>>st[i];st[b+1]=a;// memset(se,0,sizeof(se));for(int i=1;i<=b+1;i++){
    chafen(1,st[i],1,se);}// memset(an,0,sizeof(an));for(int i=1;i<=a;i++)se[i]+=se[i-1];for(int i=0;i<a;i++){
    an[s[i]-'a']+=se[i+1];}for(int i=0;i<26;i++)cout<<an[i]<<" ";cout<<endl;}return 0;
}

差分代码中差分的实现有很多细节，要掌握差分感觉还要刷写差分的题……
用差分代码的时候出现了个问题：同样的代码提交时，第一次竟然是超时，第二次提交时才AC。