题目大意：给出一个串(S)，(q)次询问每次询问字符串(T)不在(S[l,r])出现的本质不同的子串数目。
0.68
有条件(l=1,r=|S|)。考虑(SAM_T)上的parent树的结构特点，不难可以得出：若设(lim_i)为(T[1,i])在(S)中出现的最长后缀长度（在(SAM_S)上直接跑整个(T)就能预处理），(tar_x)为集合(right_x)中任一元素，答案可以表示为
[
sum_{xin SAM_T} |[0,lim_{tar_x}]cap[mxl_{prt_x}+1,mxl_x]|
]
（其实画图想了好久。。）
1.00
将上一个做法中的预处理部分做出如下修改：若目标状态的right集合存在位于([l+len-1,r])中的元素则转移（len是已上一个后缀的lim值），否则挨个考虑时len-=1，当len=prt的mxl时转向prt节点。（对于len满足|对于len-1满足？）
这样使用可持久化线段树+线段树合并求出right集合来做。
感谢 QAQ
恼惭做了60h。
代码 ：模板线段树合并求right集合
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
const int N=1e6+10; //faq
namespace SGT {
int ch[N*30][2],cnt;
bool exi[N*30];
void insert(int&x,int l,int r,int p) {
exi[x=++cnt]=1;
if(l==r) return;
int mid=(l+r)>>1;
if(p<=mid) insert(ch[x][0],l,mid,p);
else insert(ch[x][1],mid+1,r,p);
}
int merge(int x,int y,int l,int r) {
if(!x||!y) return x|y;
int nd=++cnt,mid=(l+r)>>1;
ch[nd][0]=merge(ch[x][0],ch[y][0],l,mid);
ch[nd][1]=merge(ch[x][1],ch[y][1],mid+1,r);
exi[nd]=exi[ch[nd][0]]|exi[ch[nd][1]];
return nd;
}
bool query(int x,int l,int r,int L,int R) {
//printf("[%d,%d,%d,%d,%d]n",x,l,r,L,R);
if(!x||R<L) return 0;
if(L<=l&&r<=R) return exi[x];
int mid=(l+r)>>1;
if(L<=mid&&query(ch[x][0],l,mid,L,R)) return 1;
if(mid<R&&query(ch[x][1],mid+1,r,L,R)) return 1;
return 0;
}
}
int n,m,root[N*2];
std::vector<int> e[N*2];
struct SAM {
struct Node {
int ch[26],prt,mxl,tar;
} t[N*2];
int cnt,lst;
inline void clear() {
for(int i=1; i<=cnt; ++i) memset(&t[i],0,sizeof t[i]);
cnt=lst=1;
}
inline int extend(int c,int pos) {
int p=lst,x=lst=++cnt;
t[x].tar=pos;
t[x].mxl=t[p].mxl+1;
while(p&&!t[p].ch[c]) t[p].ch[c]=x,p=t[p].prt;
if(!p) t[x].prt=1;
else {
int q=t[p].ch[c];
if(t[q].mxl==t[p].mxl+1) t[x].prt=q;
else {
int k=++cnt;
t[k]=t[q];
t[k].mxl=t[p].mxl+1;
t[q].prt=t[x].prt=k;
while(p&&t[p].ch[c]==q) t[p].ch[c]=k,p=t[p].prt;
}
}
return x;
}
inline void dfs(int x) {
for(int y:e[x]) {
dfs(y);
root[x]=SGT::merge(root[x],root[y],1,N);
}
}
inline void build(char *s,int N,bool sgt) {
clear();
for(int i=1; i<=N; ++i) {
int x=extend(s[i]-'a',i);
if(sgt) SGT::insert(root[x],1,N,i);
}
if(sgt) {
for(int i=2; i<=cnt; ++i) e[t[i].prt].push_back(i);
dfs(1);
}
}
void key() {
printf("total nodes: %dn",cnt);
for(int i=1; i<=cnt; ++i) {
printf(" %d %d %dn",t[i].mxl,t[i].tar,t[i].prt);
}
}
} S,T;
char s[N];
int L,R,Q,lim[N];
inline long long calc() {
scanf("%s%d%d",s+1,&L,&R);
T.build(s,m=strlen(s+1),0);
//T.key();
int now=1,len=0;
for(int i=1; i<=m; ++i) {
int c=s[i]-'a';
while(1) {
//printf("<%d %d> ",now,len);
if(SGT::query(root[S.t[now].ch[c]],1,n,L+len,R)) {
//printf(" ent ");
len++;
now=S.t[now].ch[c];
break;
} else {
if(now==1) break;
--len;
if(len==S.t[S.t[now].prt].mxl) now=S.t[now].prt;
}
}
lim[i]=len;
}
long long ans=0;
for(int i=1; i<=T.cnt; ++i) {
ans+=T.t[i].mxl-T.t[T.t[i].prt].mxl;
ans-=std::max(0,std::min(T.t[i].mxl,lim[T.t[i].tar])-T.t[T.t[i].prt].mxl);
}
return ans;
}
int main() {
freopen("name.in","r",stdin);
freopen("name.out","w",stdout);
scanf("%s%d",s+1,&Q);
S.build(s,n=strlen(s+1),1);
//S.key();
while(Q--) printf("%lldn",calc());
return 0;
}内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
