回文树总结 by dsl

发布于 2018-02-02  208 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:回文树总结 by dsl

回文树总结

引入

对于一般的字符串问题,我们拥有处理它们的强大工具——后缀数组,后缀树,后缀自动机。
但对于一类特殊的关于回文串的字符串问题,我们也有一种强大的工具——回文树(由Mikhail Rubinchik发明,在Petrozavodsk Summer Camp 2014上首次提出来)。

回文树

安利我的博客「学习笔记」回文树/回文自动机(Palindromic Tree)
和一篇论文国家集训队2017论文集《回文树及其应用》——翁文涛。

例题

A.[BZOJ2565]最长双回文串

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。

2≤|S|≤10^5

Solution

正反建两个回文树,同时计算出\(s_{1..i}\)的最长回文后缀和\(s_{i+1..|s|}\)的最长回文前缀。
取和的\(max\)即可。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;
char s1[maxn], s2[maxn];
int n, len1[maxn], len2[maxn], ans;

struct Palindromic_Tree 
{
    int ch[maxn][26], tot, len[maxn], fail[maxn], last;

    Palindromic_Tree() 
    {
        len[tot = 1] = -1; fail[0] = fail[1] = 1;
    }

    int insert(int c, int n, char* s)
    {
        int x = last;
        while(s[n - len[x] - 1] != s[n]) x = fail[x];
        if(!ch[x][c]) {
            int v = ++tot, k = fail[x];
            while(s[n - len[k] - 1] != s[n]) k = fail[k];
            fail[v] = ch[k][c]; len[v] = len[x] + 2; ch[x][c] = v;
        }
        last = ch[x][c];
        return len[ch[x][c]];
    }
}t1, t2;

int main()
{
    scanf("%s", s1 + 1);
    n = strlen(s1 + 1);
    for(int i = 1; i <= n; ++i) s2[i] = s1[n - i + 1];

    for(int i = 1; i <= n; ++i) 
        len1[i] = t1.insert(s1[i] - 'a', i, s1), len2[n - i + 1] = t2.insert(s2[i] - 'a', i, s2);
    for(int i = 1; i < n; ++i) 
        ans = max(ans, len1[i] + len2[i + 1]);

    printf("%d\n", ans);

    return 0;
}

B.[SHOI2011]双倍回文

Description

题面

Solution

直接构造出回文树,然后在\(fail\)树上dfs。一个回文串是双倍回文串的条件是长度是4且父亲中有长度为其一半的回文串即可。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 500005;
struct edge {
    int to, next;
}e[maxn * 2];
int n, h[maxn], cnt;
char s[maxn];

int ch[maxn][26], len[maxn], tot, fail[maxn], last, ans;

inline void link(int u, int v)
{
    e[++cnt] = (edge) {v, h[u]}; h[u] = cnt;
}

void add(int c, int n)
{
    int x = last;
    while(s[n - len[x] - 1] != s[n]) x = fail[x];
    if(!ch[x][c]) {
        int v = ++tot, k = fail[x];
        while(s[n - len[k] - 1] != s[n]) k = fail[k];
        fail[v] = ch[k][c]; ch[x][c] = v; len[v] = len[x] + 2;
        link(fail[v], v);
    }
    last = ch[x][c];
}

int vis[maxn];
void dfs(int u)
{
    if(len[u] % 4 == 0 && vis[len[u] / 2]) ans = max(ans, len[u]);
    ++vis[len[u]];
    for(int i = h[u]; i; i = e[i].next) dfs(e[i].to);
    --vis[len[u]];
}

int main()
{
    scanf("%d", &n);
    scanf("%s", s + 1);

    len[tot = 1] = -1; fail[0] = fail[1] = 1; link(1, 0);
    for(int i = 1; i <= n; ++i)
        add(s[i] - 'a', i);

    dfs(1);
    printf("%d\n", ans);

    return 0;
}

C.[51nod]Clarke and string

D.[省队集训2013day7T1]str

Description

求一个串第\(k\)小的回文子串。

字符串比较方式如下(与一般的比较方式不完全相同)

int cmp(string a, string b)
{
    if (len(a) != len(b))
        return len(a) < len(b);
    else
    {
        int i;
        for (i = 0; i < len(a); ++i)
            if(a[i] != b[i])
                return a[i] < b[i];
        return 0;
    }
}

\(|s|\leqslant 10^5\)

Solution

方法1:

