CF1416C 题解

__ryp__ · 2024-09-20 20:48:19 · 题解

看到题解区大神都写了 01 trie / 分治，根本看不懂，怎么办！

但是不要急！本题可以用根本没有思维含量的小常数基数排序 + 树状数组 O(n\log n \log V) 狠狠草过去！

这就是基数排序带给我的自信

我们直接狠狠贪心，从高到低枚举每一位，然后计算异或上这一位或是不异或的逆序对数。如果变少了，就直接选上这一位。然后就做完了。

但是……

如果你就这样天真的写了一颗平衡树 / 离散化 + 树状数组交上去，就会发现出题人狠狠的草爆了你的码！

但是！

众所周知，存在一种叫做基数排序的东西……它可以用线性的时间把一堆整数排序。

我们这里的问题是，离散化的速度太慢，是个线性对数。考虑到可以用基数排序替代快速排序 + 二分进行离散化，于是我们就做完了。

附一个基数排序离散化模板，它是本题的大功臣！

void radix_sort (int n)
{
    int mx = 0;
    for (int i = 1; i <= n; i++) ww[i] = { w[i], i };
    for (int i = 1; i <= n; i++) q[w[i] & 0x7fff]++, mx = max (mx, w[i] & 0x7fff);
    for (int i = 1; i <= mx; i++) q[i] += q[i - 1];
    for (int i = n; i >= 1; i--) rr[q[w[i] & 0x7fff]--] = ww[i];
    for (int i = 0; i <= mx; i++) q[i] = 0;
    mx = nr = 0;
    for (int i = 1; i <= n; i++) q[rr[i].fi >> 15]++, mx = max (mx, rr[i].fi >> 15);
    for (int i = 1; i <= mx; i++) q[i] += q[i - 1];
    for (int i = n; i >= 1; i--) ww[q[rr[i].fi >> 15]--] = rr[i];
    for (int i = 0; i <= mx; i++) q[i] = 0;
    for (int i = 1; i <= n; i++) w[ww[i].se] = nr += i == 1 || ww[i].fi != ww[i - 1].fi;
}

以及 Submission