@[北射天狼](/user/289056) 错误的，我只开了 3e4 过了
by Register_int_Offical @ 2023-02-15 18:02:11
@[Register_int_Offical](/user/743447) 让我看看
by 北射天狼 @ 2023-02-15 18:04:02
试了一个题解，也是 3E4 RE
by 北射天狼 @ 2023-02-15 18:04:48
@[北射天狼](/user/289056) 草，会tlqtj的
by Register_int_Offical @ 2023-02-15 18:08:35
tql
by HarmonicQuadrilatera @ 2023-02-15 18:14:15
%%% hcy爆切NOI
by TernaryTree @ 2023-02-15 19:24:52
@[北射天狼](/user/289056) 呃，那我这又是什么毛病？数组开到2e5还是70pts？？？
代码：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5;
int T,n,m,w,p,sa[N+5],rk1[N+5],rk2[N+5],oldrk[N+5],id[N+5],cnt[N+5],h1[N+5],h2[N+5],st1[N+5][20],st2[N+5][20],lg[N+5],a[N+5],b[N+5],ans;
char S1[N+5],S2[N+5];
int cmp(int x,int y,int w){
return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];
}
void SA(char *str,int *rk,int *height){
m=127;
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++) cnt[rk[i]=str[i]]++;
for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;
for(w=1;;w<<=1,m=p){
p=0;
for(int i=n;i>n-w;i--) id[++p]=i;
for(int i=1;i<=n;i++){
if(sa[i]>w) id[++p]=sa[i]-w;
}
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++) cnt[rk[id[i]]]++;
for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--) sa[cnt[rk[id[i]]]--]=id[i];
memcpy(oldrk+1,rk+1,n*sizeof(int));
p=0;
for(int i=1;i<=n;i++) rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
if(p==n){
for(int i=1;i<=n;i++) sa[rk[i]]=i;
break;
}
}
for(int k=0,i=1;i<=n;i++){
if(k) k--;
while(str[i+k]==str[sa[rk[i]-1]+k]) k++;
height[rk[i]]=k;
}
}
void ST1(){
for(int i=1;i<=n;i++) st1[i][0]=h1[i];
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++) st1[i][j]=min(st1[i][j-1],st1[i+(1<<j-1)][j-1]);
}
}
void ST2(){
for(int i=1;i<=n;i++) st2[i][0]=h2[i];
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++) st2[i][j]=min(st2[i][j-1],st2[i+(1<<j-1)][j-1]);
}
}
int query1(int l,int r){
if(l>r) swap(l,r);l++;
return min(st1[l][lg[r-l+1]],st1[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
int query2(int l,int r){
if(l>r) swap(l,r);l++;
return min(st2[l][lg[r-l+1]],st2[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
signed main(){
lg[0]=-1;
for(int i=1;i<=N;i++) lg[i]=lg[i>>1]+1;
scanf("%lld",&T);
while(T--){
scanf("%s",S1+1);
n=strlen(S1+1);
for(int i=1;i<=n;i++) S2[n-i+1]=S1[i];
SA(S1,rk1,h1);SA(S2,rk2,h2);
ST1();ST2();
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
for(int len=1;(len<<1)<=n;len++){
for(int i=len;i+len<=n;i+=len){
int lcp=query1(rk1[i],rk1[i+len]),lcs=query2(rk2[n+1-i],rk2[n+1-i-len]);
lcp=min(lcp,len);lcs=min(lcs,len);
int q=lcp+lcs-len;
if(q>0){
b[i-lcs+1]++;b[i-lcs+1+q]--;
a[i+len+lcp-q]++;a[i+len+lcp]--;
}
}
}
for(int i=1;i<=n;i++) a[i]+=a[i-1];
for(int i=1;i<=n;i++) b[i]+=b[i-1];
ans=0;
for(int i=1;i<n;i++) ans+=a[i]*b[i+1];
printf("%lld\n",ans);
}
return 0;
}
```
by YuRuochen @ 2023-02-26 19:51:26
$3\times 10^4$ 不够是因为很多地方都有可能超过了 $n$，处理好边界问题就不会 RE。
by hgzxwzf @ 2023-04-13 20:30:04