wa70求条

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define sz(a) (int)a.size()
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define ford(a,b,c) for(int a=b;a>=c;a--)
using namespace std;

const int N=5000005,Bas=13331,M=500005;
//const int inf=1e17;

int lb(int x){
	return x&-x;
}



//哈希 start ------------------------------------------------

struct _{
	string a1,a2;
	ull hah;
	int n;
	int p1,p2;
	
	void add(string s1,string s2){
		a1=s1;
		a2=s2;
	}
	
	ull doo(string s){
		ull res=0;
		int m=sz(s);
		foru(i,0,m-1){
			res=res*Bas+(s[i]-'a'+1);
		}
		return res;
	}
	
	string sub(string s,int l,int r){
		int n=sz(s);
		if(l>r||r>=n||l<0)
			return "";
		string res="";
		foru(i,l,r){
			res+=s[i];
		}
		return res;
	}
	
	void calc(){
		n=sz(a1);
		p1=0,p2=n-1;
		while(p1<=n-1){
			if(a1[p1]==a2[p1])
				p1++;
			else
				break;
		}//第一个不相等
		while(p2>=0){
			if(a1[p2]==a2[p2])
				p2--;
			else
				break;
		}//中间不同  将不同的部分 哈希呗   能替换只有不同的位置一样
		
		ull res=(doo(sub(a1,p1,p2))*Bas+'#')*Bas+doo(sub(a2,p1,p2));
		hah=res;
	}
	
	
}hh1[M],hh2[M];

// 哈希 end -----------------------------------

struct __{
	int w[N];
	void add(int x,int v){
		for(;x<N;x+=lb(x))
			w[x]+=v;
	}
	int qry(int x){
		int res=0;
		for(;x;x-=lb(x))
			res+=w[x];
		return res;
	}
}Bit;


//字典树 start ---------------------------------------------------------

int you[N][27];
int cnty;

int insy(string s){
	int p=0;
	int n=sz(s);
	foru(i,0,n-1){
		int t=s[i]-'a'+1;
		if(you[p][t]==0)
			you[p][t]=++cnty;
		p=you[p][t];
	}
	return p;//左边的树插入
}

int zuo[N][27];
int cntz;
int insz(string s){
	int p=0;
	int n=sz(s);
	foru(i,0,n-1){
		int t=s[i]-'a'+1;
		if(zuo[p][t]==0)
			zuo[p][t]=++cntz;
		p=zuo[p][t];
	}
	return p;//左边的树插入
}



//字典树 end-------------------------------------------------------------------





int dfl[N],dfr[N],siz[N],tim,posr[M],ans[M];
vector<vector<int> > dat(N),ques(N);
pii range[M];

void clr(){
	tim=0;
	foru(i,0,cnty){
		foru(j,1,26){
			you[i][j]=0;
		}
		siz[i]=0;
		dfl[i]=dfr[i]=0;
	}
	foru(i,0,cntz){
		foru(j,1,26){
			zuo[i][j]=0;
		}
		dat[i].clear();
		ques[i].clear();

	}
	cnty=cntz=0;
}


void dfsr(int u){
	dfl[u]=++tim;
	siz[u]=1;
	foru(i,1,26){
		if(you[u][i]){
			dfsr(you[u][i]);
			siz[u]+=siz[you[u][i]];
		}
	}
	dfr[u]=dfl[u]+siz[u]-1;
	
}


void dfsl(int u){
	for(auto id:dat[u]){
		int L=range[id].fi,R=range[id].se;
		Bit.add(L,1);
		Bit.add(R+1,-1);//处理询问  考虑以当前这个结尾的  被包含的点的个数
	}
	for(auto id:ques[u]){
		int pos=posr[id];
		ans[id]+=Bit.qry(pos);
	}
	foru(i,1,26){
		if(zuo[u][i]==0)
			continue;
		dfsl(zuo[u][i]);
	}
	for(auto id:dat[u]){
		int L=range[id].fi,R=range[id].se;
		Bit.add(L,-1);
		Bit.add(R+1,1);
	}
	
}