字符串比较的方式为先比较长度,然后比较字符。所以可以直接在回文树上bfs。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;
int n, k; long long p;
char s[maxn];

int ch[maxn][26], len[maxn], fail[maxn], v[maxn], last, tot;
pair<int, int> fa[maxn];

inline void add(int c, int n)
{
    int x = last;   
    while(s[n - len[x] - 1] != s[n]) x = fail[x];
    if(!ch[x][c]) {
        int v = ++tot, k = fail[x];
        while(s[n - len[k] - 1] != s[n]) k = fail[k];
        fail[v] = ch[k][c]; len[v] = len[x] + 2; ch[x][c] = v; fa[v] = make_pair(c, x);
    }
    ++v[last = ch[x][c]];
}

inline void print(int c, int u, int k)
{
    int cnt = 0; s[++cnt] = c + 'a';
    while(fa[u].second > 1) {
        u = fa[u].second;
        s[++cnt] = fa[u].first + 'a';
    }   
    for(int i = 1; i <= cnt; ++i) putchar(s[i]); 
    for(int i = cnt - k; i >= 1; --i) putchar(s[i]);
}

int que1[maxn], que2[maxn];
inline void bfs()
{
    register int l1 = 0, l2 = 0, r1 = 1, r2 = 1, u;
    que1[r1] = 1; que2[r2] = 0;
    do {
        if(l1 < r1) {
            int l = l1 + 1, r = r1;
            for(int j = 0; j < 26; ++j)
                for(int i = l; i <= r; ++i)
                    if(ch[u = que1[i]][j]) {
                        if(k <= 1) {print(j, ch[u][j], 1); return ;}
                        --k; que1[++r1] = ch[u][j];
                    }
            l1 = r;
        }
        if(l2 < r2) {
            int l = l2 + 1, r = r2;
            for(int j = 0; j < 26; ++j)
                for(int i = l; i <= r; ++i)
                    if(ch[u = que2[i]][j]) {
                        if(k <= 1) {print(j, ch[u][j], 0); return ;}
                        --k; que2[++r2] = ch[u][j];
                    }
            l2 = r;
        }
    }while(k);
}

int main()
{
    freopen("str.in", "r", stdin);
    freopen("str.out", "w", stdout);

    scanf("%d%lld\n%s", &n, &p, s + 1); 
    len[tot = 1] = -1; fail[0] = fail[1] = 1;
    for(int i = 1; i <= n; ++i) add(s[i] - 'a', i);
    printf("%d\n", tot - 1);
    k = p % (tot - 1) + 1;
    bfs();

    return 0;
}

方法2(std):
Markdown

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int MAX=500000+10;
const int INF=1000000000;
const int Alpha=28;

int n;
LL k;
char str[MAX],a[MAX];

struct Node
{
    Node* ch[Alpha];
    Node* ne[Alpha];
    Node* p;
    int len;
    int maxs;
    int place;
    int help_for_dfs;
    Node()
    {
        memset(ch,0,sizeof ch);
        memset(ne,0,sizeof ne);
        p=0;
        len=0;
        maxs=0;
        help_for_dfs=-1;
    }
}tree[MAX*2],*Root,*place[MAX];
int cnt;

Node* add(Node* v,int id,int len)
{
    Node* u=tree+cnt++;
    u->len=len;
    for(;v && !v->ch[id];v=v->p)
        v->ch[id]=u;
    if(!v)
        u->p=Root;
    else
    {
        Node* bro=v->ch[id];
        if(v->len+1==bro->len)
            u->p=bro;
        else
        {
            Node* nv=tree+cnt++;
            *nv=*bro;
            nv->len=v->len+1;
            u->p=nv;
            bro->p=nv;
            for(;v && v->ch[id]==bro;v=v->p)
                v->ch[id]=nv;
        }
    }
    return u;
}

int maxs[MAX];
int num[MAX];

int cmp(int a,int b)
{
    return tree[a].len>tree[b].len;
}

int toAdd[MAX];
LL ans[MAX];

int pa[MAX],num_pa;

void dfs(Node* S)
{
    Node* u=S;
    while(1)
    {
        int& i=u->help_for_dfs;
        if(u->place==u->len && u->len%2==0 && i==-1)
            pa[++num_pa]=u->place;
        for(++i;i<Alpha;++i)
            if(u->ne[i])
            {
                pa[++num_pa]=-u->len;
                u=u->ne[i];
                break;
            }
        if(i==Alpha)
        {
            if(u==S)
                break;
            u=u->p;
        }
    }
}

