这个题，莫队很容易想到（格式很明显），然后直接用数学公式维护一下和就行了。
题干：
题目描述 小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。 输入输出格式 输入格式： 第一行，三个整数N、M、K。 第二行，N个整数，表示小B的序列。 接下来的M行，每行两个整数L、R。 输出格式： M行，每行一个整数，其中第i行的整数表示第i个询问的答案
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(register int i = a;i <= n;i++) #define lv(i,a,n) for(register int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } struct node { int l,r,id,pos; }a[50005]; int blo,n,m,k; ll b[50005],num[56000]; ll cnt[50005]; bool cmp(node a,node b) { if(a.pos != b.pos) return a.pos < b.pos; else return a.r < b.r; } int main() { read(n);read(m);read(k); blo = sqrt(n); duke(i,1,n) { read(b[i]); } duke(i,1,m) { read(a[i].l); read(a[i].r); a[i].id = i; a[i].pos = (a[i].l - 1) / blo + 1; } sort(a + 1,a + m + 1,cmp); int l = 1,r = 0; ll ans = 0; duke(i,1,m) { while(l > a[i].l) l--,cnt[b[l]]++,ans += 2 * cnt[b[l]] - 1; while(r < a[i].r) r++,cnt[b[r]]++,ans += 2 * cnt[b[r]] - 1; while(l < a[i].l) cnt[b[l]]--,ans -= 2 * cnt[b[l]] + 1,l++; while(r > a[i].r) cnt[b[r]]--,ans -= 2 * cnt[b[r]] + 1,r--; num[a[i].id] = ans; } duke(i,1,m) { printf("%lld\n",num[i]); } return 0; }