2022 icpc杭州站 K. Master of Both

杭州站 K. Master of Both"/>

2022 icpc杭州站 K. Master of Both

题面

分析

按照给定的字典序去找逆序对，每次都进行计算会超时，可以利用字典树进行处理存下来当前字符出现的位置，对应之前出现过的字符串有多少个，sum[i][u]表示当前u字符在深度i出现过多少次，cnt[i][j]表示i字符在j字符之前出现的字符串个数，最后可以在查询中读取字典序，在新的字典序中遍历，只需要两层26循环，不会超时，如果发现新的字典序中出现了i大于j的情况，那就让答案加上cnt[i][j]，统计出有多少字符串存在i大于j的情况，最后得到答案。

代码

#include <bits/stdc++.h>using namespace std;
using ll = long long;const int N = 2e6 + 10;int nex[N][30];
int sum[N][30];
ll cnt[30][30];
int idx;
int pos[30];void insert(string s) {int p = 0;for(int i = 0; i < s.size(); i ++) {int u = s[i] - 'a' + 1;if(!nex[p][u]) nex[p][u] = ++ idx;for(int j = 0; j < 27; j ++) {cnt[j][u] += sum[p][j];}sum[p][u] ++;p = nex[p][u];}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, q;cin >> n >> q;for(int i = 0; i < n; i ++) {string s;cin >> s;s += ('a' - 1);insert(s);}while(q --) {string s;cin >> s;char ch = 'a' - 1;s = ch + s;ll ans = 0;for(int i = 0; i < 27; i ++) pos[s[i] - 'a' + 1] = i;for(int i = 0; i < 27; i ++) {for(int j = 0; j < 27; j ++) {if(pos[i] > pos[j]) ans += cnt[i][j];}}cout << ans << "\n";}
}