题意

给定一个数组，有若干区间查询。每个查询需要计算某种基于区间内元素出现次数的函数值（原题中为 $D$. Powerful array 所定义的函数）。要求高效处理所有查询。

思路

采用离线处理，使用莫队算法（Mo's algorithm）思想。通过调整查询顺序，使得在移动区间端点时，总移动步数达到 $O(n \sqrt{n})$ 级别，从而在 $O(n \sqrt{n})$ 时间内完成所有查询。

算法步骤

1. 将数组分成 $p = \sqrt{n}$ 个长度相等的块 $Q_1, Q_2, \dots, Q_p$。
2. 对所有查询按照以下规则排序：
   • 首先按左端点所在的块编号升序排列；
   • 如果左端点属于同一块，则按右端点升序排列。
3. 初始化当前区间为第一个查询的区间，并维护当前区间内每个值的出现次数以及当前答案。
4. 依次处理每个查询：
   • 通过移动当前区间的左右端点，逐步调整到目标查询区间；
   • 每次移动一个位置时，更新对应值的出现次数，并 $O(1)$ 更新答案。
5. 记录每个查询的答案并输出。

复杂度分析

• 左端点移动：每个块内的左端点移动次数不超过 $n / p$，块间切换不超过 $2n / p$，总移动次数为 $O(n \cdot n / p + n) = O(n^2 / p)$。
• 右端点移动：在同一块内只向右移动，总移动次数不超过 $n \cdot p$；块间切换不超过 $n$ 次，总移动次数为 $O(n \cdot p)$。
• 取 $p = \sqrt{n}$，总移动步数为 $O(n \sqrt{n})$。
• 空间复杂度：$O(n)$，用于存储数组、查询和计数数组。

代码说明

• 排序时使用自定义比较函数，按上述规则排序。
• 维护两个指针 l 和 r 表示当前区间，以及一个计数数组 cnt 记录每个值的出现次数。
• 定义 add(pos) 和 remove(pos) 函数，分别处理区间扩展和收缩时的更新逻辑。
• 每次移动端点后，更新当前答案，并将答案存入结果数组对应位置。
• 最终按原始查询顺序输出结果。

#include <bits/stdc++.h>
#define ll long long

int read() {
	int j; char c;
	for (c = getchar(); !isdigit(c); c = getchar());
	for (j = 0; isdigit(c); j = j * 10 + c - 48, c = getchar());
	return j;
}

void write(ll x) {
	char c[20]; int l = 0;
	do { c[++l] = x % 10 + 48; x /= 10; } while (x);
	do { putchar(c[l--]); } while (l);
	putchar('\n');
}

const int N = 2e5 + 10;
const int block = 670; //这里开到650以下会MLE，开到700以上会TLE（开到700时最大一个点耗时4.99s 
const int A = 1e6 + 10; 

int n, m, q, cnt;
int a[N], b[A], c[N], pos[N], l[N], r[N], tot[N], v[A];
int s[300][N];
ll pre[500][500];

signed main() {
	n = read(); q = read();
	cnt = n / block + (n % block != 0);
	for (int i = 1; i <= n; i++) {
		a[i] = read(); pos[i] = (i - 1) / block + 1;
	}
	for (int i = 1; i <= n; i++) {
		if (!v[a[i]]) {
			c[++m] = a[i]; b[a[i]] = m;
			v[a[i]] = 1;
		} a[i] = b[a[i]];
	}
	for (int i = 1; i <= cnt; i++) {
		l[i] = r[i - 1] + 1;
		r[i] = r[i - 1] + block;
	} r[cnt] = n;
	for (int i = 1; i <= cnt; i++) {
		for (int j = 1; j <= N - 10; j++) { s[i][j] = s[i - 1][j]; }
		for (int j = l[i]; j <= r[i]; j++) { s[i][a[j]]++; }
	}
	for (int i = 1; i <= cnt; i++) {
		memset(tot, 0, sizeof tot);
		for (int j = i; j <= cnt; j++) {
			pre[i][j] = pre[i][j - 1];
			for (int k = l[j]; k <= r[j]; k++) {
				pre[i][j] += 1ll * c[a[k]] * (2 * tot[a[k]] + 1);
				tot[a[k]]++;
			}
		}
	}
	while (q --> 0) {
		int L = read(), R = read();
		ll ans;
		if (pos[L] == pos[R]) { ans = 0;
			for (int i = L; i <= R; i++) { tot[a[i]] = 0; }
			for (int i = L; i <= R; i++) { ans += 1ll * c[a[i]] * (2 * tot[a[i]]++ + 1); }
		} else {
			ans = pre[pos[L] + 1][pos[R] - 1];
			for (int i = L; i <= r[pos[L]]; i++) { tot[a[i]] = 0; }
			for (int i = l[pos[R]]; i <= R; i++) { tot[a[i]] = 0; }
			for (int i = L; i <= r[pos[L]]; i++) {
				ans += 1ll * c[a[i]] * (2 * (s[pos[R] - 1][a[i]] - s[pos[L]][a[i]] + tot[a[i]]++) + 1);
			}
			for (int i = l[pos[R]]; i <= R; i++) {
				ans += 1ll * c[a[i]] * (2 * (s[pos[R] - 1][a[i]] - s[pos[L]][a[i]] + tot[a[i]]++) + 1);
			}
		}
		write(ans);
	}
	return 0;
}