【2024NOI模拟赛11】项链 做题记录

给定一个长 $n$ 的字符串 $s$，$q$ 次询问，第 $i$ 次查询 $r\in[L_i,R_i]$ 的所有 $s$ 的子串 $s_{[l,r]}$ 有多少个本质不同的回文串。

$1\le n,q\le 2\times 10^5$，$s$ 字符集为小写字母。

赛时题解

先求出每个点往左往右拓展的长度（二分哈希/Manacher），再建 SAM，扫描线求出 SAM 每个节点中回文串个数。

问题转化为：

给定一棵有点权的有根树和一个节点序列 $a$，$q$ 次询问，每次求 $a_{[l,r]}$ 到根的路径覆盖到的所有点的点权和。

可以离线。

回滚莫队维护，$O(n\sqrt n)$。

总复杂度 $O(n\log n+n\sqrt n)$。

赛后题解

最后一步也可以先树剖再启发式合并维护每个点子树中点在 $a$ 中出现位置的集合，先把 $u$ 的贡献算进其重儿子，启发式合并维护轻儿子的贡献。

具体的，令 $u$ 的子树大小为子树中每个点在 $a$ 中出现的次数之和，按照这个定义进行重链剖分。

剖分完令 $w_u$ 为 $u$ 到其所在重链链顶的点权和，$st_u$ 为 $u$ 子树中每个点在 $a$ 中出现位置的集合，则 $st_u$ 直接从 $st_{hev_u}$ 继承（$hev_u$ 为 $u$ 的重儿子），然后把 $u$ 在 $a$ 中的出现位置插入到 $st_u$，再遍历 $u$ 的轻儿子 $v$，把 $x\in st_v$ 插入到 $st_u$。

每次插入 $x$ 找到其前驱后继 $lb,rb$，给 $l\in [lb,x],r\in [x,rb]$ 的所有区间 $[l,r]$ 增加 $w_u$ 的贡献，这个可以离线再用扫描线维护。

这样由于轻儿子 $st_v$ 的大小总是不超过 $st_u$ 的大小，所以时间复杂度是启发式合并的复杂度，总复杂度 $O(n\log ^2n)$。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <set>

using namespace std;

typedef long long ll;

const int S=200005,MS=8000005,V=26;
const int bse=31,p1=998244353,p2=1000000007;

struct SAM
{
	int cnt,lst;
	int len[S*2],to[S*2][V],link[S*2];
	int rt[S*2];
	vector<int> son[S*2];
	int rb[S*2],rbs[S*2],siz[S*2];
	inline void init()
	{
		cnt=lst=0;
		len[0]=0;
		memset(to[0],0,sizeof(to[0]));
		link[0]=-1;
	}
	inline void ins(int c)
	{
		int u=++cnt;
		len[u]=len[lst]+1;
		memset(to[u],0,sizeof(to[u]));
		int p=lst;
		while(p!=-1&&to[p][c]==0) to[p][c]=u,p=link[p];
		if(p==-1) link[u]=0;
		else
		{
			int q=to[p][c];
			if(len[q]==len[p]+1) link[u]=q;
			else
			{
				int cpy=++cnt;
				len[cpy]=len[p]+1;
				memcpy(to[cpy],to[q],sizeof(to[q]));
				link[cpy]=link[q];
				link[q]=cpy;
				while(p!=-1&&to[p][c]==q) to[p][c]=cpy,p=link[p];
				link[u]=cpy;
			}
		}
		lst=u;
		rt[len[u]]=u;
	}
	void dfs(int u,int fa)
	{
		for(int v:son[u]) dfs(v,u),rb[u]=max(rb[u],rb[v]),rbs[u]+=rbs[v];
	}
	inline void build()
	{
		for(int i=1;i<=cnt;i++) son[link[i]].push_back(i);
		for(int i=1;i<=len[lst];i++) rb[rt[i]]=i,rbs[rt[i]]++;
		dfs(0,0);
	}
};

struct node
{
	int lb,rb,p,w;
};

int n,Q;
char a[S];
vector<pair<int,int> > que[S];
SAM sam;
int b[S*2],ext[S*2],len[S*2];
vector<pair<pair<int,int>,int> > vec[S];
int tr[S*3];
int idx[S*2];
int hev[S*2],tp[S*2],sm[S*2];
set<int> st[S*2];
vector<node> cge;
ll ans[S];

inline void manacher()
{
	int m=n*2+1;
	for(int i=1;i<=n;i++) b[i*2]=a[i];
	for(int i=1;i<=m;i+=2) b[i]=-2;
	b[0]=-1,b[m+1]=-3;
	for(int i=1,p=0;i<=m;i++)
	{
		ext[i]=1;
		if(p+ext[p]-1>=i) ext[i]=min(ext[2*p-i],p+ext[p]-i);
		while(b[i-ext[i]]==b[i+ext[i]]) ext[i]++;
		if(i+ext[i]>p+ext[p]) p=i;
	}
	for(int i=1;i<=n;i++) len[i]=ext[i*2]/2,len[n+i]=ext[i*2+1]/2;
}

