题解 CF610E【Alphabet Permutations】

· · 题解

注意到模式串循环一次只会给每个字母至多 1 的贡献。并且如果主串中两个字母连续出现，在模式串对应两个字母也是连续出现，那可以用 1 个循环模式串匹配掉这两个字母。因为如果不这么做，循环次数 +1，会使解更劣。

于是想到维护主串中相邻两个字母的出现次数。根据之前的结论，如果在主串中相邻两个字母在模式串中一后一前出现，就会使得循环次数 +1。使用线段树维护并统计答案即可。时间复杂度为 O(nk^2+mk^2\log n)。

/* stuff you should look for
    Something interesting tip copied from _kubic
    * int overflow, array bounds, uppercase/lowercase
    * special cases (n=1?)
    * do sth. instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH  
*/
#include<cstdio>
class SegmentTree {
    #define ls p<<1
    #define rs p<<1|1
    int n,K,buc[800005][10][10],chl[800005],chr[800005],tag[800005];
public:
    inline void pushup(int p) {
        for(register int i=0;i<K;++i) for(register int j=0;j<K;++j) buc[p][i][j]=buc[ls][i][j]+buc[rs][i][j];
        ++buc[p][chr[ls]][chl[rs]]; chl[p]=chl[ls]; chr[p]=chr[rs]; 
    }
    inline void build(int p,int l,int r,char *s) {
        tag[p]=-1;
        if(l==r) {
            for(register int i=0;i<K;++i) for(register int j=0;j<K;++j) buc[p][i][j]=0; 
            chl[p]=chr[p]=s[l]-'a'; return;
        }
        int mid=l+r>>1; build(ls,l,mid,s); build(rs,mid+1,r,s); pushup(p);
    } 
    inline void init(int n,int k,char *s) {this->n=n; this->K=k; build(1,1,n,s);}
    inline void work(int p,int l,int r,const int& val) {
        tag[p]=val;
        for(register int i=0;i<K;++i) for(register int j=0;j<K;++j) buc[p][i][j]=0; 
        buc[p][val][val]=r-l; chl[p]=val; chr[p]=val; return;
    }
    inline void spread(int p,int l,int r) {
        int mid=l+r>>1;
        if(tag[p]!=-1) {work(ls,l,mid,tag[p]); work(rs,mid+1,r,tag[p]); tag[p]=-1;}
    } 
    inline void _modify(int p,int L,int R,int l,int r,const int& val) {
        if(L<=l&&r<=R) {work(p,l,r,val);return;}
        int mid=l+r>>1; spread(p,l,r);
        if(L<=mid) _modify(ls,L,R,l,mid,val);
        if(R>mid) _modify(rs,L,R,mid+1,r,val);
        pushup(p);
    }
    inline void modify(int L,int R,const char& val) {_modify(1,L,R,1,n,val-'a');}
    inline int getPair(int x,int y) {return buc[1][x][y];}
}SGT;
char s[200005],tmp[15];
int rev[200005];
inline int read() {
    register int x=0,f=1;register char s=getchar();
    while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
    return x*f;
}
int main() {
    int n=read(),Q=read(),K=read();
    scanf("%s",s+1); SGT.init(n,K,s);
    while(Q--) {
        int op=read();  
        if(op==1) {
            int l=read(),r=read();
            scanf("%s",tmp);
            SGT.modify(l,r,tmp[0]);
        }
        else {
            scanf("%s",tmp);
            int ans=1;
            for(register int i=0;i<K;++i) rev[tmp[i]-'a']=i;
            for(register int i=0;i<K;++i) {
                for(register int j=0;j<K;++j) {
                    if(rev[i]>=rev[j]) ans+=SGT.getPair(i,j);
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}