字典树 计数问题（含 2022 icpc杭州 K）

//最近学了字典树，补一下

1.概念和实现

首先，字典树是一棵树（废话），边表示字母，从根到叶子节点所有边的顺序组合表示字目排列顺序。

看一下图明白很多：

例如：abc这个字母排序（或者说“单词”），可以用1->2->5->8这条路径表示。有个性质就是：同一个单词的末尾节点标号是唯一的。比如以6为末尾的“单词”只能是ac，不可能是bc。相当于每个点都要连自己的新边。

那么现在来实现字典树的插入和搜索。插入就是把单词插入树中，查找就是查找某单词出现的次数。

代码模板如下：

//ch[a,b]:在a这个节点接表示b字母的边
//cnt[a]:以节点a为末尾的“单词”的数量#include<iostream>
using namespace std;
const int N=10000010;int cnt[N],ch[N][27],idx;
strint s;void insert(string s){int p=0;for(int i=0;i<s.size();i++){int g=s[i]-'a';if(!ch[p][g])ch[p][g]=idx++;p=ch[p][g];}cnt[p]++;
}int query(string s){int p=0;for(int i=0;i<s.size();i++){int g=s[i]-'a';if(!ch[p][g])return 0;p=ch[p][g];}return cnt[p];
}int main()
{cin>>s;//...略return 0;	
}

字典树可以解决很多问题。我目前遇到的是两种，接下来再遇到就再整理：

1.记录某单词或排列的出现次数                         

2.记录不同排列从哪个字母开始有差别（比如这题）

2.例题

---

Problem - K - Codeforceshttps://codeforces.com/group/w6iGs8kreW/contest/552941/problem/K

K. Master of Both

time limit per test

1 s

memory limit per test

1024 MB

Professor Hui-Bot is the master of string theory and advanced data structures, so he came up with an interesting problem. Given a sequence of nn strings consisting of only lowercase English letters, how many inversions are there in this sequence when the strings are compared by lexicographical order?

As the most extraordinary student of Hui-Bot, Putata and Budada mastered superb string theory and advanced data structure skills respectively, and they solved this problem together with ease. However, there are qq different parallel universes, where the characters in the alphabet are not appearing in the original order.

Formally, the alphabet in each universe is a string, which is a permutation of the 2626 lowercase English letter, denoting the order each character appears.

A string aa is lexicographically smaller than a string bb if and only if one of the following holds:

• aa is a prefix of bb, but a≠ba≠b;
• in the first position where aa and bb differ, the string aa has a letter that appears earlier in the alphabet than the corresponding letter in bb.

The number of inversions in a sequence aa of length nn is the number of ordered pairs (i,j)(i,j) such that 1≤i<j≤n1≤i<j≤n, aj<aiaj<ai.

Please help Putata and Budada in each universe to solve the problem.

Input

The first line of the input contains two integers n,qn,q (1≤n≤5×1051≤n≤5×105, 1≤q≤5×1041≤q≤5×104), denoting the length of the sequence.

For the following nn lines, the ii-th line contains a string sisi (1≤|si|≤1061≤|si|≤106). It is guaranteed that the string consists of only lowercase English letters, and ∑i=1n|si|≤106∑i=1n|si|≤106.

For the following qq lines, each line contains a string tt, denoting the alphabet in one universe. It is guaranteed that tt is a permutation of 2626 lowercase English letters.

Output

Output qq lines, denoting the answer in qq universes.

---

思路：这题一开始是用树状数组暴力求逆序对个数的，但 毫无疑问地 t了。主要是每次都要排序，这就nlogn了，然后还有多组，包t。当时其实我就有这个想法，主要是 决定某两个单词是否逆序的字母排序是确定的，所以我们其实只需要把决定逆序的字母全取出来（用一个26*26的二维数组存储），每次给定一个排序原则之后，再用一个26*26的循环来看一下每一组是否真的逆序了。这样就不会超时了。

但问题就出在怎么找这些逆序对上面。暴力解方法不会，就卡住了。

其实就是用的 字典树。每一层看看还存了多少其他不同字母。这就用到了字典树的性质：同一节点上面所经过的路径一定是一样的，不存在有多个路径到达一个节点的情况。

还有一个注意的点，就是ans要开unsigned long long。这个罚了我好几发。

看一下代码吧~

#include<iostream>
#include<cstring>
using namespace std;
#define int long long 
typedef unsigned long long ull;const int N=1e6+100;
int n,q,ch[N][30],idx,sor[N];
string s[N],g;
char r='a'-1;
int cnt[100][100];//cnt[a][b]表示由于a在b前而引起的逆序对;
int num[N][30];void count(string s){int p=0;for(int i=0;i<s.size();i++){int g=s[i]-'a'+1;for(int i=0;i<=26;i++){if(i==g)continue;if(ch[p][i])cnt[i][g]+=num[p][i];}if(!ch[p][g])ch[p][g]=++idx;num[p][g]++;p=ch[p][g];}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>q;for(int i=1;i<=n;i++){cin>>s[i];s[i]+=r;count(s[i]);}while(q--){idx=0;ull ans=0;cin>>g;sor[0]=0;for(int i=0;i<g.size();i++){sor[g[i]-'a'+1]=i+1;}for(int i=0;i<=26;i++){for(int j=0;j<=26;j++){if(sor[i]>sor[j])ans+=cnt[i][j];}}cout<<ans<<endl;}return 0;
}