老早以前做的题，出了点小锅一直没修，今天突然来了兴致
于是
修了下。。。。。。
大概就是按原顺序编号，然后把编号丢到第二个序列中，求遍逆序对（这里用树状数组求）。
而关于存人名的问题---->map
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define re register 4 #define LL long long 5 #define DB double 6 #define For(x,a,b) for(re int x=a;x<=b;x++) 7 #define For2(x,a,b) for(re int x=a;x>=b;x--) 8 #define LFor(x,a,b) for(re LL x=a;x<=b;x++) 9 #define LFor2(x,a,b) for(re LL x=a;x>=b;x--) 10 #define Abs(x) ((x>0)? x:-x) 11 map<string,LL>tch; 12 int n; 13 char s[100005][7]; 14 LL p[100005]; 15 LL f[100005]; 16 LL c[500005]; 17 LL ans; 18 struct pp 19 { 20 LL val,pos; 21 }a[100005]; 22 inline LL lowbit(LL x) {return x&(-x);} 23 inline bool cmp(pp x,pp y) {return x.val==y.val? x.pos>y.pos:x.val>y.val;} 24 LL query(LL x) 25 { 26 LL sum=0; 27 while(x>0) 28 { 29 sum+=c[x]; 30 x-=lowbit(x); 31 } 32 return sum; 33 } 34 void update(LL x) 35 { 36 while(x<=n) 37 { 38 c[x]+=1; 39 x+=lowbit(x); 40 } 41 } 42 43 int main() 44 { 45 scanf("%d",&n); 46 int tot=0; 47 For(i,1,n) 48 { 49 scanf("%s",s[i]); 50 tch[s[i]]=++tot; 51 } 52 For(i,1,n) 53 { 54 scanf("%s",s[i]); 55 a[i].val=tch[s[i]]; 56 a[i].pos=i; 57 } 58 sort(a+1,a+n+1,cmp); 59 ans=0; 60 For(i,1,n) 61 { 62 update(a[i].pos); 63 ans+=query(a[i].pos-1); 64 } 65 printf("%lld",ans); 66 return 0; 67 }