#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vei;
#define pb push_back
int cnt=1;
int trie[500005][60];
int vis[500005];
inline void Insert(string s,int idx){
int root=1,len=s.length(),x;
for(int i=0;i<len;i++){
x=s[i]-'a'+1;
if(!trie[root][x]) trie[root][x]=++cnt;
root=trie[root][x];
}
vis[root]=idx;
}
inline int Find(string s){
int root=1,len=s.length(),x;
for(int i=0;i<len;i++){
x=s[i]-'a'+1;
root=trie[root][x];
}
return vis[root];
}
long long ans=0;
vei Merge(vei al,vei ar){
int i=0,j=0,x=al.size(),y=ar.size();
vei res; res.clear();
while(i<x && j<y){
if(al[i]>ar[j]) ans++;
if(al[i]<ar[j]) res.pb(al[i++]);
else res.pb(ar[j++]);
}
while(i<x) res.pb(al[i++]);
while(j<y) res.pb(ar[j++]);
return res;
}
vei Sort(vei a){
if(a.size()==1) return a;
vei al,ar; al.clear(),ar.clear();
int mid=a.size()/2;
for(int i=0;i<mid;i++) al.pb(a[i]);
for(int i=mid;i<a.size();i++) ar.pb(a[i]);
al=Sort(al),ar=Sort(ar);
return Merge(al,ar);
}
vei a; string str;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>str,Insert(str,i);
for(int i=1;i<=n;i++) cin>>str,a.pb(Find(str));
a=Sort(a);
cout<<ans<<endl;
return 0;
}
以上是代码,望好心人留步帮我看一看哪里出错行吗,谢谢您付出宝贵的时间。
代码简洁易懂(代码稍微长点但是可读性极强)。