```
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1200000;
const unsigned MLY=133;
template<class T>inline T Max(const T &a,const T &b){return a>b?a:b;}
char s[maxn];
int n;
struct TreeArray{
int tr[28];
#define lowbit(x) (x&-x)
inline void add(int x,int d){
++x;while(x<=27)tr[x]+=d,x+=lowbit(x);
}
inline int ask(int x){
++x;
int ans=0;
while(x)ans+=tr[x],x-=lowbit(x);
return ans;
}
inline void clear(){
memset(tr,0,sizeof(tr));
}
}BIT;
struct StringHash{
unsigned long long hash[maxn],base[maxn];
inline StringHash(){
base[0]=1;for(int i=1;i<maxn;++i)base[i]=base[i-1]*MLY;
}
inline void Init(){
for(int i=1;i<=n;++i)hash[i]=hash[i-1]*MLY+s[i];
}
inline unsigned long long ask(int l,int r){
return hash[r]-hash[l-1]*base[r-l+1];
}
}Hash;
int pre[maxn],suf[maxn],cnt[300],rep[maxn];
bool vis[27];
int stk[27],top;
int main(){
FILE *fin=stdin;
FILE *fout=stdout;
int T;
fscanf(fin,"%d",&T);
while(T--){
memset(pre,0,sizeof(pre));
memset(suf,0,sizeof(suf));
fscanf(fin,"%s",s+1);
n=strlen(s+1);
Hash.Init();BIT.clear();
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;++i)pre[i]=pre[i-1]+(((++cnt[s[i]])&1)?1:-1);
memset(cnt,0,sizeof(cnt));
for(int i=n;i;--i)suf[i]=suf[i+1]+(((++cnt[s[i]])&1)?1:-1);
long long ans=0;
for(int i=n-1;i;--i){
if(i*2>=n)rep[i]=1;
else if(Hash.ask(1,i)!=Hash.ask(i+1,i*2))rep[i]=1;
else{
rep[i]=rep[i*2]*2;
if(i*(rep[i]+1)<n&&Hash.ask(1,i)==Hash.ask(i*rep[i]+1,i*(rep[i]+1)))++rep[i];
}
}
for(int i=1;i<n;++i){
if(rep[i]==1){
ans+=BIT.ask(suf[i+1]);
}
else{
ans+=(rep[i]+1)/2ll*BIT.ask(suf[i+1]);
ans+=rep[i]/2ll*BIT.ask(suf[i*2+1]);
}
BIT.add(pre[i],1);
}
fprintf(fout,"%lld\n",ans);
}
return 0;
}
```
by Gary_NotFound @ 2023-10-02 08:25:50
我想问的是我这个代码为什么会TLE.
怎么该才能通过？？
by lij123 @ 2023-10-02 08:43:53
@[Gary_NotFound](/user/654056)
by lij123 @ 2023-10-02 08:44:11
试试快读快输？
by Gary_NotFound @ 2023-10-02 08:46:59
不行 @[Gary_NotFound](/user/654056)
by lij123 @ 2023-10-04 11:49:55
@[lij123](/user/1037981) 函数加inline，我也这样
by kbzcz @ 2023-10-18 08:43:20
@[kbzcz](/user/416192) 谢谢
by lij123 @ 2023-10-18 21:24:32