【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3483
【题目大意】
给出一些串，同时给出m对前缀后缀，询问有多少串满足给出的前缀后缀模式，
题目要求强制在线
【题解】
我们对于给出的每个字符串正着插入字典树A，倒着插入字典树B，
对于一个前缀来说，在字典树A上得到的dfs序[st,en]就是所有的匹配串，
同理，后缀在字典树B上dfs序[st,en]表示所有的后缀匹配串，
同时满足两者的需提供二维查询，因此我们以Adfsn为版本，Bdfsn为下标建立可持久化线段树，
查询版本间区间和的差值就是符合条件的答案。
【代码】
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int S=2000010,N=2010;
struct Trie{int tot,dfn,st[S],en[S],son[S][26],ansL,ansR;int Tr(char c){return c-'a';}void Init(){for(int i=0;i<=tot;i++)for(int j=0;j<26;j++)son[i][j]=0;dfn=tot=0;}int insert(char *s){int x=0;for(int l=strlen(s),i=0;i<l;i++){if(!son[x][Tr(s[i])])son[x][Tr(s[i])]=++tot;x=son[x][Tr(s[i])];}return x;}void dfs(int x){st[x]=++dfn;for(int i=0;i<26;i++)if(son[x][i])dfs(son[x][i]);en[x]=dfn;}void ask(char *s){int x=0;for(int l=strlen(s),i=0;i<l;i++){if(!son[x][Tr(s[i])]){ansL=ansR=0;return;}x=son[x][Tr(s[i])];}ansL=st[x],ansR=en[x];}
}A;
struct RevTrie{int tot,dfn,st[S],en[S],son[S][26],ansL,ansR;int Tr(char c){return c-'a';}void Init(){for(int i=0;i<=tot;i++)for(int j=0;j<26;j++)son[i][j]=0;dfn=tot=0;}int insert(char *s){int x=0;for(int l=strlen(s),i=l-1;i>=0;i--){if(!son[x][Tr(s[i])])son[x][Tr(s[i])]=++tot;x=son[x][Tr(s[i])];}return x;}void dfs(int x){st[x]=++dfn;for(int i=0;i<26;i++)if(son[x][i])dfs(son[x][i]);en[x]=dfn;}void ask(char *s){int x=0;for(int l=strlen(s),i=l-1;i>=0;i--){if(!son[x][Tr(s[i])]){ansL=ansR=0;return;}x=son[x][Tr(s[i])];}ansL=st[x],ansR=en[x];}
}B;
namespace Persistent_Segment_Tree{int l[N*40],r[N*40],v[N*40],tot,root[S];int change(int x,int a,int b,int c,int p){int y=++tot;v[y]=v[x]+p;if(a==b)return y;int mid=(a+b)>>1;if(c<=mid)l[y]=change(l[x],a,mid,c,p),r[y]=r[x];else l[y]=l[x],r[y]=change(r[x],mid+1,b,c,p);return y;}int query(int x,int a,int b,int c,int d){if(!x)return 0;if(c<=a&&b<=d)return v[x];int mid=(a+b)>>1,res=0;if(c<=mid)res+=query(l[x],a,mid,c,d);if(d>mid)res+=query(r[x],mid+1,b,c,d);return res;}
};
int n,m,posa[N],posb[N];
char s[S];
vector<int> G[S];
int main(){using namespace Persistent_Segment_Tree;scanf("%d",&n);for(int i=1;i<=n;i++){scanf(" %s",s);posa[i]=A.insert(s);posb[i]=B.insert(s);}A.dfs(0); B.dfs(0);for(int i=1;i<=n;i++)G[A.st[posa[i]]].push_back(B.st[posb[i]]);for(int i=1;i<=A.dfn;i++){root[i]=root[i-1];for(int j=0;j<G[i].size();j++)root[i]=change(root[i],1,B.dfn,G[i][j],1);}int ans=0; scanf("%d",&m);while(m--){scanf(" %s",s); int len=strlen(s);for(int i=0;i<len;i++)s[i]=(s[i]-'a'+ans)%26+'a';A.ask(s); scanf(" %s",s); len=strlen(s);for(int i=0;i<len;i++)s[i]=(s[i]-'a'+ans)%26+'a';B.ask(s);if(A.ansL&&B.ansL)ans=query(root[A.ansR],1,B.dfn,B.ansL,B.ansR)-query(root[A.ansL-1],1,B.dfn,B.ansL,B.ansR);else ans=0;printf("%d\n",ans);}return 0;
}
