题目

因为马上要下机并且没有时间了（这里人多

所以求调教

谢了

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
int block;
int n,m,k;
int b[N];
int cut[N];
long long cum[N],ans;
struct node {
	int l,r;
	int w;
} a[N];
bool cmp(node x,node y) {
	return (x.r/block)==(y.r/block)?x.l<y.l:x.r<y.r;
}
void del(int x) {
	cut[b[x]]--;
	ans-=2*cut[b[x]]+1;
}
void add(int x) {
	cut[b[x]]++;
	ans+=2*cut[b[x]]-1;
}
int main() {
	scanf("%d%d%d",&n,&m,&k);
	block=sqrt(n);
	for(int i=1; i<=n; i++)scanf("%d",&b[i]);
	for(int i=1; i<=m; i++) {
		scanf("%d%d",&a[i].l,&a[i].r);
		a[i].w=i;
	}
	sort(a+1,a+m+1,cmp);
	int l=1,r=0;
	for(int i=1; i<=m; i++) {
		int ql=a[i].l,qr=a[i].r;
		while(l<ql)del(l++);
		while(l>ql)add(l--);
		while(r<ql)add(r++);
		while(r>ql)del(r--);
		cum[a[i].w]=ans;
	}
	for(int i=1; i<=m; i++)printf("%lld\n",cum[i]);
	return 0;
}