C. XOR Inverse 题解(字典树求逆序对)

题目链接

题目思路

字典树居然还能求逆序对，震惊

就是利用字典树求逆序对的思想来解决此题

妙蛙种子

代码

#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;
}