【题解】会议座位

给一开始座位表顺序中每个老师一个编号，分别为。

再根据打乱后的座位表顺序求出新的编号序列。

显然是求新编号序列中逆序对个数

可以使用归并排序或者树状数组解决。

题解区里没有树状数组，那我就发个树状数组的吧。

code

#include<bits/stdc++.h>
using namespace std;

#define int long long

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

int n;
string s;
map<string,int>mp;

int c[100007];
void change(int x,int k){
    while(x<=n){
        c[x]+=k;x+=(x&(-x));
    }
}

int query(int x){
    int ret=0;
    while(x){
        ret+=c[x];x-=(x&(-x));
    }
    return ret;
}

int ans,a[100007];

signed main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(register int i=1;i<=n;i++){
        cin>>s;mp[s]=i;
    }
    for(register int i=1;i<=n;i++){
        cin>>s;a[i]=mp[s];
    }
    for(register int i=n;i>=1;i--){
        ans+=query(a[i]);change(a[i],1);
    }
    cout<<ans<<endl;
    return 0;
}

当然，给老师编号的工作除了可以用map，也可以手写Trie，都挺简单。