题意：

\(T\)组数据，对于每组数据：

给你一个长度为\(n\)的字符串\(S\)

定义一个字符串\(t\)是好的，当且仅当它能被表示成\(aabb\)的形式，其中a和b都是字符串(可以相同)

问\(S\)中有多少个子串是好的(本质相同位置不同也算不同)

\(T \le 10,n \le 30000\)

题解：

这题的构造方法极其巧妙，是道好题。

我们可以维护两个数组分别表示某个位置为结尾/开头的aa型字符串有多少个

那显然\(ans=\sum_{i=1}^{n-1}f_{i}*g_{i+1}\)（大概意思一下）

那考虑如何统计\(f\)和\(g\)

我们枚举\(a\)的长度\(len\),并设置\(len,2*len,...,\lfloor \frac{n}{len}\rfloor *len\)为关键点,求出相邻关键点的\(LCP\)和\(LCS\)(最长公共前/后缀)，大概画幅图就知道对那些点有贡献，差分一下就可以得到\(f\)和\(g\)了。

过程：

犯了个严重错误：见LCA中的第1点

同时写代码的时候在变量代表的意义上纠结不清导致调题过程过长

代码：

const int N=30010;int n;char S[N];int valf[N],valb[N];//i as end/startint s_t[2][N<<2],t_s[2][N<<1],dep[2][N<<1],fa[2][N<<1],cur=0;int head[N<<1],nxt[N<<1],to[N<<1],lst=0;int NOW,ref[2][N];inline void adde(int x,int y) {    nxt[++lst]=head[x]; to[lst]=y; head[x]=lst;}namespace SAM {    const int U=26;    struct NODE {        int tranc[U],dep,fa;    }tre[N<<1];    int las,rt,ind;    inline int New_Node() {        ++ind; mem(tre[ind].tranc,0); tre[ind].dep=tre[ind].fa=0;        return ind;    }    inline void Init() {        mem(tre,0);        cur=lst=0; mem(head,0);        ind=0; las=rt=New_Node();    }    inline void Insert(int x) {        // printf("test:%d\n",tre[1].tranc[1]);        int p=las,np=New_Node(); tre[np].dep=tre[p].dep+1;        for(;p && !tre[p].tranc[x];p=tre[p].fa) tre[p].tranc[x]=np;        if(!p) {tre[np].fa=rt;}        else {            int q=tre[p].tranc[x];            if(tre[p].dep+1==tre[q].dep) {tre[np].fa=q;}            else {                int nq=New_Node(); tre[nq].dep=tre[p].dep+1;                memcpy(tre[nq].tranc,tre[q].tranc,sizeof(tre[q].tranc));                tre[nq].fa=tre[q].fa; tre[q].fa=tre[np].fa=nq;                for(;p && tre[p].tranc[x]==q;p=tre[p].fa) tre[p].tranc[x]=nq;            }        }        las=np;    }    inline void Build() {        for(int i=1;i<=ind;i++)            if(tre[i].fa) adde(tre[i].fa,i);    }    void dfs(int u) {        // printf("u=%d dep=%d\n",u,tre[u].dep);        dep[NOW][u]=tre[u].dep; fa[NOW][u]=tre[u].fa;        s_t[NOW][++cur]=u; t_s[NOW][u]=cur;        for(int i=head[u];i;i=nxt[i]) {            int v=to[i];            if(v) {                dfs(v);                s_t[NOW][++cur]=u;            }        }    }}inline void Get_SAM(char *s) {    if(NOW) reverse(s+1,s+n+1);    for(int i=1;i<=n;i++) {        SAM::Insert(s[i]-'a');        ref[NOW][NOW ? n-i+1 : i]=SAM::las;    }    SAM::Build(); SAM::dfs(SAM::rt);}namespace ST {    const int lgN=18;    int st[2][N<<2][lgN+3],lg[N<<2];    inline void Set() {        lg[1]=0;        for(int i=2;i<=120000;i++)            lg[i]=lg[i>>1]+1;    }    inline void Init() {        mem(st,63);    }    inline int Comp(int x,int y,int c) {return dep[c][x]
    
     y) swap(x,y);        // if(x>y) swap(x,y);        int tmp=lg[y-x+1];        // printf("%d %d %d\n",x,y,tmp);        // printf("ask::%d\n",fa[c][Comp(st[c][x][tmp],st[c][y-(1<
     
      =len-1) {                int s=max(st,st+len-lcs),t=min(st+len-1,st+lcp-1);//s=st+len-1-lcs+1                // printf("%d %d\n",s,t);                // printf("%d %d %d\n",len,s+len,t+len+1);                ++valf[s+len]; --valf[t+len+1];                // printf("%d %d %d\n",len,s-len,t-len+1);                ++valb[s-len+1]; --valb[t-len+2];            }        }    }    for(int i=1;i<=n;i++)        valf[i]+=valf[i-1];    for(int i=1;i<=n;i++)        valb[i]+=valb[i-1];    ll ans=0;    for(int i=2;i
     
    

用时：3h