火柴排队

火柴排队

P1966 NOIP2013 提高组 火柴排队

获取两列火柴后，先将它们分别从小到大排序。然后建一个新数组，按骑宠一个排好序的序列的原坐标的为存另一个排好序的数列的位置的原坐标。即当前坐标的目标位置。

将数组处理好后，归并排序，每次后一半比前一半小时，统计结果，答案为结果之和，统计的结果即当前数到目标位置需要的交换次数。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
long long r_r(){//快读 
	long long x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int m_d=1e8-3;
const int o_o=1e6+10; 
long long n;
long long x[o_o];//要排序的序列 
long long p[o_o];//目标排序好的序列 
long long a_s=0;//答案 
struct po{
    int v,i;
}l_1[o_o],l_2[o_o];
bool c_1(po a,po b){
    return a.v<b.v;//从小到大排序 
}
void g_s(int l,int r){//归并排序 
    if(l==r)return ;
    int m_i=(l+r)/2;
    g_s(l,m_i);//二分 
    g_s(m_i+1,r);//二分 
    int i=l;//要排序的第一个序列的开头 
	int j=m_i+1;//要排序的第二个序列的开头 
	int k=l;//要排序好的序列的下表 
    while(i<=m_i&&j<=r){//从小到大排序 
        if(x[i]<=x[j]){
            p[k]=x[i];
            ++k;
            ++i;
        }else{
            p[k]=x[j];
            ++k;
            ++j;
            a_s=(a_s+m_i-i+1)%m_d;//要更新位置，统计答案 
        }
    }
    while(i<=m_i){//剩下的直接接上 
        p[k]=x[i];
        ++k;
        ++i;
    }
    while(j<=r){//剩下的直接接上 
        p[k]=x[j];
        ++k;
        ++j;
    }
    for(int i=l;i<=r;i++)x[i]=p[i];//复制排好序的数列到原数列 
}
int main(){
    n=r_r();//获取火柴序列长度 
    for(int i=1;i<=n;i++){
        l_1[i].v=r_r();//记录价值 
        l_1[i].i=i;//记录坐标 
    }
    for(int i=1;i<=n;i++){
        l_2[i].v=r_r();//记录价值 
        l_2[i].i=i;//记录坐标 
    }
    sort(l_1+1,l_1+n+1,c_1);//将第一列火柴排序 
    sort(l_2+1,l_2+n+1,c_1);//将第二列火柴排序 
    for(int i=1;i<=n;i++)x[l_2[i].i]=l_1[i].i;
	//对应坐标差，按第一列火柴排序好的顺序后的原坐标来存储第二列火柴排好顺序的原坐标 
    
	g_s(1,n);//归并排序统计答案 
    printf("%lld",a_s);//输出 
    return 0;
}