题目概述

CF1417E

解题报告

比赛结束之后想出来了……我做D题的时候不SB可能能做出来？

很显然我们需要考虑每个二进制位的贡献，第 $i$ 位取反之后只会影响到 $i$ 之前的高位相同，且这位不同的数，更具体地说，这些数之间的逆序对和正序对的数量互换了。

因此我们考虑如何维护第 $i$ 位之前的高位相同，且这位不同的数之间的逆序对和正序对，不难想到用Trie维护。

对于 $x$ 节点，我们记录 $L_x,R_x$ 表示 $x$ 的左右儿子，$S_x$ 表示 $x$ 子树中数的个数，$A_x$ 表示 $x$ 左子树到右子树的逆序对，$B_x$ 表示左子树到右子树的正序对。每次在 $x$ 节点向 $0$ 走时，说明出现了新的逆序对，数量是 $S_{R_x}$ ，而每次在 $x$ 节点向 $1$ 走时，说明出现了新的正序对，数量是 $S_{L_x}$ 。

最后统计第 $i$ 层中 $A_x-B_x$ 的和 $D_i$，初始逆序对数量减去所有 $D_i>0$ 的就是最少的逆序对数量。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=300000,maxt=9000000,LOG=30;

int n,X;LL ans;
int si,ro,son[maxt+5][2],sum[maxt+5];LL cnt[maxt+5][2],D[LOG+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
void Insert(int x,int p=ro){
    for (int i=29;~i;i--){
        int d=x>>i&1;sum[p]++;cnt[p][d]+=sum[son[p][d^1]];
        if (!son[p][d]) son[p][d]=++si;p=son[p][d];
    }
    sum[p]++;
}
void Count(int x,int i=29){
    ans+=cnt[x][0];D[i]+=cnt[x][0]-cnt[x][1];
    if (son[x][0]) Count(son[x][0],i-1);
    if (son[x][1]) Count(son[x][1],i-1);
}
int main(){
    freopen("E.in","r",stdin);freopen("E.out","w",stdout);
    readi(n);ro=++si;for (int i=1,x;i<=n;i++) readi(x),Insert(x);Count(ro);
    for (int i=0;i<30;i++) if (D[i]>0) ans-=D[i],X|=1<<i;
    printf("%lld %d\n",ans,X);return 0;
}