数据不大直接上莫队1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using namespace std;
const int N=50050;
struct query
{
int ql,qr,id;
} q[N];
int cnt[N],w[N],num,n,m,k;
LL ans[N],sum=0;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') {t=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x*t;
}
void add(int k)
{
sum-=cnt[w[k]]*cnt[w[k]];
cnt[w[k]]++;
sum+=cnt[w[k]]*cnt[w[k]];
}
void del(int k)
{
sum-=cnt[w[k]]*cnt[w[k]];
cnt[w[k]]--;
sum+=cnt[w[k]]*cnt[w[k]];
}
bool cmp(query a, query b)
{
return a.ql/num==b.ql/num? a.qr<b.qr:a.ql<b.ql;
}
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++) w[i]=read();
num=sqrt(n);
for(int i=1;i<=m;i++) q[i].ql=read(),q[i].qr=read(),q[i].id=i;
sort(q+1,q+m+1,cmp);
int L=0,R=0;
for(int i=1;i<=m;i++)
{
int ql=q[i].ql,qr=q[i].qr;
while (L<ql) del(L++);
while (R>qr) del(R--);
while (L>ql) add(--L);
while (R<qr) add(++R);
ans[q[i].id]=sum;
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]-1);
return 0;
}