HDU 6059 - Kanade's trio | 2017 Multi-University Training Contest 3

思路来自题解（看着题解和标程瞎吉尔比划了半天）

/*

HDU 6059 - Kanade's trio [ 字典树 ]  |  2017 Multi-University Training Contest 3

题意：

	给出数组 a[N]，问满足  (i<j<k) &&  ((A[i] xor A[j])<(A[j] xor A[k])) 的三元组数数量

	限制 N<=5e5, a[i] <= 2^30

分析：

	对于某一对 ai, ak ，满足条件的 aj 为：

		对于 ai 和 ak 的最高的不同位 p ，满足 aj[p] == ai[p]  也就是 aj[p] != ak[p]

	首先把 ak 插入字典树（从后往前），不考虑 ai 的情况下对于某个 ak 的前缀 ak[1..p]，满足条件的 ak,aj 对的数目 = (j < k && ak[p] != aj[p])

		这可以预处理 1 到 k-1 第 p 位为 0 or 1 的数字的个数，然后每插一个ak，就累加 aj

	然后就是对于每个 ai，枚举 p ,满足条件的ak则是前缀与ai相同，第 p 位不同的个数

		ans += ak[1..p]所对应的j,k对 - 不合法的即 j<=i 的 j,k 对

*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 5e5+5;

const int SIZE = N*31;

int sum[N][30][2];

int bin[30];

namespace Trie {

    int ch[SIZE][2], tot, num[SIZE];

    LL ss[SIZE];//j,k对

    int init(int n) {

        tot = 0;

        for (int i = 0; i <= n; i++)

            ch[i][0] = ch[i][1] = ss[i] = num[i] = 0;

    }

    void insert(int x, int i) {

        int now = 0;

        for (int j = 29; j >= 0; j--)

        {

            int t = x&bin[j]; t >>= j;

            if (!ch[now][t]) ch[now][t] = ++tot;

            now = ch[now][t];

            ss[now] += sum[i-1][j][t^1];

            num[now]++;

        }

    }

    LL query(int x, int i) {

        int now = 0;

        LL ans = 0;

        for (int j = 29; j >= 0; j--)

        {

            int t = x&bin[j]; t >>= j;

            if (ch[now][t^1])

            {

                ans += ss[ch[now][t^1]] - (LL)sum[i][j][t]*num[ch[now][t^1]];

            }

            if (!ch[now][t]) break;

            now = ch[now][t];

        }

        return ans;

    }

}

int t, n, a[N];

int main()

{

    bin[0] = 1;

    for (int i = 1; i <= 29; i++) bin[i] = bin[i-1]<<1;

    scanf("%d", &t);

    while (t--)

    {

        scanf("%d", &n);

        memset(sum[0], 0, sizeof(sum[0]));

        for (int i = 1; i <= n; i++)

        {

            scanf("%d", &a[i]);

            memcpy(sum[i], sum[i-1], sizeof(sum[i]));

            for (int j = 29; j >= 0; j--)

            {

                int t = a[i]&bin[j]; t >>= j;

                sum[i][j][t]++;

            }

        }

        Trie::init(n*30);

        LL ans = 0;

        for (int i = n; i >= 1; i--)

        {

            ans += Trie::query(a[i], i);

            Trie::insert(a[i], i);

        }

        printf("%lld\n", ans);

    }

}

以前不怎么打字典树，比赛的时候打成血崩- -，换队友上用了两棵字典树依旧血崩- -