字典树的一百种用法

\[\huge\texttt{0/1 Trie}\]

\[\LARGE\texttt{\#1-Count Inversions}\]

\[\large\texttt{Problem}\]
$$\texttt{link}$$

\[\large\texttt{Idea}\]
考虑逆序对总个数的表达式：

\[\sum_{i=2}^{n}\sum_{j=1}^{i-1}\left[a_i</p>显然，通过式子直接暴力，复杂度为 \(\mathcal{O}(n^2)\)，显然错误。
考虑对于内层循环进行优化，主要问题在于如果最原始地进行比较大小需要一个一个进行比较。
于是，想到高位更大的数字一定更大，我们可以从高位依次比较。
于是我们可以考虑使用字典树，利用字典树存储二进制下每个数的每一位数。

\[\large\texttt{Solution}\]
对于每个数一次插入字典树，具体参考模板，以下仅赘述统计逆序对的部分。
假设当前插入的数为 \(x\)：

• 若当前遍历的位数上的编码为 \(\texttt{0}\)，则这一位编码为 \(\texttt{1}\) 的数能与 \(x\) 构成逆序对，更新答案，继续向下一位遍历。
  
• 若当前遍历的位数上的编码为 \(\texttt{1}\)，则继续向下一位遍历。
  

具体统计可以记录每个节点下存有几个数。
这里注意一个细节，每个数二进制形式的长度不同，需要统一长度，一种方法是都将长度变为 \(30\)，在前面填 \(\texttt{0}\) 即可。
时间复杂度 \(\mathcal{O}(n)\)，实则如果全部统一成 \(30\) 位是有一个大常数 \(30\) 的，写标准复杂度应该是 \(\mathcal{O}\left(n\log\left(\max\limits_{1\le i\le n}\left\{a_i\right\}\right)\right)\)。
当然还有其它解决长度不统一的方法。

\[\large\texttt{Code}\]
[code]#includeusing namespace std;int n,nex[15000005][2],cnt,siz[15000005];long long ans;void insert(int s){    int p=0;    for(int i=29;i>=0;i--){        int c=(s>>i)&1;        if(c==0)ans+=siz[nex[p][1]];        if(!nex[p][c])nex[p][c]=++cnt;        p=nex[p][c];        siz[p]++;    }}signed main(){    cin>>n;    for(int a,i=1;i>a;        insert(a);    }    cout