int getL(int a,int b)
{
    int dif=b/2-(a-1)/2;
    if(str[b]=='z'+1)//a到b中有多少奇数 b中的奇数个数是(b+1)/2
        return dif*2;
    else return dif*2-1;
}

int main()
{
    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
    int i;
    scanf("%d",&n);
    cin>>k;
    scanf("%s",a+1);
    int tmp=0;
    str[++tmp]='z'+1;
    REP(i,1,n)
    {
        str[++tmp]=a[i];
        str[++tmp]='z'+1;
    }
    str[tmp+1]='z'+2;
    n=tmp;
    Node* last=place[0]=Root=tree+cnt++;
    REP(i,1,n)
    {
        place[i]=last=add(last,str[i]-'a',i);
        place[i]->place=i;
    }
    int mm=1;
    maxs[1]=0;
    REP(i,1,n)
    {
        if(i<=mm+maxs[mm])
            maxs[i]=min( maxs[2*mm-i] , mm+maxs[mm]-i ) ;
        for(;str[i-maxs[i]-1]==str[i+maxs[i]+1];++maxs[i])
            ;
        if(i+maxs[i]>mm+maxs[mm])
            mm=i;
        place[i]->maxs=maxs[i];
    }
    REP2(i,0,cnt)
        num[i]=i;
    sort(num,num+cnt,cmp);
    REP2(i,0,cnt)
    {
        Node* u=tree+num[i];
        if(u->p)
        {
            u->p->maxs=max(u->p->maxs,u->maxs);
            if(!u->p->place)
                u->p->place=u->place;
            u->p->ne[ str[ u->place-u->p->len ] - 'a']=u;
            int l=u->p->len+1;
            int r=min(u->len,u->maxs+1);
            l=getL(u->place-l+1,u->place);
            r=getL(u->place-r+1,u->place);
            if(r>=l)
            {
                toAdd[l]++;
                toAdd[r+2]--;
            }
        }
    }
    LL sum=0;
    LL now=0,all=1;
    for(i=1;i<=n;i+=2)
    {
        sum+=toAdd[i];
        ans[i]=sum;
        all+=ans[i];
    }
    sum=0;
    for(i=0;i<=n;i+=2)
    {
        sum+=toAdd[i];
        ans[i]=sum;
        all+=ans[i];
    }
    all-=2;
    k=k%all+1;
    cout<<all<<endl;
    now=0;
    int anslen=0;
    REP(i,1,n)
    {
        if(now<k && now+ans[i]>=k)
        {
            k-=now;
            anslen=i;
            break;
        }
        now+=ans[i];
    }
    dfs(Root);
    int height=0;
    REP(i,1,num_pa)
    {
        int c=pa[i];
        if(c<=0)
        {
            height=min(height,(-c+1)/2);
            continue;
        }
        int u=pa[i];
        if(u-anslen+1>=1 && maxs[u-anslen+1]+1>=anslen && height<anslen)//这儿目测还有问题。。。
        {
            --k;
            if(!k)
            {
                for(int j=u;anslen;j-=2,anslen--)
                    cout<<str[j];
                cout<<endl;
                break;
            }
            height=INF;
        }
    }
    return 0;
}

从这道题我们可以看出回文树在处理回文串的优越性。

E.[省队集训2015day1T1]字符串合成

Description

给定四种对字符串 S 的操作:
(1) push_back( P ):在 S 后连接一个字符串 P,即 S = S + P,代价为| P |;
(2) push_front( P ):在 S 前连接一个字符串 P,即 S = P + S,代价为| P |;
(3) symmetry_back( ):将 S 翻转后连接在 S 之后,即 S = S + rev(S),代价为 1;
(4) symmetry_front( ):将 S 翻转后连接在 S 之前,即 S = rev(S) + S,代价为 1;
给定一个目标串 S,要求你通过上述四种操作,用最少的代价合成出目标串。初始只有一个空串。

Solution

观察可以发现三个性质:

  1. 每次合成最终的串的方法一定是先合成一个回文串,然后两边的字符暴力添加。
  2. 一个偶数长度的回文串的合成方法一定是先合成一半的串,然后翻转。
  3. 合成一个偶数长度的回文串的左半边与右半边的步数相同。

