简单题。想到怎么计数就结束了。
重点就是怎么样计算循环次数。肯定是不能枚举一遍，双指针去数的。
但是发现 \(t\) 有一个很好的性质：它是 \([1,k]\) 内字符的排列。说明每个字符在 \(t\) 中只会出现一次。然后发现，可以按照最长公共子序列那题类似的思路，根据 \(t\) 内字符的位置为权值，求上升子段个数，这和循环次数是等价的。
而这个东西就很好求了，可以记录 \(\forall x,y,s_i=x,s_y=i\) 的个数，然后每次枚举 \(x,y\)，看权值大小关系算。
还要求区间推平，这种上颜色段均摊显然是很合适的。复杂度大概是 \(O(m\log n+k^2m)\) 的，好像优于其他题解（可能有误，请指出）？目前只略逊于一个 zkw 线段树。优势是思路清晰，不容易写挂。
code：
点击查看代码
int n,m,k,c[13][13];
char s[N];
struct CHtree{
struct node{
int l,r,k;
node(int _l=0,int _r=0,int _k=0):l(_l),r(_r),k(_k){}
bool operator<(const node &rhs)const{return l<rhs.l;}
};
set<node> st;
void init(){
rep(i,1,n)st.insert(node(i,i,s[i]-'a'));
}
il auto split(int pos){
if(pos==n+1)return st.end();
auto it=st.lower_bound(node(pos,0,0));
if(it!=st.end()&&it->l==pos)return it;
node tmp=*--it;
st.erase(it);
st.insert(node(tmp.l,pos-1,tmp.k));
return st.insert(node(pos,tmp.r,tmp.k)).fi;
}
il void assign(int l,int r,int k){
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++){
c[it->k][it->k]-=(it->r)-(it->l);
if(it!=st.begin())c[prev(it)->k][it->k]--;
}
if(itr!=st.end())c[prev(itr)->k][itr->k]--;
st.erase(itl,itr);
auto it=st.insert(node(l,r,k)).fi;
c[k][k]+=r-l;
if(it!=st.begin())c[prev(it)->k][k]++;
if(it!=--st.end())c[k][next(it)->k]++;
}
}C;
void Yorushika(){
scanf("%d%d%d%s",&n,&m,&k,s+1);
C.init();
rep(i,2,n)c[s[i-1]-'a'][s[i]-'a']++;
while(m--){
int op=read(),x,y;char t[13];
if(op==1){
scanf("%d%d%s",&x,&y,t);
C.assign(x,y,t[0]-'a');
}else{
scanf("%s",t);
int ans=0;
rep(i,0,k-1)rep(j,0,i)ans+=c[t[i]-'a'][t[j]-'a'];
printf("%d\n",ans+1);
}
}
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}