codeforces 86D Powerful array 莫队算法

题意：
给你n个数字，m个区间，要你算出每个区间内si*Ksi*ksi总和。
题解：
莫队算法模板题，每移动一次的时候减去之前的影响再加上现在的影响就可以了，具体看代码。

#include<stdio.h> 
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define LL long long int
const int MAXN=200000+7;
const int MAXM=1e6+7;
struct node
{
    int l,r;
    int id;
    int pos;
}q[MAXN];
bool cmp(node c,node d)
{
    if(c.pos==d.pos) return c.r<d.r;
    return c.l<d.l;
}
int block[MAXN];
int a[MAXN],cnt[MAXM];
int n,m;
LL ans[MAXN];
LL val;
void update(int x,int v)
{
    val-=(LL)cnt[a[x]]*cnt[a[x]]*a[x];
    cnt[a[x]]+=v;
    val+=(LL)cnt[a[x]]*cnt[a[x]]*a[x];
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(cnt,0,sizeof(cnt));
        int s=sqrt(n);
        for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),block[i]=(i-1)/s+1;
        for(int i=1;i<=m;i++)
        scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i,q[i].pos=block[q[i].l];
        sort(q+1,q+m+1,cmp);
//      for(int i=1;i<=m;i++)
//      printf("%d %d\n",q[i].l,q[i].r); 
        int l=1,r=0;
        val=0;
        for(int i=1;i<=m;i++)
        {
            while(l<q[i].l)
            {
                update(l,-1);
                l++;
            }
            while(l>q[i].l)
            {
                l--;
                update(l,1);
            }
            while(r>q[i].r)
            {
                update(r,-1);
                r--;
            }
            while(r<q[i].r)
            {
                r++;
                update(r,1);
            }
            ans[q[i].id]=val;
        }
        for(int i=1;i<=m;i++)
        printf("%I64d\n",ans[i]);
    }
}