【题目】http://codeforces.com/problemset/problem/86/D
【题意】给出一个长度为n的串，t次询问，每次询问l到r之间每个数*这个数出现的次数^2的和
【思路】莫队算法
【代码】
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5;//区间范围 const int MAX=1e6+5;//最大数字 int unit,cnt[MAX],arr[N]; ll res[N];//存答案 ll ans=0;//当前的答案 struct node { int l,r,id; } q[N]; bool cmp(node a,node b)//对询问排序 { return a.l/unit!=b.l/unit?a.l/unit<b.l/unit:a.r<b.r; } void add(int pos)//增加 { ans-=1ll*cnt[arr[pos]]*cnt[arr[pos]]*arr[pos];//减去旧的 cnt[arr[pos]]++; ans+=1ll*cnt[arr[pos]]*cnt[arr[pos]]*arr[pos];//加上新的 } void remove(int pos)//减少 { ans-=1ll*cnt[arr[pos]]*cnt[arr[pos]]*arr[pos];//减去旧的 cnt[arr[pos]]--; ans+=1ll*cnt[arr[pos]]*cnt[arr[pos]]*arr[pos];//加上新的 } int main() { int n; scanf("%d",&n); int m; scanf("%d",&m); unit=sqrt(n);//分块 for(int i=1; i<=n; i++) { scanf("%d",&arr[i]); } for(int i=1; i<=m; i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+m+1,cmp); int L=q[1].l,R=L-1; for(int i=1; i<=m; i++) { while(L>q[i].l) add(--L); while(L<q[i].l) remove(L++); while(R>q[i].r) remove(R--); while(R<q[i].r) add(++R); res[q[i].id]=ans; } for(int i=1; i<=m; i++) { printf("%lld\n",res[i]); } }
