The Preliminary Contest for ICPC Asia Xuzhou 2019 Colorful String(回文树+线段树+状压/bitset)

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+50;
typedef long long ll;
/*******线段树***********/ 
struct P{
    int l,r;
    bitset<30>bit;
}tree[maxn<<2];
inline void build(int l,int r,int k)
{
    tree[k].l=l;tree[k].r=r;   
    if(tree[k].l==tree[k].r)return; 
    int mid=(tree[k].l+tree[k].r)>>1;
    build(l,mid,k<<1);
    build(mid+1,r,k<<1|1);
}
inline void add(int x,int u,int k)
{
    if(tree[k].l==tree[k].r)
    {
        tree[k].bit.set(u);return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(x<=mid)add(x,u,k<<1);
    else add(x,u,k<<1|1);
    tree[k].bit=tree[k<<1].bit|tree[k<<1|1].bit;
}
inline bitset<30> find(int l,int r,int k)
{
    if(tree[k].l==l&&tree[k].r==r)return tree[k].bit;
    if(tree[k].l==tree[k].r)
    {
        return tree[k].bit;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(r<=mid)return find(l,r,k<<1);
    if(l>mid)return find(l,r,k<<1|1);
    return find(l,mid,k<<1)|find(mid+1,r,k<<1|1);
}
/***************************************/
char s[maxn];//存储主串 
ll ans1[maxn],cnt[maxn],ans;
int i,j,k,m,n,o,p,q,js,jl,tot,last;
int len[maxn],fail[maxn],ch[maxn][26];
inline int newnode(int x)
{
    tot++;
    len[tot]=x;
    return(tot);
}
inline int getfail(int x,int n)
{
    while(s[n-len[x]-1]!=s[n])x=fail[x];
    return(x);
}
int main()
{
    int u;
    scanf("%s",s+1);
    s[0]=-1;fail[0]=1;last=0;
    len[0]=0;len[1]=-1;tot=1;
    int num=strlen(s+1);
    build(1,num,1);
    for(i=1;i<=num;i++)
    {
        u=s[i]-‘a‘;
        add(i,u,1);
    }
    for(i=1;i<=num;i++)
    {
        s[i]-=‘a‘;
        p=getfail(last,i);
        if(ch[p][s[i]]==0)
        {
            q=newnode(len[p]+2);
            fail[q]=ch[getfail(fail[p],i)][s[i]];
            ch[p][s[i]]=q;
            int kkk=min(((2*i-len[q]+1)>>1)+1,i);
            ans1[ch[p][s[i]]]=find(i-len[q]+1,kkk,1).count();
        }
        last=ch[p][s[i]];
        cnt[ch[p][s[i]]]++;
    }
    ans=0;
    for(i=tot;i>1;i--)
    {
        cnt[fail[i]]+=cnt[i];
        ans+=cnt[i]*ans1[i];
    }
    printf("%lld\n",ans);
    return 0;
}