K - Master of Both

题目来源：The 2022 ICPC Asia Hangzhou Regional Programming Contest K题目链接：https://codeforces.com/gym/104090/problem/K

题意

【资料图】

给定 \(n\) 个仅包含小写字母的字符串（\(1 \le |s_i| \le 10^6\)，\(1 \le \sum\limits_{i=1}^{n} s_i \le 10^6\)），以及 \(q\) 个询问（\(1 \le q \le 5 \times 10^4\)）。

对于每个询问：给出一种字母表，越靠前的字母越小，要求输出该种字母表下，这 \(n\) 个字符串有多少个逆序对，即有多少个 \((i,j)\)，满足 \(1\le i < j \le n\)，且 \(s_i>s_j\) 。

思路：Trie

首先我们思考下如何比较两个字符串的字典序大小（记为 \(s_i\)，\(s_j\)），我们从第一个不相等的字符比较，假设分别为 \(c_i\)，\(c_j\)，那么若有 \(c_i > c_j\)，则 \(s_i > s_j\) 。

也就是说，实际上所有的字符对情况只能是 \(a \le c_i \le z\)，且 \(a \le c_j \le z\) 。

我们可以预处理出 \(f_{x,y}\)，表示 \(1 \le i < j \le n\) 的有序对中满足 \(s_{i,LCP(\large s_i,s_j)} = x\)，\(s_{j,LCP(\large s_i,s_j)} = y\) 的数量。

那么对于每个询问，统计逆序对数量时，若有字母 \(x > y\)，答案就可以增加 \(f_{x,y}\) 。

对于边界情况，当 \(s_j\) 为 \(s_i\) 的真前缀时，显然有 \(s_i > s_j\)，因此也需要预处理出这类情况 \(f_{x,null}\) 。

预处理 \(f_x,y\) 时，可以利用字典树，从前到后遍历所有字符串，对于每个字符串，先计算后插入。

代码

#include using namespace std;const int N = 1000010;int n, q;int son[N][26], cnt[N], idx;long long f[26][27];char s[N];void insert(char* str){    int p = 0;    for(int i = 0; str[i]; ++ i) {        int u = str[i] - "a";        if(!son[p][u]) son[p][u] = ++ idx;        p = son[p][u];        ++ cnt[p];    }}int main(){    cin >> n >> q;    for(int i = 1; i <= n; ++ i) {        cin >> s;        int p = 0;        for(int k = 0; k < 26; ++ k) {            f[k][s[0]-"a"] += cnt[son[0][k]];        }        for(int j = 0; s[j]; ++ j) {            int u = s[j] - "a";            if(!son[p][u]) break;            p = son[p][u];            for(int k = 0; k < 26; ++ k) {                if(s[j+1]) {                    f[k][s[j+1]-"a"] += cnt[son[p][k]];                }                else f[k][26] += cnt[son[p][k]];            }        }        insert(s);    }    for(int i = 1; i <= q; ++ i) {        char alphabet[26];        cin >> alphabet;        long long ans = 0;        for(int j = 0; j < 26; ++ j) {            ans += f[j][26];            for(int k = 0; k < j; ++ k) {                ans += f[alphabet[j]-"a"][alphabet[k]-"a"];            }        }        cout << ans << "\n";    }    return 0;}