ACM模版

描述

题解

这个题思路十分巧妙，没想到竟然可以用字母树解。

题解不难理解，就是有些出人意料了。看了题解后，我拿着官方题解，参考着写了一份，习惯性的将一些东西改成了自己的习惯……比如说，初始化能用 memset() 的都用 memset() ，然后我就超时了……，很纳闷儿，再三斟酌，我尝试将初始化改成了循环初始化，发现一下子竟然 AC 了。这是最让我十分意外的，我一直以来都十分认可 memset() ，以为他会快很多，但是，他并没有想象中那么快。之所以会超时是因为循环初始化人家用多少初始化多少，而 memset() 我则是习惯性的将整个数组初始化，导致时间消耗一下子上去了，题中有个很重要的条件， 1≤∑n≤5∗105 ，所以，这里并没有直接给 n 的范围，为了肯定可行，我们都是开了足够大，但是我们绝大多数空间都是用不到的，如果每次都是 memset() 整个数组，自然是浪费太严重，时间消耗太高， TLE 也就正常了。

所以呢，以后一定要注意 memset() 函数的用处，并不能因为他效率高，而一味的简易处理，代码虽然简单了， TLE 也是没商量的事。

代码

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;
const int MAGIC = 30;

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int n, tot;
int a[MAXN];
int go[MAXN << 5][2];
int num[MAXN << 5];
int tree[MAXN][MAGIC][2];
ll ss[MAXN << 5];

int main()
{
    int T;
    scan_d(T);
    while (T--)
    {
        for (int i = 1; i <= tot; i++)
        {
            go[i][0] = go[i][1] = 0;
            ss[i] = num[i] = 0;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < MAGIC; j++)
            {
                tree[i][j][0] = tree[i][j][1] = 0;
            }
        }

        tot = 1;
        scan_d(n);
        for (int i = 1; i <= n; i++)
        {
            scan_d(a[i]);
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < MAGIC; j++)
            {
                tree[i][j][0] = tree[i - 1][j][0];
                tree[i][j][1] = tree[i - 1][j][1];
            }
            for (int j = 0; j < MAGIC; j++)
            {
                int k = (a[i] & (1 << j)) > 0;
                tree[i][j][k]++;
            }
        }

        ll ans = 0;
        for (int i = n; i >= 1; i--)
        {
            int now = 1;
            for (int j = MAGIC - 1; j >= 0; j--)
            {
                int k = (a[i] & (1 << j)) > 0;
                if (go[now][k ^ 1])
                {
                    ans += ss[go[now][k ^ 1]] - num[go[now][k ^ 1]] * 1ll * tree[i][j][k];
                }
                if (!go[now][k])
                {
                    break;
                }
                now = go[now][k];
            }
            now = 1;
            for (int j = MAGIC - 1; j >= 0; j--)
            {
                int k = (a[i] & (1 << j)) > 0;
                if (!go[now][k])
                {
                    go[now][k] = ++tot;
                }
                now = go[now][k];
                ss[now] += tree[i - 1][j][k ^ 1];
                num[now]++;
            }
        }

        cout << ans << endl;
    }

    return 0;
}