题目链接:https://nanti.jisuanke.com/t/17122

比赛的时候去用树链剖分乱搞那个xor了Orzzzzz……

要是当时做出来这个题就好了QAQ

就……裸的字符哈希

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD=1e15+9;
LL pow26[2000005]={1};
string a,b,c,d;
struct pcs
{
	string s;
	int len;
	vector<LL> h1,h2,h3,h4;
};
vector<pcs> v;
inline void Add(string &s)
{
	vector<int> h1,h2,h3,h4;
	int len=s.length()/2;
	h1.push_back(s[0]-'a');
	h3.push_back(s[len]-'a');
	for(int i=1;i<len;i++) h1.push_back(h1[i-1]+(s[i]-'a')*pow26[i]);
	for(int i=1;i<len;i++) h3.push_back(h3[i-1]+(s[len+i]-'a')*pow26[i]);
	h2.push_back(s[len-1]-'a');
	h4.push_back(s[2*len-1]-'a');
	for(int i=1;i<len;i++) h2.push_back(h2[i-1]+(s[len-1-i]-'a')*pow26[i]);
	for(int i=1;i<len;i++) h4.push_back(h4[i-1]+(s[2*len-1-i]-'a')*pow26[i]);
//	cout<<"Debug "<<1<<endl;
//	cout<<"h1"<<" ";for(int i=0;i<len;i++) cout<<h1[i]<<" ";cout<<endl;
//	cout<<"h2"<<" ";for(int i=0;i<len;i++) cout<<h2[i]<<" ";cout<<endl;
//	cout<<"h3"<<" ";for(int i=0;i<len;i++) cout<<h3[i]<<" ";cout<<endl;
//	cout<<"h4"<<" ";for(int i=0;i<len;i++) cout<<h4[i]<<" ";cout<<endl;
	v.push_back((pcs){s,len,h1,h2,h3,h4});
}
inline int query()
{
	int ans=0;
	int lena=a.length();
	int lenb=b.length();
	int lenc=c.length();
	int lend=d.length();
	LL ha=0,hb=0,hc=0,hd=0;
	for(int i=0;i<lena;i++) ha=(ha+(a[i]-'a')*pow26[i])%MOD;
	for(int i=0;i<lenb;i++) hb=(hb+(b[lenb-i-1]-'a')*pow26[i])%MOD;
	for(int i=0;i<lenc;i++) hc=(hc+(c[i]-'a')*pow26[i];
	for(int i=0;i<lend;i++) hd+=(d[lend-i-1]-'a')*pow26[i];
//	cout<<"Debug "<<ha<<" "<<hb<<" "<<hc<<" "<<hd<<endl;
	for(int i=0;i<v.size();i++)
	{
		if (v[i].len<lena+lenb) continue;
		if (v[i].len<lenc+lend) continue;
		if (v[i].h1[lena-1]==ha && v[i].h2[lenb-1]==hb && v[i].h3[lenc-1]==hc && v[i].h4[lend-1]==hd)
			ans++;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	LL tmp=1;
	for(int i=1;i<=2000000;i++) pow26[i]=(pow26[i-1]*26)%MOD;
	int T;
	cin>>T;
	while(T--)
	{
		v.clear();
		int Q;
		cin>>Q;
		while(Q--)
		{
			int op;
			string s;
			cin>>op>>s;
			if (op==1) Add(s);
			else
			{
				a=s;
				cin>>b>>c>>d;
				cout<<query()<<endl;
			}
		}
	}
	return 0;
}