P6292 区间本质不同子串个数

又是一道SAM+LCT综合运用的题。

因为是区间查询,所以我们可以把询问离线下来,然后依次加入字符并考虑rr端点为这个字符的所有询问。然后我们需要实现两个操作:

  • 插入一个字符
  • 查询最晚的起始位置l\geq l的本质不同字串个数

考虑插入一个字符会对答案造成的影响:显然会把xx经过xx的所有祖先最后到rootroot的这条路径上的节点的最晚起始位置进行更新。这样就出现了一个问题:虽然LCT能进行链加/链覆盖,但是区间查询却做不到。那就考虑再维护一个线段树,线段树第ii位代表startpos=istartpos=i的本质不同子串的个数。

当先加入一个节点的时候,我们需要再线段树上移除会被更改的节点原来的贡献并加入新的贡献。而一个很显然的性质就是当SAMSAM上一条从儿子到祖先路径代表的所有子串的最后一个endposendpos是相同的时,那么他们的startposstartpos就是一段连续的区间。而根据LCT的性质,一个点到根的路径上只有log\logsplay,所以我们可以根据某个节点属于哪个splay将路径上节点分为log\log个类,每个类进行一次修改都能转化成线段树的区间加操作,然后就做完了。复杂度O(mlog2n)O(m\log^2n)

有个地方需要注意一下:
因为我们定义下的LCT是需要满足每个splay中的所有点的最大的endpos均相同,所以我们不能到处access,只有在修改的时候才能做一次access

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
#define int long long
typedef long long ll;
using namespace std;
const int maxn=2e5+10000;
int n,len[maxn];
struct segment_tree{
	ll val[maxn<<2],tag[maxn<<2];
	segment_tree(){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<=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 query(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+=query(l,mid,rt<<1,tl,tr);
		if(tr>=mid+1)ans+=query(mid+1,r,rt<<1|1,tl,tr);
		return ans;
	}
}t;
struct LCT{
	int ch[maxn][2],f[maxn],tag[maxn],endpos[maxn],stk[maxn];
	bool isrt(int rt){return (ch[f[rt]][0]!=rt)&&(ch[f[rt]][1]!=rt);}
	void rotate(int rt){
		int x=rt,y=f[x],z=f[y],o=ch[y][1]==x,w=ch[x][o^1];
		bool flag=isrt(y);
		ch[y][o]=w;
		f[w]=y;
		ch[x][o^1]=y;
		f[y]=x;
		if(!flag)ch[z][ch[z][1]==y]=x;
		f[x]=z;
	}
	void push_down(int rt){
		if(tag[rt]){
			tag[ch[rt][0]]=tag[ch[rt][1]]=tag[rt];
			endpos[ch[rt][0]]=endpos[ch[rt][1]]=tag[rt];
			tag[rt]=0;
		}
	}
	void splay(int rt){
		int top=0,x=rt;
		for(int y=rt;;y=f[y]){
			stk[++top]=y;if(isrt(y))break;
		}
		while(top)push_down(stk[top--]);
		for(;!isrt(x);rotate(x)){
			int y=f[x];if(isrt(y))continue;
			rotate((ch[f[x]][1]==x)==(ch[f[y]][1]==y)?y:x);
		}
	}
	void chain_update(int x1,int x2,int edpos,bool dodel,int ck){
		if(dodel){
			for(int y=0,x=(ck)?ck:x2;x;y=x,x=f[x]){
				
				splay(x);ch[x][1]=y;int st_l=len[f[x]]+1,ed_l=len[x];
				if(ed_l)t.add(1,n,1,endpos[x]-ed_l+1,endpos[x]-st_l+1,-1);
			}
		}
		for(int y=0,x=x1;x;y=x,x=f[x]){
			splay(x);ch[x][1]=y;int st_l=len[f[x]]+1,ed_l=len[x];
			if(ed_l)t.add(1,n,1,edpos-ed_l+1,edpos-st_l+1,1);
		}
	}
	void add(int x,int val){
		endpos[x]=val,tag[x]=val;
	}
	void link(int x,int fa,int edpos,int ty,int ck=0){
		splay(x);f[x]=fa;
		if(ty)
		chain_update(x,fa,edpos,edpos!=1,ck);
		if(ty){splay(x);add(x,edpos);}
	}
	void cut(int x,int st_l,int ed_l){
		splay(x);
		if(ed_l){t.add(1,n,1,endpos[x]-ed_l+1,endpos[x]-st_l+1,-1);}
		f[ch[x][0]]=f[x],ch[x][0]=0;
	}
}lct;
struct SAM{
	int link[maxn],ch[maxn][27],cnt,last;
	SAM(){cnt=last=1;}
	void insert(int c,int edpos){
		int p=last,cur=++cnt;len[cur]=len[p]+1;
		while(p&&!ch[p][c])ch[p][c]=cur,p=link[p];
		if(!p)link[cur]=1,lct.link(cur,1,edpos,1);
		else{
			int q=ch[p][c];
			if(len[p]+1==len[q])link[cur]=q,lct.link(cur,q,edpos,1);
			else{
				int cl=++cnt;len[cl]=len[p]+1;lct.splay(q);lct.endpos[cl]=lct.endpos[q];
				memcpy(ch[cl],ch[q],sizeof(ch[cl]));
				lct.cut(q,len[link[q]]+1,len[cl]);
				link[cl]=link[q];lct.link(cl,link[q],edpos,0);
				lct.link(cur,cl,edpos,1,link[cl]);
				lct.link(q,cl,edpos,0);
				link[cur]=link[q]=cl;
				while(p&&ch[p][c]==q)ch[p][c]=cl,p=link[p];
			}
		}
		last=cur;
	}
}sam;
char s[maxn];
struct QAQ{
	int l,r,id;
}query[maxn];
bool cmp(QAQ a,QAQ b){return a.r<b.r;}
ll out[maxn];
signed main(){
	scanf("%s",s+1);n=strlen(s+1);
	int q;scanf("%lld",&q);
	rep(i,1,q){
		scanf("%lld%lld",&query[i].l,&query[i].r);query[i].id=i;
	}
	sort(query+1,query+1+q,cmp);
	int top=0;
	rep(i,1,q){
		while(top<query[i].r)sam.insert(s[top+1]-'a',top+1),top++;
		ll ans=t.query(1,n,1,query[i].l,query[i].r);
		out[query[i].id]=ans;
	}
	rep(i,1,q)printf("%lld\n",out[i]);
	return 0;
}