题目描述

小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个询问的答案。

输入输出样例

输入样例#1： 

6 4 31 3 2 1 1 31 42 63 55 6

输出样例#1： 

6952

————————————————————————————————————————————-

莫队裸题。

（以及虽然是裸题但是特别反感题解千篇一律的写“不解释”三个字……那还叫啥子题解啊，直接叫抄板子得了。）

（也是，可能大佬们本身就瞧不上我这种弱鸡……）

推荐这个人的博客，找了半天唯一给解释的：

我们首先想我们要求的是c*c，如果c+1的话就变成了(c+1)*(c+1)=c*c+2c+1，也就是相当于比原答案多加了2*c+1

同理减的时候就是多减了2*c-1.

剩下的就是莫队操作了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int N=50001;inline ll read(){ ll X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct qu{ int pos,l,r;}q[N];int a[N],cnt[N],sum,n,m,k,s;ll ans[N];inline int bel(int x){ return (x-1)/s+1;}bool cmp(qu b,qu c){ return bel(b.l)==bel(c.l)?b.r
            
             
              q[i].l)add(a[--ql]); while(qr
              
               q[i].r)del(a[qr--]); ans[q[i].pos]=sum; } for(int i=1;i<=m;i++)printf("%lld\n",ans[i]); return 0;}