最近，我学习了莫队算法，用于对查询进行平方根分解，以加快解决某些问题的速度。
为了练习实现，我一直在尝试使用这个想法来解决D. Powerful array（Codeforces上的一个过去的竞赛问题）。该问题如下：
你有一个包含
个整数
的数组。
。定义
为整数
在该子数组中出现的次数。子数组的幂定义为所有整数的
之和（注意，只有这些项不为零的正数个）。
回答
个查询。在每个查询中，给定两个整数
和
，计算的幂。
它成立：
所示。我确信这个算法可以解决这个问题，并且其他人的已接受的代码也使用了类似的算法。然而，我的代码超时了。
以下是我编写的代码：
#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';
}
你能否建议一些非渐进式（或可能是渐进式）的方法来加速程序，以便通过时间限制？
我已经尝试了以下方法，但都无济于事：
- 使用向量而不是数组。
- 使用两个嵌套的对代替结构体。
- 仅使用一个对，然后使用映射来尝试恢复正确的答案顺序。
- 向（例如代码中的
）添加一些各种常数。 - 在结构体
el内部重载<比较运算符。
我觉得我错过了一些重要的东西，因为我检查过的其他代码似乎有相当大的余地通过时间限制（约半秒）。 然而，它们似乎正在使用与我的代码相同的算法。
任何帮助都将不胜感激！