字典树逆序对（Master of Both）

2022ICPC杭州K题 Master of Both

题目

给定n和m，表示n个字符串和m组询问

字符串长度1e5，总长度不超过1e6

m组询问中，每次给定一个字符串（只含有26个不同的小写字母），表示比较规则（前面小于后面），求n个字符串中的逆序对个数

性质

首先发现，对于n个字符串中任意两个字符串a,b，只有两种情况

• a是b的前缀，那么此时a<b一定成立，在任何比较规则下
• a不是b的前缀，那么，首先找到最长公共前缀的下一个字符，这俩字符即可决定a和b的大小关系，并且a和b的大小关系只由这一对字符决定

做法

1. 字典树
2. 插入字符串的时候维护res数组和cnt数组。
3. 设res[i][j]表示 字母i>字母j的情况下，产生的逆序对个数
4. 设cnt数组表示字典树中节点i的字数中有多少个单词

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int t[N][26],idx;
ll cnt[N];//trie中每个节点的权值 
ll res[26][26];//在i>j的规则下，整个序列产生的逆序对 
ll chushi;//表示一定会产生的逆序对个数 
ll n,m;

void update_res(int p,int q){
	//当前在p节点，要经过边q
	for(int i=0;i<26;i++){
		//当i>q的时候，产生的逆序对个数增加 cnt个 
		res[i][q]+=cnt[t[p][i]];
	} 
}

void insert(const string &s){
	int p=0;//当前节点 
	for(int i=0;i<s.size();i++){
		int q=s[i]-'a';//边的方向
		if(!t[p][q])t[p][q]=++idx;
		
		update_res(p,q);
		
		p=t[p][q];
		
		cnt[p]++; 
	}
	
	for(int i=0;i<26;i++){
		chushi+=cnt[t[p][i]];//一定会产生的逆序对 
	}
}

ll ask(const string &s){
	ll ans=0;
	for(int i=0;i<s.size();i++){
		for(int j=i+1;j<s.size();j++){
			//注意j在i前面，因为s[j]>s[i] 
			ans+=res[s[j]-'a'][s[i]-'a'];
		}
	}
	return ans;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		insert(s);
	}
	while(m--){
		string s;
		cin>>s;
		cout<<ask(s)+chushi<<endl;
	}
	return 0;
}