题目链接

题意分析

我们考虑从1到n不断进行维护 同时令mid=n/2

接下来我们讨论如何交换x,y这两个位置上的数

1.1≤x≤mid,mid

1 x mid y n

使用两次交换 1-y x-n
y n mid 1 x

使用一次交换 x-y 
x n mid 1 y 

使用两次交换 1-x y-n
1 y mid x n

2.x,y>mid

1 mid x y n

使用一次交换 1-y
y mid x 1 n

使用一次交换 x-y
x mid y 1 n

使用一次交换 1-x
1 mid y x n

3.x,y≤mid

1 x y mid n

使用一次交换 y-n
1 x n mid y

使用一次交换 x-y
1 y n mid x

使用一次交换 x-n
1 y x mid n

每一种情况交换次数最多不超过5次

保证了总交换次数不超过5n次

CODE:

#include
#define N 300080
using namespace std;
int n;
long long sum,ans;
struct Node
{
	long long val,mask;
	int high;
}e[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld%lld",&e[i].val,&e[i].mask);
		sum+=e[i].val;
	} 
	for(int i=1;i<=n;++i)
	{
		for(int j=62;j>=0;--j)
		if((1LL<0)
		{
			for(int i=1;i<=n;++i)
			if((1LL<