后缀平衡树

一、P6164 【模板】后缀平衡树

题解：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=998244353;
const double eps=1e-8;
const double alpha=0.75;
const int maxn=3000100;

struct node
{
    int lc,rc;
    int si;
    double key;
}t[maxn];

int res[maxn],rcnt,rt;
char s[maxn],str[maxn];
int *bad=NULL;
pair<double,double>par;

void decodeWithMask(char *s,int mask)
{
    int len=strlen(s);
    for(int i=0;i<len;i++)
    {
        mask=(mask*131+i)%len;
        swap(s[i],s[mask]);
    }
}

bool balance(int p)
{
    return (double)t[t[p].lc].si<=t[p].si*alpha&&(double)t[t[p].rc].si<=t[p].si*alpha;
}

void pushup(int p)
{
    t[p].si=t[t[p].lc].si+t[t[p].rc].si+1;
}

void dfs(int p)
{
    if(!p) return ;
    dfs(t[p].lc);
    res[++rcnt]=p;
    dfs(t[p].rc);
}

int build(int l,int r,double lkey,double rkey)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    int p=res[mid];
    t[p].key=(lkey+rkey)/2;
    t[p].lc=build(l,mid-1,lkey,t[p].key);
    t[p].rc=build(mid+1,r,t[p].key,rkey);
    pushup(p);
    return p;
}

void re_build(int *p)
{
    rcnt=0;
    dfs(*p);
    (*p)=build(1,rcnt,par.first,par.second);
}

bool cmp(int x,int y)
{
    return s[x]<s[y]||(s[x]==s[y]&&t[x-1].key<t[y-1].key);
}

void _insert(int &p,int xid,double lkey,double rkey)
{
    if(!p)
    {
        p=xid;
        t[p].si=1;
        t[p].key=(lkey+rkey)/2;
        t[p].lc=t[p].rc=0;
        bad=NULL;
        return ;
    }
    if(cmp(xid,p)) _insert(t[p].lc,xid,lkey,t[p].key);
    else _insert(t[p].rc,xid,t[p].key,rkey);
    pushup(p);
    if(!balance(p)) bad=&p,par=pr(lkey,rkey);
}

void __insert(int &rt,int xid)
{
    _insert(rt,xid,0,dnf);
    if(bad!=NULL)
        re_build(bad);
}


void _delete(int &p,int xid)
{
    if(p==xid)
    {
        if(!t[p].lc||!t[p].rc)
        {
            p=t[p].lc|t[p].rc;
        }
        else
        {
            int rmax=t[p].lc,last=p;
            while(t[rmax].rc)
            {
                last=rmax;
                t[last].si--;
                rmax=t[rmax].rc;
            }
            if(last==p)
            {
                t[rmax].rc=t[p].rc;
                p=rmax;
                pushup(p);
            }
            else
            {
                t[rmax].lc=t[p].lc;
                t[rmax].rc=t[p].rc;
                t[last].rc=0;
                p=rmax;
                pushup(p);
            }
        }
        return ;
    }
    if(cmp(xid,p)) _delete(t[p].lc,xid);
    else _delete(t[p].rc,xid);
    pushup(p);
}

bool cmp(int now)
{
    for(int p=1;str[p];p++,now=(now?now-1:0))
    {
        if(str[p]<s[now]) return true;
        else if(str[p]>s[now]) return false;
    }
}

int ask(int p)
{
    if(!p) return 0;
    if(cmp(p)) return ask(t[p].lc);
    else return t[t[p].lc].si+1+ask(t[p].rc);
}

int main(void)
{
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
    int mask=0;
    int nlen=strlen(s+1);
    for(int i=1;i<=nlen;i++) __insert(rt,i);

    char op[10];
    for(int i=1;i<=n;i++)
    {
        scanf("%s",op);
        if(op[0]=='A')
        {
            scanf("%s",str+1);
            decodeWithMask(str+1,mask);
            int len=strlen(str+1);
            for(int j=1;j<=len;j++)
            {
                s[nlen+j]=str[j];
                __insert(rt,nlen+j);
            }
            nlen+=len;
        }
        else if(op[0]=='D')
        {
            int k;
            scanf("%d",&k);
            for(int j=nlen;j>nlen-k;j--)
                _delete(rt,j);
            nlen-=k;
        }
        else
        {
            scanf("%s",str+1);
            decodeWithMask(str+1,mask);
            int len=strlen(str+1);
            reverse(str+1,str+len+1);
            str[len+1]='Z'+1;
            str[len+2]=0;
            int ans=ask(rt);
            str[len]--;
            ans-=ask(rt);
            printf("%d\n",ans);
            mask^=ans;
        }
    }
    return 0;
}

二、P5353 树上后缀排序

注意：这题 x 所代表的字符串应该是由 fa [ x ] 转移而来。
若x，y的 fa 不同，那么他们的 fa 所代表的字符串一定已经分出大小。

题解：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=998244353;
const double eps=1e-8;
const double alpha=0.75;
const int maxn=500100;

