Codeforces Round #673 (Div. 1) C. XOR Inverse 逆序对+二进制枚举

https://codeforces.com/contest/1416/problem/C

• 给你一个数组$a[i]\ge 0$，让你找一个非负整数$x$，使得让$b[i]=a[i]?x$所得到的数组$b$的逆序数$(thenumberofinversions)$最少，求最小的$x$
• 异或问题看来一般都要按照每一位来考虑，我们从最高位往最低位考虑，什么时候能够使得数组的逆序数最少，因为最高位起到决定性的作用，如果说最高位对$1$取异或所得到的逆序数小于最高位对$0$取异或得到的逆序数，那么显然应该让$x$的这一位为$1$而不能是$0$；如果二者相等，考虑到需要求一个最小的$x$，这个时候$x$的这一位就应该是$0$
• 按照这个思路我们应该能够想到思路，枚举$x$的每一位，按照上述思路对$x$的每一位进行赋值，最后得到的$x$就是最小的，然后我们再计算出整个数组的逆序对即可

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 3e5;
int n;
struct st{
    int id;int val;bool operator < (const st &B)const{
    return val < B.val;}
}s[N + 100];
int a[N + 100];
ll tree[N + 100];
int lowbit(int x){
    return x & -x;
}
void ADD(int x, int d){
    while(x <= n){
    tree[x] += d;x += lowbit(x);}
}
ll query(int x){
    ll ans = 0;while(x > 0){
    ans += tree[x];x -= lowbit(x);}return ans;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for(int i=1;i<=n;i++){
    cin >> a[i];s[i].id = i;s[i].val = a[i];}stable_sort(s + 1, s + 1 + n);ll now = 0;for(int i=1;i<=n;i++){
    ADD(s[i].id, 1);now += i - query(s[i].id);}int x = 0;for(int i=0;i<=30;i++){
    ll res = 0;for(int j=1;j<=n;j++){
    s[j].id = j;s[j].val = (a[j] ^ (1 << i));}stable_sort(s + 1, s + 1 + n);memset(tree, 0, sizeof tree);for(int j=1;j<=n;j++){
    ADD(s[j].id, 1);res += j - query(s[j].id);}if(res < now){
    x |= (1 << i);}}ll res = 0;memset(tree, 0, sizeof tree);for(int i=1;i<=n;i++){
    s[i].id = i;s[i].val = (x ^ a[i]);}stable_sort(s + 1, s + 1 + n);for(int i=1;i<=n;i++){
    ADD(s[i].id, 1);res += i - query(s[i].id);}cout << res << ' ' << x;return 0;
}