排位赛第二场 C.Intersections
题意:
给出两串有相同数字的序列,连接各个相同的数字,求出他们交叉的个数
思路:
深入理解后即:把一串序列转化为规定的序列,需要的交换次数
本来想用冒泡求交换次数,但时间肯定超。
经过资料查询后,发现这是一道求逆序对个数的题目。
逆序对,简单来说即 我的数字比你大,但你排在我后面。
这里有两种做法:
1.归并排序
初学归并排序
说说归并的过程:把序列一直二分,再合并,合并的过程中,比较两个部分的数值,加到一个新的数组中去,再处理剩下的元素,接着再把这些数字重新放回原来数组的位置,这样保证每一部分再合并前都是有序的。
求逆序对的实质:
每次分治合并的时候,若出现mid右边部分的数字比左边小,那么从该数字一定比左边当前位置到mid的所有数字都小,即都是逆序对。
我们就用一个ans把他们加上。
#include
using namespace std;
const int N = 1e6+5;
#define int long long
int a[N];
int b[N];
int ans;
void msort(int l,int r)
{
// cout<>1;
msort(l,mid);
msort(mid+1,r);
int pos=l;
int i=l;
int j=mid+1;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j])
{
b[pos++]=a[i++];
}else
{
ans+=(mid-i+1);
b[pos++]=a[j++];
}
}
while(i<=mid)
{
b[pos++]=a[i++];
}
while(j<=r)
{
b[pos++]=a[j++];
}
for(int i=l;i<=r;i++)
{
a[i]=b[i];
}
}
signed main()
{
int t;
scanf("%lld",&t);
while(t--)
{
int n;
ans=0;
scanf("%lld",&n);
mapma;
vectorc(n+1);
for(int i=1;i<=n;i++)
{
int num;
scanf("%lld",&num);
ma[num]=i;
}
for(int i=1;i<=n;i++)
{
int num;
scanf("%lld",&num);
a[ma[num]]=i;
}
msort(1,n);
printf("%lld\n",ans);
}
}
2.树状数组
求逆序对实质:
用树状数组表示x数字之前存在的数字个数num,(x-1)- num 就是还未出现的数字个数,即和x互相为逆序对的个数(本应该出现了,却没出现,说明其在后面出现)
#include
using namespace std;
const int N = 1e5+7;
int a[N];
int n;
int lowbit(int x)
{
return x&-x;
}
void update(int x,int u)
{
for(;x<=n;x+=lowbit(x))
{
a[x]+=u;
}
}
int ask(int x)
{
int data=0;
for(;x>0;x-=lowbit(x))
{
data+=a[x];
}
return data;
}
signed main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(a,0,sizeof a);
scanf("%d",&n);
mapma;
vectorb(n+1);
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
ma[b[i]]=i;
}
vectorc(n+1);
for(int i=1;i<=n;i++)
{
int num;
scanf("%d",&num);
c[ma[num]]=i;
}
long long ans=0;
for(int i=1;i<=n;i++)
{
update(c[i],1);
ans+=(c[i]-1)-ask(c[i]-1);
}
printf("%lld\n",ans);
}
}