考虑在回文树上DP,设\(f(s)\)为在合成回文串\(s\)的最小代价。
同时在回文树求出\(fail_s\)(\(s\)的最长回文前缀(后缀)),\(fa_s\)(\(s\)在回文树上的父亲,\(half_s\)(不超过s长度一半的最长回文前缀)。

  • 如果\(s\)为奇数长度的回文串,则\(f_s=min(f_{fa_s}+2,f_{fail_s}+|s|-|fail_s|\)。因为\(s\)长度为奇数,所以不可能由翻转得出,只可能由首尾加字符得来。
  • 如果\(s\)为偶数唱的回文串,则合成\(s\)的最后一步一定是翻转。而\(s\)的一半却不一定是回文串。所以考虑把转移合并。若翻转前在串首增加了字符,则\(f_s=f_{fa_s}+1\)表示\(s_fa\)在最后一步翻转前在首部增加了字符。若翻转加倍前未在尾部增加了字符则\(f_s=f_{s_{half}}+\frac{s_{len}}{2}\)表示先合成\(s_{half}\)然后在尾部添加字符合成\(s\)的一半。最后翻转加倍。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;
int m, ans;
char s[maxn];

int ch[maxn][26], fail[maxn], len[maxn], half[maxn], fa[maxn], tot, last;
int f[maxn];

void add(int c, int n)
{
    int x = last;
    while(s[n - len[x] - 1] != s[n]) x = fail[x];
    if(!ch[x][c]) {
        int v = ++tot, k = fail[x];
        memset(ch[v], 0, sizeof(ch[v]));
        while(s[n - len[k] - 1] != s[n]) k = fail[k];
        fail[v] = ch[k][c]; len[v] = len[x] + 2; fa[v] = x;
        if((len[k = half[x]] + 2) * 2 > len[v]) k = fail[k];
        while(s[n - len[k] - 1] != s[n]) k = fail[k]; if(ch[k][c]) k = ch[k][c];
        half[v] = k; ch[x][c] = v; 
        if(len[v] & 1) f[v] = min(f[fa[v]] + 2, f[fail[v]] + len[v] - len[fail[v]]);
        else if(fa[v]) f[v] = min(f[fa[v]] + 1, f[half[v]] + len[v] / 2 - len[half[v]] + 1);
        else f[v] = 2;
        ans = min(ans, m - len[v] + f[v]); 
    }
    last = ch[x][c];
}

int main()
{
    freopen("synthesis.in", "r", stdin);
    freopen("synthesis.out", "w", stdout);

    int T; scanf("%d", &T);
    while(T--) {
        scanf("%s\n", s + 1); ans = m = strlen(s + 1);
        memset(ch[0], 0, sizeof(ch[0])); memset(ch[1], 0, sizeof(ch[1]));
        len[tot = 1] = -1; fail[0] = fail[1] = half[0] = half[1] = 1; last = 1;
        for(int i = 1; i <= m; ++i) add(s[i] - 'a', i);
        printf("%d\n", ans);
    }

    return 0;
}

F.[省队集训2015day1T1]月宫的符卡序列

Description

题意

Solution

这道题我的做法是用Manacher建出一个类似回文树的东西。
对这个串进行Manacher的预处理,使得每个回文串的长度都为奇数。
现在考虑建出这棵回文树(明显,所有回文串都位于odd节点下方)
对于每个位置\(i\),它对每个以它为中心的回文串贡献为\(i\)。设其最远的回文串延伸了\(f_i\),则相当于给串\(s_{[i-f_i+1,i+f_i-1]}\)到根异或上了i。
现在的问题是怎么建出这棵回文树:
在Manacher的算法过程中,设当前中心为i,当前节点为x,如果\(s_{i-f_i}=s_{i+f_i}\),那么\(x'=x→s_{i+f_i}\),这样算法结束,这棵树也就建出来了。
至于每个位置在串中的位置的求法,可以自己yy或者看下代码。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2000005;
int n;
char s[maxn];

int f[maxn], pos[maxn], ch[maxn][27], g[maxn][22], val[maxn], tot;

inline int getfa(int u, int dis)
{
    for(int i = 0; i <= 20; ++i)
        if(dis & (1 << i)) u = g[u][i];
    return u;
}

inline int next(int u, int c)
{
    if(ch[u][c]) return ch[u][c];
    ch[u][c] = ++tot;
    memset(ch[tot], 0, sizeof(ch[tot]));
    val[tot] = 0; g[tot][0] = u;
    for(int i = 1; (1 << i) <= n; ++i)
        g[tot][i] = g[g[tot][i - 1]][i - 1];
    return tot;
}

int main()
{
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);

    int T; scanf("%d\n", &T);
    memset(s, -1, sizeof(s));
    while(T--) {
        s[n = 0] = 'a' + 26; char c = getchar();
        while('a' <= c && c <= 'z') {
            s[++n] = c; s[++n] = 'a' + 26; c = getchar();
        }
        tot = 1; val[1] = 0;memset(ch[1], 0, sizeof(ch[1]));
        for(int i = 0, k = 0; i <= n; ++i) {
            if(i == 68)
                i = 68;
            if(k + f[k] - 1 >= i) {
                if(i + f[k - (i - k)] <= k + f[k]) f[i] = f[k - (i - k)], pos[i] = pos[k - (i - k)];
                else f[i] = f[k] + k - i, pos[i] = getfa(pos[k - (i - k)], f[k - (i - k)] - f[i]);
            }else f[i] = 1, pos[i] = next(1, s[i] - 'a');
            while(i - f[i] >= 0 && i + f[i] <= n && s[i - f[i]] == s[i + f[i]]) 
                pos[i] = next(pos[i], s[i - f[i]] - 'a'), ++f[i];
            val[pos[i]] ^= (i - 1) / 2;
            if(i + f[i] > k + f[k]) k = i;
        }
        int ans = 0;
        for(int i = tot; i >= 2; --i) {
            if(i != ch[1][26]) ans = max(ans, val[i]);
            val[g[i][0]] ^= val[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}

这个是laofu的做法:
先建出回文树并求出\(s_{1..i}\)的最长回文后缀,然后跑Manacher,在Manacher的过程中求出f数组,然后暴跳\(i+f_i\)最长回文后缀的fail,直到len等于f_i为止。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<queue>
#include<set>
#include<algorithm>
#define inf 2147483647
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
#define my int
#define d "%d"
#define md double
using namespace std;
const int N=2e6+100;
int getint();
int n,n2;
char s[N];
int next[N][26],fail[N],len[N],sum[N],ans,tot,last,id[N],p[N];
inline int get_fail(int p,int n) {
    while (s[n]!=s[n-len[p]-1]) p=fail[p];
    return p;
}
inline void add(int c,int n) {
    int p=get_fail(last,n);
    if (!next[p][c]) {
        len[++tot]=len[p]+2;memset(next[tot],0,sizeof(next[tot]));sum[tot]=0;
        fail[tot]=next[get_fail(fail[p],n)][c];
        next[p][c]=tot;
    }
    last=next[p][c];
}
inline void work() {
    scanf("%s",s+1);n=strlen(s+1);ans=0;memset(next,0,sizeof(next[0])<<1);
    last=tot=1;len[0]=0,len[1]=-1,fail[0]=fail[1]=1;
    for (int i=1;i<=n;i++)
        add(s[i]-'a',i),p[i]=last;
    for (int i=n;i;i--) s[i<<1]=s[i],s[(i<<1)-1]='*';s[0]='^';n2=n<<1;s[n2+1]='*';s[n2+2]='&';
    for (int i=1,mx=0,cn;i<=n2;i++) {
        id[i]=mx>i?min(mx-i,id[(cn<<1)-i]):0;
        while (s[i-id[i]-1]==s[i+id[i]+1]) id[i]++;
        int &j=p[(i+id[i])>>1];
        while(len[j]>id[i]) j=fail[j];
        sum[j]^=(i>>1)-1;
        if (i+id[i]>mx) mx=i+id[i],cn=i;
    }
    for (int i=tot;i!=1;i--) {
        for (int j=0;j<26;j++) if (next[i][j]) sum[i]^=sum[next[i][j]];
        ans=max(ans,sum[i]);
    }
    printf("%d\n",ans);
}
int main()
{
    fre("A");
    for (int T=getint();T--;)
        work();
      return 0;
}
int getint()
{
      int w=0;
    bool q=1;
    char c=getchar();
    while ((c<'0'||c>'9') && c!='-') c=getchar();
    if (c=='-') q=0,c=getchar();
      while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
    return q? w:-w;
}

G.[省队集训2017day3T2]回文串

Description

Description

Solution

可以看出题目所求的其实是\(fail\)树的一段路径和。
考虑离线建出最终的回文树,然后在求出每个位置最终的最长回文前缀与后缀。
每次询问实际上的值是\(len_i*right_i\),其中right是字符串的出现次数。用动态树维护即可。
值得注意的是lca有时候不会被统计进答案,所以要特判。

感觉讲的好不清楚啊,不懂来问我吧,QAQ...

#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
const int maxn = 300005;
int n, m;

inline int gi()
{
    char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    int sum = 0;
    while('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
    return sum;
}

//动态树
struct link_cut_tree
{

    int ch[maxn][2], f[maxn], rev[maxn], val[maxn];
    lint sumv[maxn], suml[maxn], sum[maxn], addv[maxn];

    #define isroot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x)
    #define get(x) (ch[f[x]][1] == x)

    inline void update(int x)
    {
        suml[x] = suml[ch[x][0]] + suml[ch[x][1]] + val[x];
        sumv[x] = sumv[ch[x][0]] + sumv[ch[x][1]] + sum[x] + addv[x] * suml[x];
    }

    inline void rotate(int x)
    {
        int fa = f[x], gfa = f[fa], k = get(x);
        if(!isroot(fa)) ch[gfa][get(fa)] = x;
        ch[fa][k] = ch[x][k ^ 1]; f[ch[x][k ^ 1]] = fa;
        ch[x][k ^ 1] = fa; f[fa] = x;
        f[x] = gfa;
        update(fa); update(x);
    }

    inline void pushdown(int x)
    {
        if(addv[x]) {
            if(ch[x][0]) addv[ch[x][0]] += addv[x], sumv[ch[x][0]] += addv[x] * suml[ch[x][0]];
            if(ch[x][1]) addv[ch[x][1]] += addv[x], sumv[ch[x][1]] += addv[x] * suml[ch[x][1]];
            sum[x] += addv[x] * val[x];
            addv[x] = 0;
        }
        if(rev[x]) {
            rev[x] = 0;
            if(ch[x][0]) rev[ch[x][0]] ^= 1;
            if(ch[x][1]) rev[ch[x][1]] ^= 1;
            swap(ch[x][0], ch[x][1]);
        }
    }

    int stk[maxn], top;
    inline void splay(int x)
    {
        stk[top = 1] = x;
        while(!isroot(x)) stk[++top] = x = f[x];
        while(top) pushdown(stk[top--]);
        x = stk[1];
        while(!isroot(x)) {
            int fa = f[x];
            if(!isroot(fa))
                get(x) ^ get(fa) ? rotate(x) : rotate(fa);
            rotate(x);
        }
    }

    inline void access(int x)
    {
        for(int y = 0; x; y = x, x = f[x])
            splay(x), ch[x][1] = y, update(x);
    }

    inline void make_root(int x) {access(x); splay(x); rev[x] ^= 1;}

    inline void add(int u, int fa, int w) //添加新节点
    {
        if(!fa) fa = 1;
        val[u] = w; f[u] = fa;
        update(u);
    }

    inline lint query(int u, int v) //询问u,v之间的路径和
    {
        if(!u) u = 1; if(!v) v = 1;
        make_root(u); access(v); splay(v);
        return sumv[v];
    }

    inline void addright(int u) //u的right+1
    {
        make_root(1); access(u); splay(u);
        ++addv[u]; update(u);
    }

}lct;

//回文树
struct palindromic_tree
{

    int l, r, tot, s[maxn], ch[maxn][26], len[maxn], fail[maxn], pre[maxn], suf[maxn];
    int dep[maxn], f[maxn][20];

    inline void prepare() 
    {
        l = n; r = l - 1;
        len[tot = 1] = -1; fail[0] = fail[1] = 1;
        memset(s, -1, sizeof(s));
        pre[l] = pre[r] = suf[l] = suf[r] = 1;
    }

    inline void get_fa(int v)
    {
        f[v][0] = fail[v]; dep[v] = dep[fail[v]] + 1;
        for(int i = 1; i <= 18; ++i) f[v][i] = f[f[v][i - 1]][i - 1];
        lct.add(v, fail[v], len[v]);
    }

    inline int addl(int c)
    {
        s[--l] = c;
        int x = pre[l + 1]; while(s[l + len[x] + 1] != s[l]) x = fail[x];
        if(!ch[x][c]) {
            int v = ++tot, k = fail[x];
            while(s[l + len[k] + 1] != s[l]) k = fail[k];
            fail[v] = ch[k][c]; len[v] = len[x] + 2; ch[x][c] = v;
            get_fa(v);
        }
        return pre[l] = suf[l + len[ch[x][c]] - 1] = ch[x][c];
    }

    inline int addr(int c)
    {
        s[++r] = c;
        int x = suf[r - 1]; while(s[r - len[x] - 1] != s[r]) x = fail[x];
        if(!ch[x][c]) {
            int v = ++tot, k = fail[x];
            while(s[r - len[k] - 1] != s[r]) k = fail[k];
            fail[v] = ch[k][c]; len[v] = len[x] + 2; ch[x][c] = v;
            get_fa(v);
        }
        return suf[r] = pre[r - len[ch[x][c]] + 1] = ch[x][c];
    }

    inline void rebuild()
    {
        for(int i = l; i <= r; ++i) { //addr
            int x = suf[i - 1];
            while(s[i - len[x] - 1] != s[i]) x = fail[x];
            suf[i] = ch[x][s[i]];
        }
        for(int i = r; i >= l; --i) { //addl
            int x = pre[i + 1];
            while(s[i + len[x] + 1] != s[i]) x = fail[x];
            pre[i] = ch[x][s[i]];
        }
    }

    inline int lca(int u, int v)
    {
        if(dep[u] > dep[v]) swap(u, v);
        int p = dep[v] - dep[u];
        for(int i = 0; i <= 18; ++i)
            if(p & (1 << i)) v = f[v][i];
        if(u == v) return u;
        for(int i = 18; i >= 0; --i)
            if(f[u][i] != f[v][i]) {
                u = f[u][i]; v = f[v][i];
            }
        return f[u][0];
    }

    inline int jump(int u, int Maxlen)
    {
        for(int i = 18; i >= 0; --i) if(len[f[u][i]] >= Maxlen) u = f[u][i];
        return len[u] <= Maxlen ? u : f[u][0];
    }

    inline lint calcl(int l1, int r1, int l2, int r2)
    {
        int u = suf[r1], v = suf[r2];
        int lenx = r1 - l1 + 1, leny = r2 - l2 + 1;
        u = jump(u, lenx); v = jump(v, leny);
        lint ret = lct.query(u, v);
        int w = lca(u, v);
        if(len[w] != lenx && len[w] != leny && s[r1 - len[w]] == s[r2 - len[w]])
            ret -= lct.query(w, w);
        return ret;
    }

    inline lint calcr(int l1, int r1, int l2, int r2)
    {
        int u = pre[l1], v = pre[l2];
        int lenx = r1 - l1 + 1, leny = r2 - l2 + 1;
        u = jump(u, lenx); v = jump(v, leny);
        lint ret = lct.query(u, v);
        int w = lca(u, v);
        if(len[w] != lenx && len[w] != leny && s[l1 + len[w]] == s[l2 + len[w]])
            ret -= lct.query(w, w);
        return ret;
    }

}pam;

struct query
{
    bool type;
    int l1, r1, l2, r2;
}q[maxn];

int main()
{
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);

    n = gi(); m = gi(); pam.prepare();
    for(int c, i = 1; i <= n; ++i) 
        c = gi(), lct.addright(pam.addr(c));

    char s[8];
    for(int x, l1, r1, l2, r2, i = 1; i <= m; ++i) {
        scanf("%s", s);
        if (s[0] == 'a') {
            x = gi();
            if (s[3] == 'l') q[i] = (query) {0, 0, pam.addl(x)};
            else q[i] = (query) {0, 0, pam.addr(x)};
        } else {
            l1 = gi(); r1 = gi(); l2 = gi(); r2 = gi();
            q[i] = (query) {s[5] == 'r', l1 + pam.l - 1, r1 + pam.l - 1, l2 + pam.l - 1, r2 + pam.l - 1};
        }
    }

    pam.rebuild();

    for(int i = 1; i <= m; ++i) {
        if (!q[i].l1) lct.addright(q[i].r1);
        else if (!q[i].type) printf("%lld\n", pam.calcl(q[i].l1, q[i].r1, q[i].l2, q[i].r2));
        else printf("%lld\n", pam.calcr(q[i].l1, q[i].r1, q[i].l2, q[i].r2));
    }

    return 0;
}

完结撒花!
鼓掌熊

感觉回文树很有趣的,大家都来学一下吧。

超人熊

最后声明一下:由于这篇文章包括了部分校内题,所以仅限会员查看。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:回文树总结 by dsl


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前,相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!