线段树

void build(int s, int t, int p) {
	if (s == t) {
		d[p] = a[s];
		return;
	}
	int m = s + ((t - s) >> 1);
	build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
	d[p] = d[p * 2] + d[(p * 2) + 1];
}
void update(int l, int r, int c, int s, int t, int p) {
	if (l <= s && t <= r) {
		d[p] += (t - s + 1) * c, b[p] += c;
		return;
	}
	int m = s + ((t - s) >> 1);
	if (b[p] && s != t) {
		d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
		b[p * 2] += b[p], b[p * 2 + 1] += b[p];  
		b[p] = 0;                              
	}
	if (l <= m) update(l, r, c, s, m, p * 2);
	if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
	d[p] = d[p * 2] + d[p * 2 + 1];
}
int getsum(int l, int r, int s, int t, int p) {
	if (l <= s && t <= r) return d[p];
	int m = s + ((t - s) >> 1);
	if (b[p]) {
		d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
		b[p * 2] += b[p], b[p * 2 + 1] += b[p]; 
		b[p] = 0;                             
	}
	int sum = 0;
	if (l <= m) sum = getsum(l, r, s, m, p * 2);
	if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
	return sum;
}

kmp

int kmp(string a , string b){
	int n = a.size();
	int m = b.size();
	a = '$' + a;
	b = '$' + b;
	for(int k = 2 , j = 0 ; k <= m ; k++){
		while(j > 0 && b[k] != b[j + 1]){
			j = f[j];
		}
		if(b[k] == b[j + 1]){
			j++;
		}
		f[k] = j;
	}
	int ans = 0;
	for(int k = 1 , j = 0 ; k <= n ; k++){
		while(j > 0 && a[k] != b[j + 1]){
			j = f[j];
		}
		if(a[k] == b[j + 1]){
			j++;
			if(j == m){
				ans++;
				j = f[j];
			}
		}
	}
	return ans;
}

莫队

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 5;
int n , m , k , B , a[maxn];
long long cnt[maxn] , ans , op[maxn];
struct query{
	int l , r , id;
}q[maxn];
void add(int x , int d){
	ans -= cnt[x] * cnt[x];
	cnt[x] += d;
	ans += cnt[x] * cnt[x];
}
bool cmp(const query &a , const query &b){
	if(a.l / B != b.l / B){
		return a.l / B < b.l / B;
	}
	return a.r < b.r;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> k;
	B = sqrt(n);
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i];
	}
	for(int i = 1 ; i <= m ; i++){
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1 , q + 1 + m , cmp);
	ans = 0;
	int l = 1 , r = 0;
	for(int i = 1 ; i <= m ; i++){
		while(l > q[i].l) add(a[--l] , 1);
		while(l < q[i].l) add(a[l++] , -1);
		while(r > q[i].r) add(a[r--] , -1);
		while(r < q[i].r) add(a[++r] , 1);
		op[q[i].id] = ans;
	}
	for(int i = 1 ; i <= m ; i++){
		cout << op[i] << endl;
	}
}