2022 ICPC 杭州站 K - Master of Both // Trie

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 <bits/stdc++.h>
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;
}