M. Minimal and Maximal XOR Sum 2023“钉耙编程”中国大学生算法设计超级联赛（7）hdu7359

Problem - 7359

题目大意：给出一个n个数的排列，可以将任意区间内的所有数头尾翻转，每次操作的费用等于区间长度，要求将其变成一个递增排列，求消耗费用的异或和的最小值和最大值

1<=n<=1e5

思路：操作的最小费用就是翻转相邻两个数，费用为2，而这样翻转的最小操作次数就是排列的逆序对数量，而这样任意操作的操作数的奇偶性也与逆序对的数量的奇偶性相同，所以最小的异或和要么是0要么是2，与逆序对的数量的奇偶性有关。

考察如何使异或和最大，异或和最大也就是在与n的二进制位数相同时，每一位都为1，这样就需要分别翻转一次肠胃所有2的幂的区间，然后我们发现翻转了一个长为x的区间后，可以用x*(x-1)/2次翻转相邻两数的操作将区间还原，因为x是2的幂所以x*(x-1)/2一定是偶数，也就是i>1是所有2的i次方且小于等于n的数都能加到答案上，然后因为区间长度可以为1，所以也可以+1，那么最大值也就是在最小值基础上将n的二进制表达的其他位都变成1

#include<__msvc_all_public_headers.hpp>
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
ll tree[N];
int n;
ll a[N];
ll lowbit(ll x)
{return x & -x;
}
void add(ll x)
{//树状数组的建立while (x <= n){tree[x]++;x += lowbit(x);}
}
ll summ(ll x)
{//树状数组求前缀和ll ans = 0;while (x){ans += tree[x];x -= lowbit(x);}return ans;
}
void solve()
{cin >> n;for (int i = 1; i <= n; i++){//初始化树状数组tree[i] = 0;}ll inv = 0;for (ll i = 1; i <= n; i++){cin >> a[i];add(a[i]);inv += i - summ(a[i]);}int ans1 = inv & 1 ? 2 : 0;ll ans2 = log2l(n);if (1 << ans2 != log2l(n)){ans2++;}ans2 = (1 << ans2) - 1;//将n的二进制表达都填满1ans2 += !ans1 && n > 1 ? -2 : 0;//如果n!=1且an1等于0就要把2减掉cout << ans1 << " " << ans2 << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--){solve();}
}