记录编号	618749	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4499.陆家嘴想起飞	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	0.264 s
提交时间	2026-09-11 20:04:48	内存使用	4.23 MiB

#include <algorithm>
#include <cstdio> 
#include <iostream>

using namespace std;

const int N = (1 << 18) + 10;
const int Len = 18; 

int n;
int nums[N];
int len;

int all_nums[N];
int left_nums[N];
int left_tot;
int right_nums[N];
int right_tot;

long long inv_no[Len];
long long inv_yes[Len];

long long res_no_xor;
long long res_xor;

void cut (int l, int r, int k) {
    if (k < 0) {
        return;
    }
    
    left_tot = right_tot = 0;
    int one = 0;
    int zero = 0;
    for (int i = l; i <= r; i++) {
        if (all_nums[i] & (1 << k)) {
            right_tot++;
            right_nums[right_tot] = all_nums[i];
            inv_yes[k] += zero;
            one++;
        }
        else {
            left_tot++;
            left_nums[left_tot] = all_nums[i];
            inv_no[k] += one;
            zero++;
        }
    }
    
    for (int i = 1; i <= left_tot; i++) {
        all_nums[l + i - 1] = left_nums[i];
    }
    for (int i = 1; i <= right_tot; i++) {
        all_nums[l + left_tot + i - 1] = right_nums[i];
    }
    
    int mid = l + left_tot - 1;
    cut (l, mid, k - 1);
    cut (mid + 1, r, k - 1);
}

int main () {
    
    freopen ("wantfly.in", "r", stdin);
    freopen ("wantfly.out", "w", stdout);
    
    bool flag = true;
    
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf ("%d", &(nums[i]));
        all_nums[i] = nums[i];
    }
    for (len = 0; (1 << len) < n; len++) {}
    
    cut (1, n, len - 1);
    
    for (int i = len - 1; i >= 0; i--) {
        res_no_xor += inv_no[i];
        res_xor += min (inv_yes[i], inv_no[i]);
    }
    res_xor += 1;
    
    cout << min (res_no_xor, res_xor) << endl;
    
    return 0;
}