c++ - Mo算法计算数组的 "power"

Question

最近，我学习了Mo's algorithm用于查询的平方根分解，以加快解决某些问题的速度。

为了练习实现，我一直在努力解决D. Powerful array (Codeforces 上的一个过去的竞赛问题)使用这个想法。问题如下:

你有一个数组 整数 .

考虑一个任意子数组 .定义 是整数出现的次数 在这个子数组中。子数组的 幂 定义为 的总和对于所有整数 (请注意，只有正数的项不为零)。

回答查询。在每个查询中，给定两个整数 和 , 计算 的幂 .

它拥有:

使用莫氏算法，我在中编写了离线解决这个问题的代码。 .我确信这个问题可以使用这个算法和时间复杂度来解决，因为我已经检查了其他人接受的代码并且他们也使用了类似的算法。

然而，我的代码是gets a time limit exceeded verdict .

下面是我写的代码:

#include <ios>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>

int sqt;
long long int ans = 0;
long long int arr[200005] = {};
long long int cnt[1000005] = {};
long long int tans[200005] = {};

struct el
{
    int l, r, in;
};

bool cmp(const el &x, const el &y)
{
    if (x.l/sqt != y.l/sqt)
        return x.l/sqt < y.l/sqt;
    return x.r < y.r;
}

el qr[200005];

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    int n, q, a, b;
    std::cin >> n >> q;
    sqt = sqrt((double)(n))+27;
    for (int i = 0; i < n; i++)
        std::cin >> arr[i];
    for (int i = 0; i < q; i++)
    {
        std::cin >> a >> b;
        a--; b--;
        qr[i].l = a;
        qr[i].r = b;
        qr[i].in = i;
    }
    std::sort(qr, qr+q, cmp);

    int li = 0; //left iterator
    int ri = 0; //right iterator
    ans = arr[0];
    cnt[arr[0]]++;

    for (int i = 0; i < q; i++)
    {
        while (li < qr[i].l)
        {
            ans -= cnt[arr[li]]*cnt[arr[li]]*arr[li];
            cnt[arr[li]]--;
            ans += cnt[arr[li]]*cnt[arr[li]]*arr[li];
            li++;
        }
        while (li > qr[i].l)
        {
            li--;
            ans -= cnt[arr[li]]*cnt[arr[li]]*arr[li];
            cnt[arr[li]]++;
            ans += cnt[arr[li]]*cnt[arr[li]]*arr[li];
        }
        while (ri < qr[i].r)
        {
            ri++;
            ans -= cnt[arr[ri]]*cnt[arr[ri]]*arr[ri];
            cnt[arr[ri]]++;
            ans += cnt[arr[ri]]*cnt[arr[ri]]*arr[ri];
        }
        while (ri > qr[i].r)
        {
            ans -= cnt[arr[ri]]*cnt[arr[ri]]*arr[ri];
            cnt[arr[ri]]--;
            ans += cnt[arr[ri]]*cnt[arr[ri]]*arr[ri];
            ri--;
        }
        tans[qr[i].in] = ans;
    }
    for (int i = 0; i < q; i++)
        std::cout << tans[i] << '\n';
}

您能否提出任何非渐近(或什至可能是渐近)改进，使程序加速到足以通过时间限制？

我已经尝试过以下方法，但无济于事:

1. 使用 vector 而不是数组。
2. 使用两个嵌套对而不是结构。
3. 仅使用一对，然后使用映射尝试恢复答案的正确顺序。
4. 向 sqt 添加一些不同的常量(例如上面代码中的 )。
5. 在结构 el 本身中重载 < 比较运算符。

我觉得我错过了一些重要的东西，因为我检查过的其他代码似乎以相当大的回旋余地(大约半秒)通过了时间限制。然而，他们似乎使用与我的代码相同的算法。

非常感谢任何帮助!

Answer 1

你可以降低强度

    while (li < qr[i].l)
    {
        ans -= cnt[arr[li]]*cnt[arr[li]]*arr[li];
        cnt[arr[li]]--;
        ans += cnt[arr[li]]*cnt[arr[li]]*arr[li];
        li++;
    }

到

    while (li < qr[i].l)
    {
        ans -= (2*cnt[arr[li]]-1)*arr[li];
        cnt[arr[li]]--;
        li++;
    }

其他人也是如此。