回文(version 3）

莫队，时间复杂度有点极限，牛客评测机牛逼。

x=1时增加删除都是+1。

x=2时，设a[i]为i字符出现的次数，在区间端点删除字符i，答案会减少a[i]-1 。添加字符i，答案会增加a[i].

x=3时，设ansl[i],ansr[i]，ansl[i]表示在右边插入i字符时答案会增加多少，ansr[i]在左边插入i字符时答案会增加多少。删除时直接倒着来一遍就行了。

时间复杂度)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200050;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int ansl[30],ansr[30],cnt[N],a[N],res,k,d[N];
int l,r;
struct unt{
    int x,y;
    int id;
};
bool cmp(unt x,unt y){
    if(cnt[x.x]!=cnt[y.x])  return x.x<y.x;
    if(cnt[x.x]&1)  return x.y<y.y;
    return x.y>y.y;
}
vector<unt> v[4];
void init(int n){
    int x=sqrt(n),y=(n+x-1)/x;
    for(int i=1;i<=y;i++){
        for(int j=0;j<x&&(i-1)*x+j<=n;j++){
            cnt[(i-1)*x+j]=i;
        }
    }
}
void modify1(int &res,int c[],int b[],int x){
    res+=c[x];
    for(int i=0;i<26;i++){
        c[i]+=a[i];
    }
    b[x]+=(r-l);
    a[x]++;
}
void modify2(int &res,int c[],int b[],int x){
    a[x]--;
    b[x]-=(r-l+1);
    for(int i=0;i<26;i++)
    c[i]-=a[i];
    res-=c[x];
}
void add(int x,int f,int w){
    if(f==1){
        res++;
    }else if(f==2){
        res+=a[x];
        a[x]++;
    }else{
        if(w)
        modify1(res,ansl,ansr,x);
        else
        modify1(res,ansr,ansl,x);
    }
}
void del(int x,int f,int w){
    if(f==1)
    res--;
    else if(f==2){
        a[x]--;
        res-=a[x];
    }else if(f==3){
        if(w)
        modify2(res,ansl,ansr,x);
        else
        modify2(res,ansr,ansl,x);
    }
}
void solve(){
    int n,q;
    cin >>n>>q;
    string s;
    cin >>s;
    s=' '+s;
    init(n);
    for(int i=1;i<=q;i++){
        int x,y,z;
        cin >>x>>y>>z;
        v[z].push_back({x,y,i});
    }
    for(int i=1;i<=3;i++){
        l=1,r=0;
        memset(a,0,sizeof a);
        memset(ansl,0,sizeof ansl);
        memset(ansr,0,sizeof ansr);
        res=0;
        sort(v[i].begin(),v[i].end(),cmp);
        for(int j=0;j<v[i].size();j++)
        {
        int x=v[i][j].x,y=v[i][j].y;
        while(l>x)  add(s[--l]-'a',i,0);
        while(r<y)  add(s[++r]-'a',i,1);
        while(l<x)  del(s[l++]-'a',i,0);
        while(r>y)  del(s[r--]-'a',i,1);
        d[v[i][j].id]=res;
        }
    }
    for(int i=1;i<=q;i++)
    cout <<d[i]<<"\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    while(t--) solve();
   
   return 0;
}