https://codeforces.com/gym/104090/problem/K

题意：给你n个字符串，在给你m个字符大小顺序规则。求逆序对数量。

1. 常规求这n个字符串的逆序对数量O(n^2)的时间复杂度，必爆，肯定要想办法优化，就往预处理上想。

2. 在不同规则下，比较这n个字符串谁大，两个字符串比较谁大，无论什么字符串大，都是比较顺序遍历到双方不同字符时，在按规则比。就可以转化为比较两个不同字符的出现的前后顺序。且在比较时要保持前面字符相同。

// Problem: K. Master of Both
// Contest: Codeforces - The 2022 ICPC Asia Hangzhou Regional Programming Contest
// URL: https://codeforces.com/gym/104090/problem/K
// Memory Limit: 1024 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;

// #define x first
// #define y second
#define NO cout << "NO" << '\n';
#define YES cout << "YES" << '\n';
#define int long long

const int N = 2e6 + 10;
int son[N][30], cnt[N][30], idx, sum[100][100];
char s[N];
int pos[N];

void insert()
{
	int p = 0; // p代表前i个字符相同的情况。
	for (int i = 0; s[i]; i ++)
	{
		int u = s[i] - 'a' + 1;
		if (!son[p][u]) son[p][u] = ++ idx;
		for (int j = 0; j < 27; j ++)
		{
			sum[j + 1][u + 1] += cnt[p][j]; // 记录j字符在前，i字符在后的的数量。
		}
		cnt[p][u] ++;  // 记录每个字符的出现情况且是前i-1个字符相同的情况下。
		p = son[p][u];
	}
}

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) 
    {
    	cin >> s;
    	int len = strlen(s);
    	s[len] = 'z' + 1; // 可能会出现abc 和 abcd 的情况， 这样为了避免无字符可比， 就直接定义一个不可能出现的数，并把这个数标记成字符大小最小。
    	s[len + 1] = 0;
    	insert();
    }
    
    // for (int i = 0; i < 27; i ++)
	// {
		// for (int j = 0; j < 27; j ++)
		// {
			// cout << sum[i + 1][j + 1] << ' ';
		// }
		// cout << '\n';
	// }
    
    while (m --)
    {
    	cin >> (s + 1);
    	s[0] = 'z' + 1;
    	for (int i = 0; i < 27; i ++)
    	{
    		pos[s[i] - 'a' + 1] = i;
    	}
    	int ans = 0;
    	for (int i = 0; i < 27; i ++)
    	{
    		for (int j = 0; j < 27; j ++)
    		{
    			if (pos[i] > pos[j])
    			{
    				ans += sum[i + 1][j + 1];
    			}
    		}
    	}
    	cout << ans << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout<<fixed<<setprecision(15);
	// freopen("input.txt", "r", stdin);
	// freopen("input.txt", "w", stdout);
    //init();
    int _ = 1;
    //cin >> _;
    while (_ --) solve();
    return 0;
}