用KMP做的，只有68分，开$O_2$ 优化有84分

#include<bits/stdc++.h>
using namespace std;
long long odd_a[1050000],odd_c[1050000];
long long c[30],nxt[1050000],v[1050000];
char s[1050000];
long long n,len,ans;
void init(){
    memset(odd_a,0,sizeof(odd_a));
    memset(odd_c,0,sizeof(odd_c));
    memset(c,0,sizeof(c));
    for(long long i=1;i<=len;i++){
        if(++c[s[i]-'a']&1) odd_a[i]=odd_a[i-1]+1;
        else odd_a[i]=odd_a[i-1]-1;
    }
    memset(c,0,sizeof(c));
    odd_c[len]=1;c[s[len]-'a']++;
    for(long long i=len-1;i>0;i--){
        if(++c[s[i]-'a']&1) odd_c[i]=odd_c[i+1]+1;
        else odd_c[i]=odd_c[i+1]-1;
    }
}
void get_nxt(char* p){
    nxt[0]=-1;
    long long j=0,k=-1;
    while(j<strlen(p)){
       if (k==-1||p[j]==p[k]){
           nxt[++j]=++k;
       }else{
           k=nxt[k];
       }
    }
}
int main(){
    scanf("%lld",&n);
    while(n--){
        scanf("%s",s+1);
        len=strlen(s+1);
        init();
        memset(nxt,0,sizeof(nxt));
        get_nxt(s+1);
        ans=0;
        memset(c,0,sizeof(c));
        // for(long long i=1;i<=len;i++){
        //     cout<<nxt[i]<<" ";
        // }
        // cout<<endl;
        for(long long i=2;i<len;i++){
            for(long long j=odd_a[i-1];j<26;j++) c[j]++;
            ans+=c[odd_c[i+1]];
            for(long long j=2*i;j<len;j+=i){
                if(i%(j-nxt[j])==0) ans+=c[odd_c[j+1]];
                else break;
            }
            // for(long long j=i+1;j<=len;j+=i){
            //     if(strncmp(s+1,s+j-i,i)) break;
            //     ans+=c[odd_c[j]];
            //     for(long long k=1;k<i;k++){
            //         if(odd_a[k]<=odd_c[j]){
            //             ans++;
            //         }
            //     }
            // }
        }
        printf("%lld\n",ans);
    }
}

加线段树优化反而更慢？

#include<bits/stdc++.h>
using namespace std;
long long odd_a[1050000],odd_c[1050000];
long long c[30],nxt[1050000],v[1050000];
long long sum[1050000];
char s[1050000];
long long n,len,ans;
void init(){
    memset(odd_a,0,sizeof(odd_a));
    memset(odd_c,0,sizeof(odd_c));
    memset(c,0,sizeof(c));
    for(long long i=1;i<=len;i++){
        if(++c[s[i]-'a']&1) odd_a[i]=odd_a[i-1]+1;
        else odd_a[i]=odd_a[i-1]-1;
    }
    memset(c,0,sizeof(c));
    odd_c[len]=1;c[s[len]-'a']++;
    for(long long i=len-1;i>0;i--){
        if(++c[s[i]-'a']&1) odd_c[i]=odd_c[i+1]+1;
        else odd_c[i]=odd_c[i+1]-1;
    }
}
void get_nxt(char* p){
    nxt[0]=-1;
    long long j=0,k=-1;
    while(j<strlen(p)){
       if (k==-1||p[j]==p[k]){
           nxt[++j]=++k;
       }else{
           k=nxt[k];
       }
    }
}
long long lowbit(long long x){
    return x&(-x);
}
void updata(long long i,long long x){
    while(i<=len){
        sum[i]+=x;
        i+=lowbit(i);
    }
}
long long get_sum(long long i){
    long long res=0;
    while(i>0){
        res+=sum[i];
        i-=lowbit(i);
    }
    return res;
}
int main(){
    scanf("%lld",&n);
    while(n--){
        scanf("%s",s+1);
        len=strlen(s+1);
        init();
        memset(nxt,0,sizeof(nxt));
        get_nxt(s+1);
        ans=0;
        memset(c,0,sizeof(c));
        memset(sum,0,sizeof(sum));
        // for(long long i=1;i<=len;i++){
        //     cout<<nxt[i]<<" ";
        // }
        // cout<<endl;
        for(long long i=2;i<len;i++){
        	updata(26+1,-1);updata(odd_a[i-1]+1,1);
//            for(long long j=odd_a[i-1];j<26;j++) c[j]++;
            ans+=get_sum(odd_c[i+1]+1);
            for(long long j=2*i;j<len;j+=i){
//            	cout<<get_sum(odd_c[j+1]+1)<<" "<<c[odd_c[j+1]]<<endl;
                if(i%(j-nxt[j])==0) ans+=get_sum(odd_c[j+1]+1);
                else break;
            }
            // for(long long j=i+1;j<=len;j+=i){
            //     if(strncmp(s+1,s+j-i,i)) break;
            //     ans+=c[odd_c[j]];
            //     for(long long k=1;k<i;k++){
            //         if(odd_a[k]<=odd_c[j]){
            //             ans++;
            //         }
            //     }
            // }
        }
        printf("%lld\n",ans);
    }
}

蒟蒻求救