# Description

$$n, q, \sum a_i \leqslant 100000$$

# Solution

upd:

1. 设$$|s_x|\leqslant \sqrt n$$或$$|s_y|\leqslant \sqrt n$$，由于时间复杂度与较短的串有关，所以复杂度显然正确。

2. 否则$$|s_x|\geqslant\sqrt n$$的串最多有$$\sqrt n$$个,$$|s_x|\geqslant \sqrt n$$且$$|s_y|\geqslant \sqrt n$$最多只有$$n$$种询问，加
上记忆化后显然正确。

c++11
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<unordered_set>

#define pb push_back
#define mp make_pair

using namespace std;

template<typename T>inline void upmin(T &x,T y) { y<x?x=y:0; }
template<typename T>inline void upmax(T &x,T y) { x<y?x=y:0; }

typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1e18;

const int N=2e5+100;

int gi() {
int w=0;bool q=1;char c=getchar();
while ((c<'0'||c>'9') && c!='-') c=getchar();
if (c=='-') q=0,c=getchar();
while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
return q? w:-w;
}

char str[N];

int son[N][26],fail[N],len[N],tot,last;
bool vis[N];

inline int getfail(int k,int n) {
while (str[n-len[k]-1]!=str[n]) k=fail[k];
return k;
}
inline int add(int k,int n) {
k=getfail(k,n);
if (!son[k][str[n]-'a']) {
len[++tot]=len[k]+2;
fail[tot]=son[getfail(fail[k],n)][str[n]-'a'];
son[k][str[n]-'a']=tot;
}
k=son[k][str[n]-'a'];
return k;
}
unordered_set<ULL>H[N];
const ULL seed=19260817;
ULL key[26];
map<PR,int>ans;
ULL pre[N],num[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("D.in","r",stdin);
freopen("D.out","w",stdout);
#endif
int n=gi(),m,i,j,l,a,b;
for (i=0;i<26;i++) key[i]=rand();
for (i=num[0]=1;i<=1e5;i++) num[i]=num[i-1]<em>seed;
for (i=1;i<=n;i++) {
len[1]=-1;fail[0]=1;
last=tot=1;
scanf("%s",str+1);str[0]='#';
l=strlen(str+1);
vis[0]=vis[1]=true;
for (j=1;j<=l;j++) {
pre[j]=pre[j-1]</em>seed+key[str[j]-'a'];
if (!vis[last])
H[i].insert(pre[j]-pre[j-len[last]]<em>num[len[last]]);
}
memset(vis,0,(tot+1));
memset(len,0,(tot+1)</em>4);
memset(fail,0,(tot+1)<em>4);
memset(son,0,sizeof(son[0])</em>(tot+1));
}
m=gi();
last=0;
while (m--) {
a=gi()^last,b=gi()^last;
if (H[a].size()<H[b].size())
swap(a,b);
if (ans.find(mp(a,b))==ans.end()) {
int res=0;
for (ULL t:H[b])
res+=H[a].find(t)!=H[a].end();
ans[mp(a,b)]=res;
}
printf("%d\n",last=ans[mp(a,b)]);
}
return 0;
}


## FAQ:

Q:你怎么来sycstudio.com写文章了？
A:因为csdn广告太多，cnblogs不想配置，自己的博客还没搭好，所以就来蹭博客了。
Q:你的代码常数有多大？
A:AC中我跑得最慢。
Q:数学公式为什么出锅了？
A:我不会用这个编辑器的公式，我也很无奈好心的萝卜帮我改改吧。
My question：为什么我不能添加分类？？数学公式到底要用什么？萝卜不能改改这个东西吗？