ull buc[N*2];
int cnt;
int n,q;
string s1[M],s2[M],t1[M],t2[M];
bool bd[M*2];
vector<vector<int> > g1(N*2),g2(N*2);

int gt(ll x){
	return lower_bound(buc+1,buc+1+cnt,x)-buc;
}


signed main(){
//------------------------------------------------------------------------------
//	freopen("replace4.in","r",stdin);
//	freopen("a.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//------------------------------------------------------------------------------
//	hh1[1].add("xabcx","xadex");
//	hh1[1].calc();
//	dbge(hh1[1].hah);
//	dbge(hh1[1].p2);


	cin>>n>>q;
	foru(i,1,n){
		cin>>s1[i]>>s2[i];
		hh1[i].add(s1[i],s2[i]);
		hh1[i].calc();
		if(hh1[i].p1>hh1[i].p2)
            bd[i]=1;
		int nw=hh1[i].hah;
		buc[++cnt]=nw;
	}
//	q=1;
	foru(i,1,q){
		cin>>t1[i]>>t2[i];
		hh2[i].add(t1[i],t2[i]);
		hh2[i].calc();
		if(hh2[i].p1>hh2[i].p2)
			bd[i+n]=1;
		int nw=hh2[i].hah;
		buc[++cnt]=nw;
	}
//	foru(i,1,cnt){
//		cout<<buc[i]<<'\n';
//	}
//	dbg;
	sort(buc+1,buc+1+cnt);
	cnt=unique(buc+1,buc+1+cnt)-buc-1;
	foru(i,1,n){
		if(bd[i])
			continue;
		ull nw=hh1[i].hah;
		nw=gt(nw);
		g1[nw].pb(i);
	}
	foru(i,1,q){
		if(bd[i+n])
			continue;
		ull nw=hh2[i].hah;
		nw=gt(nw);
		g2[nw].pb(i);
	}
	
	
	
	foru(i,1,cnt){//把t插入  将右边插入  那么遍历左边的时候就要查询到根有多少个点
		//使得这些点的右边的dfs包含当前的右边的dfn   那么先插右边   在左边的地方丢vector  查询右边即可
		//有多少点可以Bit维护
		//插到右边需要维护每个的位置的dfn
		
		for(auto id:g2[i]){
			if(bd[id+n])
				continue;
			string s=hh2[id].a1;
			string t=hh2[id].sub(s,hh2[id].p2+1,hh2[id].n-1);
			posr[id]=insy(t);//询问  要找右边的点
			t=hh2[id].sub(s,0,hh2[id].p1-1);
			reverse(t.begin(),t.end());
			int pos=insz(t);//找左边的点在哪里
			ques[pos].pb(id);
		}
		
		for(auto id:g1[i]){
			if(bd[id])
				continue;
			string s=hh1[id].a1;
			string t=hh1[id].sub(s,hh1[id].p2+1,hh1[id].n-1);//小的串
			range[id].fi=insy(t);//右边的范围
			t=hh1[id].sub(s,0,hh1[id].p1-1);
			reverse(t.begin(),t.end());
			int pos=insz(t);//如果是0咋办呢
			dat[pos].pb(id);
		}
		dfsr(0);
		for(auto id:g1[i]){
			if(bd[id])
				continue;
			int pos=range[id].fi;
			range[id]={dfl[pos],dfr[pos]};//草插入的是反串啊
		}
		for(auto id:g2[i]){
			if(bd[id+n])
				continue;
			posr[id]=dfl[posr[id]];
		}
		dfsl(0);
		clr();
		
		
		
		
	}
	foru(i,1,q){
		cout<<ans[i]<<'\n';
	}
	



	return 0;


}
/*
bit不用清空啊


*/