自动搬运

查看原文

来自洛谷，原作者为

	渺小的Mastar 这个家伙很傻，什么也没有留下

搬运于2025-08-24 22:07:39，当前版本为作者最后更新于2019-04-18 16:54:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

trie树加树状数组求逆序对，绝对没有重复题解=.=

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define rgi register int 
#define maxn 100005
#define N 500005
using namespace std;
int n,a[maxn],tree[maxn],num[N],trie[N][100];
ll ans=0,tot;
string s;
void upd(string s,int x)
{
    int p=0;
    for(int i=0;i<s.size();i++)
    {
        if(!trie[p][s[i]-'A'])
            trie[p][s[i]-'A']=++tot;
        p=trie[p][s[i]-'A'];
    }
    num[p]=x;
}//插入字符串
int get(string s)
{
    int p=0;
    for(int i=0;i<s.size();i++)
        p=trie[p][s[i]-'A'];
    return num[p];
}
inline int lowbit(int x)
{
	return x&(-x);
}
inline void add(int x,int k)
{
	for(;x<=n;x+=lowbit(x))
		tree[x]+=k;
}
ll query(int x)
{
	ll tmp=0;
	for(;x;x-=lowbit(x))
		tmp+=tree[x];
	return tmp;
}
int main()
{
	cin>>n;
	for(rgi i=1;i<=n;++i)
	{
		cin>>s;
		upd(s,i);
	}
	for(rgi i=1;i<=n;++i)
	{
		cin>>s;
		a[i]=get(s);
	}
	for(rgi i=1;i<=n;++i)
	{
		add(a[i],1);
		ans+=i-query(a[i]);
	}
	cout<<ans;
}