D. Powerful array - 题解
比赛与标签
比赛: Yandex.Algorithm 2011: Round 2 标签: data structures, implementation, math, two pointers, *2200 难度: *2200
题目大意喵~
主人，这道题是这样的呐：
我们有一个包含 n 个正整数的数组 a，还有 t 个查询。 每个查询会给我们一个区间 [l, r]。我们需要计算这个子数组 a[l...r] 的 “力量值”（Power）。
那...什么是“力量值”呢？对于子数组中的每一个出现过的数字 s，我们先数一数它出现了多少次，记作 Ks。然后，这个子数组的力量值就是所有 Ks * Ks * s 的总和。
简单来说，就是对子数组里每一种数值，算出它的 (出现次数的平方) * (数值本身)，然后把这些结果全部加起来，就是这个子-数组的力量值啦！我们的任务就是回答所有 t 个查询。
解题思路喵！
这道题的数据范围 n 和 t 都达到了 200000，如果对每个查询都傻乎乎地遍历一遍区间 [l, r] 来计算，那复杂度就是 O(n*t)，肯定会超时的说！(｡>ω<｡)
所以，我们需要一个更聪明的办法！注意到题目并不要求我们“在线”回答查询，也就是说，我们可以先把所有查询读进来，再按我们喜欢的顺序去处理它们。这种可以离线处理的区间查询问题，马上就能让聪明的猫娘想到一个超级厉害的算法——莫队算法！喵~
莫队算法的核心思想就是，通过对查询进行巧妙的排序，来减少区间左右端点指针移动的总次数。
1. 莫队算法基础：分块与排序
首先，我们将整个数组 a 分成 sqrt(n) 个块，每个块的大小也是 sqrt(n)。
然后，我们对所有的查询 [l, r] 进行排序。排序规则是：
- 如果两个查询的左端点
l在不同的块里，那么就按l所在的块的编号从小到大排。 - 如果两个查询的左端点
l在同一个块里，那么就按右端点r从小到大排。
这样排序后，处理查询时，左端点 l 会在一个块内缓慢移动，而右端点 r 会在整个数组上有序地移动。当左端点移动到下一个块时，右端点才会大幅度跳跃。这样整体上就大大减少了指针移动的总距离！
小优化（奇偶性排序/蛇形排序）：为了让右端点 r 的移动更平滑，我们可以在排序时加一个小技巧。当左端点 l 所在的块编号是偶数时，我们让 r 升序排；当块编号是奇数时，我们让 r 降序排。这样，右端点在处理完一个块的查询后，就不用“跳”回数组的开头，而是可以顺势“滑”向下一个目标，就像一条小蛇一样扭来扭去，非常可爱，也更高效喵！
2. 指针移动与贡献计算
莫队算法的精髓在于，当我们把当前处理的区间 [L, R] 移动到下一个查询的目标区间 [l, r] 时，我们只需要一步一步地移动指针，并在每一步都快速更新答案。
假设我们已经算好了区间 [L, R] 的力量值 current_power。现在我们要把这个区间扩展或缩小。
添加一个元素 x： 当我们的区间右端点从 R 移动到 R+1 时，我们把新元素 x = a[R+1] 加入了区间。假设 x 在原区间 [L, R] 中出现了 k 次，它的贡献是 k*k*x。现在它出现了 k+1 次，贡献变成了 (k+1)*(k+1)*x。 那么力量值的变化量就是： Δ_power = (k+1)² * x - k² * x= (k² + 2k + 1) * x - k² * x= (2k + 1) * x 所以，我们只需要 O(1) 的时间就可以更新力量值啦！
删除一个元素 x： 当我们的区间左端点从 L 移动到 L+1 时，我们把元素 x = a[L] 移出了区间。假设 x 在原区间 [L, R] 中出现了 k 次，它的贡献是 k*k*x。现在它出现了 k-1 次，贡献变成了 (k-1)*(k-1)*x。 那么力量值的变化量就是： Δ_power = (k-1)² * x - k² * x= (k² - 2k + 1) * x - k² * x= (-2k + 1) * x 也就是说，力量值要减去 (2k - 1) * x。这也同样是 O(1) 的操作！
通过这两个神奇的 add 和 remove 操作，我们就可以在指针的每次移动中，飞快地更新答案。整个算法的流程就是：
- 读入所有数据和查询。
- 对查询进行莫队排序（带奇偶性优化）。
- 初始化当前区间为空
[0, -1]，力量值为0。 - 遍历排好序的查询，通过
add和remove函数，将当前区间[current_l, current_r]调整到目标查询区间[q.l, q.r]。 - 记录下当前的力量值作为该查询的答案。
- 所有查询处理完毕后，按原始顺序输出答案。
这样，我们就能在规定时间内解决问题啦，喵~！
代码实现喵
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
// 使用一个全局数组来记录频率，可以提高性能喵~
// a[i] 的最大值是 10^6
const int MAX_A_VAL = 1000001;
int counts[MAX_A_VAL] = {};
// 莫队算法状态的全局变量
long long current_power = 0;
std::vector<int> a;
// 查询的结构体，用来存放查询信息和原始ID
struct Query {
int l, r, block, id;
};
// 将一个元素添加到当前区间
void add(int index) {
int val = a[index];
// 力量值的变化是 ((k+1)^2 - k^2) * val = (2k+1) * val
// 这里的 k 是 val 当前的出现次数
current_power += (2LL * counts[val] + 1) * val;
counts[val]++; // 更新出现次数
}
// 从当前区间移除一个元素
void remove(int index) {
int val = a[index];
counts[val]--; // 先更新出现次数
// 力量值的变化是 ((k-1)^2 - k^2) * val = (-2k+1) * val
// 相当于减去 (2k-1) * val。
// 在 counts[val]-- 之后，新的 counts[val] 是 k-1
// 所以 (2 * (新次数) + 1) * val 就是 (2*(k-1)+1)*val = (2k-1)*val
// 所以我们直接减去 (2LL * counts[val] + 1) * val 就好啦
current_power -= (2LL * counts[val] + 1) * val;
}
int main() {
// 快速 I/O，让程序跑得更快一点~
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, t;
std::cin >> n >> t;
a.resize(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
}
std::vector<Query> queries(t);
// 计算块的大小，这是莫队算法的关键一步
int block_size = static_cast<int>(sqrt(n));
if (block_size == 0) { // 防止n=0的情况
block_size = 1;
}
for (int i = 0; i < t; ++i) {
std::cin >> queries[i].l >> queries[i].r;
// 转换为 0-based 索引，方便编程喵
queries[i].l--;
queries[i].r--;
queries[i].id = i; // 记录原始ID，以便最后按顺序输出
queries[i].block = queries[i].l / block_size; // 计算左端点所在的块
}
// 使用 lambda 表达式对查询进行排序，这就是莫队的核心！
std::sort(queries.begin(), queries.end(), [&](const Query& q1, const Query& q2) {
if (q1.block != q2.block) {
return q1.block < q2.block; // 按块编号排序
}
// 奇偶性优化（蛇形排序）
// 如果块号是偶数，r 升序；如果是奇数，r 降序
if (q1.block % 2 == 0) {
return q1.r < q2.r;
}
return q1.r > q2.r;
});
std::vector<long long> answers(t);
// 初始化莫队算法的当前区间状态
int current_l = 0;
int current_r = -1; // 代表一个空区间 [0, -1]
// 遍历排好序的查询
for (const auto& q : queries) {
int l = q.l;
int r = q.r;
// 调整当前区间 [current_l, current_r] 到 [l, r]
// 注意：最好先扩展区间再收缩区间，避免处理空的或无效的中间状态
// 扩展左边界
while (current_l > l) {
current_l--;
add(current_l);
}
// 扩展右边界
while (current_r < r) {
current_r++;
add(current_r);
}
// 收缩左边界
while (current_l < l) {
remove(current_l);
current_l++;
}
// 收缩右边界
while (current_r > r) {
remove(current_r);
current_r--;
}
// 区间调整完毕，记录答案
answers[q.id] = current_power;
}
// 按原始顺序输出所有答案
for (int i = 0; i < t; ++i) {
std::cout << answers[i] << "\n";
}
return 0;
}复杂度分析喵
时间复杂度: O((N + T) * sqrt(N)) 的说。
- 对查询排序的时间是
O(T log T)。 - 指针移动的总时间是分析的关键：
- 右指针
r：由于奇偶性排序，对于每个块，r指针最多从头到尾或从尾到头扫一遍数组，移动O(N)。总共有sqrt(N)个块，所以r指针总移动次数是O(N * sqrt(N))。 - 左指针
l：当l在同一个块内移动时，每次移动距离不超过块的大小sqrt(N)，总共有T个查询，这部分是O(T * sqrt(N))。当l跨块时，最多跳2 * sqrt(N)，这种情况最多发生sqrt(N)次，总共是O(N)。
- 右指针
- 两者相加，总时间复杂度由
O(N * sqrt(N) + T * sqrt(N))主导，也就是O((N + T) * sqrt(N))。对于这道题的数据范围，这个复杂度是可以通过的！
- 对查询排序的时间是
空间复杂度: O(N + T + max(a_i)) 的说。
O(N)用于存储输入数组a。O(T)用于存储查询和答案。O(max(a_i))用于counts数组来统计数字出现的次数，这里是O(10^6)。
知识点与总结喵
这道题是莫队算法的一个非常经典的模板题，非常适合用来学习和练习这个算法呐！
- 核心算法：莫队算法 (Mo's Algorithm)。它是一种处理离线区间查询的强大工具，通过分块和对查询重排序来优化暴力计算。
- 适用场景：
- 查询是离线的（可以打乱顺序处理）。
- 从区间
[l, r]到[l+1, r],[l-1, r],[l, r+1],[l, r-1]的答案可以快速计算（通常是O(1)或O(log N)）。
- 关键技巧：
- 分块思想：将问题分解为更小、更易于管理的单元。
- O(1) 贡献更新：本题解题的关键在于推导出添加/删除一个元素时，力量值变化的数学公式
(2k+1)*x，这使得每次指针移动的更新成本极低。 - 奇偶性排序：一个简单但有效的常数优化，能让
r指针的移动路径更短。
- 注意事项：
- 一定要记得用
long long来存储答案current_power，因为Ks² * s的结果可能会很大，会超出int的范围。 - 数组下标是 0-based 还是 1-based 要处理清楚，统一用 0-based 会让代码更简洁。
- 一定要记得用
希望这篇题解能帮助到主人！如果还有不懂的地方，随时可以再来问我哦，喵~ (ฅ'ω'ฅ)