题解：P4384 [八省联考 2018] 制胡窜

· · 题解

套路题，不太懂为什么能放到 \text{D2T3}，感觉难度低于 \text{D1T1} 的一双木棋。

Solution

先对这个串建出 \text{SAM}，并用线段树合并求出每个状态的 \text{endpos}，所有对于一次询问 (l,r) 先在 \text{parent} 树上倍增找到 [l,r] 对应的状态，令 len 为这个串的长度，S 为这个串的 \text{endpos}，然后考虑容斥：

总时间复杂度 O(n\log n+q\log n)。

Code

//when you use vector or deque,pay attention to the size of it.
//by OldDirverTree
#include<bits/stdc++.h>
//#include<atcoder/all>
#define P pair<int,int>
#define int long long
#define mid (l+r>>1)
using namespace std;
//using namespace atcoder;
const int N=2e5;
int cur=1,tot=1;
vector<int> g[N];
int n,m,fa[N][17];
int pos[N],root[N];
char s[N];

struct node {
    int len,fa;
    int son[10];
}T[N];

struct custom_hash
{
    static uint64_t splitmix64(uint64_t x) {
        x+=0x9e3779b97f4a7c15;
        x=(x^(x>>30) )*0xbf58476d1ce4e5b9;
        x=(x^(x>>27) )*0x94d049bb133111eb;
        return x^(x>>31);
    }
    size_t operator() (uint64_t x) const {
        static const uint64_t FIXED_RANDOM=chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x+FIXED_RANDOM);
    }
};
int read() {
    int x=0; bool _=true; char c=0;
    while (!isdigit(c) ) _&=(c!='-'),c=getchar();
    while (isdigit(c) ) x=x*10+(c&15),c=getchar();
    return _?x:-x;
}
namespace SGT
{
    struct node
    {
        int l,r,pre,suf,ans;
        node friend operator +(node a,node b) {
            if (!a.ans&&!b.ans) return {a.l,b.r,0,0,0};
            if (!a.ans) return {a.l,b.r,b.pre,b.suf,b.ans+(a.r-a.l+1)*(b.r-b.pre+1)};
            if (!b.ans) return {a.l,b.r,a.pre,a.suf,a.ans+(a.suf-a.l+1)*(b.r-b.l+1)};
            return {a.l,b.r,a.pre,b.suf,a.ans+b.ans+(a.suf-a.l+1)*(b.r-b.l+1)+(a.r-a.suf)*(b.r-b.pre+1)};
        }
    }T[N<<6];
    int tot,ls[N<<6],rs[N<<6];
    void update(int &rt,int l,int r,int x) {
        T[rt=++tot]={l,r,x,x,(x-l+1)*(r-x+1)}; if (l==r) return;
        x<=mid?update(ls[rt],l,mid,x):update(rs[rt],mid+1,r,x);
    }
    node query(int rt,int l,int r,int s,int t) {
        if (s<=l&&r<=t) return rt?T[rt]:(node){l,r,0,0,0};
        if (t<=mid) return query(ls[rt],l,mid,s,t);
        if (mid<s) return query(rs[rt],mid+1,r,s,t);
        return query(ls[rt],l,mid,s,t)+query(rs[rt],mid+1,r,s,t);
    }
    int merge(int x,int y,int l,int r) {
        if (!x||!y) return x|y; int z=++tot; T[z]={l,r,0,0,0};
        ls[z]=merge(ls[x],ls[y],l,mid),rs[z]=merge(rs[x],rs[y],mid+1,r);
        return T[z]=(ls[z]?T[ls[z] ]:(node){l,mid,0,0,0})+(rs[z]?T[rs[z] ]:(node){mid+1,r,0,0,0}),z;
    }
}
void extend(int c) {
    int p=cur,np=cur=++tot; T[np].len=T[p].len+1;
    for (;p&&!T[p].son[c];p=T[p].fa) T[p].son[c]=np;
    if (!p) return T[np].fa=1,void(); int q=T[p].son[c];
    if (T[q].len==T[p].len+1) return T[np].fa=q,void();
    int nq=++tot; T[nq]=T[q],T[nq].len=T[p].len+1,T[np].fa=T[q].fa=nq;
    for (;T[p].son[c]==q;p=T[p].fa) T[p].son[c]=nq;
}
void dfs(int u) {
    for (int i=1;i<17;i++)
    fa[u][i]=fa[fa[u][i-1] ][i-1];
    for (int v:g[u]) fa[v][0]=u,dfs(v),
    root[u]=SGT::merge(root[u],root[v],1,n);
}
main()
{
    n=read(),m=read(),scanf("%s",s+1);
    for (int i=1;i<=n;i++) extend(s[i]&15),pos[i]=cur,SGT::update(root[cur],1,n,i);
    for (int i=2;i<=tot;i++) g[T[i].fa].push_back(i); dfs(1);
    while (m--) {
        int l=read(),r=read(),len=r-l+1,now=pos[r];
        for (int i=16;~i;i--) if (T[fa[now][i] ].len>=len) now=fa[now][i];
        SGT::node tmp=SGT::T[root[now] ]; int p=tmp.pre,q=tmp.suf-len+1;
        int ans=(n-p)*(n-p-1)/2+(q-1)*(q-2)/2; if (p<q) ans-=(q-p)*(q-p-1)/2;
        if (1+len<n) ans+=SGT::query(root[now],1,n,1+len,n-1).ans;
        if (p+len<n) ans-=SGT::query(root[now],1,n,p+len,n-1).ans;
        if (1+len<q) ans-=SGT::query(root[now],1,n,1+len,q-1).ans;
        if (p+len<q) ans+=SGT::query(root[now],1,n,p+len,q-1).ans;
        printf("%lld\n",ans);
    }
    return 0;
}