struct node
{
    int lc,rc;
    int si;
    double key;
}t[maxn];

int fa[maxn];
int res[maxn],rcnt,rt;
int sa[maxn],sacnt,rk[maxn];
char s[maxn],str[maxn];
int *bad=NULL;
pair<double,double>par;

bool balance(int p)
{
    return (double)t[t[p].lc].si<=t[p].si*alpha&&(double)t[t[p].rc].si<=t[p].si*alpha;
}

void pushup(int p)
{
    t[p].si=t[t[p].lc].si+t[t[p].rc].si+1;
}

void dfs(int p)
{
    if(!p) return ;
    dfs(t[p].lc);
    res[++rcnt]=p;
    dfs(t[p].rc);
}

int build(int l,int r,double lkey,double rkey)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    int p=res[mid];
    t[p].key=(lkey+rkey)/2;
    t[p].lc=build(l,mid-1,lkey,t[p].key);
    t[p].rc=build(mid+1,r,t[p].key,rkey);
    pushup(p);
    return p;
}

void re_build(int *p)
{
    rcnt=0;
    dfs(*p);
    (*p)=build(1,rcnt,par.first,par.second);
}

bool cmp(int x,int y)
{
    return s[x]<s[y]||(s[x]==s[y]&&t[fa[x]].key<t[fa[y]].key);
}

void _insert(int &p,int xid,double lkey,double rkey)
{
    if(!p)
    {
        p=xid;
        t[p].si=1;
        t[p].key=(lkey+rkey)/2;
        t[p].lc=t[p].rc=0;
        bad=NULL;
        return ;
    }
    if(cmp(xid,p)) _insert(t[p].lc,xid,lkey,t[p].key);
    else _insert(t[p].rc,xid,t[p].key,rkey);
    pushup(p);
    if(!balance(p)) bad=&p,par=pr(lkey,rkey);
}

void __insert(int &rt,int xid)
{
    _insert(rt,xid,0,dnf);
    if(bad!=NULL)
        re_build(bad);
}

void dfsForSa(int p)
{
    if(!p) return ;
    dfsForSa(t[p].lc);
    sa[++sacnt]=p;
    dfsForSa(t[p].rc);
}

void buildTree(int n)
{
    for(int i=1;i<=n;i++)
        __insert(rt,i);
    dfsForSa(rt);
    for(int i=1;i<=n;i++) rk[sa[i]]=i;
}

int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
        scanf("%d",&fa[i]);

    scanf("%s",s+1);
    buildTree(n);

    for(int i=1;i<=n;i++)
        printf("%d ",sa[i]);

    return 0;
}

三、P2408 不同子串个数

（一）每次插入后通过查询维护height：这样就实现了动态维护height，注意这个height的含义是 位置为i的后缀（其排名为rank[i]）与排名为rank[i]-1的后缀的lcp
也可以链表维护前后排名所指向的节点，插入完成时维护 height（需要讨论当前节点是父亲节点的哪个儿子）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=998244353;
const double eps=1e-8;
const double alpha=0.75;
const int maxn=100100;
const int p=131;

struct node
{
    int lc,rc;
    int si;
    double key;
}t[maxn];

int res[maxn],rcnt,rt;
int height[maxn];
llu pw[maxn],has[maxn];
char s[maxn];
int *bad=NULL;
pair<double,double>par;


bool balance(int p)
{
    return (double)t[t[p].lc].si<=t[p].si*alpha&&(double)t[t[p].rc].si<=t[p].si*alpha;
}

void pushup(int p)
{
    t[p].si=t[t[p].lc].si+t[t[p].rc].si+1;
}

void dfs(int p)
{
    if(!p) return ;
    dfs(t[p].lc);
    res[++rcnt]=p;
    dfs(t[p].rc);
}

int build(int l,int r,double lkey,double rkey)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    int p=res[mid];
    t[p].key=(lkey+rkey)/2;
    t[p].lc=build(l,mid-1,lkey,t[p].key);
    t[p].rc=build(mid+1,r,t[p].key,rkey);
    pushup(p);
    return p;
}

void re_build(int *p)
{
    rcnt=0;
    dfs(*p);
    (*p)=build(1,rcnt,par.first,par.second);
}

bool cmp(int x,int y)
{
    return s[x]<s[y]||(s[x]==s[y]&&t[x-1].key<t[y-1].key);
}

bool eq(int l1,int l2,int len)
{
    int r1=l1+len-1,r2=l2+len-1;
    return has[r1]-has[l1-1]*pw[len]==has[r2]-has[l2-1]*pw[len];
}

