洛谷P5149——会议座位【字典树 + 逆序对】

大致思路：我们先用字典树把单词存起来，在每个单词的末尾节点给这个单词按照出现顺序标号，然后在查找的过程中，把其出现顺序用一个数组一次存起来，然后求这个数组的逆序对即可。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>

using namespace std;

const int MAXN = 500010;
char na[110];
int trie[MAXN][60],ed[MAXN],a[MAXN],b[MAXN * 2];
long long n,tot,k,t,cnt;

inline void insert(char *s){
 int len = strlen(s),p = 1;
 for(int i = 0; i < len; i++){
  int ch = s[i] - 'A';
  if(trie[p][ch] == 0) trie[p][ch] = ++tot;
  p = trie[p][ch];
 }
 ed[p] = ++k; //给每一个字符串编号
}

inline void search(char *s){
 int len = strlen(s), p = 1;
 for(int i = 0; i < len; i++){
  int ch = s[i] - 'A';
  p = trie[p][ch];
 }
 a[++t] = ed[p]; //打乱顺序后每个字符串的顺序
}

inline void merge(int l,int r, int mid){
 int i = l, j = mid + 1;
 for(int k = l; k <= r; k++){
  if(j > r || (i <= mid && a[i] < a[j])) b[k] = a[i++];
  else b[k] = a[j++],cnt += mid - i + 1;
 }
 for(int k = l; k <= r; k++) a[k] = b[k];
}

void merge_sort(int left,int right){
 int center;
 if(left < right){
  center = (left + right) / 2;
  merge_sort(left,center);
  merge_sort(center + 1,right);
  merge(left,right,center);
 }
}

int main(int argc, char const *argv[])
{
 tot = 1,cnt = 0,k = 0,t = 0;
 memset(trie,0,sizeof(trie));
 memset(ed,0,sizeof(ed));
 scanf("%lld",&n);
 for(int i = 1; i <= n; i++){
  scanf("%s",na);
  insert(na);
 }
 for(int i = 1; i <= n; i++){
  scanf("%s",na);
  search(na);
 }
 merge_sort(1,t);
 printf("%lld\n",cnt);
 return 0;
}