题目链接：http://codeforces.com/problemset/problem/86/D
题目大意：给定一个数组，每次询问一个区间[l,r]，设cnt[i]为数字i在该区间内的出现次数，求该区间内所有的cnt[i]^2*i。
解题思路：莫队模板题，改一下add,remove就好了。
1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 typedef long long ll; 6 const int N=2e5+5; 7 const int MAX=1e6+5; 8 int cnt[MAX],arr[N],unit; 9 ll power,res[N]; 10 11 struct node{ 12 int l,r; 13 int id; 14 }q[N]; 15 16 void add(int pos){ 17 power=power+(ll)arr[pos]*(cnt[arr[pos]]<<1|1);//(a+1)*(a+1)=a*a+2*a+1; 18 cnt[arr[pos]]++; 19 } 20 21 void remove(int pos){ 22 power=power-(ll)arr[pos]*(cnt[arr[pos]]<<1-1); 23 cnt[arr[pos]]--; 24 } 25 26 bool cmp(node a,node b){ 27 return a.l/unit!=b.l/unit?a.l/unit<b.l/unit:a.r<b.r; 28 } 29 30 int main(){ 31 int n,m; 32 scanf("%d%d",&n,&m); 33 unit=sqrt(n); 34 for(int i=1;i<=n;i++){ 35 scanf("%d",&arr[i]); 36 } 37 for(int i=1;i<=m;i++){ 38 scanf("%d%d",&q[i].l,&q[i].r); 39 q[i].id=i; 40 } 41 sort(q+1,q+1+m,cmp); 42 43 int L=q[1].l,R=L-1; 44 for(int i=1;i<=m;i++){ 45 while(L>q[i].l) 46 add(--L); 47 while(L<q[i].l) 48 remove(L++); 49 while(R<q[i].r) 50 add(++R); 51 while(R>q[i].r) 52 remove(R--); 53 res[q[i].id]=power; 54 } 55 for(int i=1;i<=m;i++){ 56 printf("%I64d\n",res[i]); 57 } 58 }