题目链接
题目思路
字典树居然还能求逆序对,震惊
就是利用字典树求逆序对的思想来解决此题
妙蛙种子
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<long long,long long >
//typedef pair<long long,long long > pii
const int maxn=3e5+5,inf=0x3f3f3f3f,mod=998244353;
const double eps=1e-6;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n;
int a[maxn];
ll num[40][2];
struct trie {
int nex[maxn*30][2], cnt;
ll sz[maxn*30]; // 该结点结尾的字符串是否存在
void insert(int x) { // 插入字符串
int p = 0;
for (int i = 30; i>=0; i--) {
int c =(x>>i)&1;
num[i][c]+=sz[nex[p][c^1]];
if (!nex[p][c]) nex[p][c] = ++cnt; // 如果没有,就添加结点
p = nex[p][c];
sz[p]++;
}
}
}t;
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
t.insert(a[i]);
}
ll pr1=0,pr2=0;
for(int i=30;i>=0;i--){
if(num[i][1]<num[i][0]){
pr1+=num[i][1];
pr2+=(1<<i);
}else{
pr1+=num[i][0];
}
}
printf("%lld %lld\n",pr1,pr2);
return 0;
}