source：区间本质不同子串(Luogu6292) 区间本质不同回文子串(bzoj5384)
两个问题都可以归结为「区间本质不同元素个数」。解决这个问题有两个十分常用的方法：
离线询问。对于一个固定的右端点 ，我们对于在 中出现的元素，只在它出现的最大位置处标记。然后枚举所有以该右端点为结束位置的询问，查询 中的标记个数。然后将 后移，将因 后移引起的新增元素在其原最大位置处的标记消去，并在新最大位置处标记。
离线询问。维护答案序列
ans[]。ans[i]的值就表示当前情况下 的答案。 后移时，对于每个新增的元素 ，均在答案序列中的 处 +1 ，其中 pos 是该元素上次出现的位置，l 是该元素本次出现的位置。在处理完 后移后顺便处理询问。
实际应用中，主要看各操作所维护的是否可以连成一段，以通过数据结构加速处理。
在两个问题中，分别将「区间本质不同子串」和「区间本质不同回文子串」视为一个元素，并将其出现的位置的左端点视为「元素的位置」。
首先考虑「区间本质不同子串」。
假设右端点后移后为 ，那么 的所有新增子串为 。所以新增标记的操作很好完成，只需要区间 +1 就可以了。考虑如何找到原最大位置。
在 parent 树上考虑这些新增子串，其必然是一条自底向上的链。如果我们对于每个子串记录其最后出现的位置的右端点 rps ，显然 parent 树上的同一个节点代表的那些子串 rps 都是一样的，只是最后出现的位置的左端点是一段区间而已。所以这里有一个暴力的思路：逐级跳 link ，找到节点代表的左端点区间，区间 -1 。但是暴力跳 link 复杂度是不可取的。
实际上，假设我这次新增了 ，那么 s[1:i] 代表的子串对应的节点一直到根的这条链的 rps 都是一样的。然后左端点区间当然也是连续的，所以可以拼成一个更大的左端点，加速修改过程。问题转化为如何找到向上的最长相同 rps 段。我们可以将 rps 的赋值视作是染色操作。
对于「每次将某个节点到根染成同一种未曾出现过的颜色」这种问题，我们可以使用 LCT 中的 access 来实现。这也是个经典 trick 。一条实链上的点颜色相同，我们可以直接找到实链顶端并修改。
access 的均摊复杂度是 的，我们还需要一个线段树来支持区间修改，所以总的复杂度为 。
于是这道题可以用第一种方法来实现。
当然，第二种方法也可以做。因为 pos 刚好是逐一递减的，也就相当于在 access 内我们每次在答案序列上区间加一个等差数列。
代码采用的是第一种方法。
const int N=1e5+5,M=2e5+5;
int n;
namespace SAM{
int tot=1,las=1;
int pos[N];
struct node{
int l,link,c[26];
}a[N<<1];
int extend(int k){
int p=las,cur=las=++tot;a[cur].l=a[p].l+1;
while(p&&!a[p].c[k]) a[p].c[k]=cur,p=a[p].link;
if(!p) return a[cur].link=1,cur;
int q=a[p].c[k];
if(a[q].l==a[p].l+1) return a[cur].link=q,cur;
int now=++tot;a[now]=a[q];
a[q].link=a[cur].link=now,a[now].l=a[p].l+1;
while(p&&a[p].c[k]==q) a[p].c[k]=now,p=a[p].link;
return cur;
}
void build(char *s){
int len=strlen(s+1);
for(int i=1;i<=len;++i)
pos[i]=extend(s[i]-'a');
}
}
using namespace SAM;
using namespace std;
namespace SEG{
#define mid (l+r>>1)
#define ls p<<1,l,mid
#define rs p<<1|1,mid+1,r
long long t[N<<2],tag[N<<2];
void update(int p){
t[p]=t[p<<1]+t[p<<1|1];
}
void pushmk(int p,int l,int r,long long v){
t[p]+=1ll*(r-l+1)*v;
tag[p]+=v;
}
void pushdn(int p,int l,int r){
if(!tag[p]) return;
pushmk(ls,tag[p]);
pushmk(rs,tag[p]);
tag[p]=0;
}
void modify(int p,int l,int r,int nl,int nr,int v){
if(l>=nl&&r<=nr) return pushmk(p,l,r,v),void();
if(l> nr||r< nl) return;
pushdn(p,l,r);
modify(ls,nl,nr,v),modify(rs,nl,nr,v);
update(p);
}
long long query(int p,int l,int r,int nl,int nr){
if(l>=nl&&r<=nr) return t[p];
if(l> nr||r< nl) return 0;
pushdn(p,l,r);
return query(ls,nl,nr)+query(rs,nl,nr);
}
}
namespace LCT{
#define lc(x) c[x][0]
#define rc(x) c[x][1]
int fa[N<<1],tag[N<<1],rps[N<<1],c[N<<1][2];
bool nrt(int x){
return lc(fa[x])==x||rc(fa[x])==x;
}
void pushmk(int x,int v){
tag[x]=rps[x]=v;
}
void pushdn(int x){
pushmk(lc(x),tag[x]);
pushmk(rc(x),tag[x]);
tag[x]=0;
}
void rotate(int x){
int y=fa[x],z=fa[y],t=rc(y)==x;
if(nrt(y)) c[z][rc(z)==y]=x;fa[x]=z;
c[y][t]=c[x][t^1];fa[c[x][t^1]]=y;
c[x][t^1]=y;fa[y]=x;
}
void pushall(int x){
if(nrt(x)) pushall(fa[x]);
if(tag[x]) pushdn(x);
}
void splay(int x){
pushall(x);
while(nrt(x)){
int y=fa[x],z=fa[y];
if(nrt(y))
((rc(z)==y)^(rc(y)==x))?rotate(x):rotate(y);
rotate(x);
}
}
void access(int x,int p){
int old=x;
for(int i=0;x;x=fa[i=x]){
splay(x);rc(x)=i;
if(int v=rps[x])
SEG::modify(1,1,n,v-a[x].l+1,v-a[fa[x]].l,-1);
}
SEG::modify(1,1,n,1,p,1);
splay(old);pushmk(old,p);
}
void build(){
for(int i=2;i<=tot;++i)
fa[i]=a[i].link;
}
}
struct Query{
int l,r,id;
bool operator <(const Query &b)const{
if(r==b.r) return l<b.l;
return r<b.r;
}
}q[M];
long long ans[M];
char s[N];
int main(){
scanf("%s",s+1);n=strlen(s+1);
build(s);LCT::build();
int m;scanf("%d",&m);
for(int i=1;i<=m;++i)
r(q[i].l),r(q[i].r),q[i].id=i;
sort(q+1,q+m+1);
for(int i=1,j=1;i<=m;++i){
while(j<=q[i].r)
LCT::access(pos[j],j),++j;
ans[q[i].id]=SEG::query(1,1,n,q[i].l,q[i].r);
}
for(int i=1;i<=m;++i)
w(ans[i]),putchar(10);
return 0;
}
接下来考虑 「区间本质不同回文子串」。
所有的新增回文子串是 fail 树上的一条链。但我们怎么快速知道每个节点的上一次出现位置呢。
回文子串的最长回文后缀有如下性质
回文子串的最长回文后缀是原回文子串的 border 。
同时 border 有如下性质
将一个串的所有 border 分成 组等差数列，则 是 级别的（规定等差数列的前一项长度不大于后一项的一半）。此处的等差数列不仅是长度意义上的，也是字符串本身意义上的。
有了最长回文后缀的性质，我们可以发现这样一个优美的事实：
如上图， p 为 s 的最长回文后缀，q 为 p 的最长回文后缀。由于 p 又是 s 的前缀且 ，所以 p 的上次出现位置必然是 s 的前缀那儿；同理，q 的上次出现位置必然是 p 的前缀那儿，所以除了 s 之外，其余位置的 刚好可以拼成一个连续区间 🍻。如果设当前右端点扩展到 i ，该等差数列的最小串的目前起始位置为 P ，那么这些串的贡献区间恰好为 ；如果知道了 s 的上次出现位置 Pos ，那么当前的贡献就是 。
问题转化为 s 的上次出现位置。某个串的所有出现位置一定在其 fail 树的子树的出现位置的并集中。由于在 fail 树上，某个子树内的子串右端点一致，并且我们只需要 s 出现位置的右端点最大值，也能推出来它的左端点最大值，故我们在 fail 树上给每个节点赋值为该节点代表子串目前出现位置的右端点最大值，然后查询就是子树查询（转 DFS 序然后上线段树），修改就是单点修改。
所以对于同一个等差数列，我们可以一起处理。
再根据 border 的性质，复杂度也得到了保证。复杂度应为 。
这道题如果采用第一种离线就不好做。但是第二种离线就可以充分发掘性质。
代码
namespace SEG{
#define mid (l+r>>1)
#define ls p<<1,l,mid
#define rs p<<1|1,mid+1,r
int t[N<<2];
void modify(int p,int l,int r,int pos,int v){
t[p]=v;
if(l==r) return;
if(mid>=pos) modify(ls,pos,v);
else modify(rs,pos,v);
}
int query(int p,int l,int r,int nl,int nr){
if(l>=nl&&r<=nr) return t[p];
if(l> nr||r< nl) return 0;
return max(query(ls,nl,nr),query(rs,nl,nr));
}
}
namespace BIT{
#define lowb(x) (x&-x)
int t[N];
void add(int p,int v){
for(int i=p;i<N;i+=lowb(i))
t[i]+=v;
}
int query(int p){
int ret=0;
for(int i=p;i;i-=lowb(i))
ret+=t[i];
return ret;
}
}
namespace PAM{
int dfn,las,top,tot;
int inp[N],out[N],dif[N],upp[N],pos[N];
vector<int>g[N];
struct node{
int len,fail,c[26];
}a[N];
int getfail(int x){
while(s[top]!=s[top-a[x].len-1])
x=a[x].fail;
return x;
}
void extend(int k){
++top;
int cur=getfail(las);
if(!a[cur].c[k]){
int now=++tot;
a[now].len=a[cur].len+2;
a[now].fail=a[getfail(a[cur].fail)].c[k];
dif[now]=a[now].len-a[a[now].fail].len;
upp[now]=dif[now]==dif[a[now].fail]?upp[a[now].fail]:now;
a[cur].c[k]=now;
}
las=a[cur].c[k];
}
void dfs(int p){
inp[p]=++dfn;
for(auto v:g[p])
dfs(v);
out[p]=dfn;
}
void build(char *s){
int len=strlen(s+1);
las=tot=1;top=0;
a[0].len=0,a[1].len=-1;
a[0].fail=a[1].fail=1;
for(int i=1;i<=len;++i)
extend(s[i]-'a'),pos[i]=las;
g[1].push_back(0);
for(int i=2;i<=tot;++i)
g[a[i].fail].push_back(i);
dfs(1);
}
void solve(){
for(int i=1,now=1;i<=n;++i){
for(int j=pos[i];j;j=a[upp[j]].fail){
int l=max(1,SEG::query(1,1,dfn,inp[j],out[j])-a[j].len+2);
int r=i-a[upp[j]].len+1;
BIT::add(l,1);BIT::add(r+1,-1);
}
SEG::modify(1,1,dfn,inp[pos[i]],i);
while(q[now].r==i)
ans[q[now].id]=BIT::query(q[now].l),++now;
}
}
}