跳转至

区间本质不同子串数

题意

\(q\)次询问区间本质不同子串个数，非强制在线。

\(n,q\le10^5\)

题解

考虑离线，枚举右端点，处理所有相关的询问。对于每种本质不同的子串，考虑只记录其最后一次出现。有这样一种暴力做法：维护SAM上每个节点的\(ed\)，对于节点\(x\)，若其表示的串长度范围为\([L,R]\)，则在\([ed[x]-R+1,ed[x]-L+1]\)这个区间\(+1\)，最后每个位置\(i\)上的值就表示有多少个以\(i\)为左端点的串是当前的最后出现，询问则直接查询区间和，这个可以用线段树实现。问题是如何维护\(ed\)。每次移动右端点，相当于把parent树上某个点到根的路径上所有点的\(ed\)修改为当前右端点，这与LCT中的access操作有些类似，可以借助类似的手段，把该点到根路径上所有点搞到一个splay中后再打标记修改，途中再维护一下相关的贡献即可，由于parent树的性质，一个splay中的点代表的长度区间也一定是连续的，依然可以直接区间修改。复杂度\(\mathcal{O}(n\log^2n)\)。

代码（洛谷P6292）

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int N=200010;
const int inf=2147483647;
LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10ll+ch-'0',ch=getchar();
    return x*f;
}
//SAM
char str[N];
int lst=1,tot=1,ch[N][26],mx[N],par[N],ed[N];
void extend(int x)
{
    int p=lst,np=++tot;mx[np]=mx[p]+1;
    while(p&&!ch[p][x])ch[p][x]=np,p=par[p];
    if(!p)par[np]=1;
    else
    {
        int q=ch[p][x];
        if(mx[p]+1==mx[q])par[np]=q;
        else
        {
            int nq=++tot;mx[nq]=mx[p]+1;
            for(int i=0;i<26;i++)ch[nq][i]=ch[q][i];
            par[nq]=par[q];
            par[q]=par[np]=nq;
            while(ch[p][x]==q)ch[p][x]=nq,p=par[p];
        }
    }
    lst=np;
}
//Segment Tree
struct Seg
{
    int l,r,lc,rc;LL s,tag;
}tr[N<<1];
int cnt=0;
void up(int x)
{
    int lc=tr[x].lc,rc=tr[x].rc;
    tr[x].s=tr[lc].s+tr[rc].s;
}
void build(int l,int r)
{
    int x=++cnt;
    tr[x].l=l;tr[x].r=r;tr[x].s=tr[x].tag=0;
    if(l==r)return;
    int mid=l+r>>1;
    tr[x].lc=cnt+1,build(l,mid);
    tr[x].rc=cnt+1,build(mid+1,r);
}
void Add(int x,LL v){tr[x].s+=(LL)v*(tr[x].r-tr[x].l+1);tr[x].tag+=v;}
void down(int x)
{
    if(tr[x].tag)
    {
        int lc=tr[x].lc,rc=tr[x].rc;
        Add(lc,tr[x].tag),Add(rc,tr[x].tag);
        tr[x].tag=0;
    }
}
void add(int x,int l,int r,LL v)
{
    if(tr[x].l==l&&tr[x].r==r){Add(x,v);return;}
    down(x);
    int mid=tr[x].l+tr[x].r>>1,lc=tr[x].lc,rc=tr[x].rc;
    if(r<=mid)add(lc,l,r,v);
    else if(l>mid)add(rc,l,r,v);
    else add(lc,l,mid,v),add(rc,mid+1,r,v);
    up(x);
}
LL query(int x,int l,int r)
{
    if(tr[x].l==l&&tr[x].r==r)return tr[x].s;
    down(x);
    int mid=tr[x].l+tr[x].r>>1,lc=tr[x].lc,rc=tr[x].rc;
    if(r<=mid)return query(lc,l,r);
    if(l>mid)return query(rc,l,r);
    return query(lc,l,mid)+query(rc,mid+1,r);
}
//Link Cut Tree
int son[N][2],fa[N],R[N];bool mark[N];
void push_down(int x)
{
    if(mark[x])
    {
        if(son[x][0])R[son[x][0]]=R[x],mark[son[x][0]]=true;
        if(son[x][1])R[son[x][1]]=R[x],mark[son[x][1]]=true;
        mark[x]=false;
    }
}
bool is_root(int x)
{
    if(son[fa[x]][0]==x)return false;
    if(son[fa[x]][1]==x)return false;
    return true;
}
void rotate(int x)
{
    int y=fa[x],z=fa[y];
    int a=son[y][1]==x,b=son[z][1]==y;
    if(!is_root(y))son[z][b]=x;
    fa[x]=z;
    int g=son[x][!a];
    son[y][a]=g;fa[g]=y;
    son[x][!a]=y;fa[y]=x;
}
void w(int x)
{
    if(!is_root(x))w(fa[x]);
    push_down(x);
}
void splay(int x)
{
    w(x);
    while(!is_root(x))
    {
        int y=fa[x],z=fa[y];
        if(!is_root(y))
        {
            if((son[z][1]==y)==(son[y][1]==x))rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
}
void access(int x,int r)
{
    add(1,1,r,1);
    int last=0;
    while(x)
    {
        splay(x);
        son[x][1]=last;
        push_down(x);
        if(x!=1&&R[x])add(1,R[x]-mx[x]+1,R[x]-mx[fa[x]],-1);
        last=x;
        x=fa[x];
    }R[last]=r;mark[last]=true;
}
vector<pa>Q[N];LL ans[N];
int main()
{
    scanf("%s",str+1);
    int len=strlen(str+1);
    for(int i=1;i<=len;i++)extend(str[i]-'a'),ed[i]=lst;
    for(int i=2;i<=tot;i++)fa[i]=par[i];
    build(1,len);
    int q=read();
    for(int i=1;i<=q;i++)
    {
        int l=read(),r=read();
        Q[r].push_back(make_pair(l,i));
    }
    for(int i=1;i<=len;i++)
    {
        access(ed[i],i);
        for(pa t:Q[i])ans[t.second]=query(1,t.first,i);
    }
    for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
    return 0;
}