直接莫队即可。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define MAXN 50005struct Node {    int l,r,num,ans;}G[MAXN];int book[MAXN];int cur[MAXN],rec[MAXN];int N,M,K,size;int ans = 0;inline void work(int x,int u) {    ans -= book[cur[x]]*book[cur[x]];    book[cur[x]] += u;    ans += book[cur[x]]*book[cur[x]];}inline bool cmp(Node a,Node b) {    return (a.l/size)^(b.l/size) ? a.l
        
         b.r);}int main() {        scanf("%d%d%d",&N,&M,&K);    for(int i=1;i<=N;++i) {        scanf("%d",&cur[i]);    }    size = floor(sqrt(N));    std::memset(book,0,sizeof(book));        for(int i=1;i<=M;++i) {        scanf("%d%d",&G[i].l,&G[i].r);        G[i].num = i;    }        std::sort(G+1,G+1+M,cmp);    int L = G[1].l,R = G[1].r;    ans = 0;    for(int i=L;i<=R;++i) work(i,1);        for(int i=1;i<=M;++i) {        while(L>G[i].l) work(--L,1);        while(R>G[i].r) work(R--,-1);        while(R