Link
ICPC2022Hangzhou F Da Mi Lao Shi Ai Kan De
Question
给出 \(Q\) 个 \(a-z\) 的排序表示比较规则，求 \(n\) 个串在每个比较规则下的逆序对个数
Solution
我们发现，对于两个串的比较来说，决定大小的只是两个字母的比较，比如说
aac
aab
判断这是否是逆序对，起决定性作用的就是比较规则中 \(c\) 在 \(b\) 前面还是 \(b\) 在 \(c\) 前面。然而，前面的 aa 其实对任意的一组比较规则都可以忽略不看，就取决于 \(c\)，\(b\) 的顺序
如果我们可以先不看比较规则，提前构造出起决定性作用的那些字符二元组， 定义 \(f(x,y)\) 表示 \(n\) 个串中，起决定性作用的两个字母是 \(x\) 和 \(y\)，\(x\) 的串在 \(y\)的串前面，出现的数量。例如前面的数据中 \(x\) 就是 \(c\)，\(y\) 就是 \(b\)
如果构造出了 \(f(x,y)\) ，如果一组排列中，\(y\) 在 \(x\) 前面，那么 \(f(x,y)\) 就构成了逆序，要加上 \(f(x,y)\)
关键在于如何构造 \(f(x,y)\)
\(x,y\) 只与不同的那个字符有关，所以考虑字典树，刚开始是一颗空的字典树，往字典树里面加字符串，当遍历到的字典树的节点为 \(pos\) 时，需要加入的下一个字符是 \(s_j\) ，那么对于 \(pos\) 的每一个儿子所对应的序列都在 \(s\) 前面，所以 \(f(son_k,s_j)+=num[sum_k]\) ，\(num[x]\) 表示字典树上 \(x\) 点所包含的串数
如图，蓝色部分就是在当前串之前已经处理好的串，我需要加入 \(c\) ，那么就要增加 \(f(a,c)\) 和 \(f(b,c)\) 的值
有一个小细节，就是在处理一个串是另外一个串的前缀的时候，是无法处理的，比如 aaab 和 aa 也是逆序对，这就需要在处理 aa 的最后一个字符的时候，加上这个字符的所有字数的 \(num\)
Code
#include<bits/stdc++.h>
using namespace std;
int N,Q;
typedef long long LL;
const int maxn=5e5+5,maxL=1e6+5;
inline int read(){
int ret=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
int t[maxL][26],Len=0;
LL num[maxL],now_ans=0,ans2;
string s[maxn];
LL ans[26][26];
void in(string s){
int siz=s.length(),pos=0;
for(int i=0;i<siz;i++){
int now_x=s[i]-'a';
for(int j=0;j<26;j++){
if(now_x==j) continue;
ans[j][now_x]+=num[t[pos][j]];
}
if(t[pos][now_x]==0) {
++Len;
t[pos][now_x]=Len;
pos=Len;
}
else {
pos=t[pos][now_x];
if(i==siz-1){
for(int j=0;j<26;j++)
ans2+=num[t[pos][j]];
}
}
num[pos]++;
}
}
int main(){
N=read(),Q=read();
for(int i=1;i<=N;i++){
cin>>s[i];
in(s[i]);
}
for(int i=1;i<=Q;i++){
now_ans=0;
string q;cin>>q;
int siz=q.length();
vector<int> id(26);
for(int j=0;j<siz;j++){
id[q[j]-'a']=j;
}
for(int j1=0;j1<26;j1++)
for(int j2=0;j2<26;j2++){
if(id[j1]>id[j2]){
now_ans+=ans[j1][j2];
}
}
printf("%lld\n",now_ans+ans2);
}
return 0;
}