题意：2种操作：①往集合里添加一个串
②给你四个小串a b c d，问你集合里有几个串S满足S=a+S1+b+c+S2+d的形式。S1 S2可以为空，并且a+S1+b=c+S2+d。
就搞四颗Trie出来，分别存的是
所有S的前半部分 + 所有a串；
所有S的前半部分倒置 + 所有b串倒置；
所有S的后半部分 + 所有c串；
所有S的后半部分倒置 + 所有d串倒置。
这样把问题转化成了询问有几个S串同时在四个串所限制的子树里，用dfs序处理。
另外，由于ab不能交叠，cd不能交叠，所以串的长度要大于等于max(a+b,c+d)*2。
由于我们离线处理，所以对于每次询问，如果其编号为i，所找的串的编号必须小于i。
这样把问题转化成了六维空间内的矩形内点的个数问题，可以用kd-tree解决。
另，开4个Trie是开不下的，只能开一个，重复利用空间……
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
#define N 2000005
#define Q 30005
#define KD 6
int dn,n,root,qp[2][KD];
struct Node
{
int ch[2],w,minn[KD],maxx[KD],p[KD],sumv;
void Init()
{
sumv=w;
ch[0]=ch[1]=0;
for(int i=0;i<KD;++i)
minn[i]=maxx[i]=p[i];
}
}T[N];
bool operator < (const Node &a,const Node &b){return a.p[dn] < b.p[dn];}
void pushup(const int &rt)
{
T[rt].sumv=T[rt].w;
for(int i=0;i<2;++i)
if(T[rt].ch[i])
{
T[rt].sumv+=T[T[rt].ch[i]].sumv;
for(int j=0;j<KD;++j)
{
T[rt].minn[j]=min(T[rt].minn[j],T[T[rt].ch[i]].minn[j]);
T[rt].maxx[j]=max(T[rt].maxx[j],T[T[rt].ch[i]].maxx[j]);
}
}
}
int buildtree(int l=1,int r=n,int d=0)
{
dn=d;
int m=(l+r>>1);
nth_element(T+l,T+m,T+r+1);
T[m].Init();
if(l!=m) T[m].ch[0]=buildtree(l,m-1,(d+1)%KD);
if(m!=r) T[m].ch[1]=buildtree(m+1,r,(d+1)%KD);
pushup(m);
return m;
}
bool Inside(const int &o)
{
for(int i=0;i<KD;++i)
if(qp[0][i] > T[o].p[i] || T[o].p[i] > qp[1][i])
return 0;
return 1;
}
bool AllInside(const int &o)
{
for(int i=0;i<KD;++i)
if(qp[0][i] > T[o].minn[i] || T[o].maxx[i] > qp[1][i])
return 0;
return 1;
}
bool Cross(const int &o)
{
for(int i=0;i<KD;++i)
if(qp[0][i] > T[o].maxx[i] || T[o].minn[i] > qp[1][i])
return 0;
return 1;
}
int ans;
void Query(int rt=root)
{
if(Inside(rt)) ans+=T[rt].w;
for(int i=0;i<2;++i)
if(T[rt].ch[i] && Cross(T[rt].ch[i]))
{
if(AllInside(T[rt].ch[i]))
ans+=T[T[rt].ch[i]].sumv;
else if(T[T[rt].ch[i]].sumv)
Query(T[rt].ch[i]);
}
}
int q;
string s[Q],t;
int ch[N][26];
int sz,Ls[4][N],Rs[4][N];
int num[4][Q];
void Insert(int op,int id,string s)
{
int U=0,len=s.length();
for(int i=0;i<len;++i)
{
int V=s[i]-'a';
if(!ch[U][V]) ch[U][V]=++sz;
U=ch[U][V];
}
num[op][id]=U;
}
string as[Q],bs[Q],cs[Q],ds[Q];
int tot;
void dfs(int op,int U){
Ls[op][U]=++tot;
for(int i=0;i<26;++i){
if(ch[U][i]){
dfs(op,ch[U][i]);
}
}
Rs[op][U]=tot;
}
int main()
{
// freopen("i.in","r",stdin);
// freopen("i.out","w",stdout);
int opt,zu;
scanf("%d",&zu);
for(;zu;--zu){
n=0;
memset(ch,0,sizeof(ch));
sz=0;
scanf("%d",&q);
for(int i=1;i<=q;++i){
scanf("%d",&opt);
if(opt==1){
cin>>s[i];
++n;
}
else{
cin>>as[i]>>bs[i]>>cs[i]>>ds[i];
}
}
for(int j=1;j<=q;++j)
if(s[j]!=""){
int slen=s[j].length();
t=s[j].substr(0,slen>>1);
Insert(0,j,t);
}
else{
int alen=as[j].length();
Insert(0,j,as[j]);
}
tot=0;
dfs(0,0);
memset(ch,0,sizeof(ch));
sz=0;
for(int j=1;j<=q;++j)
if(s[j]!=""){
int slen=s[j].length();
t=s[j].substr(0,slen>>1);
reverse(t.begin(),t.end());
Insert(1,j,t);
}
else{
int blen=bs[j].length();
reverse(bs[j].begin(),bs[j].end());
Insert(1,j,bs[j]);
}
tot=0;
dfs(1,0);
memset(ch,0,sizeof(ch));
sz=0;
for(int j=1;j<=q;++j)
if(s[j]!=""){
int slen=s[j].length();
t=s[j].substr(slen>>1,slen>>1);
Insert(2,j,t);
}
else{
int clen=cs[j].length();
Insert(2,j,cs[j]);
}
tot=0;
dfs(2,0);
memset(ch,0,sizeof(ch));
sz=0;
for(int j=1;j<=q;++j)
if(s[j]!=""){
int slen=s[j].length();
t=s[j].substr(slen>>1,slen>>1);
reverse(t.begin(),t.end());
Insert(3,j,t);
}
else{
int dlen=ds[j].length();
reverse(ds[j].begin(),ds[j].end());
Insert(3,j,ds[j]);
}
tot=0;
dfs(3,0);
int cnt=0;
for(int i=1;i<=q;++i)if(s[i]!=""){
++cnt;
T[cnt].p[0]=Ls[0][num[0][i]];
T[cnt].p[1]=Ls[1][num[1][i]];
T[cnt].p[2]=Ls[2][num[2][i]];
T[cnt].p[3]=Ls[3][num[3][i]];
T[cnt].p[4]=i;
T[cnt].p[5]=s[i].length();
T[cnt].w=1;
}
root=(1+n>>1);
buildtree();
for(int i=1;i<=q;++i){
if(as[i]!=""){
ans=0;
qp[0][0]=Ls[0][num[0][i]]; qp[1][0]=Rs[0][num[0][i]];
qp[0][1]=Ls[1][num[1][i]]; qp[1][1]=Rs[1][num[1][i]];
qp[0][2]=Ls[2][num[2][i]]; qp[1][2]=Rs[2][num[2][i]];
qp[0][3]=Ls[3][num[3][i]]; qp[1][3]=Rs[3][num[3][i]];
qp[0][4]=1; qp[1][4]=i;
qp[0][5]=max(as[i].length()+bs[i].length(),cs[i].length()+ds[i].length())*2;
qp[1][5]=2147483647;
Query();
printf("%d
",ans);
}
}
for(int i=1;i<=q;++i){
s[i].clear();
as[i].clear();
bs[i].clear();
cs[i].clear();
ds[i].clear();
}
}
return 0;
}