莫队

解决离线区间询问问题
如果从 \([l, r]\) 的答案能够 \(O(1)\) 扩展到相邻区间的答案，莫队算法可以 \(O(n\sqrt n)\) 求出所有询问的答案

普通莫队例题：https://codeforces.com/problemset/problem/86/D

代码：

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 10, M = 1e6 + 10;
LL sum, ans[N], cnt[M], a[N];
int block;
struct node{
	int l, r, id;
	bool operator < (const node & x) const{
		if (l / block != x.l / block) return l < x.l;
		if ((l / block) & 1) return r < x.r;
		return r > x.r;
	}
}mo[N];
void add(int i){
	sum -= cnt[a[i]] * cnt[a[i]] * a[i];
	cnt[a[i]] ++ ;
	sum += cnt[a[i]] * cnt[a[i]] * a[i];
}
void del(int i){
	sum -= cnt[a[i]] * cnt[a[i]] * a[i];
	cnt[a[i]] -- ;
	sum += cnt[a[i]] * cnt[a[i]] * a[i];
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n, m;
	cin >> n >> m;
	block = sqrt(n);// n / sqrt(m * 2 / 3)
	for (int i = 1; i <= n; i ++ ){
		cin >> a[i];
	}
	for (int i = 0; i < m; i ++ ){
		cin >> mo[i].l >> mo[i].r;
		mo[i].id = i;
	}
	sort(mo, mo + m);
	
	for (int i = 0, l = 1, r = 0; i < m; i ++ ){
		while (l > mo[i].l) add( -- l);
		while (r < mo[i].r) add( ++ r);
		while (l < mo[i].l) del(l ++ );
		while (r > mo[i].r) del(r -- );
		ans[mo[i].id] = sum;
	}
	for (int i = 0; i < m; i ++ ){
		cout << ans[i] << "\n";
	}
	return 0;
}