区间本质不同子串个数

题目传送门

前言

借鉴了题解中的这篇。

起因

前面多校训练的时候，出了一道和这道题十分类似但是又差别很大的题目。于是想着先把这道题给学会了，然后再尝试写多校训练中出现的那道题目。

本题知识点一览

$SAM$ + $LCT$ + 线段树 + 扫描线思想 + 离线处理

乱七八糟的

因为当时我还并不会 $LCT$ ，于是才有了昨天的那篇学习 $LCT$ 的文章。然后，为了学 $LCT$ ，又需要学会 $splay$ 和树剖，于是又有了上上篇的学习树剖， $splay$ 实在是学不动了(其实就是懒)，就直接跳过 $splay$ 去学 $LCT$ 了，然后对于 $LCT$ 的理解，除了 $splay$ 部分，感觉还是可以的(然而只有学会 $splay$ 才能完全理解 $LCT$ )。

当时写着写着才发现我甚至还没有一个像样的线段树板子，于是当时就去 copy 了一份，到后面了再总结一下这个板子。

步入正文

题意

给出一个长度为 $n(1 \leq n \leq 10^5)$ 的字符串 $S$ ，$m(1 \leq m \leq 2 \times 10^5)$ 次询问由 $S$ 的第 $L$ 到第 $R$ 个字符组成的字符串包含多少个本质不同的子串。

思路

我们首先考虑静态区间不同元素种类数这种经典问题的求解方法。

首先把所有询问离线下来，根据右端点排序。

对于一个固定的右端点 $i$ ，贪心的只考虑 $i$ 之前每种元素最后出现的位置。按下标从左到右扫描线，用线段树维护每个位置是否在前缀 $i$ 种最后一次出现。加入第 $i$ 个元素时，在线段树中把当前位置 $+1$ ，把上一个相同元素的位置 $-1$ 。答案就直接区间查询即可。

我们发现这道题是可以采用这个思路的。

我们把每种本质不同的子串都当作是一种元素。

线段树中维护区间和，每个位置 $i$ 表示那些此时以 $i$ 位置为开头并且是最后一次出现的子串的数量。

那么，在插入 $i$ 位置时，我们应当把所有以 $i$ 为结尾的子串的贡献加入到线段树中，再把重复出现的子串的上次出现位置的贡献给删掉，子串有长度，我们只需要维护左端点即可(即上一段说的定义)。把贡献加入到线段树我们可以直接使用一次区间加就可以完成，但是把上次的贡献给删掉就不好搞了，因为我们并不知道他们上次出现的位置。

于是，我们建一个后缀自动机，那么以 $i$ 位置结尾的子串就是前缀 $i$ 对应的节点在后缀链接树上的所有 $father$ 节点。根据 $SAM$ 的特点，每个节点会表示同一个状态的多个子串，而他们的上一次出现的位置的右端点是完全一样的，而且他们的左端点是一个连续的片段。

考虑暴力求解，对每一个节点设置一个染色，我们可以暴力向上跳后缀链接树并在线段树上进行区间修改，同时，我们还需要把这条链染成 $i$ 颜色，表示最后一次出现的位置的右端点是 $i$ 。但是显然这种复杂度是无法接受的。

通过观察，我们发现我们操作的好像都是 $SAM$ 上的链，于是我们考虑 $LCT$ 进行优化，我们发现“暴力向上跳后缀链接树并在线段树上进行区间修改”正好对应着 $LCT$ 上的 $access$ 操作，我们可以利用 $access$ 操作中的断链、连接链来直接进行线段树上的区间加操作和整条链染色的操作，这样做的复杂度是十分友好的。

代码

#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=100005;

int n,m,pos[MAXX];
char s[MAXX];

