翻译

原题链接

  简述一下就是每次询问重新定义一个字母排序表，问在这个顺序下n个字符串的序列的逆序数是多少。

字典树计算逆序数

  先考虑初始状况下，即$a<b<...<z$的情况下，逆序数如何计算。而对于这种多字符串问题，优先考虑的肯定是字典树，我们可以对所有字符串构建一棵字典树，在字典树的每个节点上记录所有经过它的字符串的下标，然后计算两种情况的逆序数：

  （1）$S_i$是$S_j$的前缀，则它们在字典树上的情况一定会在某一个节点$nod{e}_t$处满足$i\in nod{e}_t,j\in nod{e}_t$，而$i$将不会出现在$nod{e}_t$的任何子节点上，假如$i>j$，那就产生了一组逆序对。我们记这种情况的总逆序数为$AN{S}_1$

  （2）$S_i$与$S_j$存在一位不一样的字符，则一定存在一个节点$nod{e}_t$，在这里两个字符串走了不同的路，称这两个字符串在这个节点上出现了分歧（后面要用）。于是我们可以遍历每个节点下的两条分支，在这两个分支中跑一遍求逆序数，采用双指针的方式，类似归并排序时求逆序数，复杂度大约为$O(13\ast 26\ast n)$，记这种情况的总逆序对数为$AN{S}_2$

  于是，答案就是$AN{S}_1+AN{S}_2$。

打乱字母表下如何计算逆序数

  那么好，现在考虑字母表排序打乱的情况，上述过程会有什么变化。容易发现，第一种情况不会受到任何影响，仍然是$AN{S}_1$。

  对于第二种情况，假如新的顺序变成了$a>b$，发现原本因为分歧原因为$a$与$b$的字符串大小关系发生变化，在初始的排序下，我们不再需要它们的逆序对，而是要顺序对。而这种变化会在$a$与$b$大小关系变化时同时发生，可以将所有因此需要调整的地方统一处理。

  思路可能有点抽象，直接上方法。不再直接求$AN{S}_2$，而是两个列表$w_1[26][26]$和$w_2[26][26]$，其中$w1[c_1][c_2]$表示两个字符串因为$c_1$和$c_2$产生了分歧而产生的顺序对数，$w_2$则是逆序对数，则初始的$ANS2$其实可以直接表示为：

$AN{S}_2={\sum }_{i=0}^{25}{\sum }_{j=i+1}^{25}{w}_2[i][j]$

  而在新的顺序下，我们设一个数组$weight[26]$表示$a$到$z$的权重，则$AN{S}_2$可以表示为：

$AN{S}_2={\sum }_{i=0}^{25}{\sum }_{j=i+1}^{25}{w}_1[i][j]\ast (ifweight[i]>weight[j])$
$+{\sum }_{i=0}^{25}{\sum }_{j=i+1}^{25}{w}_2[i][j]\ast (ifweight[i]<weight[j])$

  最后别忘了加上$AN{S}_1$。

时间复杂度

  建树阶段为$O({\sum }_{i=1}^n|S_i|)$，
  求$AN{S}_1$阶段为$O({\sum }_{i=1}^n|S_i|)$，
  求$w_1$，$w_2$阶段为$O(13\ast 26\ast {\sum }_{i=1}^n|S_i|)$，
  回答询问阶段为$O(13\ast 26\ast q)$。

  注意，上述时间复杂度只是大约，大概率达不到，且中间有一些微微的剪枝优化 。

  此外，千万不要新建一个vector并用另一个vector给它赋值，只为了弄个新的变量名方便写代码，因为vector赋值是默认$O(size)$一个一个拷贝过去的，而不是指针！！！（因为这个TLE了半天）

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{int nxt[26];int value=-1;int h;vector<int> v;
} G[1000006];
int H[500005];
int new_weight[26];
int szG=1;
int w;     // 子串形成的逆序对数
int w1[26][26], w2[26][26];   // i与j的比较中产生的逆序对数, 反转后产生的逆序对数
int n, q;
inline void ct(int x, int y) {    // 求w1顺序对, w2逆序对if(G[x].value > G[y].value) swap(x, y);    // 保证分别为a子树，b子树int value1 = G[x].value, value2 = G[y].value;int t1 = 0, t2 = 0;while(t1 < G[x].v.size() && t2 < G[y].v.size()) {if(G[x].v[t1] < G[y].v[t2]) {w2[value1][value2] += G[y].v.size() - t2;t1 ++;} else {w1[value1][value2] += G[x].v.size() - t1;t2 ++;}}
}
inline void ct2(int x) {    // 求ANS1，即前缀关系的逆序数vector<int> v1, v2;     // 消失的，剩余的for(int i=0;i<G[x].v.size();i++) {int now = G[x].v[i];if(H[now] == G[x].h) {v1.push_back(now);} else {v2.push_back(now);}}int t1 = 0, t2 = 0;while(t1 < v1.size() && t2 < v2.size()) {if(v1[t1] < v2[t2]) {t1 ++;} else {w += v1.size() - t1;t2 ++;}}
}
inline void dfs(int id) { if(id != 0 && G[id].v.size() <= 1) return;for(int i=0;i<26;i++) {if(G[id].nxt[i] == 0) continue;for(int j=i+1;j<26;j++) {if(G[id].nxt[j] == 0) continue;ct(G[id].nxt[i], G[id].nxt[j]);}}ct2(id);for(int i=0;i<26;i++) {if(G[id].nxt[i] == 0) continue;dfs(G[id].nxt[i]);}
}
signed main() {cin>>n>>q;for(int i=1;i<=n;i++) {string s; cin>>s;H[i] = s.length();int id = 0;   // 根for(int j=0;j<s.size();j++) {if(G[id].nxt[s[j]-'a'] == 0) {   // 下一个节点不存在G[szG].value = s[j] - 'a';G[szG].h = G[id].h + 1;G[id].nxt[s[j]-'a'] = szG;szG++;}id = G[id].nxt[s[j]-'a'];G[id].v.push_back(i);}}dfs(0);while(q--) {           string s; cin>>s;for(int i=0;i<26;i++) {new_weight[s[i]-'a'] = i;}int sum = 0;for(int i=0;i<26;i++) {for(int j=i+1;j<26;j++) {if(new_weight[i] < new_weight[j])sum += w1[i][j];elsesum += w2[i][j];}}printf("%lld\n", w + sum);}return 0;
}