inline void addtr(int p,int x)
{
	p+=n*2;
	for(int i=p;i<=n*3;i+=i&-i) tr[i]+=x;
}
inline int quetr(int p)
{
	p+=n*2;
	int res=0;
	for(int i=p;i>=1;i-=i&-i) res+=tr[i];
	return res;
}

void dfs1(int u)
{
	hev[u]=-1;
	for(int v:sam.son[u])
	{
		dfs1(v);
		if(hev[u]==-1||sam.rbs[v]>sam.rbs[hev[u]]) hev[u]=v;
	}
}

void dfs2(int u,int top)
{
	tp[u]=top;
	sm[u]+=sam.siz[u];
	if(hev[u]!=-1) sm[hev[u]]+=sm[u],dfs2(hev[u],top);
	for(int v:sam.son[u]) if(v!=hev[u]) dfs2(v,v);
}

void dfs3(int u)
{
	if(hev[u]!=-1) dfs3(hev[u]);
	int rt=tp[u];
	if(idx[u]!=0)
	{
		int x=idx[u];
		int lb,rb;
		auto p=st[rt].upper_bound(x);
		if(p==st[rt].begin()) lb=1;
		else lb=*prev(p)+1;
		p=st[rt].lower_bound(x);
		if(p==st[rt].end()) rb=n;
		else rb=*p-1;
		if(lb<=x&&rb>=x)
		{
			// ([lb,x],[x,rb])
			cge.push_back((node){lb,x,x,sm[u]});
			if(rb<n) cge.push_back((node){lb,x,rb+1,-sm[u]});
			st[rt].insert(x);
		}
	}
	for(int v:sam.son[u])
	{
		if(v==hev[u]) continue;
		dfs3(v);
		for(int x:st[v])
		{
			int lb,rb;
			auto p=st[rt].upper_bound(x);
			if(p==st[rt].begin()) lb=1;
			else lb=*prev(p)+1;
			p=st[rt].lower_bound(x);
			if(p==st[rt].end()) rb=n;
			else rb=*p-1;
			if(lb<=x&&rb>=x)
			{
				// ([lb,x],[x,rb])
				cge.push_back((node){lb,x,x,sm[u]});
				if(rb<n) cge.push_back((node){lb,x,rb+1,-sm[u]});
				st[rt].insert(x);
			}
		}
	}
}

int main()
{
	freopen("necklace.in","r",stdin);
	freopen("necklace.out","w",stdout);
	scanf("%s%d",a+1,&Q);
	for(int i=1;i<=Q;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		que[r].emplace_back(l,i);
	}
	n=strlen(a+1);
	for(int i=1;i<=n;i++) a[i]-='a';
	sam.init();
	for(int i=1;i<=n;i++) sam.ins(a[i]);
	sam.build();
	manacher();
	for(int i=1;i<=sam.cnt;i++)
	{
		vec[sam.rb[i]].emplace_back(make_pair(sam.len[sam.link[i]]+1,sam.len[i]),i);
	}
	priority_queue<pair<int,int> > q;
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&-q.top().first<i) addtr(q.top().second,-1),q.pop();
		int r=i+len[i]-1,sz=1-i*2;
		addtr(sz,1);
		q.push(make_pair(-r,sz));
		if(i>1&&len[n+i-1]>0)
		{
			int r=i+len[n+i-1]-1,sz=2-i*2;
			addtr(sz,1);
			q.push(make_pair(-r,sz));
		}
		for(auto t:vec[i])
		{
			int lb=t.first.first,rb=t.first.second,id=t.second;
			sam.siz[id]=quetr(rb-i*2)-quetr(lb-1-i*2);
			// printf("((%d %d) %d) %d\n",lb,rb,i,sam.siz[id]);
		}
	}
	// for(int i=0;i<=sam.cnt;i++)
	// {
		// for(int v:sam.son[i]) printf("%d %d\n",i,v);
	// }
	// for(int i=0;i<=sam.cnt;i++) printf("%d ",sam.siz[i]);
	// printf("\n"); 
	// for(int i=1;i<=n;i++) printf("%d ",sam.rt[i]);
	// printf("\n");
	for(int i=1;i<=n;i++) idx[sam.rt[i]]=i;
	dfs1(0),dfs2(0,0);
	// for(int i=0;i<=sam.cnt;i++) printf("%d: (%d %d)\n",i,tp[i],sm[i]);
	for(int i=1;i<=n*3;i++) tr[i]=0;
	dfs3(0);
	sort(cge.begin(),cge.end(),[&](node x,node y){return x.p<y.p;});
	for(int i=1,j=0;i<=n;i++)
	{
		while(j<cge.size()&&cge[j].p==i) addtr(cge[j].lb,cge[j].w),addtr(cge[j].rb+1,-cge[j].w),j++;
		for(auto t:que[i]) ans[t.second]+=quetr(t.first);
	}
	for(int i=1;i<=Q;i++) printf("%lld\n",ans[i]);
	return 0;
}