【LGP5112】FZOUTSY

如果是\(hash\)做法的话显然就是把每一个位置后面的\(k\)个位置的hash值拿出来做一个莫队板子就好了

考虑一下牛逼的\(SAM\)

我们完全可以构造出来一棵后缀树，对于每个点找到其祖先里深度最小且\(len<=k\)的一个点，我们莫队一下就好了

最优分块大小是\(\frac{n}{\sqrt{m}}\)，这样复杂度是\(O(n\sqrt{m})\)

代码

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const int maxn=6000005;

struct Ask{int l,r,rk;}q[100005];

int n,m,k,lst=1,cnt=1;LL ans;

char S[maxn>>1];

int g[maxn],h[maxn],son[maxn][7],len[maxn],pos[maxn>>1],fa[maxn],tmp[maxn];

int tax[maxn>>1],A[maxn],id[maxn>>1];LL Ans[100005];

inline void ins(int c,int o) {

	int p=++cnt,f=lst;lst=p;

	len[p]=len[f]+1,pos[o]=p;

	while(f&&!son[f][c]) son[f][c]=p,f=fa[f];

	if(!f) {fa[p]=1;return;}

	int x=son[f][c];

	if(len[f]+1==len[x]) {fa[p]=x;return;}

	int y=++cnt;

	len[y]=len[f]+1,fa[y]=fa[x],fa[x]=fa[p]=y;

	for(re int i=0;i<7;i++) son[y][i]=son[x][i];

	while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];

}

inline int chk(char x) {

	if(x=='f') return 0;if(x=='z') return 1;

	if(x=='o') return 2;if(x=='u') return 3;

	if(x=='t') return 4;if(x=='s') return 5;

	return 6;

}

inline void add(int x) {

	if(!h[pos[x]]) return;

	ans+=tmp[h[pos[x]]];++tmp[h[pos[x]]];

}

inline void del(int x) {

	if(!h[pos[x]]) return;

	--tmp[h[pos[x]]];ans-=tmp[h[pos[x]]];

}

inline int cmp(Ask A,Ask B) {return id[A.l]==id[B.l]?A.r<B.r:id[A.l]<id[B.l];}

int main() {

	n=read(),m=read(),k=read();scanf("%s",S+1);

	for(re int i=1;i<=n;i++) S[i]=chk(S[i]);

	for(re int i=n;i;--i) ins(S[i],i);

	for(re int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].rk=i;

	int sz=n/(std::sqrt(m)+1);int L=1,tot=1;

	while(L<=n) {for(re int i=L;i<=min(L+sz-1,n);i++) id[i]=tot;L+=sz,++tot;}

	std::sort(q+1,q+m+1,cmp);

	for(re int i=2;i<=cnt;i++) if(len[i]>=k&&len[fa[i]]<k) g[i]=1;

	for(re int i=1;i<=cnt;i++) tax[len[i]]++;

	for(re int i=1;i<=n;i++) tax[i]+=tax[i-1];

	for(re int i=cnt;i;--i) A[tax[len[i]]--]=i;

	for(re int i=1;i<=cnt;i++) {

		int x=A[i];

		if(g[x]) h[x]=x;else h[x]=h[fa[x]];

	}

	int l=0,r=0;

	for(re int i=1;i<=m;i++) {

		while(r<q[i].r) add(++r);

		while(l<q[i].l) del(l++);

		while(l>q[i].l) add(--l);

		while(r>q[i].r) del(r--);

		Ans[q[i].rk]=ans;

	}

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

	return 0;

}

巴特西

【LGP5112】FZOUTSY

最新文章

热门文章