记录编号	602348	评测结果	AAAAAAAAAA
题目名称	4166.遵循指令之意	最终得分	100
用户昵称	ChenBp	是否通过	通过
代码语言	C++	运行时间	2.368 s
提交时间	2025-07-03 16:52:44	内存使用	9.83 MiB

#include <iostream>
#include <algorithm>
using namespace std;
int n,a[1000000],b[1000000],c[1000006];
int tree1[1000006],tree2[1000006];
int lowbit(int x){
	return x&(-x);
}
void add(int tree[],int x,int y){
	for(int i=x;i<=n;i+=lowbit(i)){
		tree[i]+=y;
	}
}
int ask(int tree[],int x){
	int ans=0;
	for(int i=x;i;i-=lowbit(i)){
		ans+=tree[i];
	}
	return ans;
}
int main() {
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	cin>>n;
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++){
		if(i&1) cin>>a[++cnt1];
		else cin>>b[++cnt2];
	}
	
	// 求逆序对 
	int n1=0,n2=0;
	for(int i=1;i<=cnt1;i++){
		n1+=ask(tree1,a[i]-1);
		add(tree1,a[i],1);
	}
	for(int i=1;i<=cnt2;i++){
		n2+=ask(tree2,b[i]-1);
		add(tree2,b[i],1);
	}
	
	sort(a+1,a+1+cnt1);
	sort(b+1,b+1+cnt2);
	cnt1=cnt2=0;
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(i&1) c[++cnt]=a[++cnt1];
		else c[++cnt]=b[++cnt2];
	}
	
	if((n1&1)!=(n2&1)){
		swap(c[cnt],c[cnt-2]);
	}
	
	for(int i=1;i<=n;i++){
		cout<<c[i]<<" ";
	}
	return 0;
}