P1966 火柴排队解题报告
无秒
2020-05-14 20:17:06
这题其实是有点意思的树状数组。由题目可以知道，其实每个数组只要第i大的对应的另外一个数组第i个就行，所以先离散化一波，然后将每个互相映射一下（是不是想到map了，其实用数组就行了），然后求的就是交换的次数，使得互相对应，即映射的那个数组p[i]=i，so，这个之前考过的，很熟悉，就是求逆序对，额，对，就是这样。
附上一个稍微诡异的代码：（极其诡异的sort,把我的离散化吓蓝了）
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a1[100003],a2[100003],b1[100003],b2[100003],p[100003];
int n,m1,m2,C[100003],ans,mod=99999997;
int lowbit(int i){return i&(-i);}
void chage(int i,int data)
{
while(i<=n)
{
C[i]+=data;
i+=lowbit(i);
}
}
int SUM(int i)
{
int sum=0;
while(i>0)
{
sum=sum+C[i];
i=i-lowbit(i);
}
return sum;
}
inline bool cmp1(int i, int j){return a1[i]<a1[j];}
inline bool cmp2(int i, int j){return a2[i]<a2[j];}
int main()
{
freopen("1966.in","r",stdin);
freopen("1966.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&a1[i]);b1[i]=a1[i];}
sort(b1+1,b1+n+1,cmp1);/*
m1=unique(b1+1,b1+n+1)-b1-1;
for(int i=1;i<=n;i++)
a1[i]=lower_bound(b1+1,b1+m1+1,a1[i])-b1;
*/
for(int i=1;i<=n;i++){scanf("%d",&a2[i]);b2[i]=a2[i];}
sort(b2+1,b2+n+1,cmp2);/*
m2=unique(b2+1,b2+n+1)-b2-1;
for(int i=1;i<=n;i++)
a2[i]=lower_bound(b2+1,b2+m2+1,a2[i])-b2;
*/
for(int i=1;i<=n;i++) p[b1[i]]=b2[i];
for(int i=1;i<=n;i++)
{
ans=ans+i-1-SUM(p[i]);
ans%=99999997;
chage(p[i],1);
}
printf("%d",(ans%mod+mod)%mod);
return 0;
}
```