题解 P5149 【会议座位】

渺小的Mastar · 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;
}