int getlcp(int x,int y)
{
    int l=1,r=min(x,y),ans=0;//二分长度
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(eq(x-mid+1,y-mid+1,mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}


void _insert(int &p,int xid,double lkey,double rkey)
{
    if(!p)
    {
        p=xid;
        t[p].si=1;
        t[p].key=(lkey+rkey)/2;
        t[p].lc=t[p].rc=0;
        bad=NULL;
        return ;
    }
    if(cmp(xid,p)) _insert(t[p].lc,xid,lkey,t[p].key);
    else _insert(t[p].rc,xid,t[p].key,rkey);
    pushup(p);
    if(!balance(p)) bad=&p,par=pr(lkey,rkey);
}

int findRank(int p,int xid)
{
    if(p==xid) return t[t[p].lc].si+1;
    if(cmp(xid,p)) return findRank(t[p].lc,xid);
    else return t[t[p].lc].si+1+findRank(t[p].rc,xid);
}

int findId(int p,int k)
{
    if(!p) return 0;
    if(t[t[p].lc].si==k-1) return p;
    if(t[t[p].lc].si>=k) return findId(t[p].lc,k);
    else return findId(t[p].rc,k-t[t[p].lc].si-1);
}

void __insert(int &rt,int xid)
{
    has[xid]=has[xid-1]*p+s[xid];
    _insert(rt,xid,0,dnf);
    if(bad!=NULL)
        re_build(bad);
    int k=findRank(rt,xid);
    int pre=findId(rt,k-1);
    int nt=findId(rt,k+1);
    height[xid]=getlcp(pre,xid);
    height[nt]=getlcp(xid,nt);
}

void buildTree(int n)
{
    for(int i=1;i<=n;i++)
        __insert(rt,i);
}


int main(void)
{
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
    reverse(s+1,s+n+1);
    pw[0]=1;
    for(int i=1;i<=n;i++)
        pw[i]=pw[i-1]*p;
    buildTree(n);
    ll ans1=1ll*n*(n+1)/2;
    ll ans2=0;
    for(int i=1;i<=n;i++)
        ans2+=height[i];
    printf("%lld\n",ans1-ans2);
    return 0;
}

（二）处理结束时，维护sa，rank，然后维护height
不知道是我姿势的问题，还是这玩意就是常数有点大。。。
后缀数组88ms，这个东西408ms。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=998244353;
const double eps=1e-8;
const double alpha=0.75;
const int maxn=500100;

struct node
{
    int lc,rc;
    int si;
    double key;
}t[maxn];

int res[maxn],rcnt,rt;
int sa[maxn],sacnt,rk[maxn],height[maxn];
char s[maxn];
int *bad=NULL;
pair<double,double>par;


bool balance(int p)
{
    return (double)t[t[p].lc].si<=t[p].si*alpha&&(double)t[t[p].rc].si<=t[p].si*alpha;
}

void pushup(int p)
{
    t[p].si=t[t[p].lc].si+t[t[p].rc].si+1;
}

void dfs(int p)
{
    if(!p) return ;
    dfs(t[p].lc);
    res[++rcnt]=p;
    dfs(t[p].rc);
}

int build(int l,int r,double lkey,double rkey)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    int p=res[mid];
    t[p].key=(lkey+rkey)/2;
    t[p].lc=build(l,mid-1,lkey,t[p].key);
    t[p].rc=build(mid+1,r,t[p].key,rkey);
    pushup(p);
    return p;
}

void re_build(int *p)
{
    rcnt=0;
    dfs(*p);
    (*p)=build(1,rcnt,par.first,par.second);
}

bool cmp(int x,int y)
{
    return s[x]<s[y]||(s[x]==s[y]&&t[x+1].key<t[y+1].key);
}

void _insert(int &p,int xid,double lkey,double rkey)
{
    if(!p)
    {
        p=xid;
        t[p].si=1;
        t[p].key=(lkey+rkey)/2;
        t[p].lc=t[p].rc=0;
        bad=NULL;
        return ;
    }
    if(cmp(xid,p)) _insert(t[p].lc,xid,lkey,t[p].key);
    else _insert(t[p].rc,xid,t[p].key,rkey);
    pushup(p);
    if(!balance(p)) bad=&p,par=pr(lkey,rkey);
}

void __insert(int &rt,int xid)
{
    _insert(rt,xid,0,dnf);
    if(bad!=NULL)
        re_build(bad);
}

void dfsForSa(int p)
{
    if(!p) return ;
    dfsForSa(t[p].lc);
    sa[++sacnt]=p;
    dfsForSa(t[p].rc);
}

void buildTree(int n)
{
    for(int i=n;i>=1;i--)
        __insert(rt,i);
    dfsForSa(rt);
    for(int i=1;i<=n;i++) rk[sa[i]]=i;
}

void getheight(int n)
{
    int k=0;
    for(int i=1;i<=n;i++)
    {
        if(k) k--;
        int j=sa[rk[i]-1];
        while(s[i+k]==s[j+k]) k++;
        height[i]=k;
    }
}

int main(void)
{
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
    buildTree(n);
    getheight(n);
    ll ans1=1ll*n*(n+1)/2;
    ll ans2=0;
    for(int i=1;i<=n;i++)
        ans2+=height[i];
    printf("%lld\n",ans1-ans2);
    return 0;
}