struct SamNode{
	int ch[26];
	int len,fa;
	SamNode(){memset(ch,0,sizeof(ch));len=0;}
}sam[MAXX<<1];
int las=1,sam_cnt=1;
//LL num[MAXX<<1];
void add(int c){
	int p=las;int np=las=++sam_cnt;
//	num[np]=1LL;//此行为计数用，标记出现过几次 
	sam[np].len=sam[p].len+1;
	for(;p&&!sam[p].ch[c];p=sam[p].fa) sam[p].ch[c]=np;
	if(!p) sam[np].fa=1;
	else{
		int q=sam[p].ch[c];
		if(sam[q].len==sam[p].len+1) sam[np].fa=q;
		else{
			int nq=++sam_cnt;sam[nq]=sam[q];
			sam[nq].len=sam[p].len+1;
			sam[q].fa=sam[np].fa=nq;
			for(;p&&sam[p].ch[c]==q;p=sam[p].fa) sam[p].ch[c]=nq;
		}
	}
}
struct Seg{
	LL val[MAXX<<2],tag[MAXX<<2];
	Seg(){memset(val,0,sizeof(val));memset(tag,0,sizeof(tag));}
	void push_down(int rt,int l,int r){
		if(tag[rt]){
			int mid=(l+r)>>1;
			tag[rt<<1]+=tag[rt],tag[rt<<1|1]+=tag[rt];
			val[rt<<1]+=tag[rt]*(mid-l+1);val[rt<<1|1]+=tag[rt]*(r-(mid+1)+1);
			tag[rt]=0;
		}
	}
	void push_up(int rt){
		val[rt]=val[rt<<1]+val[rt<<1|1];
	}
	void add(int l,int r,int rt,int tl,int tr,LL w){
        if(tl>tr) return;
		if(tl<=l&&r<=tr){
			tag[rt]+=w;val[rt]+=w*(r-l+1);return;
		}
		push_down(rt,l,r);
		int mid=(l+r)>>1;
		if(tl<=mid)add(l,mid,rt<<1,tl,tr,w);
		if(tr>=mid+1)add(mid+1,r,rt<<1|1,tl,tr,w);
		push_up(rt);
	}
	LL getsum(int l,int r,int rt,int tl,int tr){
		if(tl<=l&&r<=tr){return val[rt];}
		push_down(rt,l,r);
		int mid=(l+r)>>1;LL ans=0;
		if(tl<=mid)ans+=getsum(l,mid,rt<<1,tl,tr);
		if(tr>=mid+1)ans+=getsum(mid+1,r,rt<<1|1,tl,tr);
		return ans;
	}
}seg;
//add(1,n,1,l,r,v);
struct LCT{
    struct node{
        int fa,left,right,val,cov;
    }s[MAXX<<1];
    inline void pushdown(int i){
        if(s[i].cov){
            if(s[i].left) s[s[i].left].val=s[s[i].left].cov=s[i].cov;
            if(s[i].right) s[s[i].right].val=s[s[i].right].cov=s[i].cov;
            s[i].cov=0;
        }
    }
    inline int identify(int i){
        if(s[s[i].fa].left==i) return 0;
        if(s[s[i].fa].right==i) return 1;
        return -1;
    }
    inline void connect(int i,int f,int op){
        s[i].fa=f;
        if(op==1) s[f].right=i;
        if(op==0) s[f].left=i;
    }
    inline void rotate(int x){
        int y=s[x].fa;
        int z=s[y].fa;
        int opy=identify(y);
        int opx=identify(x);
        int u=0;
        if(opx==1) u=s[x].left;
        if(opx==0) u=s[x].right;
        connect(u,y,opx);
        connect(y,x,opx^1);
        connect(x,z,opy);
    }
    void pushall(int x){
        if(identify(x)!=-1) pushall(s[x].fa);
        pushdown(x);
    }
    inline void splay(int i){
        pushall(i);
        while(identify(i)!=-1){
            int up=s[i].fa;
            if(identify(up)==-1) rotate(i);
            else if(identify(i)==identify(up)) rotate(up),rotate(i);
            else rotate(i),rotate(i);
        }
    }
    inline int access(int k,int id){
        int temp=0;
        while(k){
            splay(k);
            if(s[k].val){
                // printf("*%d %d %d\n",s[k].val-sam[k].len+1,s[k].val-sam[s[k].fa].len,-1);//
                seg.add(1,n,1,s[k].val-sam[k].len+1,s[k].val-sam[s[k].fa].len,-1);
            }
            s[k].right=temp;
            temp=k;
            k=s[k].fa;
        }
        // printf("*1 %d 1\n",id);//
        seg.add(1,n,1,1,id,1);
        s[temp].val=s[temp].cov=id;
        return temp;
    }
}lct;
struct QQ{
    int l,r,id;
}a[MAXX*2];
bool cmp(QQ jj,QQ kk){return (jj.r<kk.r);}
LL ans[MAXX*2];

inline void solve(){
    scanf("%s\n%d",s+1,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&a[i].l,&a[i].r);
        a[i].id=i;
    }
    n=strlen(s+1);
    sort(a+1,a+m+1,cmp);

    for(int i=1;i<=n;++i){
        add(s[i]-'a');
        pos[i]=las;
    }

    for(int i=2;i<=sam_cnt;++i){
        lct.s[i].fa=sam[i].fa;
    }

    int p=1;
    for(int i=1;i<=n;++i){
        lct.access(pos[i],i);
        while(a[p].r==i)
            ans[a[p].id]=seg.getsum(1,n,1,a[p].l,a[p].r),++p;
    }

    for(int i=1;i<=m;++i)
        printf("%lld\n",ans[i]);
}

signed main(){
//	LL t;scanf("%lld",&t);
//	while(t--)
		solve();
	
	return 0;
}